mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-05-05, 03:22   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default Where is P-1, P+1 effort recorded?

Is there any record of how much P-1 and P+1 effort has been applied to the Cunningham numbers?

If not, does anyone have a guess? Is it reasonable to assume the base two numbers have all had P-1 done at least to the Prime95 limit B1=4.29e9?
geoff is offline   Reply With Quote
Old 2004-05-05, 08:34   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,753 Posts
Default

Quote:
Originally Posted by geoff
Is there any record of how much P-1 and P+1 effort has been applied to the Cunningham numbers?

If not, does anyone have a guess? Is it reasonable to assume the base two numbers have all had P-1 done at least to the Prime95 limit B1=4.29e9?
Paul Zimmermann and/or Alex Kruppa have done a lot of P-1 and P+1 on the Cunningham tables. I don't have figures to hand, but I know Alex posts here on occasion.

Paul
xilman is offline   Reply With Quote
Old 2004-05-05, 11:04   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Most of the P-1 and all of the P+1 I've done myself was either on Fibonacci-/Lucasnumbers which Blair Kelly keeps track of on his web site, or mostly on Cunninghams before factoring them with NFS.

AFAIK Paul Zimmermann and Torbjorn Granlund have done a lot of P-1 and P+1 on Cunningham numbers, Torbjorn on base 10 numbers and Paul on other bases afaik. Paul recently told me in an email:

Quote:
Originally Posted by Paul Zimmermann
I'm testing all (regular) Cunningham composites (1173 currently) by
increasing size. For P-1, I've finished a complete run at B1=1e9, and
I'm doing a 2nd one at B1=4e9, currently at 151 digits.

Another machine is doing a P+1 test (3 curves each) at B1=1e9, and is currently
at 190 digits.
Base 2 numbers may already have been tested to higher bounds than that with Prime95, George Woltman would probably be the one who keeps track of the effort.

Alex
akruppa is offline   Reply With Quote
Old 2004-05-05, 13:34   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by akruppa
Most of the P-1 and all of the P+1 I've done myself was either on Fibonacci-/Lucasnumbers which Blair Kelly keeps track of on his web site, or mostly on Cunninghams before factoring them with NFS.

AFAIK Paul Zimmermann and Torbjorn Granlund have done a lot of P-1 and P+1 on Cunningham numbers, Torbjorn on base 10 numbers and Paul on other bases afaik. Paul recently told me in an email:



Base 2 numbers may already have been tested to higher bounds than that with Prime95, George Woltman would probably be the one who keeps track of the effort.

Alex
Back about 15 years ago I ran P-1 on all Cunningham base 2 numbers. I
used a lower B1 limit (10^7), with a much higher B2 limit (10^13). I was
testing out my FFT implementation of Step 2 on an Alliant FX8 using 4 of
its 68020 processors. I also ran the smaller unfactored Fermat numbers.
R.D. Silverman is offline   Reply With Quote
Old 2004-05-05, 18:41   #5
Wolf
 
Wolf's Avatar
 
Jul 2003
UK

3316 Posts
Default

Quote:
Originally Posted by geoff
Is it reasonable to assume the base two numbers have all had P-1 done at least to the Prime95 limit B1=4.29e9?
Yes

