Hi Brian,
At 06:41 AM 7/22/00 +0000, Brian J. Beesley wrote:
>Hi guys,
>
>I found the following in my results.txt file:
>
>[Sat Jul 22 01:50:43 2000]
>P-1 found a factor in stage #2, B1=1000000, B2=25000000.
>UID: beejaybee/Simon2, M131437 has a factor: 603794102057268841
>
>The interesting thing here is that the prime factorization of P-1
>(603794102057268840) is 2^3.3^2.5.57.131437.344879201 i.e. the
>largest prime factor of P-1 is greater than B2 and I'm therefore
>unable to understand why P-1 managed to find the factor.
>
>Could someone please enlighten me?
If there is enough memory available (and there often is when running
P-1 on "small" Mersenne numbers), then prime95 uses Suyama's
improvement for stage 2. Paul Zimmermann introduced me to this.
I've excerpted his email below.
In practice, it is rare that this improvement finds a factor that an
ordinary stage 2 would miss.
Regards,
George
you were looking for improvements in phase 2. Here is one which improves
the efficiency of phase 2, with about the same memory and time used. It is
a slight modification of the birthday paradox continuation improvement
suggested by Suyama [see section 3.3 from Richard's paper].
Currently our phase 2 computes some points tQ and sQ (where Q is the point
computed at the end of phase 1), and tries all combinations x_t-x_s for
t-s<=B2 and prime.
Now, for each s and t, compute t^eQ and s^eQ instead for some small integer
e, and try all combinations x_{t^e}-x_{s^e} for t-s<=B2 and prime. The
overhead will be the computation of t^eQ and s^eQ from tQ and sQ, i.e. about
2*e*sqrt(B2) multiplications of points by a O(B2) scalar. Compared to phase
1 which performs O(B1/log(B1)) multiplications of points by a O(B1) scalar,
the overhead remains small when 20*e*log(B1) is small wrt sqrt(B1).
The advantage is that now phase 2 will succeed not only if the largest factor
of the group order is of the form t-s, but whenever it divides t^e-s^e
for some t,s. This improves the number of possibilities, especially when
t^e-s^e has many factors:
>> Factor(t^48-s^48);
2 2 4 4 8 8 2 2
- (s + t) (s - t) (s + t ) (s + t ) (s + t ) (s t + s + t )
2 2 4 4 2 2 8 8 4 4 16 16 8 8
(s - s t + t ) (s + t - s t ) (s + t - s t ) (s + t - s t )
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
