Primality Testing and Factoring Algorithms

[raman22feb1988]

Primality Testing

Most obvious algorithm is trial division, it gives the solution quickly for small numbers. But, from the Fermat Little Theorem, p is prime iff a^(p-1)=1 (mod p) is very fast for large numbers, a, p being relatively prime, but the problem is that there are lots of pseudoprimes, i.e. composite numbers p that satisfy the above property for each base a. What about testing it for more than one base? Huh, there exist Carmichael numbers for which above is true for every base a, that is relatively prime to p. 561, 1105, 1729, 2465, 2821, 6601, 8911 are the first few. There are not too many Carmichael numbers, but below 10^15, there are about 10^5 Carmichael numbers. There is another advanced test, Rabin-Miller SPRP test, which states that if p is prime and a^(p-1)/(2^r)=1 (mod p), then a^(p-1)/2^(r+1)=1 or -1 (mod p). Consider p=341, 2^170=1 mod 341, 2^85=32 mod 341, so 341 is not a prime. In fact 32^2=1 mod 341. 31x33=0 mod 341. GCD of each factor with 341 gives out away with the factors, which are 31, 11. Another example: 2^280=1 mod 561, 2^140=67 mod 561. There are cases for which this test will also fail so. For example, 2047 is a SPRP base 2 and 91 is a SPRP base 10.

[raman22feb1988]

Primality Proving

Consider the first test by Lucas in 1876. If a^(p-1)=1 (mod p), but if a^(p-1)/q != 1 (mod p) for every prime q dividing p-1, then p is prime. This holds so because the first condition implies that the order of a in multiplication (mod p) is a divisor of p-1 while the second condition implies that the order of a is not a proper divisor of p-1, order of a = p-1. If p is composite, phi(p) <= p-2, which is less than p-1. So p must be prime. The difficulty with this is in completely factoring p-1, and not in finding out a. For Fermat Numbers p=2^(2^k)+1, for which p-1 can be easily factored, this test, viz. Pepin test, can be applied, F(k)=2^(2^k)+1 is prime iff 3^(F(k)-1)/2 = -1 (mod F(k)). So, there exists test to prove the primality of special numbers. For example, for Mersenne numbers of the form (2^p)-1, the Lucas Lehmer test is used to prove the primality. Let S(1)=4, S(n)=S(n-1)^2 - 2 (mod (2^p)-1). (2^p)-1 is prime if and only if S(p-1) = 0 (mod (2^p)-1). And the Proth Theorem, which states that if p>1, 2^k|p-1, 2^k>sqrt(p), a^(p-1)/2 = -1 (mod p), then p is prime. What about for general numbers? For general numbers, the frequently used primality proving algorithm is "Elliptic Curve Primality Proving". In August 2002, three IIT Kanpur Students, Agrawal, Kayal, Saxena discovered a deterministic polynomial time algorithm for proving primality: p is prime iff (x-a)^p = (x^p)-a mod p.

[raman22feb1988]

Factoring Algorithms

Pollard's Rho

Most obvious algorithm for factoring is trial division. It gives the small factors quickly. But for larger factors, you need better algorithms. Pollard Rho is a heuristic algorithm, improvement to trial division, to return fairly bigger factors. In trial division, you start with 2, and test by all the odd numbers till p, where p is the factor of N. So, time complexity is O(p). In Pollard Rho, you start with a random number < N, and iterate by using a function, say x^2+1 (mod p). This function, after certain number of iterations, catches in a cycle and starts repeating (mod p). Since we do not know what p is, do so with f(x)=x^2+1 (mod N). If two iterations U and V are equal (mod p) and different (mod N), then GCD(U-V,N) will return p. You can use the tortoise-hare algorithm to check the matching value with the old ones: For each iteration, iterate U once and V twice, so that V-U will advance by one iteration. Compare its GCD with N, if it is a non-trivial factor, return it out up! What about the time complexity? By birthday paradox, it will take O(sqrt p) iterations to get caught up in a cycle (mod p). So, the time complexity is indeed O(sqrt p).

[raman22feb1988]

p-1 and ECM

