[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.