Re: Mersenne: P-1 and non k-smooth factors
- 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 +, 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 pB2 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
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, December 05, 2002 12:31 PM Subject: Re: Mersenne: P-1 and non k-smooth factors There is obviously a tradeoff here between increasing B2 and simplifying E and increasing E compensating for increased run time by lowering B2. However it does seem to be obvious that increasing E always has to be paid for in increased memory requirements. It's the larger values of D, rather than E which use the most memory. The client rarely uses all it's allowed, except in the low memory situations. For example, it needs 46 temps to run at D=150, E=2. If only 45 temps were available, the client, as currently configured, would run at D=120, E=2 using 38 temps. But it could afford to run at D=120, E=6 (42 temps) or even D=120, E=8 (44 temps), although, for reasons given, I don't think the latter would be a good idea. For exponents around 8M, this is not a particular issue. However there is a real, practical constraint so far as Prime95/mprime is concerned - the entire _virtual_ address space is limited to 4 GBytes by the 32 bit address bus, and the OS kernel claims some (usually half) of this, so that the total memory usable by a single process is limited to 2 GBytes. (There is a big memory variant of the linux kernel which expands this to 3 GBytes, but the point still stands). As mentioned by other list members, there's also a 64GB version, which, apparently, doesn't work. I expect they'll have it working by the time 4GB systems become commonplace. Since, on my practical experience, a 17M exponent will quite happily use ~ 800 MBytes in P-1 stage 2,... At 7186MB per temp, that sounds like a plan of D=420, E=4 (104 temps) ...the 32 bit address bus may well be a limiting factor within the exponent range covered by current versions of Prime95/mprime. Easily, even at 17M. To run with D=2310, E=12 requires 496 temps. It would go higher, if the memory was there. D is capped at sqrt(B2-B1). [...] What I was thinking of doing was writing a program to read in the factor database from, say, 1M up (to avoid any factors found by ECM), discard .any below the TF limit, then try to find the smallest B2 which would yield the factor given E=4, 6, 8, 10, or 12. This won't tell us the absolute frequency of extended factors, but the relative frequencies would test, and perhaps quantify, my conjecture about the relative effectiveness of these values. Why not simply use a random sample of numbers of suitable size? Say around 2^41, you are looking for factors from 2^65 upwards with exponents around 2^23. P-1 is really about the factors of k in f=2kp+1 since the +1 is implicit and the 2p comes out in the wash. (Does the size of the numbers in the sample actually matter from the theoretical point of view?) No, but if I use random numbers rather than genuine factors of Mersenne numbers, then the suspicion will be there that there's something special about the latter which invalidates the result. But it would probably be sensible to try this first. Regards Brian Beesley Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: George Woltman [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, December 05, 2002 2:35 AM Subject: Re: Mersenne: P-1 and non k-smooth factors The analysis is more complex than this... I never doubted that. :-) [...] Why not take your example: on an 8.1M exponent, B1=45000, B2=731250 and varying values for D and E, I get the following results D E Stage 2 transforms 420 2 93946 420 4 98618 (the default for my memory settings) Done one more: 420 6 103746 It's looking very linear. and write a program that emulates stage 2's selection of (x^E - d^E), does a prime factorization of the value, and keeps track of which factors above B2 get included. It should be possible to calculate your increased chance of finding a factor (someone please fill in the formula here). That's a rather more extensive programming job than the one I had in mind. It would also be expensive at runtime, with a prime factorisation in every cycle. What I was thinking of, is to take the k of known Mersenne factors, or at Brian's suggestion, random integers of an appropriate size, factor them to obtain the second largest and largest factor, a and b, say, then emulate the stage 2 selection of (x^E - d^E) from B1=a through to B2=b or until I find one divisible by b, which ever comes first. Regards Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
