Efficently find divisors of numbers up to 20 digits

Question

I am aware that finding divisors of large numbers is a well known mathematical problem (which is one of the reasons why cryptography works). Most solutions I've stumbled across used prime factorization to speed up the process a bit. However, on numbers bigger then $2^{32}$ all these solutions started to take seconds, minutes and hours.

For some reason this website can find the divisors for numbers up to $20$, digits, thats around $2^{64}$, within milliseconds. The algorithm can be seen by looking at the page source code. Apparently the input number is splitted into a high and a low section. Can somebody tell me the algorithm used here, and why it is so fast?

For numbers of this size, I think the most widely used is SQUFOF and its variations. — metamorphy, Oct 21 '18 at 05:02

David G. Stork · Answer 1 · 2018-10-21T06:17:18.500

1

Mathematica factors 20-digit integers in 0.000225 seconds:

Timing[FactorInteger[54605705157543059870]]

{0.000225, 
   {{2, 1}, {5, 1}, {7, 1}, {193, 1}, {811, 1}, {4983813894767, 1}}}

and its speed is due, apparently, to its use of trial division, Pollard p−1, Pollard rho, elliptic curve, and quadratic sieve algorithms. Elliptic Curve Method.

edited Oct 21 '18 at 06:17

answered Oct 21 '18 at 01:15

David G. Stork

29,774

That might be true, but how can they achieve such speeds? What algorithm is used? – Kyu96 Oct 21 '18 at 01:17
According to this (https://mathematica.stackexchange.com/questions/11286/does-mathematica-use-the-elliptic-curve-method-ecm-in-factorinteger) Mathematica uses the Elliptic Curve Method (ECM). – David G. Stork Oct 21 '18 at 06:17

score 0 · Answer 2 · answered Oct 21 '18 at 01:11

0

The code here uses a brute force search, with the slight optimization of sieving $\bmod 30$.

answered Oct 21 '18 at 01:11

Bill Dubuque

272,048

Efficently find divisors of numbers up to 20 digits

2 Answers2