View Single Post
 2009-03-29, 16:32 #1 Mr. P-1     Jun 2003 100100100012 Posts 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