gap> Factors(1459^60-1); #I #I Check for n = b^k +/- 1 #I 697136005439518321339364341462731479643931164718338822169985761598533184155968\ 687683267309071831767783053294661533309653344501590527857911683460652704454392\ 2114173712945384179913214273324400 = 1459^60 - 1 #I The factors corresponding to polynomial factors are [ 1458, 1460, 2127223, 2128682, 2130141, 4528179181405, 4531280671081, 4534390675481, 20518450806493943781446161, 20532514165758816624282961, 20546596816316767296268561, 421584732115767299535558510031830342788459718258721 ] #I Intermediate result : [ [ 4531280671081, 20546596816316767296268561 ], [ 1458, 1460, 2127223, 2128682, 2130141, 4528179181405, 4534390675481, 20518450806493943781446161, 20532514165758816624282961, 421584732115767299535558510031830342788459718258721 ] ] #I #I Factors already found : [ 4531280671081, 20546596816316767296268561 ] #I #I #I Trial division by all primes p < 1000 #I Intermediate result : [ [ 2, 3, 3, 3, 3, 3, 3 ], [ ] ] #I Intermediate result : [ [ 2, 2, 5, 73 ], [ ] ] #I Intermediate result : [ [ 7, 303889 ], [ ] ] #I Intermediate result : [ [ 2, 1064341 ], [ ] ] #I Intermediate result : [ [ 3, 13, 193, 283 ], [ ] ] #I Intermediate result : [ [ 5, 11, 521, 158024051 ], [ ] ] #I Intermediate result : [ [ 31, 146270666951 ], [ ] ] #I Intermediate result : [ [ 61 ], [ 336368046008097439040101 ] ] #I #I Factors already found : [ 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 7, 11, 13, 31, 61, 73, 193, 283, 521, 303889, 1064341, 158024051, 146270666951, 4531280671081, 20546596816316767296268561 ] #I #I #I Trial division by some already known primes #I #I Check for perfect powers #I #I Pollard's Rho Steps = 16384, Cluster = 1638 Number to be factored : 336368046008097439040101 #I Intermediate result : [ [ 2251, 149430495783250750351 ], [ ] ] #I #I Pollard's Rho Steps = 16384, Cluster = 1638 Number to be factored : 20532514165758816624282961 #I #I Pollard's Rho Steps = 16384, Cluster = 1638 Number to be factored : 421584732115767299535558510031830342788459718258721 #I #I Factors already found : [ 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 7, 11, 13, 31, 61, 73, 193, 283, 521, 2251, 303889, 1064341, 158024051, 146270666951, 4531280671081, 149430495783250750351, 20546596816316767296268561 ] #I #I #I Pollard's p - 1 Limit1 = 10000, Limit2 = 400000 Number to be factored : 20532514165758816624282961 #I Initializing prime differences list, PrimeDiffLimit = 1000000 #I p-1 for n = 20532514165758816624282961 a : 2, Limit1 : 10000, Limit2 : 400000 #I First stage #I Second stage #I #I Pollard's p - 1 Limit1 = 10000, Limit2 = 400000 Number to be factored : 421584732115767299535558510031830342788459718258721 #I p-1 for n = 421584732115767299535558510031830342788459718258721 a : 2, Limit1 : 10000, Limit2 : 400000 #I First stage #I Second stage #I #I Williams' p + 1 Residues = 2, Limit1 = 2000, Limit2 = 80000 Number to be factored : 20532514165758816624282961 #I p+1 for n = 20532514165758816624282961 Residues : 2, Limit1 : 2000, Limit2 : 80000 #I Residue no. 1 #I Residue no. 2 #I #I Williams' p + 1 Residues = 2, Limit1 = 2000, Limit2 = 80000 Number to be factored : 421584732115767299535558510031830342788459718258721 #I p+1 for n = 421584732115767299535558510031830342788459718258721 Residues : 2, Limit1 : 2000, Limit2 : 80000 #I Residue no. 1 #I Residue no. 2 #I #I Elliptic Curves Method (ECM) Curves = Init. Limit1 = , Init. Limit2 = , Delta = Number to be factored : 20532514165758816624282961 #I ECM for n = 20532514165758816624282961 #I Digits : 26, Curves : 3 #I Initial Limit1 : 200, Initial Limit2 : 20000, Delta : 200 #I Curve no. 1 ( 3), Limit1 : 200, Limit2 : 20000 #I Curve no. 2 ( 3), Limit1 : 400, Limit2 : 40000 #I 11 - digit factor 12077430061 was found in second stage #I Intermediate result : [ [ 12077430061, 1700073116718901 ], [ ] ] #I #I Elliptic Curves Method (ECM) Curves = Init. Limit1 = , Init. Limit2 = , Delta = Number to be factored : 421584732115767299535558510031830342788459718258721 #I ECM for n = 421584732115767299535558510031830342788459718258721 #I Digits : 51, Curves : 27 #I Initial Limit1 : 200, Initial Limit2 : 20000, Delta : 200 #I Curve no. 1 ( 27), Limit1 : 200, Limit2 : 20000 #I Curve no. 2 ( 27), Limit1 : 400, Limit2 : 40000 #I Curve no. 3 ( 27), Limit1 : 600, Limit2 : 60000 #I Curve no. 4 ( 27), Limit1 : 800, Limit2 : 80000 #I Curve no. 5 ( 27), Limit1 : 1000, Limit2 : 100000 #I Curve no. 6 ( 27), Limit1 : 1200, Limit2 : 120000 #I Curve no. 7 ( 27), Limit1 : 1400, Limit2 : 140000 #I Curve no. 8 ( 27), Limit1 : 1600, Limit2 : 160000 #I Curve no. 9 ( 27), Limit1 : 1800, Limit2 : 180000 #I Curve no. 10 ( 27), Limit1 : 2000, Limit2 : 200000 #I Curve no. 11 ( 27), Limit1 : 2200, Limit2 : 220000 #I Curve no. 12 ( 27), Limit1 : 2400, Limit2 : 240000 #I Curve no. 13 ( 27), Limit1 : 2600, Limit2 : 260000 #I Curve no. 14 ( 27), Limit1 : 2800, Limit2 : 280000 #I Curve no. 15 ( 27), Limit1 : 3000, Limit2 : 300000 #I Curve no. 16 ( 27), Limit1 : 3200, Limit2 : 320000 #I Curve no. 17 ( 27), Limit1 : 3400, Limit2 : 340000 #I Curve no. 18 ( 27), Limit1 : 3600, Limit2 : 360000 #I Curve no. 19 ( 27), Limit1 : 3800, Limit2 : 380000 #I Curve no. 20 ( 27), Limit1 : 4000, Limit2 : 400000 #I Curve no. 21 ( 27), Limit1 : 4200, Limit2 : 420000 #I Curve no. 22 ( 27), Limit1 : 4400, Limit2 : 440000 #I Curve no. 23 ( 27), Limit1 : 4600, Limit2 : 460000 #I Curve no. 24 ( 27), Limit1 : 4800, Limit2 : 480000 #I Curve no. 25 ( 27), Limit1 : 5000, Limit2 : 500000 #I Curve no. 26 ( 27), Limit1 : 5200, Limit2 : 520000 #I Curve no. 27 ( 27), Limit1 : 5400, Limit2 : 540000 #I #I Factors already found : [ 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 7, 11, 13, 31, 61, 73, 193, 283, 521, 2251, 303889, 1064341, 158024051, 12077430061, 146270666951, 4531280671081, 1700073116718901, 149430495783250750351, 20546596816316767296268561 ] #I #I #I Multiple Polynomial Quadratic Sieve (MPQS) Number to be factored : 421584732115767299535558510031830342788459718258721 #I MPQS for n = 421584732115767299535558510031830342788459718258721 #I Digits : 51 #I Multiplier : 1 #I Size of factor base : 1326 #I Prime powers to be sieved : 1349 #I Length of sieving interval : 131072 #I Small prime limit : 117 #I Large prime limit : 3500186 #I Number of used a - factors : 4 #I Size of a - factors pool : 52 #I Initialization time : 11 sec. #I #I Sieving #I #I Complete factorizations over the factor base : 50 #I Relations with a large prime factor : 5 #I Relations remaining to be found : 1343 #I Total factorizations with a large prime factor : 614 #I Used polynomials : 67 #I Elapsed runtime : 39 sec. #I Progress (relations) : 3 % #I #I #I Complete factorizations over the factor base : 101 #I Relations with a large prime factor : 20 #I Relations remaining to be found : 1277 #I Total factorizations with a large prime factor : 1364 #I Used polynomials : 149 #I Elapsed runtime : 73 sec. #I Progress (relations) : 8 % #I #I #I Complete factorizations over the factor base : 150 #I Relations with a large prime factor : 51 #I Relations remaining to be found : 1197 #I Total factorizations with a large prime factor : 2085 #I Used polynomials : 233 #I Elapsed runtime : 107 sec. #I Progress (relations) : 14 % #I #I #I Complete factorizations over the factor base : 200 #I Relations with a large prime factor : 80 #I Relations remaining to be found : 1118 #I Total factorizations with a large prime factor : 2692 #I Used polynomials : 301 #I Elapsed runtime : 134 sec. #I Progress (relations) : 20 % #I #I #I Complete factorizations over the factor base : 250 #I Relations with a large prime factor : 129 #I Relations remaining to be found : 1019 #I Total factorizations with a large prime factor : 3350 #I Used polynomials : 375 #I Elapsed runtime : 163 sec. #I Progress (relations) : 27 % #I #I #I Complete factorizations over the factor base : 301 #I Relations with a large prime factor : 177 #I Relations remaining to be found : 920 #I Total factorizations with a large prime factor : 3910 #I Used polynomials : 438 #I Elapsed runtime : 189 sec. #I Progress (relations) : 34 % #I #I #I Complete factorizations over the factor base : 350 #I Relations with a large prime factor : 250 #I Relations remaining to be found : 798 #I Total factorizations with a large prime factor : 4665 #I Used polynomials : 517 #I Elapsed runtime : 221 sec. #I Progress (relations) : 42 % #I #I #I Complete factorizations over the factor base : 400 #I Relations with a large prime factor : 333 #I Relations remaining to be found : 665 #I Total factorizations with a large prime factor : 5576 #I Used polynomials : 618 #I Elapsed runtime : 264 sec. #I Progress (relations) : 52 % #I #I #I Complete factorizations over the factor base : 450 #I Relations with a large prime factor : 433 #I Relations remaining to be found : 515 #I Total factorizations with a large prime factor : 6345 #I Used polynomials : 707 #I Elapsed runtime : 302 sec. #I Progress (relations) : 63 % #I #I #I Complete factorizations over the factor base : 500 #I Relations with a large prime factor : 545 #I Relations remaining to be found : 353 #I Total factorizations with a large prime factor : 7257 #I Used polynomials : 809 #I Elapsed runtime : 347 sec. #I Progress (relations) : 74 % #I #I #I Complete factorizations over the factor base : 550 #I Relations with a large prime factor : 622 #I Relations remaining to be found : 226 #I Total factorizations with a large prime factor : 7840 #I Used polynomials : 875 #I Elapsed runtime : 379 sec. #I Progress (relations) : 83 % #I #I #I Complete factorizations over the factor base : 601 #I Relations with a large prime factor : 713 #I Relations remaining to be found : 84 #I Total factorizations with a large prime factor : 8405 #I Used polynomials : 939 #I Elapsed runtime : 413 sec. #I Progress (relations) : 93 % #I #I #I Complete factorizations over the factor base : 651 #I Relations with a large prime factor : 826 #I Relations remaining to be found : 0 #I Total factorizations with a large prime factor : 9164 #I Used polynomials : 1021 #I Elapsed runtime : 455 sec. #I Progress (relations) : 100 % #I #I Creating the exponent matrix #I Doing Gaussian Elimination, #rows = 1477, #columns = 1378 #I Processing the zero rows #I Dependency no. 1 yielded no factor #I Dependency no. 2 yielded no factor #I Dependency no. 3 yielded no factor #I Dependency no. 4 yielded no factor #I Dependency no. 5 yielded no factor #I Dependency no. 6 yielded no factor #I Dependency no. 7 yielded no factor #I Dependency no. 8 yielded no factor #I Dependency no. 9 yielded factor 26725378467920336641 #I The factors are [ 26725378467920336641, 15774696422795817479975816558881 ] #I Digit partition : [ 20, 32 ] #I MPQS runtime : 473.507 sec. #I Intermediate result : [ [ 26725378467920336641, 15774696422795817479975816558881 ], [ ] ] #I #I The result is [ [ 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 7, 11, 13, 31, 61, 73, 193, 283, 521, 2251, 303889, 1064341, 158024051, 12077430061, 146270666951, 4531280671081, 1700073116718901, 26725378467920336641, 149430495783250750351, 20546596816316767296268561, 15774696422795817479975816558881 ], [ ] ] #I The total runtime was 799.408 sec. [ 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 7, 11, 13, 31, 61, 73, 193, 283, 521, 2251, 303889, 1064341, 158024051, 12077430061, 146270666951, 4531280671081, 1700073116718901, 26725378467920336641, 149430495783250750351, 20546596816316767296268561, 15774696422795817479975816558881 ] gap>