Trial Factoring backwards
 

Since [url=http://www.mersenneforum.org/showthread.php?t=16019]we know[/url] 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?

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.

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 [I]some[/I] Mersenne numbers at an astonishing rate, you get prime factors for [I]interesting[/I] Mersenne numbers much more slowly than by the usual trial division.

[QUOTE=axn;279506]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.[/QUOTE]You can take your pick of timings here: [url]http://mersenne-aries.sili.net/bench.php[/url]

[QUOTE=James Heinrich;279510]You can take your pick of timings here: [url]http://mersenne-aries.sili.net/bench.php[/url][/QUOTE]

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)

[QUOTE=akruppa;279509]A prime p divides M_q iff ord_p(2) | q. [/quote]
Since we're looking at q prime, that becomes ord_p(2) = q, right?

[QUOTE=akruppa;279509]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. [/quote]
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?

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.

[QUOTE=axn;279511]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)[/QUOTE]The one derives from the other. [url=http://mersenne-aries.sili.net/throughput.php?cpu1=Intel%28R%29%20Core%28TM%29%20i7%20CPU%20920%20%40%202.67GHz|256|8192&mhz1=3210]This version of the data[/url] 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.

[QUOTE=James Heinrich;279516]The one derives from the other. [url=http://mersenne-aries.sili.net/throughput.php?cpu1=Intel%28R%29%20Core%28TM%29%20i7%20CPU%20920%20%40%202.67GHz|256|8192&mhz1=3210]This version of the data[/url] 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.[/QUOTE]

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.

[QUOTE=axn;279517]Hmmm... It is coming out tighter than I expected. Still, at first glance, the conventional approach wins handily.[/QUOTE]

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?

[QUOTE=Bdot;279884]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?[/QUOTE]

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.

[QUOTE=axn;279931]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.[/QUOTE]

Mathematica took 172 seconds to compute the order for 10^5 primes between 2^65 and 2^66.

Since q is prime ord[SUB]p[/SUB](2) = q. But ord[SUB]p[/SUB](2) is a factor of phi(p)=p-1.

So for each prime p, we trialfactor p-1 up to 1 billion and check if any of the factors found are ord[SUB]p[/SUB](2) ?

For each prime power q^k || p-1 you find, you can look for the largest 0 <= i <= k for which 2^((p-1)/q^i) == 1 (mod p); then q^(k-i) exactly divides ord_p(2). Since ((p-1)/something) will include the same prime factors over and over again, maybe it's worthwhile to build some kind of tree. Then again, taking powers of 2 modulo a relatively small prime is pretty fast already, the tree might lose due to overhead.

I am still missing how ord[SUB]p[/SUB](2) can be composite?

If p | Mq => 2[SUP]q[/SUP] = 1 (mod p) => q = k*ord[SUB]p[/SUB](2), but since we are only interested in q prime then k=1 and ord[SUB]p[/SUB](2) is prime and equal to q?

So if p-1 = r[SUB]1[/SUB]^k[SUB]1[/SUB] * r[SUB]2[/SUB]^k[SUB]2[/SUB] * ... * r[SUB]n[/SUB]^k[SUB]n[/SUB] then we only need to check if ord[SUB]p[/SUB](2) is r[SUB]1[/SUB], r[SUB]2[/SUB]... up to 1 billion?

Ord(2,M=2^p-1) it is always p, which is prime. Ord(2,q), where q divides M it is always p, no matter if q is prime or not. There is a simple theorem saying that ord(x,a*b)=lcm(ord(x,a),ord(x,b)) for x prime and any a,b.

Ex: Ord(2,2^29-1)=29. Because the smallest power you need to raise 2 to get 1 mod M, is 29. There is no other smaller power. Therefore, ord(2,233)=29, ord(2,1103)=29, ord(2,2089)=29, ord(2,233*1103)=29, and so on. If any of them would be different, then by the LCM theorem above we would get ord(2,M)>29, which is impossible.

Generally, ord(2,q) can be composite. Ord(2,73)=9, ord(2,13)=12, etc.

I played with these things long time ago. I was hunting factors of mersenne numbers Mp not by p, but by k in 2*k*p+1. Still have the files with all factors below 2^56 or so, for all exponents under 10 billions. I also tried (random) higher numbers ([URL="http://www.mersenneforum.org/showpost.php?p=271691&postcount=26"]see here[/URL] some discussion) and sometime got lucky to find a factor after hours of (random) search. The problem with this method is [B]EXACTLY one described by akruppa[/B] in post #3 above, in this thread. The method is feasible under approximatively 2^56 (for the factor q, not for k) with a HIGHLY optimized program (for CPU). For the pari script presented in the link above, the cut-off is somewhere between 2^29 and 2^33, depending of how fast is your computer. [B]Over[/B] this limits, you will try TOO MANY numbers q whose order is q-1, or (q-1)/2 (the most of the primes, even if you filter them by 8k[TEX]\pm[/TEX] 1) which are NOT INTERESTED for our domain (lower then a billion).

ATH, yes, if you want to restrict reported factors to those of Mersenne numbers with prime exponent, then just check whether 2^q==1(mod p) for each prime factor q of p-1.