20040625, 23:20  #1 
Jun 2003
1,579 Posts 
P1
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 
20040626, 03:12  #2 
May 2003
140_{8} 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. 
20040626, 03:38  #3 
Jun 2003
11000101011_{2} 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 20040626 at 03:39 
20040626, 03:58  #4  
Jun 2003
62B_{16} Posts 
Quote:
146420587 79309*2^5131 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 20040626 at 03:59 

20040626, 04:51  #5 
Jun 2003
2^{3}·607 Posts 
Can you post your program here?

20040626, 05:01  #6 
Jun 2003
1,579 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 
20040626, 06:49  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
There are at least three effects how P1 can occasionally find factors that are not B1,B2 smooth. Say p1 has two factors >B1, r and s.
 The starting element of P1 could already be an rth or sth power (mod p). Then there is no need to exponentiate by r for P1 to find p. The probability of a random residue being an rth power (mod p) is 1/r if rp1 so this wont happen often for large r. For example, the smallest starting values that are a 127th power (mod 146420587) are 89, 149, 219, 554...  The implementation of P1 might exponentiate by N1 at the start of stage 1. This is useful if there is some k that divides p1 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^5132.  The r and s may be included by the BrentSuyama extension. If t is the order of the endofstage1 residue, the factor p will be found if tf(l)f(m). Here f() is the BrentSuyama 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 20040626 at 06:50 
20040626, 06:53  #8 
Jun 2003
11000101011_{2} Posts 
My program used base 3 to start with.
Also p1= 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 20040626 at 06:55 