p-1 algorithm gives the factor p if p-1 is smooth. From Fermat Little Theorem a^(p-1)=1 (mod p). Further, a^k(p-1)=1 (mod p) for any multiple k. So, if we choose B such that p-1 is B smooth (all factors of p-1 lying under B) and L is the LCM of all numbers upto B, then calculating GCD(a^L-1,N) will return p. Another improvement to p-1 is the Elliptic Curve Method, in ECM, you have to find a multiple of a point in the Elliptic Curve that is smooth to the group order. The multiples of points in the Elliptic Curves can be calculated similar to modular exponentiation and the group order lies between p-2sqrt(p) and p+2sqrt(p), depending on the sigma value of the curve. It can be used to find out factors upto 50 or 55 digits, the current record being 67 digits from (10^381)+1. ECM is a probabilistic algorithm that on repeated trials returns the factor.

[raman22feb1988]

General Purpose Factoring Algorithms

What about when N consists of two large primes? In Quadratic Sieve, the goal is to find out two numbers a, b such that their squares are equal (mod N), and a+b!=N, a-b!=1. They should give the non-trivial factorization of N. Once a^2=b^2 mod N, (a+b)(a-b)=0 mod N, and so GCD(N,a+b) and GCD(N,a-b) will return so the factors of N, if they are non-trivial. So, the approach is to first create a factor base consisting of small primes. Let N=11111, choose a factor base containing primes upto 20. Next, find squares mod N, such that they are factor base smooth. Start up with sqrt(N). For example, 106^2=5^3 mod 11111, 107^2=2.13^2 mod 11111, 109^2=2.5.7.11 mod 11111, 111^2=2.5.11^2 mod 11111. After that, try to find a congruence of squares, by solving the matrix on the RHS consisting of only zeros and ones. (Since we want only congruence of squares, just do all powers mod 2 and the one entries correspond to the odd powers of the corresponding primes in the factor base). Solve the matrix by using Gaussian elimination, though the frequently used algorithm for the sparse matrix is Block Lanczos. Try to establish a congruence of squares, for example the first, second and the fourth equation gives, 3419^2=7150^2 mod 11111. So, GCD(11111,7150-3419)=41 and GCD(11111,7150+3419)=271 are the factors of 11111. Note that a prime p divides x^2-N if and only if x=sqrt(N) mod p, so N should be a quadratic residue mod p. For example, the values of x for which 7 divides x^2-11111 can be given by sqrt(11111) mod 7 = sqrt(2) mod 7 = 3, 4 mod 7. So, the sequences of x for which 7 divides x^2-11111 are 108, 115, 122, 129... and 109, 116, 123, 130... Quadratic Sieve can be used to find out factors upto 100 digits, after that Number Field Sieve is faster. In NFS, instead of a degree 2 polynomial, a higher degree polynomial is used, usually 5 or 6, so here the quadratic residues does not work so. General NFS can be used to factor any number. Special NFS is fast for numbers of the form ax^6+bx^5+cx^4+dx^3+fx^2+gx+h, where a,b,c,d,f,g,h are all small. A good category of these type of numbers are the Cunningham numbers, which are of the form a^b+1 and a^b-1. The largest number factored so far using the GNFS is RSA-200 and by the SNFS is (2^1039)-1. Quadratic Sieve and NFS run under sub-exponential time. In 1994, Shor proposed a probabilistic algorithm to factor N in polynomial time in a quantum computer. It is indeed a general purpose factoring algorithm, factoring a number of N bits using this algorithm requires a quantum computer capable of holding (2N-1) qubits. In 2001, a group of workers at IBM factored 15 in a quantum computer of 7 qubits. This is the current state of factoring by using this algorithm. Because of this algorithm, factoring is now in complexity class BQP, i.e. quantum polynomial-time solvable algorithm.

[raman22feb1988]

Primality Testing
Fermat's Little Theorem: If a^(p-1) = 1 (mod p), then p may be prime.
Rabin Miller's Test:
If p is prime and a^[(p-1)/2^r] = 1 (mod p), then a^[(p-1)/2^(r+1)] = ± 1 (mod p)

