----- 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 0<m<n. 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 y<D, 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 a different plan for each combination of B1, D, E, and epsilon. OTOH if you distributed tables of prime factors of Suyama's powers, then you'd need one for each combination of D and E. You could even have the client generate the tables it needs for just those values of D and E it's using. > Alex Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
