P-1 factoring anyone?

[cheesehead]

Originally Posted by diep

I completely disagree with you here as it all has to do with the B1/B2.

That's what I mean by "within the B1/B2 search space".

Once you choose a B1 and B2, P-1 will find any factor that is of the form:

(Product of any number of prime factors or prime powers no greater than B1) * (a prime factor or prime power no greater than B2) + 1

In the case of Mersennes, prime95 also throws in the Mersenne exponent (n), so that it will find any factor of the form:

(Product of any number of prime factors or prime powers no greater than B1) * (a prime factor or prime power no greater than B2) * n + 1

That is deterministic, not probabilistic.

This because of the political wording you choose: " P-1 will always find a factor if that factor is within the B1/B2 search space."

It's simply factual. No politics involved. Perhaps my phrase "B1/B2 search space" is not clear enough for you.

The real problem is the selection of the B1/B2 to pick.

That's like saying that "the real problem in TF is selection of the upper bound. Shall we TF to 2^75 or to 2^76? "

If you TF to 2^75, you'll find any factor less than 2^75. If you subsequently TF from 2^75 to 2^76 will find any factor between 2^75 and 2^76.

The same is true of P-1, except that the B1/B2 search space is multidimensional, not the simple one-dimensional number line that TF searches.

If we compare this with a systematic search through all hills and valleys

... which is exactly what P-1 does.

then this is just a randomly behaving algorithm as it depends upon your initial random selection of a starting number.

No, it does not.

Because the algorithm is based on properties of a multiplicative group, it does not matter what the starting number (prime95 always uses 3) is, just as long as it is coprime with the number being factored.

As the Wikipedia article states,

... by working in the multiplicative group modulo a composite number N, we are also working in the multiplicative groups modulo all of N's factors.