Primality Proving
If a^(p-1) = 1 (mod p), but a^(p-1)/q ≠1 (mod p) for every prime q dividing p-1, then p is prime.
Pepin's Test For Fermat Numbers:
Let F(p) = 2^(2^p)+1. F(p) is prime if and only if 3^(F(p)-1)/2 = -1 (mod F(p)).
Lucas Lehmer Test For Mersenne Numbers:
Let M(p) = (2^p)-1. Define S(1) = 4. S(i) = S(i-1)^2 - 2 (mod M(p)) for all i ≥ 2.
M(p) is prime if and only if S(p-1) = 0.

Factoring
Trial Division: For factoring N, you test all the primes p ≤ √N.

Pollard's Rho: Consider the group {0, 1, 2, 3, 4... p-1} mod p.
If you start with a value P(0) and use a linear function ax+b, it will take p iterations
to return back to the original value P(0).
But if you use a quadratic function, say x^2+b, then it will get catch in a cycle sooner.

Since you don't know what p is, do mod N. If a = b (mod p), then GCD(|a-b|, N) will give p.
Do we need to examine all the previous values while iterating for congruence mod p?
No, you can use the tortoise-hare algorithm for cycle finding: Compare P(1) with P(2),
P(2) with P(4), P(3) with P(6), ... P(k) with P(2k).

By using birthday paradox, it will take O(√p) iterations to get looped in a cycle (mod p).

p-1: Returns factor p if p-1 is B-smooth.
From the Fermat's Little Theorem, we have that a^(p-1) = 1 (mod p). Further a^k(p-1) = 1 (mod p)
for any multiplier k. If we choose a value of B such that LCM of all numbers to B is a multiple
of p-1, then we can compute GCD(a^LCM(1...B)-1, N) to return the factor p.

Actually, to speed up the computations, we choose another bound B2 > B1, and the algorithm
returns the factor p if all the prime factors of p-1 except the largest lie below B1 and the largest
lie below B2.

p+1: Returns factor p if p+1 is B-smooth and Legendre Symbol (∆/p) = -1, or
if p-1 is B-smooth and Legendre Symbol (∆/p) = 1.
Lucas Sequences: Let α, β be the roots of x^2-Px+Q=0.
Then, define U(n) = (α^n-β^n)/(α-β) and V(n) = (α^n+β^n).
∆ = P^2-4Q. Then U(n) and V(n) can be computed by using the following formula:
U(0)=0, U(1)=1, U(n)=PU(n-1)-QU(n-2), U(2n)=V(n).U(n), U(2n-1)=U(n)^2-QU(n-1)^2
V(0)=2, V(1)=P, V(n)=PV(n-1)-QV(n-2), V(2n)=V(n)^2-2, V(2n-1)=V(n)V(n-1)-PQ^(n-1)
If P=1 and Q=-1, then these are the Fibonacci and the Lucas Sequences.

Further, we have that if p is prime, then U(p-(∆/p)) = 0 (mod p). U(k(p-(∆/p))) = 0 (mod p).
So, if p+1 is B-smooth and (∆/p) = -1, then computing
GCD(U(LCM(1...B)), N) will return the value for p.

General Purpose Factoring Algorithms:
These are all based upon the Fermat's Factorization Method.
Fermat's Factorization Method: In order to factor N, you need to find two distinct values of a, b < N
such that a^2 = b^2 (mod N) and a+b ≠N. If you have found out such a congruence, then GCD(a-b, N)
and GCD(a+b, N) will be the factors of N.
Sometimes, a multiplier may be used to N, to find out such a congruence easily. In this case, a^2 = b^2
(mod kN). This is the Lehman's Method.

Dixon's Factorization Method: For bigger numbers, it will be difficult to find out such a congruence. So,
we take a factor base consisting of all primes to a bound B. Only primes p such that (kN/p) = 1 will divide a^2-kN.

After we take the factor base, we find many squares a^2 (mod N) that are B-smooth. Each smooth square is a
relation. After this, we can combine the squares (mod N), such that their product is a perfect square (mod N).

Realize that this can be done through linear algebra. Construct a vector space for each relation consisting of the
size of the factor base. For each prime, if the power of prime in the relation for a^2 (mod N) is odd, then assign a
1 for it. If it is even, assign a 0 for it. You will have to find out a linearly dependent set of vectors.

One or more large primes can be included in the factor base, after examining the relations, for the sake of the
convenience purposes.

