Factorise and Test Primality

Arthur Vause

Enter Number:


This is an experiment to see how quickly a number could be factorised into primes using straightforward readable javascript.

The algorithms test primality of a number using Miller-Rabin and factorise a number using trial division, Pollard Rho, and Elliptic Curve Method (ECM). Factorisation may take some time if the number has two large prime factors.

ECM algorithm

The ECM algorithm uses Montgomery elliptic curves with Suyama parameterisation to construct the curves, and has 2 phases based on the descriptions in [1] and [2]

Phase 1 multiplies the initial point on the elliptic curve by all prime powers pn < B1 to produce a point Q on the curve

Phase 2 calculates multiples pQ for each prime B1 < p ≤ B:
Multiples of Q : [Q,2Q,3Q,..,(D-1)Q] and [DQ,2DQ,3DQ,...], where D is set to √B2 , are pre-calculated and then used to calculate pQ = kDQ + rQ where 0 ≤ r < D
The pre-calculated multiples mQ=(x,z) are converted to (x/z,1) to simplify the calculation of pQ

Bounds B1 and B2 are calculated from the size of the number to be factored, based on the table in [3], and assumes that the number to be factored is a semiprime with 2 similarly sized factors

Some numbers to try:

This page uses the algorithms to calculate factors of Cunningham numbers of the form bn ± 1 for n=1,2,3,....

Try these numbers: 12345678910987654321 , 10000000000000000000000000000001 (1031+1), 111111111111111111111111111111111111111111111111 (48 '1's) , 29629629629629629629629629629629629629629629629629 (50 digits)

A related pair: 111111111 and 12345678987654321

These take a bit longer: 1010101010101010101010101010101010101 (37 digits) , 11111111111111111111111111111111111111 (38 '1's), 100000000000000000000000000000000000000001 (1041 + 1)

References

[1] P. Zimmermann. 20 years of ECM. 7th Algorithmic Number Theory Symposium (ANTS VII),2006, Berlin, pp.525–542. inria-00070192v1 https://hal.inria.fr/inria-00070192v1/document

[2] R.Brent, Factorization Of The Tenth Fermat Number, 1999, Mathematics of Computation, Vol. 68, p. 429-451 https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00992-8/S0025-5718-99-00992-8.pdf

[3] P. Zimmermann. Optimal parameters for ECM https://members.loria.fr/PZimmermann/records/ecm/params.html

Web Counter
Website Hit Counters