We give algorithms to factorize large integers in the duality computer. We provide three duality algorithms for factorization based on a naive factorization method, the Shor algorithm in quantum computing, and the Fer...We give algorithms to factorize large integers in the duality computer. We provide three duality algorithms for factorization based on a naive factorization method, the Shor algorithm in quantum computing, and the Fermat＇s method in classical computing. All these algorithms may be polynomial in the input size.展开更多
Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm sa...Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,展开更多
For any integer n ≥ 2, let P（n） be the largest prime factor of n. In this paper, we prove 1 This that the number of primes p 〈 x with P（p- 1） ≥ pC is more than （1 -c＋o（1））π（x） for 0 〈 c 〈 1/2 extends...For any integer n ≥ 2, let P（n） be the largest prime factor of n. In this paper, we prove 1 This that the number of primes p 〈 x with P（p- 1） ≥ pC is more than （1 -c＋o（1））π（x） for 0 〈 c 〈 1/2 extends a recent result of Luca, Menares and Madariaga for1/4≤c≤1/2. We also pose two conjectures for further research.展开更多
Let P（x） denote the greatest prime factor of ∏<sub>x【n≤x+x<sup>1/2</sup></sub>n. In this paper, we shall prove that P（x）】x<sup>0.728</sup>holds true for sufficiently large x.
In this paper,rank factorizations and factor left prime factorizations are studied.The authors prove that any polynomial matrix with full row rank has factor left prime factorizations.And for a class of polynomial mat...In this paper,rank factorizations and factor left prime factorizations are studied.The authors prove that any polynomial matrix with full row rank has factor left prime factorizations.And for a class of polynomial matrices,the authors give an algorithm to decide whether they have rank factorizations or factor left prime factorizations and compute these factorizations if they exist.展开更多
Let p(n) and Q(n) stand for the smallest and the largest prime factors of the natural number n, respectively. Recently, the sums involving reciprocals of the functions p(n) and Q(n) were studied by Erds, Ivié et ...Let p(n) and Q(n) stand for the smallest and the largest prime factors of the natural number n, respectively. Recently, the sums involving reciprocals of the functions p(n) and Q(n) were studied by Erds, Ivié et al. For example, Ivié proved展开更多
This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying contin...This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.展开更多
In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that comp...In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that computes a factor of a semi-prime integer n=pq, where prime factors p and q are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves y2=x(x2+b2)(modn) , where b is a control parameter. Although in the worst case, for some n the number of required values of parameter b that must be considered (the number of basic steps of the algorithm) substantially exceeds four, hundreds of computer experiments indicate that the average number of the basic steps does not exceed six. These experiments also confirm all important facts discussed in this paper.展开更多
In the history of mathematics different methods have been used to detect if a number is prime or not. In this paper a new one will be shown. It will be demonstrated that if the following equation is zero for a certain...In the history of mathematics different methods have been used to detect if a number is prime or not. In this paper a new one will be shown. It will be demonstrated that if the following equation is zero for a certain number p, this number p would be prime. And being m an integer number higher than (the lowest, the most efficient the operation). . If the result is an integer, this result will tell us how many permutations of two divisors, the input number has. As you can check, no recurrent division by odd or prime numbers is done, to check if the number is prime or has divisors. To get to this point, we will do the following. First, we will create a domain with all the composite numbers. This is easy, as you can just multiply one by one all the integers (greater or equal than 2) in that domain. So, you will get all the composite numbers (not getting any prime) in that domain. Then, we will use the Fourier transform to change from this original domain (called discrete time domain in this regards) to the frequency domain. There, we can check, using Parseval’s theorem, if a certain number is there or not. The use of Parseval’s theorem leads to the above integral. If the number p that we want to check is not in the domain, the result of the integral is zero and the number is a prime. If instead, the result is an integer, this integer will tell us how many permutations of two divisors the number p has. And, in consequence information how many factors, the number p has. So, for any number p lower than 2m?- 1, you can check if it is prime or not, just making the numerical definite integration. We will apply this integral in a computer program to check the efficiency of the operation. We will check, if no further developments are done, the numerical integration is inefficient computing-wise compared with brute-force checking. To be added, is the question regarding the level of accuracy needed (number of decimals and number of steps in the numerical integration) to have a reliable result for large numbers. This will be commented on the paper, but a separate study will be needed to have detailed conclusions. Of course, the best would be that in the future, an analytical result (or at least an approximation) for the summation or for the integration is achieved.展开更多
Define the total number of distinct prime factors of an odd perfect number n asω(n). We prove that if n is an odd perfect number which is relatively prime to 3 and 5 and7, then ω(n) ≥ 107. And using this result, we...Define the total number of distinct prime factors of an odd perfect number n asω(n). We prove that if n is an odd perfect number which is relatively prime to 3 and 5 and7, then ω(n) ≥ 107. And using this result, we give a conclusion that the third largest prime factor of such an odd perfect number exceeds 1283.展开更多
基金The project supported by the 973 Program under Grant No. 2006CB921106, National Natural Science Foundation of China under Grant Nos. 10325521 and 60433050, and the Key Project 306020 and Science Research Fund of Doctoval Program of the Ministry of Education of China
文摘We give algorithms to factorize large integers in the duality computer. We provide three duality algorithms for factorization based on a naive factorization method, the Shor algorithm in quantum computing, and the Fermat＇s method in classical computing. All these algorithms may be polynomial in the input size.
基金Supported by the National Natural Science Foundation of China
文摘Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,
基金Supported by National Natural Science Foundation of China(Grant Nos.11571174,11401411 and 11371195)
文摘For any integer n ≥ 2, let P（n） be the largest prime factor of n. In this paper, we prove 1 This that the number of primes p 〈 x with P（p- 1） ≥ pC is more than （1 -c＋o（1））π（x） for 0 〈 c 〈 1/2 extends a recent result of Luca, Menares and Madariaga for1/4≤c≤1/2. We also pose two conjectures for further research.
基金Project supported by the Tian Yuan Item in the National Natural Science Foundation of China.
文摘Let P（x） denote the greatest prime factor of ∏<sub>x【n≤x+x<sup>1/2</sup></sub>n. In this paper, we shall prove that P（x）】x<sup>0.728</sup>holds true for sufficiently large x.
基金supported by the National Science Foundation of China under Grant Nos.11371131 and 11501192
文摘In this paper,rank factorizations and factor left prime factorizations are studied.The authors prove that any polynomial matrix with full row rank has factor left prime factorizations.And for a class of polynomial matrices,the authors give an algorithm to decide whether they have rank factorizations or factor left prime factorizations and compute these factorizations if they exist.
基金Project supported by the National Natural Science Foundation of China
文摘Let p(n) and Q(n) stand for the smallest and the largest prime factors of the natural number n, respectively. Recently, the sums involving reciprocals of the functions p(n) and Q(n) were studied by Erds, Ivié et al. For example, Ivié proved
文摘This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.
文摘In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that computes a factor of a semi-prime integer n=pq, where prime factors p and q are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves y2=x(x2+b2)(modn) , where b is a control parameter. Although in the worst case, for some n the number of required values of parameter b that must be considered (the number of basic steps of the algorithm) substantially exceeds four, hundreds of computer experiments indicate that the average number of the basic steps does not exceed six. These experiments also confirm all important facts discussed in this paper.
文摘In the history of mathematics different methods have been used to detect if a number is prime or not. In this paper a new one will be shown. It will be demonstrated that if the following equation is zero for a certain number p, this number p would be prime. And being m an integer number higher than (the lowest, the most efficient the operation). . If the result is an integer, this result will tell us how many permutations of two divisors, the input number has. As you can check, no recurrent division by odd or prime numbers is done, to check if the number is prime or has divisors. To get to this point, we will do the following. First, we will create a domain with all the composite numbers. This is easy, as you can just multiply one by one all the integers (greater or equal than 2) in that domain. So, you will get all the composite numbers (not getting any prime) in that domain. Then, we will use the Fourier transform to change from this original domain (called discrete time domain in this regards) to the frequency domain. There, we can check, using Parseval’s theorem, if a certain number is there or not. The use of Parseval’s theorem leads to the above integral. If the number p that we want to check is not in the domain, the result of the integral is zero and the number is a prime. If instead, the result is an integer, this integer will tell us how many permutations of two divisors the number p has. And, in consequence information how many factors, the number p has. So, for any number p lower than 2m?- 1, you can check if it is prime or not, just making the numerical definite integration. We will apply this integral in a computer program to check the efficiency of the operation. We will check, if no further developments are done, the numerical integration is inefficient computing-wise compared with brute-force checking. To be added, is the question regarding the level of accuracy needed (number of decimals and number of steps in the numerical integration) to have a reliable result for large numbers. This will be commented on the paper, but a separate study will be needed to have detailed conclusions. Of course, the best would be that in the future, an analytical result (or at least an approximation) for the summation or for the integration is achieved.
基金Foundation item： Supported by the Science Foundation of Kashgar Teacher＇s College（112390）
文摘Define the total number of distinct prime factors of an odd perfect number n asω(n). We prove that if n is an odd perfect number which is relatively prime to 3 and 5 and7, then ω(n) ≥ 107. And using this result, we give a conclusion that the third largest prime factor of such an odd perfect number exceeds 1283.