Continued Fraction Method: How will you collect many squares (mod N) that are B-smooth?
If you take the continued fraction expansion of √kN, then
√kN = q0 + 1/(q1 + 1/(q2 + 1/(q3 + 1/(q4 + 1/...))))

We have that, A(-1) = 1, B(-1) = 0
A(0) = q0, B(0) = 1
Then, A(i) and B(i) satisfy: A(i) = q(i).A(i-1) + A(i-2) and B(i) = q(i).B(i-1) + B(i-2)
The (n)th convergent is given by A(n)/B(n).

Further, we have that
A(i-1)^2 - kNB(i-1)^2 = (-1)^i.Q(i).
So, A(i-1)^2 = (-1)^i.Q(i) (mod N)
Each value of Q(i) satisfies 0 < Q(i) < 2√kN.
So, we have Q(i) (mod N), for checking if it is B-smooth, which is being the square of A(i-1), and we can thus have a
relation for each B-smooth value (mod N).

Quadratic Sieve: We need not trial divide all the Q(i) values in the continued fraction method for which the A(i-1) values
occur at random.

If we take the value of a^2-kN, in which the values of a are sequential, and if a prime p divides it, then
a^2-kN = 0 (mod p). So, a^2 = kN (mod p), then kN should be a quadratic residue (mod p), so the factor base needs to
contain only those primes for which the Legendre Symbol (kN/p) = 1.

Further, we have that a values are given by the square root of kN (mod p), so we need to sieve only those values of a,
thus examining only those relations, that satisfy a=±√kN (mod p), for any given value of prime p.

[raman22feb1988]

Have a look up, at my document, which explains all the algorithms for
the following problems in detail.
1) Primality Tests
2) Integer Factorization
3) Discrete Logarithms

Note that: Do not unzip the files. These files are not zipped at all. Just
use the renaming facility to simply change their file extensions to PPT or DOC
respectively.

[DOSGuy]

I am credited with discovering a Proth Prime. My computer found that 4087*2^477950+1 is prime. That number is 143 881 digits long, making it both a titanic prime (and its discoverer a titan) and a gigantic prime.

Primes of this size are not difficult for modern computers to find, but I did make it a goal of mine to become a titan before my next birthday. I exceeded my expectations when it made the Top 5000 List in Chris Caldwell's The Largest Known Primes Database (90675). At the time, it was the 4353rd largest prime ever discovered.

I found the prime using the BOINC client and joining PrimeGrid's Proth Prime Search. You, too, can find an enormous prime in a month or so with a reasonably good computer if you join the project.

[raman22feb1988]

I have seen your post that day itself;
I contribute for the Cunningham project; I have factored six numbers for it; doing my seventh and eighth.
http://homes.cerias.purdue.edu/~ssw/cun/index.html

The factoring project, with Number Field Sieve I choose because you can definitely get the credit after spending CPU-months of work. There are other popular projects too, in which you can participate within.

