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

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− 51816241=
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