George Woltman wrote:
At 10:31 PM 12/3/2002 +0000, Daran wrote:
Peter Montgomery's dissertation, "An FFT Extension to the Elliptic Curve Method of Factorization", ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz ,The analysis is more complex than this. It really depends on the prime [...] I'd be greatly interested in such a study.
contains in chapter 5 an analysis of Suyama's powers and Dickson polynomials for the Brent-Suyama extension to stage 2.
The number of algebraic factors in the Suyama/Dickson polynomial is the interesting part, i.e.
(x^6-y^6) = (x-y)*(x+y)*(x^2+x*y+y^2)*(x^2-y*x+y^2)
where (x-y) and (x+y) usually are both <=B2, so primes >B2 have two opportunities of appearing as prime factors of algebraic factors of the Suyama polynomial. If we assume that the values taken on by the algebraic factors of the poly behave like integers chosen uniformly at random, we could conclude that a prime p>B2 appears in (x^6-y^6) with probability 1-(1-1/p)^2 ~= 2/p.
However, primitive factors of x^n-y^n must be ==1 (mod n) and so the factors do not behave particularly randomly at all. Primes p where p-1 has many factors in common with n have a better chance of appearing as factors, while those with p-1 coprime to n can only appear as factor of (x+y)(x-y) and are thus p<=B2. This causes "clumping" of primes included by Suyama's powers (some primes appearing often, others not at all) and reduces their efficiency. Apparantly Dickson polynomials do better, but I don't really know much about them.
Montgomery's dissertation is probably a very good starting point if someone would like to investigate the optimal choice for Suyama's powers (or Dickson polynomials) for Prime95.
Alex
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
