Factorize big integers using Miller Rabin and Pollards Rho

▼ Factorizing integers

Factorizing integers is a well-researched field, and there are several complicated algorithms which are used in order to factorize integers of over 100 digits. These include the Quadratic Sieve, the Elliptic Curve Method, and the General Number Field Sieve. Programs which can factorize numbers over 100 digits may take minutes, hours or days to run, depending on the factors of the number. The algorithm on this page uses three sub-algorithms: trial division, Pollard's Rho, and the Miller-Rabin algorithm. Trial division simply tries integers of increasing size up to the square root of the number to be factorized, to see if they are factors. This can be very inefficient. Pollard's Rho algorithm quickly finds factors (which may be non-prime), allowing the integer to be partially factorized. Using Pollard's Rho repeatedly can be more efficient than trial division. The Miller-Rabin algorithm quickly identifies if an integer is prime or not, and so is very useful to check factors found using Pollard's Rho. The version of Pollard's Rho used here involves random quadratics. Therefore it is possible that the program may factorize an integer on one occasion but not on another.

▼ Some factorizations this algorithm can find

31415926535897 = 163×44777×4304347

239812014798221 = 15485863×15485867

2310000000000000000000000000000000000 = 2^{34}×3×5^{34}×7×11

1001001000000007 = 64513×15516268039

10000000000000331 = 31×322580645161301

5313531353135313531353135313 = 3×7×11×23×29×239×281×4649×909091×121499449

352523661753384896 = 2^{6}×83×2603401×25491133

341550071728318 = 2×53×1194883×2696641

3825123056546413051 = 149491×747451×34233211

79798272259984334113870248395353 = 1303×6763×10627×16927×29947×157543×10670053

41615325283752522089299429 = 16927^{5}×29947

100000000000000000000000000000000000000000001 = 73×137×617×16205834846012967584927082656402106953

341550071728319 = 4185971×81593989

100000000000000000000000000000001 = 19841×976193×6187457×834427406578561

281728347264723747372617263727162736372615 = 3×5×11^{2}×11673043×26741327×497263838545366893718661

314159265358979323846264338327950288419716939937510 = 2×5×1657×2767321×6851218613299640439836648376783398546983

109890109889010989011 = 599144041×183411838171

▼ Strong pseudoprimes

Strong pseudoprimes are harder for prime factorization algorithms to factorize. You can find a more technical definition here at Wikipedia. You can find lists of strong pseudoprimes in the Online Encyclopaedia of Integer Sequences (OEIS).

Here are some strong pseudoprimes to factorize!

3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981, 2152302898747, 2273312197621, 2366338900801, 3343433905957