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展开更多
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.展开更多
Considering Pythagorician divisors theory which leads to a new parameterization, for Pythagorician triplets ( a,b,c )∈ ℕ 3∗ , we give a new proof of the well-known problem of these particular squareless numbers n∈ ℕ...Considering Pythagorician divisors theory which leads to a new parameterization, for Pythagorician triplets ( a,b,c )∈ ℕ 3∗ , we give a new proof of the well-known problem of these particular squareless numbers n∈ ℕ ∗ , called congruent numbers, characterized by the fact that there exists a right-angled triangle with rational sides: ( A α ) 2 + ( B β ) 2 = ( C γ ) 2 , such that its area Δ= 1 2 A α B β =n;or in an equivalent way, to that of the existence of numbers U 2 , V 2 , W 2 ∈ ℚ 2∗ that are in an arithmetic progression of reason n;Problem equivalent to the existence of: ( a,b,c )∈ ℕ 3∗ prime in pairs, and f∈ ℕ ∗ , such that: ( a−b 2f ) 2 , ( c 2f ) 2 , ( a+b 2f ) 2 are in an arithmetic progression of reason n;And this problem is also equivalent to that of the existence of a non-trivial primitive integer right-angled triangle: a 2 + b 2 = c 2 , such that its area Δ= 1 2 ab=n f 2 , where f∈ ℕ ∗ , and this last equation can be written as follows, when using Pythagorician divisors: (1) Δ= 1 2 ab= 2 S−1 d e ¯ ( d+ 2 S−1 e ¯ )( d+ 2 S e ¯ )=n f 2;Where ( d, e ¯ )∈ ( 2ℕ+1 ) 2 such that gcd( d, e ¯ )=1 and S∈ ℕ ∗ , where 2 S−1 , d, e ¯ , d+ 2 S−1 e ¯ , d+ 2 S e ¯ , are pairwise prime quantities (these parameters are coming from Pythagorician divisors). When n=1 , it is the case of the famous impossible problem of the integer right-angled triangle area to be a square, solved by Fermat at his time, by his famous method of infinite descent. We propose in this article a new direct proof for the numbers n=1 (resp. n=2 ) to be non-congruent numbers, based on an particular induction method of resolution of Equation (1) (note that this method is efficient too for general case of prime numbers n=p≡a ( ( mod8 ) , gcd( a,8 )=1 ). To prove it, we use a classical proof by induction on k , that shows the non-solvability property of any of the following systems ( t=0 , corresponding to case n=1 (resp. t=1 , corresponding to case n=2 )): ( Ξ t,k ){ X 2 + 2 t ( 2 k Y ) 2 = Z 2 X 2 + 2 t+1 ( 2 k Y ) 2 = T 2 , where k∈ℕ;and solutions ( X,Y,Z,T )=( D k , E k , f k , f ′ k )∈ ( 2ℕ+1 ) 4 , are given in pairwise prime numbers.2020-Mathematics Subject Classification 11A05-11A07-11A41-11A51-11D09-11D25-11D41-11D72-11D79-11E25 .展开更多
基金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
文摘我们把算法给 factorize 在两重性计算机的大整数。Weprovide 为因式分解的三个两重性算法基于一个天真的因式分解方法,在量计算的 Shoralgorithm,和 Fermat “在古典计算的 s 方法。所有这些算法可以是在输入尺寸的多项式。
基金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
文摘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.
文摘Considering Pythagorician divisors theory which leads to a new parameterization, for Pythagorician triplets ( a,b,c )∈ ℕ 3∗ , we give a new proof of the well-known problem of these particular squareless numbers n∈ ℕ ∗ , called congruent numbers, characterized by the fact that there exists a right-angled triangle with rational sides: ( A α ) 2 + ( B β ) 2 = ( C γ ) 2 , such that its area Δ= 1 2 A α B β =n;or in an equivalent way, to that of the existence of numbers U 2 , V 2 , W 2 ∈ ℚ 2∗ that are in an arithmetic progression of reason n;Problem equivalent to the existence of: ( a,b,c )∈ ℕ 3∗ prime in pairs, and f∈ ℕ ∗ , such that: ( a−b 2f ) 2 , ( c 2f ) 2 , ( a+b 2f ) 2 are in an arithmetic progression of reason n;And this problem is also equivalent to that of the existence of a non-trivial primitive integer right-angled triangle: a 2 + b 2 = c 2 , such that its area Δ= 1 2 ab=n f 2 , where f∈ ℕ ∗ , and this last equation can be written as follows, when using Pythagorician divisors: (1) Δ= 1 2 ab= 2 S−1 d e ¯ ( d+ 2 S−1 e ¯ )( d+ 2 S e ¯ )=n f 2;Where ( d, e ¯ )∈ ( 2ℕ+1 ) 2 such that gcd( d, e ¯ )=1 and S∈ ℕ ∗ , where 2 S−1 , d, e ¯ , d+ 2 S−1 e ¯ , d+ 2 S e ¯ , are pairwise prime quantities (these parameters are coming from Pythagorician divisors). When n=1 , it is the case of the famous impossible problem of the integer right-angled triangle area to be a square, solved by Fermat at his time, by his famous method of infinite descent. We propose in this article a new direct proof for the numbers n=1 (resp. n=2 ) to be non-congruent numbers, based on an particular induction method of resolution of Equation (1) (note that this method is efficient too for general case of prime numbers n=p≡a ( ( mod8 ) , gcd( a,8 )=1 ). To prove it, we use a classical proof by induction on k , that shows the non-solvability property of any of the following systems ( t=0 , corresponding to case n=1 (resp. t=1 , corresponding to case n=2 )): ( Ξ t,k ){ X 2 + 2 t ( 2 k Y ) 2 = Z 2 X 2 + 2 t+1 ( 2 k Y ) 2 = T 2 , where k∈ℕ;and solutions ( X,Y,Z,T )=( D k , E k , f k , f ′ k )∈ ( 2ℕ+1 ) 4 , are given in pairwise prime numbers.2020-Mathematics Subject Classification 11A05-11A07-11A41-11A51-11D09-11D25-11D41-11D72-11D79-11E25 .