The GIMPS at (http://www.mersenne.org) is the most popular project; just simply download the Prime95 (for Windows); mprime (for Linux) software and then start starting out for a new Mersenne Prime. But note that it is very rare that the number you will be testing turns out to be a Mersenne Prime unless you are VERY lucky.

You can also try to find out factors of Fermat Numbers by using the Elliptical Curve method; factors are available at http://prothsearch.net/fermat.html; Fermat Numbers 14, 20, 22, 24 have no known factors at all; it is too difficult to find out a new factor of any Fermat Number; all these numbers already have had a lot of ECM curves; are your hands lucky enough?

Feel free to join up http://www.mersenneforum.org to ask for any help. It has lots of prime searching and factoring projects. For example, you may terminate a new aliquot sequence (see the aliquot sequence forum; http://www.aliquot.de/aliquote.htm). This is relatively easier to find out; to do so only.

Or that you may use the Elliptic Curve method to find out any new small factors of Cunningham numbers; use GMP-ECM; Mersenne 1061, 1237, 1277 have no known factors at all; but it is increasingly very difficult to find out a new factor of any Cunningham number by using ECM, as the factor size increases up; all the Cunningham numbers already have had plenty of ECM curves! You would need to start up right with 55 digit factors only.

To use the Number Field Sieve tool for factoring Cunningham numbers; you would need access to atleast 3 to 4 CPUs for a few months. As all the remaining Cunningham composites are already big enough. Download up the softwares GGNFS, msieve at http://www.boo.net/~jasonp/qs.html; start up to use them; feel free to contact the Mersenne Forum for any further help. How old are you? Where are you living at? Where are you from? (If you want up to maintain privacy of these details; you may send me up a PM about these personal details only.)

Good Luck! If you are still interested as yet; you may carry on with the Seventeen or Bust project itself within your systems. I am not compelling you at all to join the other projects; just simply giving up a suggestion only.

[raman22feb1988]

Yesterday, I saw the announcement that RSA 768 has been factored.
It is 768 bits when written in binary, so 232 digits in decimal notation only.
RSA numbers are chosen such that it splits up into two equal sized primes,
such that they are difficult to factor. This is the largest factorization of a
general number, by using the General Number Field Sieve factoring algorithm.
Numbers that are closer to higher power of integer, of the same size, are
comparatively very much easier to factor, by using the Special Number Field
Sieve algorithm itself. The General Number Field Sieve is indeed only derived
up from the Special Number Field Sieve for factoring any general number. It
only varies in the polynomial that is being used up, as Special Number Field
Sieve makes use of special polynomials for making it very easy to factor. The
numbers that can be attacked up by using the Special Number Field Sieve include
Cunningham Numbers, Fibonacci/Lucas Numbers, Homogeneous Cunninghams,
near Repdigits, etc.

For details about the factorization of RSA 768, please see at this place:
http://crypto-world.com/announcements/rsa768.txt

[raman22feb1988]

Only a few days ago, on December 28, 2009, an ECM record factor was found out.
A 68 digit prime factor from 64.(10^341)-1. The previous record was 67 digits from
(10^381)+1. The Elliptic Curve Method is the fastest known algorithm to eliminate
out the small factors of any general number. The fastest implementation of this ECM
algorithm is GMP-ECM.

Please have a look up at
http://www.loria.fr/%7Ezimmerma/records/top50.html
for the all time top 50 factors that are being found out by using this Elliptic Curve Method only.

A prime factor p, from any given number can be easily found out, if either p-1 or p+1
is smooth enough, by using the respective algorithms itself. So, it is very important
to ensure that the prime factors of the so generated RSA numbers, do not satisfy up
this property at all. Otherwise, that they would be very easy to crack out by using these
methods only. Thus, then they would not be challenge numbers at all.

[DOSGuy]

I discovered my titanic prime because I decided that I wanted to become a titan before age 30, so I stopped doing Seventeen or Bust in favor of PrimeGrid for BOINC and found a prime after almost exactly one month.

A couple of days ago I found out that my prime had fallen off of the Top 5000 list, so I fired BOINC back up... and found another prime less than 24 hours later!

I am credited with discovering another Proth Prime. My computer found that 5441*2^487041+1 is prime. That number is 146 618 digits long, and made the Top 5000 List in Chris Caldwell's The Largest Known Primes Database (91606). At the time, it was the 4693rd largest prime ever discovered.

So, if you're interested in being the discoverer of a prime number, apparently it isn't that hard to do!

[raman22feb1988]

F14 is factored

Yesterday, Tapio Rajula of Finland discovered a factor of the 14th Fermat Number
(2^16384)+1 which is 116928085873074369829035993834596371340386703423373313
This was the smallest Fermat Number with no known factors before itself, at all.
The factor was being found out by using the Elliptic Curve Method in Prime95 from GIMPS.
More details about Fermat Numbers can be found out at http://prothsearch.net/fermat.html

As of now, it is known that only the first five Fermat numbers F(0) through F(4) namely
3, 5, 17, 257, 65537 are known to be prime.
F(5) through F(11) are being completely factored out
F(12) through F(24) are all incompletely factored, with all their cofactors known to be composite only, though no factors are known at all for F(20), F(22), F(24).
F(25) through F(32) each have atleast one prime factor known.
F(33) is the smallest Fermat number without known status (prime or composite).

F(n) = 2^(2^n)+1
Any factor of F(n) will only always be of the form k.2^(n+2)+1.

Here is the known factorization of the first twenty Fermat numbers:
F0 = 3
F1 = 5
F2 = 17
F3 = 257
F4 = 65537
F5 = 641 · 6700417
F6 = 274177 · 67280421310721
F7 = 59649589127497217 · 5704689200685129054721
F8 = 1238926361552897 · P62
F9 = 2424833 · 7455602825647884208337395736200454918783366342657 · P99
F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252
F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513 · P564
F12 = 114689 · 26017793 · 63766529 · 190274191361 · 1256132134125569 · C1187
F13 = 2710954639361 · 2663848877152141313 · 3603109844542291969 ·
319546020820551643220672513 · C2391
F14 = 116928085873074369829035993834596371340386703423373313 · C4880
F15 = 1214251009 · 2327042503868417 · 168768817029516972383024127016961 · C9808
F16 = 825753601 · 188981757975021318420037633 · C19694
F17 = 31065037602817 · C39444
F18 = 13631489 · 81274690703860512587777 · C78884
F19 = 70525124609 · 646730219521 · 37590055514133754286524446080499713 · C157770

Only a few months back, the last known prime factor of F19 had been discovered up.

[raman22feb1988]

On March 6, 2010, Thorsten Kleinjung, Joppe Bos, Arjen Lenstra, Peter Montgomery
from Bonn University, Switzerland found out a 73 digit prime factor from (2^1181)-1
thus setting up a new ECM record.
For more details, visit up the information at the following page only
by now itself

http://www.loria.fr/~zimmerma/records/ecmnet.html

[raman22feb1988]

Two New Fermat Number Factors !!
F22

Only after a few weeks after F14 = 2^(2^14)+1 had been factored
day before yesterday a factor of F22 = 2^(2^22)+1 had been found out
by using the Elliptic Curve Method by David Bessell
F22 has a factor: 64658705994591851009055774868504577
This is the first known factor of this number!

Any factor of 2^(2^n)+1 will always be of the form k.(2^(n+2))+1
No factors are known till now for F20, F24 which are known
to be already composite as of now. Awaiting the factors for
these numbers right now!!

All the known Fermat factors are always being available at
this following website: http://prothsearch.net/fermat.html

Hope that this will be a great year for more of the Fermat number
factors!

F12

Yesterday, Michael Vang found out this new factor of F12 = 2^(2^12)+1
568630647535356955169033410940867804839360742060818433
by using GMP-ECM

F12 is the lowest Fermat Number that is incompletely factored
The 1133 digit cofactor is still composite, as yet, as of now

Once again, I repeat that any factor of 2^(2^n)+1 will always be of
the form k.(2^(n+2))+1, and then that any factor of (2^p)-1 if p is
prime will always be of the form 2kp+1.
All the known Fermat number factors are always being available
at this following website page: http://prothsearch.net/fermat.html
Thus, being updated up regularly, frequently

The status of the first 25 Fermat Numbers status right now:

F0 = 3
F1 = 5
F2 = 17
F3 = 257
F4 = 65537
F5 = 641 · 6700417
F6 = 274177 · 67280421310721
F7 = 59649589127497217 · 5704689200685129054721
F8 = 1238926361552897 · P62
F9 = 2424833 · 7455602825647884208337395736200454918783366342657 · P99
F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252
F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513 · P564
F12 = 114689 · 26017793 · 63766529 · 190274191361 · 1256132134125569 · 568630647535356955169033410940867804839360742060818433 · C1133
F13 = 2710954639361 · 2663848877152141313 · 3603109844542291969 ·
319546020820551643220672513 · C2391
F14 = 116928085873074369829035993834596371340386703423373313 · C4880
F15 = 1214251009 · 2327042503868417 · 168768817029516972383024127016961 · C9808
F16 = 825753601 · 188981757975021318420037633 · C19694
F17 = 31065037602817 · C39444
F18 = 13631489 · 81274690703860512587777 · C78884
F19 = 70525124609 · 646730219521 · 37590055514133754286524446080499713 · C157770
F20 = C315653
F21 = 4485296422913 · C631294
F22 = 64658705994591851009055774868504577 · C1262577
F23 = 167772161 · C2525215
F24 = C5050446

It is true that atleast one prime factor is known for the Fermat Numbers F25 through F32. The status of their cofactors whether prime or composite is unknown as of now. The smallest Fermat number without any known factors at all whose entire status is being unknown right now is thus F33, right then?