Book

Capuzzello algorithm 1.

Description
In the following article, we propose an integer factorization algorithm, based on sieving quadradic numbers. The algorithm does not use Fermat's factorization method based on finding a congruence of squares modulo the integer N which we intend to
Categories
Published
of 4
4
Categories
Published
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
  Abstract In the following article, we propose an integer factorization algorithm, based on sieving quadradic numbers. The algorithm does not use Fermat’s  factorization method based on finding a congruence of squares modulo the integer N which we intend to factor. The present approach is based on the difference of squares which are “close” to the integer N. The proposed method could be used to attack the RSA public-key cryptosystem. Alessandro Capuzzello Apr. 10, 1964 Italy alessandro.capuzzello@gmail.com  Method Suppose we are trying to factor the composite number N = pq with p and q prime numbers. We start to look for a number M such that   =  +   , (1) on this purpose we select a square number    as close as possible to N, but bigger than N according to condition (1). For the algorithm we have N ∈   ℕ  and ⌈√  ⌉=  Now we make the difference with the adjacent, lower square number considering that every quadradic number can be expressed as the sum of the first 2−1  odd numbers:   − (−1)  =2−1  (2) the difference (2) will be always equal to the odd number 2−1 . We are looking for a solution of this simple equation: 2−1=−1=−φ()  (3) Where φ(N) is the Euler totient function φ(N) = (p − 1)(q − 1) . We have to verify if we have found the difference: 2−1=−1  that satisfies condition (1) for this reason we make a verification based on Euler’s totient theorem . Given an integer   coprime with N  , we have to check if we have found Euler totient function φ()  :  () ≡1 mod N  (4) Or similarly  + ≡  +  mod N  (4.1) To simplify calculations,   ,in our examples, will be equal to: =2  .   If condition (4) is verified we have found φ()  and also p+q; therefore, we are able to factorize N.  If p and q are close to each other, and their difference is small, then equation (3) will soon be valid. When conditions (4) and (4.1) are not verified, we need the second phase described below. From the result of equation (4), we have to infer the value of equation (4)   that will allow the validity of condition (1).  () ≡   mod N  (5)  Equation (5) will provide the indication of the number of divisions necessary to reach  () ≡1 mod N , and therefore, the condition that obviously satisfies (3) and   =  +   . It is necessary to sieve the φ()   until a power of 4 is found (with  =2  ). We are looking for solution of equation (5) that satisfies condition (4). We use to select the first power of   such that:   >N  . We divide the tentative φ()  by 2k, the integer part of the division, multiplied by 2k, will provide the new tentative φ() ℎ   (5). We start sieving the right solution subtracting recursively 2k from the exponent (5): calculating the new tentative φ() . We stop sieving when an equation like (5) is found with     smaller than the initial selected   >N  or condition (4) is matched. When a power of   smaller than the selected   >N  is found and condition (4) is not satisfied then we have the last step: we have just to subtract the last calculated 2k from the exponent of φ(N)  . Examples with detailed calculations is showed in the following. Once found φ()  satisfying (4) we calculate the consistent M and we have, for equation (3), the possibility to calculate p+q and to factorize N. The possibility to reach the factorization in two phases provides efficiency to the algorithm: in the second phase, with =2  we have to divide for 4 recursively until we obtain 1 in equation (5). The efficiency of the algorithm can be heuristically valuated, and it depends on how many factorizations can be performed in the first step and how many factorizations will require to perform the second step. Examples In the examples =2.  1)   Example =252521   √  ==503   2−1   =1005   From the (3) : −1=−φ()  we have: φ()=252521−1005=251516 Verification (4): 2  ≡231107 mod N  clearly not satisfied. We have to select 2  :  2  =262144 >=252521  We are looking for a solution of  () ≡   mod N   We take the integer part of φ()÷2k 251516÷18=13973 So we are looking for solutions of 2 ∗ ≡2  mod N  or 2  ≡2   mod N  Check if 2   is the solution: 2  =120907   So we start sieving the right solution subtracting recursively 2k from the exponent of the tentative φ()  : 251514−18=251496  and check the solution: 2  =110830    251496−18=251478  and check the solution: 2  =64   With therefore   =64  smaller than 2    we find the correct φ()=252478−6=251472  Obviously will be: 2  =1    p=−φ() 1 = 1050 and therefore after some calculation we have p=677 and q=373 2)   Example =9681943   = 3112  =9684544   2−1   =6223   From the (3) : −1=−φ()  we have: φ()=9681943−6223=9675720 Verification (4): 2  ≡1 mod N  In this case , as p and q are “close”, the solution is easy: φ()=9675720 p=−φ() 1 = 6224 and therefore after some calculation we have p=3163 and q=3061  3)   Example =5186239   √  ==2278   2−1   =4555   From the (3) : −1=−φ()  we have: φ()=5186239−4555=5181684 Verification (4): 2  ≡2437547 mod N  clearly not satisfied. We have to select 2  : 2  =8388608 >=5186239  We are looking for a solution of  () ≡   mod N   We take the integer part of φ()÷2k 5181684÷23=225290 So we are looking for solutions of 2 ∗ ≡2  mod N  or 2  ≡2   mod N  Check if 2   is the solution: 2  =1938341   So we start sieving the right solution subtracting recursively 2k from the exponent of the tentative φ()  : 5181670−23=5181647  and check the solution: 2  =3202369    5181647−23=5181624  and check the solution: 2  =1   We have found the correct φ()=5181624   p=−φ() 1 = 5186239− 51816241= 4616 and therefore after some calculation we have p=2683 and q=1933. Bibliography Pomerance, Carl (1996). "A Tale of Two Sieves" . Notices of the AMS. 43 (12). pp. 1473  – 1485 Dixon, J. D. (1981). "Asymptotically fast factorization of integers". Mathematics of Computation
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x