According to PMINUS1.TXT (see bottom of the page of http://www.mersenne.org/status.htm) all base two numbers <10000 (those with no known factor anyway) have been tested to B1=4.29E9
Wolf is offline   Reply With Quote
Old 2004-05-07, 08:14   #6
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Thanks for the information, I don't think I will do any P-1 or P+1 on the Cunningham numbers at this time, but just continue with ECM.
geoff is offline   Reply With Quote
Old 2004-05-07, 08:36   #7
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Another thought about P-1 testing:

Say I was to do a very large P-1 stage one, say on M(2^19) with B1=4.29e9 which would take me about 2 months. If the test finished and the final GCD found all the expected known factors (those known P where the largest factor of P-1 is less than 4.29e9) would that be a good enough check that no error had occured during the test, or is there some way that an incorrect residue could still lead to the known factors being found?
geoff is offline   Reply With Quote
Old 2004-05-10, 15:45   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

Yes, that would be a very powerful check to ensure that the residue did not get corrupted during the computation. In fact, it should suffice to leave one resonably sized (and smooth enough) prime factor out of low[mp].txt and check that that one is found.

A factor p is found in stage 1 if the order of the starting element of P-1 has only prime factors that are included in stage 1, i.e. that are <=B1. If an error occurs somewhere during the computation, we can look at it as another P-1 factoring attempt with a random starting element which gets exponentiated by the stage 1 primes remaining at that point. So if the error occurs while we are processing the prime q, the factor will still be found if the corrupted residue happens to be a k-th power where k is the product of all prime factors of p-1 smaller than q. The probability of a random residue being such a power is 1/k. So unless the error occurs right at the start of the computation, k will usually be large enough to make an "accidental" discovery of p in spite of the error very unlikely.

Alex

Last fiddled with by akruppa on 2004-05-10 at 15:45
akruppa is offline   Reply With Quote
Old 2004-05-10, 23:13   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

2×13×43 Posts
Default

Actually, I have had apparent errors doing P-1 on large, highly composite exponents, most recently on M9699690. For example, in October 2003 (this was with version 23.4.1) I ran stage 1 to a bound of B1=2000 and stage 2 to B2=200,000. (I found a number of factors at the same time which I then factored using Dario Alpern's Java applet.) But then I ran stage 1 to B1=100,000 and found the following two factors:
320731441801 = 2^3 * 3 * 5^2 * 7 * 11 * 17 * 19 * 21493 + 1
119609902307611 = 2 * 3^2 * 5 * 11 * 13 * 17^2 * 19 * 59 * 28687 + 1
My question is, why didn't these factors show up earlier when I ran stage 2 to 200,000?
Then again, I continued running stage 2 to B2=10,000,000 and turned up:
150747052048811 = 2 * 5 * 7 * 17 * 19 * 307 * 509 * 42667 + 1
So why did this factor only turn up at the end of stage 2 when it seems like it should have turned up at the end of stage 1? I've had this on the to-do list for quite awhile without getting to it, but since factors have been missed in both stage 1 and stage 2, I have wondered if it could be a GCD problem instead.
This particular exponent requires a lowm.txt file of over 400 entries, so perhaps it isn't a problem that normally arises with typical (prime) exponents, but I have been wondering about it. In which case, geoff's testing idea might be a good one.
philmoore is offline   Reply With Quote
Old 2004-05-11, 09:28   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

The factor
M( 19427 )C: 53089736370439
which is 1 (mod 28687) is not being found with B1=2000, B2=200000, either. I didn't find another good test case that's 1 (mod 21493).

It looks almost as if Prime95 skipped a few primes in stage 2. Which ones apparantly depends on the choice of B2 and perhaps B1. Maybe this has something to do with the new duplication-preventing code that was introduced in, afaik, v23. It does pairing of primes similar as described in Montgomery's "Speeding" paper, but also cancels smaller primes p if p|(mD+d) where mD-d is a prime included in stage 2. Perhaps it cancels those small primes a little too eagerly, i.e. even in cases where (mD+-D) ends up not being included in stage 2 after all.

It not too many primes are skipped this way, it's probably not a big deal, but it is unfortunate that smallish primes are lost which have a good probability of dividing the group order.

Alex
akruppa is offline   Reply With Quote
Old 2004-05-11, 21:57   #11
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1C9316 Posts
Default

Quote:
Originally Posted by akruppa
The factor
M( 19427 )C: 53089736370439
which is 1 (mod 28687) is not being found with B1=2000, B2=200000, either. I didn't find another good test case that's 1 (mod 21493).
Input an integer =? 53089736370438
2 * 3 * 15877 * 19427 * 28687

P-1 shouldn't find that factor with B1=2000
Prime95 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor not recorded by GPU72 bayanne GPU to 72 24 2014-05-16 09:20
Problem: results not recorded Unregistered Information & Answers 6 2012-04-18 02:54
PrimeNet has composite factors recorded James Heinrich PrimeNet 4 2011-09-16 14:40
Results not recorded? Yura Information & Answers 8 2010-05-26 21:06
Researchers Play Tune Recorded Before Edison ewmayer Science & Technology 18 2008-04-03 10:35

All times are UTC. The time now is 11:34.

Mon Jan 25 11:34:40 UTC 2021 up 53 days, 7:45, 0 users, load averages: 2.88, 2.69, 2.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.