mersenneforum.org P-1
 Register FAQ Search Today's Posts Mark Forums Read

 2004-06-25, 23:20 #1 Citrix     Jun 2003 32×52×7 Posts P-1 Just need some clarification, Is this quote wrong. "There is an enhancement to Pollard's algorithm called stage 2 that uses a second bound, B2. Stage 2 will find the factor q if k has just one factor between B1 and B2 and all remaining factors are below B1." Taken from http://www.mersenne.org/math.htm Let me know! Thanks, Citrix
 2004-06-26, 03:12 #2 Axel Fox     May 2003 25·3 Posts Nope, that sounds about right. First stage only uses B1 and all factors of k have to be below B1. Stage two is a little more general and allows for 1 of the factors of k to be above B1, but still below a second bound (B2). Greets, Axel Fox.
 2004-06-26, 03:38 #3 Citrix     Jun 2003 32·52·7 Posts Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's. Citrix Last fiddled with by Citrix on 2004-06-26 at 03:39
2004-06-26, 03:58   #4
Citrix

Jun 2003

32×52×7 Posts

Quote:
 Originally Posted by Citrix Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's.

146420587 |79309*2^513-1

Found this uisng a program I wrote.
b1=25 and b2=1000.

I think this prooves my point.

Citrix

Last fiddled with by Citrix on 2004-06-26 at 03:59

 2004-06-26, 04:51 #5 axn     Jun 2003 22×5×239 Posts Can you post your program here?
 2004-06-26, 05:01 #6 Citrix     Jun 2003 32·52·7 Posts Here you go. It is very basic. The routines are primitive etc. Don't try very large numbers. The file is 183 KB, it won't let me upload it. If you PM me your email, I can send it to you or better yet I can test and print the results for you. Citrix
 2004-06-26, 06:49 #7 akruppa     "Nancy" Aug 2002 Alexandria 9A016 Posts There are at least three effects how P-1 can occasionally find factors that are not B1,B2 smooth. Say p-1 has two factors >B1, r and s. - The starting element of P-1 could already be an r-th or s-th power (mod p). Then there is no need to exponentiate by r for P-1 to find p. The probability of a random residue being an r-th power (mod p) is 1/r if r|p-1 so this wont happen often for large r. For example, the smallest starting values that are a 127-th power (mod 146420587) are 89, 149, 219, 554... - The implementation of P-1 might exponentiate by N-1 at the start of stage 1. This is useful if there is some k that divides p-1 for every prime factor p of N because is includes k as a stage 1 exponent, without having to know what the actual value of k is. But this is not what happened here, neither 127 nor 379 divide 79309*2^513-2. - The r and s may be included by the Brent-Suyama extension. If t is the order of the end-of-stage-1 residue, the factor p will be found if t|f(l)-f(m). Here f() is the Brent-Suyama function (usually just a power) and l and m are usually chosen so that all primes >B1, <=B2 are included. It's possible that a composite t divides one such value, but is again not too likely to happen. Whether that's why the factor was found requires knowing which function f() the implenentation uses and how it generates the l and m values. Alex Last fiddled with by akruppa on 2004-06-26 at 06:50
 2004-06-26, 06:53 #8 Citrix     Jun 2003 32·52·7 Posts My program used base 3 to start with. Also p-1= 2 x 3 ^ 2 x 13 ^ 2 x 127 x 379 All factors found by my program irrespective of the base fall in the same category. Citrix Last fiddled with by Citrix on 2004-06-26 at 06:55