Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, December 11, 2002 12:11 PM Subject: Re: Mersenne: P-1 and non k-smooth factors Daran wrote: Ad far as I can see it is a regular PostScript. I don't know if the extra l indicates a variant of the format, but the file behaves normally in ghostscript/when printing. OK I can read it now. Understanding it is another matter entirely. 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? A prime factor of x^n-y^n is called primitive if it divides no x^m-y^m with 0mn. And thus, with x and y distinct (mod p) and neither a multiple of p, Right. I was confusing 'primitive' with 'irreducible'. BTW, I don't think I've thanked you enough for your earlier replies on this subject, which have contributed enormously to my understanding of the problem. [snip lengthy analysis which I will need to study] 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? Yes, or compute which ones do actually apprear and eliminate them from the stage 2 primes... I was under the impression that this might be too expensive. ...Another idea is to exclude from stage 2 those primes that appear as factors of (x+y). For D=2310 and B2/B1=100, primes between 13 and 97 may divide (x+y) so that the cofactor is a prime in the stage 2 interval. That requires a bitfield of all the stage 2 primes that must be processed top down which makes getting the prime pairing right more difficult. I tried that once in my own P-1 factorer but it had a bug that I didn't find yet. The saving was iirc ~10% of the multiplies in stage 2. In my experience the program chooses B2 10-20 times the size of B1. All this can be generalised. The goal is to choose a subset of NxN (pairs of positive integers) so that the efficiency is maximal for the factor we hope to find. Of course we won't know the precise factor we want to find, but we can integrate over all remaining candidate factor weighted with their respective probability of dividing the input number. I love this idea! An simple algorithm would be to take all the pairs (x,y) with x=mD for a hightly composite D and yD, gcd(y,D)=1 (as in the current stage 2, but not only pairs where x-y is a prime), factoring all the x^n-y^n over primes B1 (and below some other bound)... Call this other bound C. ...and making a bipartite graph of (x,y) pairs connected with their factors. A greedy algorithm would choose the best (x,y) pair (i.e. where the sum of reciprocals of the connected prime factors maximal) and remove those prime factors and their edges from the graph. Repeat until the best remaining (x,y) pair is worse that some chosen limit. Call this limit epsilon. This assumes that each (x,y) pair costs the same, but in fact, there is a cost associated with increasing x. I doubt that the greedy algo is optimal, but it should be pretty fast, except for the factoring part maybe. I'm certain it wouldn't be. For a start, if you don't take this extra cost into account, and you choose C too high, then your largest x may be much higher than is desirable. If you do take the extra cost into account, by attaching it to each x larger than any previous x, then you'll tend to fill up your bit array from the bottom, and lose much of the benefit of the smaller factors of the larger candidates. Better would be to use a two-pass greedy algorithm. The first using a very large C 1/epsilon, but including the extra cost of large x. Use the result of this to reset C to be just large enough to accommodate the largest x, then redo the algorithm ignoring that extra cost. You might be able to improve it further by choosing a slightly larger C for the second pass, than the one suggested by the first, or you could implement a multipass algorithm as follows:- Choose limits C 1/epsilon and B2 initially equal to B1. Then for each pass, factor in the extra cost only for those x (larger than any previous x) which are also larger than B2. Use the result of each pass to reset B2 to accommodate the largest x. The result should be independent of C, provided the latter is large enough. I doubt that this would be optimal, even if iterated to equilibrium. The problem bears the hallmarks of computational intractability. The so created plan can be stored and distribued to factoring clients. You mean the bitmap of (x,y) pairs? You'd need
Re: Mersenne: P-1 and non k-smooth factors
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 ,
What do I need to read a psl file?
Ad far as I can see it is a regular PostScript. I don't know if the
extra l indicates a variant of the format, but the file behaves
normally in ghostscript/when printing.
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?
A prime factor of x^n-y^n is called primitive if it divides no x^m-y^m
with 0mn. And thus, with x and y distinct (mod p) and neither a
multiple of p,
x^n-y^n == 0 (mod p)
x^n == y^n (mod p)
(x/y)^n == 1 (mod p)
Since p is a primitive factor, ord(x/y) = n and n|p-1.
The probability that p|(x^n-y^n) is gcd(n, p-1)/(p-1) if x and y are
chosen independently at random from the residues != 0 (mod p).
Choose some value for x and let y range over all the possible residues
(mod p). x^n and y^n both go into the subgroup of d-th powers (mod p)
where d=gcd(n, p-1) and the order of that subgroup is (p-1)/d. As y
ranges over all the possible residues (mod p), y^n visits every element
in the subgroup d times and so has d matches with x^n. For a randomly
chosen y the chance of a match x^n==y^n is d/(p-1), independent of x.
If we compute k different values of x^n-y^n in stage 2, the probability
of the prime p showing up at least once as a factor among them should be
1-(1-gcd(n, p-1)/(p-1))^k.
However, in the P-1 stage 2 we don't choose x and y at random from all
the possible residues (mod p). We want the analysis for primes B2, and
x=mD B2 and yD. How this changes the analysis is not quite clear to
me.. at least the probability that the linear factors generate p should
be subtracted as we know that their values are p. That gives a
probability of 1-(1-(gcd(n, p-1)-2)/(p-1))^k for odd n. As you pointed
out, the values of the other small terms may not be large enough to
justify a probability of 1/p for p dividing them, but I think the
difference will not be very great.
I have hacked up a small program to determine which primes (within a
given interval) appear as factors of (mD)^n-d^n for mDB2, gcd(d,D)=1
and given n, and the counts come out reasonably close to the predicted
values. I.e. for D=2310, B2=100 and n=4, examining primes in
[1005000, 200] (only the x^2+y^2 term can produce these primes), I
get 9829 distinct primes that appear as factors vs an predicted 8737.26.
The sum of reciprocals of the primes that appear as factors is 0.007096,
vs predicted 0.006270. Curiously, the actual counts are higher than the
predicted values.
For B1=10, D=2310, n=4 and p in [1000, 11000], the number of
primes that appear as factors is 2880 vs 2926.47 and the sum of
reciprocals is 0.000111 vs predicted 0.000114.
For B2=10, D=2310, n=6, primes in [1000, 11000], I get 5720
distinct primes as factors vs 5847.96 predicted, sum of reciprocals
0.000227 vs 0.000227. The predicted values seem to become more accurate
for larger n and p.
These figures seem to support the gcd-2 idea, but I'd feel better if
there were some theoretical grounds to it.
If we accept this estimate, the total chance of finding a factor f for
P-1 with B1 and B2 bounds, Suyama's power n and k distinct (x^n-y^n)
values computed in stage 2 comes out like
Pr[f-1 is B1-smooth] + (1 - Pr[f-1 is B1-smooth]) * Sum_{pB1} 1/p *
Pr[p included] * Pr[(f-1)/p, Stage1]
where Pr[p included] is 1 for p=B2 and 1-(1-(gcd(n, p-1)-2)/(p-1))^k
for pB2.
The goal would then be to maximize the efficiency
(Pr[hit in stage 1] + Pr[hit in stage 2]) / (time for stage 1 + Pr[no
hit in stage 1] * time for stage2 ).
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?
Yes, or compute which ones do actually apprear and eliminate them from
the stage 2 primes. Another idea is to exclude from stage 2 those primes
that appear as factors of (x+y). For D=2310 and B2/B1=100, primes
between 13 and 97 may divide (x+y) so that the cofactor is a prime in
the stage 2 interval. That requires a bitfield of all the stage 2 primes
that must be processed top down which makes getting the prime pairing
right more difficult. I tried that once in my own P-1 factorer but it
had a bug that I
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
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 , 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 pB2 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
Re: Mersenne: P-1 and non k-smooth factors
On Wednesday 04 December 2002 21:46, Daran wrote: [... snip ...] ...though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be... I agree. My tests have been limited to exponents in the 8.1M range, for no particular reason than those are the ones I am doing. Well, you seem to have more experimental evidence than anyone else. As for the theory - whilst there is adequate theoretical modelling of the expected distributions of the largest and second-largest factors of arbitary numbers, I couldn't find much in the literature which would help predict how many extra factors you would expect to find with different values of E. 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. 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). Since, on my practical experience, a 17M exponent will quite happily use ~ 800 MBytes in P-1 stage 2, the 32 bit address bus may well be a limiting factor within the exponent range covered by current versions of Prime95/mprime. George - is there a sanity check on the memory constraints? If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. I was under the impression the ECM was only practical for small exponents well below the current DC range. ECM stage 2 quickly becomes impractical with larger exponents because of the memory requirement. ECM stage 1 is not particularly heavy on memory. Running stage 1 only with small limits on DC sized exponents is feasible ... it's just a question of whether the extra computation costs would be justified by the discovery of factors which were inaccessible to trial factoring or P-1. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. It's the only sample I have. I'm trying to increase it by doing some P-1s on exponents in the 1.2M range which have only been tested to B1=B2=1000. How many of these were found during stage 2? (If half your factors were found during P-1 stage 2, and half of those used E=4 or greater, then your single 'surprising' factor would not be out of line with my two.) Well, actually I was doing the test in several steps, with gradually increasing B1 then gradually increasing B2 - the cost of the GCDs with small exponents is very small so it's worth checking fairly frequently to see if a factor is available. I don't have the full data to hand but I do have some of it. The distribution of 22 factors found at various limits was as follows: stage 1 B1 = 50 1 stage 1 B1 = 100 1 stage 2 B1 = 100 B2 = 4004 stage 2 B1 = 100 B2 = 1000 5 stage 2 B1 = 100 B2 = 2500 11 Some easier factors were in all probability missed because someone had found them by running P-1 with smaller limits before I started. I have a total of 57 factors, including one found earlier today. A few were by TFs, 30 in P-1 stage 2 (including today's) and the rest in stage 1. OK. Actually for about the last three weeks I've been running P-1 with standard limits on some exponents in the range 2M-6M (those exponents where all the entries in lucas_v have the same user ID, with the exception of a very few where P-1 was already completed to reasonable limits). The system I'm using is configured with mem=224 MBytes (about as much as I dare on a 512 MBytes dual-processor system). I'm getting E=4 logged fairly consistently. The results so far are: No factor found, 130 Factor found in stage 1, 2 Factor found in stage 2, 6 - all smooth to B limits used. One of the factors found in stage 1 is _very_ interesting: 6807510023694431 is a factor of M(5993719) (smooth to B1=353) The factoring depth database had this trial factored
RE: Mersenne: P-1 and non k-smooth factors
From: Brian J. Beesley [mailto:[EMAIL PROTECTED]] 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). FWIW, WinNT and its descendents can be booted with /3gb in boot.ini, whereupon a single process may use up to 3G of physical memory. This switch tends to be used mainly on big SQL server boxes but I found it necessary when running very large filtering and linear algebra jobs for NFS factorizations. For this I needed a very large chunk (1Gb) of *contiguous* virtual memory and although the standard boot mode would let me have up to 2G of VM, system DLLs were loaded somewhere near the 1G region, thereby fragmenting memory. Booting with /3gb placed the OS well out of the way and let me have the space I needed. Paul _ 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
Isn't this (3GB user mode) only supported on Windows NT Advanced Server? (which is probably free for you to use but for everyone else costs the same as a new car!) If it isn't then I've encountered some people who will wish they'd have known about this a long time ago :-) Paul Leyland wrote: From: Brian J. Beesley [mailto:[EMAIL PROTECTED]] 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). FWIW, WinNT and its descendents can be booted with /3gb in boot.ini, whereupon a single process may use up to 3G of physical memory. This switch tends to be used mainly on big SQL server boxes but I found it necessary when running very large filtering and linear algebra jobs for NFS factorizations. For this I needed a very large chunk (1Gb) of *contiguous* virtual memory and although the standard boot mode would let me have up to 2G of VM, system DLLs were loaded somewhere near the 1G region, thereby fragmenting memory. Booting with /3gb placed the OS well out of the way and let me have the space I needed. -- === Gareth Randall === _ 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
Do not add the /3GB switch if you are running Windows 2000 Server, Microsoft Small Business Server 2000, or Microsoft BackOffice Server 2000. This switch is designed for use only with Windows 2000 Advanced Server and above. (from the MS knowledge base). Same applies to NT 4, where it only works with the Enterprise edition. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Gareth Randall Sent: Thursday, December 05, 2002 2:25 PM To: Paul Leyland Cc: Brian J. Beesley; Daran; [EMAIL PROTECTED] Subject: Re: Mersenne: P-1 and non k-smooth factors Isn't this (3GB user mode) only supported on Windows NT Advanced Server? (which is probably free for you to use but for everyone else costs the same as a new car!) If it isn't then I've encountered some people who will wish they'd have known about this a long time ago :-) _ 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
On Tuesday 03 December 2002 22:31, Daran wrote: [... snip ...] For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) I can't think of any reason why either of the two algebraic factors of C when E is 6 should be any better or worse than the single irreducible factor when E=4. And there are two of them. This suggests to me that E=6 should be about twice as effective as E=4 in providing additional factors, at about twice the cost (over and above the 'cost' of E=2). If this is correct, then it will always be worth going to E=6, whenever it is worth going to E=4, (provided there is sufficient memory to do so). Let's see if I get this right. Overwhelmingly, the factors produced by P-1 factoring come out because they are smooth to the limits selected. The fraction that comes out because of the extension is 10%. To double that fraction (i.e. to increase the total number of factors found by 10%) we have to double the stage 2 run time? Doesn't sound that great to me, even without worrying about memory considerations. If we're talking about the _extra_ computation time in stage 2 then obviously the suggestion makes a lot more sense - though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be (as opposed to a rather simplistic linear model, which fails to take into account that some of the temporaries needed for small E probably drop out pretty well for free). If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. Some time ago I found a considerable number of first factors for exponents in the range 100,000-150,000 using P-1 with limits up to B1=10^6, B2=25x10^6. The results.txt file doesn't record the E value used; though I did have tons of memory available (in relation to the exponent size) and seem to remember something about wondering what E=12 meant in the console output. Or maybe I'm confusing this with recollections about running ECM? My records show 67 factors found; I mailed George on one occasion because P-1 found a factor which surprised me, but I don't think it happened twice. Incidentally I found a factor only yesterday using P-1 on a production system: [Tue Dec 3 07:54:38 2002] P-1 found a factor in stage #2, B1=22, B2=5665000. UID: beejaybee/Procyon, M17359099 has a factor: 312980494172935109497751 Again no mention of E. If it helps, this system was set up to use 384 MBytes memory. In any case this should have come out without extensions; B1=65267 B2=3077953 is sufficient to find the factor with the standard stage 2 algorithm. Would there be any means of retrieving actual factors found using P-1 and the E values used from the server logs? The problem otherwise is that, so far as the database is concerned, once a factor is found, nobody cares much how! Regards Brian Beesley _ 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: Wednesday, December 04, 2002 2:55 PM Subject: Re: Mersenne: P-1 and non k-smooth factors Let's see if I get this right. Overwhelmingly, the factors produced by P-1 factoring come out because they are smooth to the limits selected. The fraction that comes out because of the extension is 10%. To double that fraction (i.e. to increase the total number of factors found by 10%) we have to double the stage 2 run time? That's not what I meant. Doesn't sound that great to me, even without worrying about memory considerations. If we're talking about the _extra_ computation time in stage 2 then obviously the suggestion makes a lot more sense - Yes. If it takes Time t to run a stage 2 with E=2, and t+d to run it with E=4, then we should be willing to spend t+2d to run it with E=6, and t+5d to run it with E=12, which, as far as I can see, is approximately how the cost increases anyway. I've only had time to run a few tests, but 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) 42012 121520 210 4 104272 150 4 111962 120 4 116464 I did one with D=420, E=6, but I don't seem to have made a note of it. Nor did I record running times, because I was using the computer to do other things. Transforms ought to be reasonably proportionate. The first three tests are consistent with the cost increasing linearly with E, while the latter show the penalty of lowering the memory. (Note that an unmodified client would drop to E=2 below D=210, but I wanted to see just the effect of lowering D) With D=420, E=12 is over 23% dearer than the E=4 which is currently used. However, this does *not* mean that it needs to find more 23% more factors to be worthwhile. If guess_pminus1_bounds is altered to be aware of D and E, then it compensates for the extra cost by reducing B2, trading 'normal' factors for extended ones. My (limited) tests suggest, as I said, that 2% more factors with E=6 or 10% more factors with E=12 would be a worthwhile trade. (This assumes that my formula for estimating the number of squarings is accurate, something I have not checked.) ...though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be... I agree. My tests have been limited to exponents in the 8.1M range, for no particular reason than those are the ones I am doing. (as opposed to a rather simplistic linear model, which fails to take into account that some of the temporaries needed for small E probably drop out pretty well for free). I don't understand. If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. I was under the impression the ECM was only practical for small exponents well below the current DC range. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. It's the only sample I have. I'm trying to increase it by doing some P-1s on exponents in the 1.2M range which have only been tested to B1=B2=1000. Some time ago I found a considerable number of first factors for exponents in the range 100,000-150,000 using P-1 with limits up to B1=10^6, B2=25x10^6. The results.txt file doesn't record the E value used; though I did have tons of memory available (in relation to the exponent size) and seem to remember something about wondering what E=12 meant in the console output. Or maybe I'm confusing this with recollections about running ECM? That's possible as E is also used in the ECM code. But E=12 output from a P-1 means what it says. If the value of E is not output, then it means E=2 (or perhaps E=1, but I've never tried using that little memory.) E (2) is recorded in the results.txt file by recent clients, so either the version of the client you were using then didn't record it, or your memory setting didn't allow E2. My records show 67 factors found; I mailed George on one occasion because P-1 found a factor which surprised me, but I don't think it happened twice. How many of these were found during stage 2? (If half your factors were found during
Re: Mersenne: P-1 and non k-smooth factors
At 10:31 PM 12/3/2002 +, Daran wrote: For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) The analysis is more complex than this. It really depends on the prime factorization of these algebraic factors. If an algebraic factor's prime factorization contains factors all below B2, then the algebraic factor does you no good. 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) 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). Then you can run this on several D,E options and compare it to your count of FFT transforms and come up with the optimal choice of D and E. I'd be greatly interested in such a study. _ 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, November 28, 2002 2:18 AM Subject: Re: Mersenne: P-1 and non k-smooth factors At 06:05 PM 11/27/2002 +, Daran wrote: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? No good reason. As far as I know, there haven't been any studies on the best values to choose for E. For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) I can't think of any reason why either of the two algebraic factors of C when E is 6 should be any better or worse than the single irreducible factor when E=4. And there are two of them. This suggests to me that E=6 should be about twice as effective as E=4 in providing additional factors, at about twice the cost (over and above the 'cost' of E=2). If this is correct, then it will always be worth going to E=6, whenever it is worth going to E=4, (provided there is sufficient memory to do so). Turning to E=8 it is tempting to make a similar argument, that (x^4 + d^4) should be about as good as (x^4 + x^2d^2 + d^4). If so then E=8 would be three times as good as E=4 at about three times the cost. However this ignores the fact that (x^4 + d^4) is irreducible, and therefore likely to have one very large factor, (which would not be much use to us) and fewer smaller ones. OTOH an irreducible factor of order four will be better than any single factor of order two. I therefore (tentatively) conclude that E=8 will be better than twice as good as E=4, but not three times as good. With E=10, the situation is even worse. C = (x^8 + x^6d^2 + x^4d^4 + x^2d^6 + d^8), which (I think) is irreducible. It is possible that E=10 may be less effective than E=8 or even E=6. Things improve with E=12. C = (x^2 + d^2)*(x^2 + xd + d^2)*(x^2 - xd + d^2)*(x^4 - x^2d^2 + d^4) i.e. we get every extra factor produced by E=4 and E=6 and then some more, suggesting that E=12 is between four and five times as effective as E=4 at about five times the cost. In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. I freely admit this analysis is simplistic and lacks rigour. Perhaps some of the number theorists on the list could improve upon it. Regards 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: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, September 25, 2002 12:03 AM Subject: Re: Mersenne: P-1 and non k-smooth factors This is the Brent-Suyama extension, aka Suyama's powers. In short, if you choose a Suyama's power E, a factor f will be found if the largest factor of f-1 divides some (mD)^E - d^E, where D is an integer chosen according to available memory, m and d are integers so that B1 mD-d = B2, 1 = d D and mD-d is prime. [...] ...the choice of D and E depends on the implementation. Prime95 chooses D so that phi(D)+E+4 (phi() is Euler's totient function) residues fit into memory, and chooses E like this: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; (see ecm.c, choose_pminus1_plan() ) I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? 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
At 06:05 PM 11/27/2002 +, Daran wrote: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? No good reason. As far as I know, there haven't been any studies on the best values to choose for E. _ 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: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, September 25, 2002 1:03 AM Subject: Re: Mersenne: P-1 and non k-smooth factors This is the Brent-Suyama extension, aka Suyama's powers. In short, if you choose a Suyama's power E, a factor f will be found if the largest factor of f-1 divides some (mD)^E - d^E, where D is an integer chosen according to available memory, m and d are integers so that B1 mD-d = B2, 1 = d D and mD-d is prime. Right. And (mD)^E - d^E has mD-d as a factor, which yields all the usual stage 2 factors, while the cofactor ((mD)^E - d^e) / (mD-d) possibly introduces new ones. Thanks to everyone for their replies. Alex Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
