mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2009-03-29, 16:32   #1
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 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
Old 2009-03-29, 17:17   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-03-30, 07:54   #3
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

49116 Posts
Default

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
Mr. P-1 is offline   Reply With Quote
Old 2009-03-30, 14:05   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246410 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-10-11, 10:49   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

296510 Posts
Default

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
ATH is offline   Reply With Quote
Old 2009-10-11, 12:44   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A016 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aurifeuillian Factorizations Raman Cunningham Tables 39 2020-08-28 14:34
The worth or futility of gratituous factorizations R.D. Silverman Factoring 79 2012-01-12 10:58
algorithms for special factorizations jjcale Factoring 6 2011-07-28 02:06
Schinzel's Aurifeuillian style factorizations? wblipp Math 2 2010-08-15 20:33
Prime k-value density rating and factorizations 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.