With any coprime initial value a, the result of the exponentiation has the property that it is congruent to (a factor satisfying the above criteria) mod p, if such factor exists. 100% guaranteed. (Fermat's Little Theorem) No guessing or probability involved.

If you pick a constant then you will miss the entire other search space that is out there.

No, because the search space does not depend on the choice of a (as long as it's coprime ...). It depends only on B1/B2.

Each time you're just busy in a single valley trying to hillclimb a single mountain.

No, you are misunderstanding the multiplicative group property upon which P-1 is based. It's based on multiplication mod N, which cycles through all possible congruence classes 1, 2, 3, ... N-1 if N is prime. If N is composite, there are subsequences of prime lengths which divide N, and those lengths are found by the GCD.

Perhaps someone with a more practical understanding of multiplicative groups than my intuitive understanding can explain it better for you.

[diep]

Originally Posted by cheesehead

That's what I mean by "within the B1/B2 search space".

Once you choose a B1 and B2, P-1 will find any factor that is of the form:

(Product of any number of prime factors or prime powers no greater than B1) * (a prime factor or prime power no greater than B2) + 1

In the case of Mersennes, prime95 also throws in the Mersenne exponent (n), so that it will find any factor of the form:

(Product of any number of prime factors or prime powers no greater than B1) * (a prime factor or prime power no greater than B2) * n + 1

That is deterministic, not probabilistic.

It's simply factual. No politics involved. Perhaps my phrase "B1/B2 search space" is not clear enough for you.

That's like saying that "the real problem in TF is selection of the upper bound. Shall we TF to 2^75 or to 2^76? "

If you TF to 2^75, you'll find any factor less than 2^75. If you subsequently TF from 2^75 to 2^76 will find any factor between 2^75 and 2^76.

The same is true of P-1, except that the B1/B2 search space is multidimensional, not the simple one-dimensional number line that TF searches.

... which is exactly what P-1 does.

No, it does not.

Because the algorithm is based on properties of a multiplicative group, it does not matter what the starting number (prime95 always uses 3) is, just as long as it is coprime with the number being factored.

As the Wikipedia article states,
With any coprime initial value a, the result of the exponentiation has the property that it is congruent to (a factor satisfying the above criteria) mod p, if such factor exists. 100% guaranteed. (Fermat's Little Theorem) No guessing or probability involved.

No, because the search space does not depend on the choice of a (as long as it's coprime ...). It depends only on B1/B2.

No, you are misunderstanding the multiplicative group property upon which P-1 is based. It's based on multiplication mod N, which cycles through all possible congruence classes 1, 2, 3, ... N-1 if N is prime. If N is composite, there are subsequences of prime lengths which divide N, and those lengths are found by the GCD.

Perhaps someone with a more practical understanding of multiplicative groups than my intuitive understanding can explain it better for you.

I think you misunderstand my search terminology.

If we perform a brute force search we ain't gonna miss anything.
Now TF is a very stupid form of brute force search. You do n bits then n+1 bits and so on.

P-1 simply will sometimes find big factor for 1 prime, then miss a simple 63 bits factor for other prime. In fact odds it misses that 63 bits factor is *huge*.

So the result is total random from brute force viewpoint seen.

Missing small factors say < 128 bits is incredible childish for factoring algorithm considering system time put into P-1.

What i call the hill there, you call of course correctly the multiplicative group; as a search expert i only see things from search viewpoint of course and i just see it's the wrong hill nearly always. Just in a few % of cases it's the correct hill. Very primitive.

If we compare the public factorisation algorithms with progress in for example computerchess, then factorisation algorithms have stood still and are still years 70s so to speak compared to how search moved in computerchess. But of course there was public money to make with it in computerchess and lots of prestige. In factorisation publicly nothing happened that's worth even mentionning.

Regards,
Vincent

[diep]

In fact, we've done P-1 at some tens of thousands of exponents now for Wagstaff just around and mostly above 8 million bits; it doesn't even break even. And that though we just trial factored to 61 bits so far. Still have to throw GPU into action to factor further.

Jeff Gilchrist also tried other forms of public factorisation. ECM and others. All been tried at his cluster. Nothing even remotely breaks even.

Well let me rephrase that. The oldie k8's are of course not so great in SSE2. Just 1 instruction per cycle (2 flops per cycle per core) so from his viewpoint having them factor is ok as it's slow for VRB-Reix test anyway. Which of course all is 1 to 1 similar to a LL (Wagstaff has 100% same properties like Mersenne).

Even at those k8's it's hardly break even. Just because it's nicer to have things factored than to maybe have 1 or 2 wrong residue's *maybe* we prefer the factorisation.

So 50 years of factorisation or so, what has it brought in terms of public algorithms? Especially the past 16 years.

*nothing*

How comes?

Regards,
Vincent

[Christenson]

Originally Posted by James Heinrich

Using an example of M333000013, which TF's by default to 2^76, we find:
* TF to 4 levels above that (2^80) takes an additional 689 GHz-days and has a 5.16% chance of finding a factor
* P-1, for the same 5.16% chance of factor, takes 85GHz-days of work.

So your TF processor has to perform at least 8.1x faster than your P-1 processor to be worth it (this goes up to roughly 10x performance-per-chance difference at 2^86, 12%).

Without a CUDA P-1, mfaktc can get that 689GHz days in approximately 24 hours on a high end card, and 8 days or so on my medium (GTX440) card, except that it's off helping out on Operation Billion Digits this week. Assuming a CUDA P-1 at 10X speedup, we are roughly at equilibrium. Without a CUDA P-1, we are way behind and should do more TF.

So here's my next question: If, for our P-1 operation, we are spending the majority of our time raising three to a high exponent, can we improve the algorithm time by saving the result, and then multiplying this by 3 to a much smaller power for the next, presumably nearby mersenne exponent we wish to work our P-1 on?

[axn]

Originally Posted by diep

In fact, we've done P-1 at some tens of thousands of exponents now for Wagstaff just around and mostly above 8 million bits; it doesn't even break even. And that though we just trial factored to 61 bits so far.

Can you provide some details on this? What were the bounds used? What was the run-time relative to a V-R test? What was the hit rate? How much memory was used? What software was used?

[cheesehead]

Originally Posted by diep

I think you misunderstand my search terminology.

If we perform a brute force search we ain't gonna miss anything.

... and by brute force search I think you mean that it searches sequentially among candidates which are arranged along the customary one-dimensional number line.

P-1 simply will sometimes find big factor for 1 prime, then miss a simple 63 bits factor for other prime. In fact odds it misses that 63 bits factor is *huge*.

But there, you're looking at the P-1 search as though it proceeded along the same one-dimensional number line as TF. When you look at it in a more appropriate coordinate system, P-1 is a well-behaved deterministic method with no strange misses. What you perceive as adjacent points in the TF search space are not necessarily adjacent points in the P-1 search space, and vice versa.

I use the terminology "B1/B2 search space" to denote the two-dimensional space that P-1 searches for factors of N. Neither of its dimensions are one-dimensional integer number line that TF searches.

Instead, in B1/B2 P-1 search space, one axis represents the largest prime or prime power factor of P-1 where P is any factor of N. The other axis represents the second largest prime or prime power factor of P-1 where P is any factor of N.

Most intersections at integral coordinates of that space are empty, but each factor P of N occupies one intersection. The P-1 algorithm searches the rectangle with (0,0) at one corner and (B1,B2) at the diagonally opposite corner. If any factor of N resides in that rectangle, P-1 will definitely find it.

Examples:

The integer 19 corresponds to the intersection (2,9) in B1/B2 P-1 search space.

37 corresponds to (4,9).

127 corresponds to (7,9) in B1/B2 P-1 search space. 631 corresponds to the same intersection (7,9).

Any numbers which have either 127 or 631 as a factor can be factored by P-1 with limits of B1=7 and B2=9.

That same search (B1=7,B2=9) will find any other factor that exists (corresponds to an intersection) in the rectangle from (0,0) to (7,9). Intersection (4,5) corresponds to 61 and 101, which would also be found by a (7,9) search -- if either is a factor of the number being tested.

If more than one prime factor is in the search rectangle, P-1 will find their product, so factors found by P-1 need to be checked for compositeness.

Now, a mapping from that P-1 search space to some other space may transform the nice neat rectangle from (0,0) to (B1,B2) into a pattern of hills and valleys, but insisting that such hills and valleys are the proper way, or only way, to look at a P-1 search will lead one to misunderstandings such as considering P-1 to be a probabilistic method. In the most appropriate view of the P-1 search space, it is a deterministic rectangle on the other end of the mapping.

So the result is total random from brute force viewpoint seen.

... only if one is looking at the P-1 search space without using the most appropriate coordinate system, or looking at the wrong end of a mapping from one space to the other.

Missing small factors say < 128 bits is incredible childish for factoring algorithm considering system time put into P-1.

All you're doing there is judging P-1 by an inappropriate standard (size of factor P, rather than size of largest factor of P-1), which leads you to a mistaken conclusion about the algorithm's childishness.

What i call the hill there, you call of course correctly the multiplicative group;

No, the hill is simply a part of a mapping from P-1 search space to TF search space.

What the multiplicative group corresponds to is a rectangle in P-1 search space from

(0,0)

to

(largest prime or prime power factor of P-1 where P is any factor of the group order,

second largest prime or prime power factor of P-1 where P is any factor of the group order).

That rectangle will map to many noncontiguous hills and valleys in your conventional search space.

as a search expert i only see things from search viewpoint of course

... but here, you're using only one type of coordinate space -- one that's inappropriate for P-1.

In your space, a 128-bit prime number may be just 2 away from a number whose largest factor is, say, 11-bit. In mapping to P-1 space, those two numbers may be very far apart, or close together, depending on the factorizations of the numbers-1.

and i just see it's the wrong hill nearly always. Just in a few % of cases it's the correct hill. Very primitive.

... because what you're looking at is only a part of one end of a mapping from P-1 search space -- and it's the inappropriate end for understanding P-1.

[cheesehead]

Originally Posted by Christenson

So here's my next question: If, for our P-1 operation, we are spending the majority of our time raising three to a high exponent, can we improve the algorithm time by saving the result, and then multiplying this by 3 to a much smaller power for the next, presumably nearby mersenne exponent we wish to work our P-1 on?

Good question.

The problem is that in practice, for the size of numbers we're working with, we have to handle all the exponentiation in mod N. (N is often some Mersenne 2^p-1). The same consideration applies to the squaring in the Lucas-Lehmer test in addition to the exponentiation in P-1.

Without the modular reductions, we'd quickly (surprisingly quickly) be trying to store numbers which have more digits than the number of particles in the known universe.

See the response to "Why not skip the modular reduction in the LL test and reuse residues?" on this page http://www.mersennewiki.org/index.ph...d_improvements

and

the second and third paragraphs (which include a calculation about the number of particles in the known universe) under "Simple Explanation" on this page http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test

Since we're therefore dealing with residues mod N, the ones we compute for one value of N are useless when computing for a different value of N.

So it is necessary to start fresh each time ... unless one is continuing a computation for the same N, but higher limits! Therefore, saving the final residue from an unsuccessful P-1 is useful when another P-1 test is simply extending the limits used by the first P-1 test -- but note that here we're not changing N, which is why the earlier mod N result is useful.

Furthermore (again, for the size of numbers we're dealing with), it's actually much faster to restart exponentiation afresh, with modular arithmetic, than it would be to "read" stored full non-modular products from wherever we managed to store them. (Consider that the size of "disk" you'd be reading from might need to be larger than the Milky Way galaxy.)

[xilman]

Originally Posted by diep

So 50 years of factorisation or so, what has it brought in terms of public algorithms? Especially the past 16 years.

*nothing*

How comes?

You are very, very wrong. The last 50 years have produced a slew of sub-exponential factoring algorithms, including the quadratic sieve, the number field sieve and the elliptic curve method.

They have produce a number of exponential but fast algorithms for finding small factors, including P-1, P+1, SQUFOF, and Pollard rho.

All of these algorithms are public and all are in daily use.

Much of the advance in the last few decades can be ascribed to three people: John Pollard, Hendrik Lenstra and Peter Montgomery.

Paul

[Christenson]

Originally Posted by cheesehead

Good question.

The problem is that in practice, for the size of numbers we're working with, we have to handle all the exponentiation in mod N. (N is often some Mersenne 2^p-1). The same consideration applies to the squaring in the Lucas-Lehmer test in addition to the exponentiation in P-1.

Without the modular reductions, we'd quickly (surprisingly quickly) be trying to store numbers which have more digits than the number of particles in the known universe.

See the response to "Why not skip the modular reduction in the LL test and reuse residues?" on this page http://www.mersennewiki.org/index.ph...d_improvements

and

the second and third paragraphs (which include a calculation about the number of particles in the known universe) under "Simple Explanation" on this page http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test

Since we're therefore dealing with residues mod N, the ones we compute for one value of N are useless when computing for a different value of N.

So it is necessary to start fresh each time ... unless one is continuing a computation for the same N, but higher limits! Therefore, saving the final residue from an unsuccessful P-1 is useful when another P-1 test is simply extending the limits used by the first P-1 test -- but note that here we're not changing N, which is why the earlier mod N result is useful.

Furthermore (again, for the size of numbers we're dealing with), it's actually much faster to restart exponentiation afresh, with modular arithmetic, than it would be to "read" stored full non-modular products from wherever we managed to store them. (Consider that the size of "disk" you'd be reading from might need to be larger than the Milky Way galaxy.)

I had missed that the practical B1 on my machine is 660,000, and 660,000 Primorial is of, well, nontrivial, size.

In the P-1 operation, we do all the arithmetic modulo some N...I assume that N would be 2^P-1, with no other reasonable choices, right? (That is, some other choice, such as the product of the three mersenne exponents we wanted to test in parallel, would more than triple the compute time, and a product of, say, 10, wouldn't allow testing of additional mersenne exponents beyond the 10 listed)

I'm thinking at this point that the only obvious optimization of P-1 on a GPU would be to run exponents in parallel, to the size of available memory, thus maximising usage of the many compute cores in the GPU.

[axn]

Originally Posted by Christenson

In the P-1 operation, we do all the arithmetic modulo some N...I assume that N would be 2^P-1, with no other reasonable choices, right? (That is, some other choice, such as the product of the three mersenne exponents we wanted to test in parallel, would more than triple the compute time, and a product of, say, 10, wouldn't allow testing of additional mersenne exponents beyond the 10 listed)

Correct.

Originally Posted by Christenson

I'm thinking at this point that the only obvious optimization of P-1 on a GPU would be to run exponents in parallel, to the size of available memory, thus maximising usage of the many compute cores in the GPU.

Stage 2 of a single exponent can also be parallelised.

[petrw1]

Originally Posted by diep

TF is very cheap. It soon gets a lot less than 1.5% each additional bitlevel of course, otherwise we'd only be doing TF.

If I understand the approimation alogorithm correctly on the Math page: at 65 bits the odds are abouut 1/65 or 1.53%; 1.43% at 70 bits. Most TF now is in that range so that is why I said "about 1.5%" in my post.

So TF really has major advantages to do real deep.

Define "real deep". If you can do the 70 bit level in 1 minute, 80 bits is 17 hours; 85 bits is 22.66 days; 90 bits is about 2 years.

Additional to that, once we get to the 100M digits level, it's like 1 year at a gpu now to run a LL or so of 100M digits size?

Yes, based on current hardware but hardware advances have done a pretty good job of keeping pace with the project. In the 8 or so years I have been involved leading edge LL tests have always taken 3-4 weeks on mainstream PC's.

Compared to all those problems with LL, i'd guess TF is pretty efficient and fast to do real real deep.

Depends on your perspective. I think George does a good job determining the break-even point between TF and LL. Granted with the recent influx of GPUs it's now much harder to determine.

So i guess now is the time to TF real real deep, because as soon as we get the 22 nm GPU's which might be able to do a LL within 1 or 2 months at the 332M+ bitlevel, then i guess most will soon abandon running TF and other factoring software.

Again I suggest mainstream PCs will be doing these LL tests in a few weeks by the time the project gets there. Mind you, if the consistently linear rate of 3 1-million ranges per year continues we are looking at 93 more years. I know I won't be around to witness that. I doubt there would ever be a time that it made sense to abandon TF; there will always be a bit-level where TF is more effective than LL. That being said; if the current rate of TF continues to increase as more and more GPUs get involved I suspect all necessary TF up to 332M+ will be done in less than this same 93 years.