Factorise and Test Primality
Arthur Vause
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 ≤ B2 :
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
Website Hit Counters