mersenneforum.org Why do these P+1 factorizations work?
 Register FAQ Search Today's Posts Mark Forums Read

 2009-03-29, 16:32 #1 Mr. P-1     Jun 2003 7·167 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
 2009-03-29, 17:17 #2 akruppa     "Nancy" Aug 2002 Alexandria 25×7×11 Posts In P-1, if all factors p of N are p≡1 (mod m) for some m, then N≡1 (mod m), and we can include m in the stage 1 exponent by exponentiating by N-1, without actually knowing what m is. GMP-ECM does that, so that for example for cyclotomic numbers Φm(x), the known factor m in p-1 is always included, without the user having to specify m via the -go parameter. For P+1, we adapt this to exponentiating by N2-1 in stage 1. This way, if all factors are p≡±1 (mod m) for some m, we are certain to include m in the exponent. In your two cases, N2-1 happens to be divisible by 12223199 and 12215821, respectively, so these to primes got included in stage 1 even though they are greater than B1. Alex Last fiddled with by akruppa on 2009-03-30 at 22:49 Reason: typos
 2009-03-30, 07:54 #3 Mr. P-1     Jun 2003 49116 Posts That's great! In fact, I already knew about the 12223199 and 12215821 factors of p-1. Both Ns are composite factors of Mersennes found by P-1, and I was looking for the best way to resolve them. Of course I can break them in seconds by throwing a few curves at them, but using P+1 to the original P-1 bounds breaks them in a fraction of a second. The downside is that sometimes you get a "found input number N" and the program halts even if there are more runs to do. Is there a way to make in continue when that happens? Last fiddled with by Mr. P-1 on 2009-03-30 at 07:57
 2009-03-30, 14:05 #4 akruppa     "Nancy" Aug 2002 Alexandria 246410 Posts Hmm... a "Don't take N for an answer" option should not be too hard, once I figure out how the loop in main.c works again. In the meantime, if you find N frequently, it's a strong hint that the B1,B2 values are too high. If you give "-v -v" verboseness and a composite factor is found in stage 2, it'll test each point of evaluation for a factor (instead of just their product) and try to determine the largest prime factor in the group order associated with each prime factor of N. A side effect is that usually the prime factors of the composite factor of N are printed. (And when I tested whether that code actually still works, I found that the code could segfault sometimes... fixed in SVN, but beware if you use 6.2.2. There are enough bugs piling up that we may need a 6.2.3 soon. ) Alex
 2009-10-11, 10:49 #5 ATH Einyen     Dec 2003 Denmark 296510 Posts Is this also why this factor was found by P-1 during P+1? GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [P+1] Input number is (2^2917+1)/3 (878 digits) Using B1=10000000, B2=93541776130, polynomial x^1, x0=3358300603 Step 1 took 75640ms Step 2 took 100922ms [factor found by P-1] ********** Factor found in step 2: 19038883797876537274366477800610849 Found probable prime factor of 35 digits: 19038883797876537274366477800610849 Composite cofactor ((2^2917+1)/3)/19038883797876537274366477800610849 has 844 digits
 2009-10-11, 12:44 #6 akruppa     "Nancy" Aug 2002 Alexandria 9A016 Posts P+1 can either end up working in a group of order p-1 or p+1, depending on whether x02 - 4 is a quadratic residue modulo p or not. Since we don't know p in advance, we can't tell which one it was until after p was found. If it was actually p-1, the GMP-ECM prints the message you quoted. The effect of getting either p-1 or p+1 is pretty fundamental to how P+1 works, we don't know how to construct a quadratic extension of GF(p) reliably without knowing p. The extra exponentiation etc. we do in GMP-ECM is not related to this. Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Cunningham Tables 39 2020-08-28 14:34 R.D. Silverman Factoring 79 2012-01-12 10:58 jjcale Factoring 6 2011-07-28 02:06 wblipp Math 2 2010-08-15 20:33 gd_barnes No Prime Left Behind 25 2009-07-30 12:06

All times are UTC. The time now is 21:20.

Mon Oct 19 21:20:45 UTC 2020 up 39 days, 18:31, 1 user, load averages: 2.16, 1.85, 1.84