View Single Post
Old 2009-03-29, 16:32   #1
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

100100100012 Posts
Default Why do these P+1 factorizations work?

Code:
$ echo 264230314763760208834215981504580626343342447 | ecm -x0 407367722 -pp1 1312500 0
GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1]
Input number is 264230314763760208834215981504580626343342447 (45 digits)
Using B1=1312500, B2=0, polynomial x^1, x0=407367722
Step 1 took 1776ms
********** Factor found in step 1: 5661205017073505552389801
Found probable prime factor of 25 digits: 5661205017073505552389801
Probable prime cofactor 46673864303955381847 has 20 digits
p+1 = 5661205017073505552389802 = 2 * 13 * 1693921 * 128541209715699337
p-1 = 5661205017073505552389800 = 2^3 * 3 * 5^2 * 7 * 19 * 137 * 619 * 215899 * 12223199

Neither p+1 nor p-1 is smooth to the given bound.

Here's another:

Code:
$ echo 2855451057157704997579326497626590663028969 | ecm -pp1 -x0 3338685868 1277500 0
GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1]
Input number is 2855451057157704997579326497626590663028969 (43 digits)
Using B1=1277500, B2=0, polynomial x^1, x0=3338685868
Step 1 took 1720ms
********** Factor found in step 1: 896774094182730749591
Found probable prime factor of 21 digits: 896774094182730749591
Probable prime cofactor 3184136423744490284159 has 22 digits
p+1 = 896774094182730749592 = 2^3 * 3 * 659 * 4093351 * 13851838237
p-1 = 896774094182730749590 = 2 * 5 * 11 * 257 * 25307 * 102611 * 12215821
Mr. P-1 is offline   Reply With Quote