Trial Factoring backwards

James Heinrich · 2011-11-22, 16:11

Since we know that all factors only belong to (at most) one Mersenne exponent, is there any merit to going about the trial factoring process in the reverse order from what we currently do? That is, instead of picking a Mersenne number and then running through a massive list of factor candidates to see if they divide nicely, what if the approach was to go through the list of candidate factors (which would be all prime numbers that are not already known to be a factor of another Mersenne number) and for each candidate check if it divides into any Mersenne number (in the range we're interested in looking in, i.e. <M1000M or whatever seems appropriate). Would this require more, or less, or the same effort as the standard approach?

Perhaps this is a silly idea, and perhaps it's been discussed before; if so perhaps someone could point me to that discussion please?

axn · 2011-11-22, 16:38

I think everything has been TFed to 65 bits (or well on the way to doing so). So let's look at doing the TF from 2^65 to 2^66. Let's also restrict our exponents from 100M to 1G.

There are about 8.1e17 primes between 2^65 and 2^66. Assume that a single CPU can "handle" 10^7 primes/sec -- i.e generate them, figure out which of the candidates between 100M & 1G, if any, they might divide, and then perform the actual division to see if they divide. Then we're looking at about 8e10 CPU secs -- 2530 CPU years -- to do this task.

Would we be able to do the same thing "conventionally" in less time? I don't have the data, but if someone can give me any TF timing (for any bit > 64 for any expo on any CPU), I can calculate the time for the whole range.

I would expect that the end result would be that conventional approach is best.

akruppa · 2011-11-22, 16:45

I've tried that once in the Mersenne mailing list age, before mersenneforum. A prime p divides M_q iff ord_p(2) | q. It is very easy for a given p to compute ord_p(2), which gives you the exponent of the smallest Mersenne number which this prime p divides. Problem is, ord_p(2) is usually about as large as p, so almost all of those exponents are too large (huge M_q in which no one is interested). For p in the interesting range, you very rarely get a q where we actually want to know a factor of M_q. In the end, although you do get prime factors of some Mersenne numbers at an astonishing rate, you get prime factors for interesting Mersenne numbers much more slowly than by the usual trial division.

James Heinrich · 2011-11-22, 16:46

Quote:

Originally Posted by axn

if someone can give me any TF timing (for any bit > 64 for any expo on any CPU), I can calculate the time for the whole range.

You can take your pick of timings here: http://mersenne-aries.sili.net/bench.php

axn · 2011-11-22, 16:58

Quote:

Originally Posted by James Heinrich

You can take your pick of timings here: http://mersenne-aries.sili.net/bench.php

Not useful. I need actual time (in seconds or minutes or ...) for taking some specific exponent from 2^65 to 2^66 (or any bit depth > 64 to any other bit depth)

axn · 2011-11-22, 17:04

Quote:

Originally Posted by akruppa

A prime p divides M_q iff ord_p(2) | q.

Since we're looking at q prime, that becomes ord_p(2) = q, right?

Quote:

Originally Posted by akruppa

It is very easy for a given p to compute ord_p(2), which gives you the exponent of the smallest Mersenne number which this prime p divides.

Do you remember what was the thruput of the order calculation -- how many p's/sec? Rough order-of-magnitude will do.

Also, can the ordering calculation be sped up by doing them in bulk -- for example, I assume that we need to factor p-1 for finding the order. Can somehow _that_ be sped up by some kind of sieving technique?

akruppa · 2011-11-22, 17:13

I don't remember any figures, sorry. That experiment must have been close to 10 years ago. However, the trial factoring limits L were lower then than they are today, and the ratio q/L (where q is of the same size as the exponents for which we want factors) determines how likely reverse factoring is to produce an interesting exponent. That ratio only got smaller in since back then.

My code did not use sieving, iirc it did mostly trial division. Sieving should be faster, but I doubt it would be fast enough to make reverse factoring worthwhile.

James Heinrich · 2011-11-22, 17:24

Quote:

Originally Posted by axn

Not useful. I need actual time (in seconds or minutes or ...) for taking some specific exponent from 2^65 to 2^66 (or any bit depth > 64 to any other bit depth)

The one derives from the other. This version of the data shows a table that's perhaps more useful to you. For example for M13,380,000 from 2^64 to 2^65 on an i7-920@3.2GHz it takes 5930 seconds.

axn · 2011-11-22, 17:38

Quote:

Originally Posted by James Heinrich

The one derives from the other. This version of the data shows a table that's perhaps more useful to you. For example for M13,380,000 from 2^64 to 2^65 on an i7-920@3.2GHz it takes 5930 seconds.

Going by that data, we can take a 300M exponent from 2^65 to 2^66 in about 9 mins. There are about 4.5e7 expos between 100M & 1G. Using 300M as the average size, that'd mean about 40.5e7 cpu mins -- 770 cpu years -- for the whole range.

Hmmm... It is coming out tighter than I expected. Still, at first glance, the conventional approach wins handily.

Bdot · 2011-11-26, 00:03

Quote:

Originally Posted by axn

Hmmm... It is coming out tighter than I expected. Still, at first glance, the conventional approach wins handily.

770 to 2530 is rather close ... given that its based on estimates? Especially the "Assume that a single CPU can "handle" 10^7 primes/sec" - is that based on real experiences/tests? Or a rather high ballpark figure?

Would increasing the acceptable exponent range to, say, 10G turn the tides? I would assume that the factorizations of the (prime-1)'s are a major part of the total effort. It would yield more possible exponents that "just" need to be tested ... On the other hand, the traditional TF gets easier with bigger exponents. I just cannot judge which effect would be stronger.

And another question: is it possible to give a good estimate which fraction of all primes is a factor of any Mersenne number?

axn · 2011-11-26, 05:16

Quote:

Originally Posted by Bdot

Especially the "Assume that a single CPU can "handle" 10^7 primes/sec" - is that based on real experiences/tests? Or a rather high ballpark figure?

The latter. For comparison, computing Ord_2 for the first 10^5 primes > 2^65 takes PARI about 9min. That's about 4.5 order-of-magnitude shy of 10^7 primes/sec.

2011-11-22, 16:11	#1
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 11×311 Posts	Trial Factoring backwards Since we know that all factors only belong to (at most) one Mersenne exponent, is there any merit to going about the trial factoring process in the reverse order from what we currently do? That is, instead of picking a Mersenne number and then running through a massive list of factor candidates to see if they divide nicely, what if the approach was to go through the list of candidate factors (which would be all prime numbers that are not already known to be a factor of another Mersenne number) and for each candidate check if it divides into any Mersenne number (in the range we're interested in looking in, i.e. <M1000M or whatever seems appropriate). Would this require more, or less, or the same effort as the standard approach? Perhaps this is a silly idea, and perhaps it's been discussed before; if so perhaps someone could point me to that discussion please?

2011-11-22, 16:38	#2
axn Jun 2003 2·3·7·11² Posts	I think everything has been TFed to 65 bits (or well on the way to doing so). So let's look at doing the TF from 2^65 to 2^66. Let's also restrict our exponents from 100M to 1G. There are about 8.1e17 primes between 2^65 and 2^66. Assume that a single CPU can "handle" 10^7 primes/sec -- i.e generate them, figure out which of the candidates between 100M & 1G, if any, they might divide, and then perform the actual division to see if they divide. Then we're looking at about 8e10 CPU secs -- 2530 CPU years -- to do this task. Would we be able to do the same thing "conventionally" in less time? I don't have the data, but if someone can give me any TF timing (for any bit > 64 for any expo on any CPU), I can calculate the time for the whole range. I would expect that the end result would be that conventional approach is best. Last fiddled with by axn on 2011-11-22 at 16:38 Reason: zeros!!!!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Trial Factoring on AMD/ATI GPU's?	Stargate38	GPU Computing	9	2018-08-31 07:58
What is Trial Factoring?	Unregistered	Information & Answers	5	2012-08-02 03:47
over trial factoring	JFB	Software	23	2004-08-22 05:37
Trial factoring	Citrix	Software	7	2004-02-26 03:24
About trial factoring	gbvalor	Math	4	2003-05-22 02:04

2011-11-22, 16:45	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I've tried that once in the Mersenne mailing list age, before mersenneforum. A prime p divides M_q iff ord_p(2) \| q. It is very easy for a given p to compute ord_p(2), which gives you the exponent of the smallest Mersenne number which this prime p divides. Problem is, ord_p(2) is usually about as large as p, so almost all of those exponents are too large (huge M_q in which no one is interested). For p in the interesting range, you very rarely get a q where we actually want to know a factor of M_q. In the end, although you do get prime factors of some Mersenne numbers at an astonishing rate, you get prime factors for interesting Mersenne numbers much more slowly than by the usual trial division.

2011-11-22, 17:13	#7
akruppa "Nancy" Aug 2002 Alexandria 2467₁₀ Posts	I don't remember any figures, sorry. That experiment must have been close to 10 years ago. However, the trial factoring limits L were lower then than they are today, and the ratio q/L (where q is of the same size as the exponents for which we want factors) determines how likely reverse factoring is to produce an interesting exponent. That ratio only got smaller in since back then. My code did not use sieving, iirc it did mostly trial division. Sieving should be faster, but I doubt it would be fast enough to make reverse factoring worthwhile.