----- Original Message ----- From: "Alexander Kruppa" <[EMAIL PROTECTED]> To: "George Woltman" <[EMAIL PROTECTED]> Cc: "Daran" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Thursday, December 05, 2002 12:18 PM Subject: Re: Mersenne: P-1 and non k-smooth factors
> George Woltman wrote: > > At 10:31 PM 12/3/2002 +0000, Daran wrote: > > > > > The analysis is more complex than this. It really depends on the prime > > [...] > > I'd be greatly interested in such a study. > > Peter Montgomery's dissertation, "An FFT Extension to the Elliptic Curve > Method of Factorization", > ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz , What do I need to read a psl file? > 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. That was the conclusion I came to. > (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. In addition to the remarks you go on to make, this will only be true for primes << the algebraic factor; intuitively I feel it ought only to be true for primes < sqrt(factor) ~= x (in the case of x^6-y^6). All these will be < B2. > However, primitive factors of x^n-y^n must be ==1 (mod n) and so the > factors do not behave particularly randomly at all... This doesn't make sense. Any primitive factor f of x^n-y^n is a primitive factor of x^(kn)-y^(kn) for any k, so the above would imply that f==1 (mod kn) for any k. What am I missing? > 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... Hence E should be chosen to be highly composite, which conclusion I had already come to, from consideration of the number of algebraic factors. > This causes "clumping" of primes included > by Suyama's powers (some primes appearing often, others not at all) and > reduces their efficiency... Could we use this somehow? Would it be worth skipping primes in the B1-B2 range that were highly likely to crop up in a Suyama power? > ...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. As soon as I can figure out how to read it. > Alex Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
