Database of multiplicative order of 2 mod p

[bur]

Is there a database or list of the known multiplicative order of 2 mod various primes?

There's a list for all odd numbers < 20001 at OEIS (https://oeis.org/A002326/b002326.txt). I know factordb or mersenne.ca in general have the answers, but not in an easy to search form as far as I know.

I'm occasionally factoring Proth/Riesel numbers and am just curious if any of the factors have a known multiplicative order.

[LaurV]

A "snail way" to print that, define a function in pari:

/*get smallest p such as n divides 2^p-1*/
getp(n=23,limt=10^5)=
{
    if(n<3 || n%2==0, print("Only odd positive numbers!");return);
   
    rg=1;
    sm=0;
    until(rg==1 || sm>=limt, 
        rg+=n;
        while(rg%2==0 && sm<limt, 
            rg>>=1;
            sm++;
            if(bitand(sm,1048575)==0, printf("...%d...%c",sm,13));
        )
    );
    return(sm);
}

(what have I done and why that works? )

and call it with:

forstep(q=3,10^3,2,print(q": "getp(q)))

For larger numbers you need to use both parameters. Also, the "bitand" line is to show the progress, you can comment it out if it bothers your output for large numbers.
When you step on a prime p, you just found a factor of mersenne number Mp. (why?)
You could also read the help for the fucntion znorder() in pari.
When q is prime there are faster ways to get its order.

[Dr Sardonicus]

Originally Posted by bur

<snip>
I'm occasionally factoring Proth/Riesel numbers and am just curious if any of the factors have a known multiplicative order.

Beyond the fact that for p > 2 the multiplicative order of 2 (mod p) divides p - 1, I don't know much. Artin's conjecture on primitive roots predicts that 2 is a primitive root of a positive proportion (something like 37% IIRC) of primes.

For Proth and Riesel numbers, though, it's not just the multiplicative order of 2 (mod p).

For a given odd k (by convention 1 < k < 2^n if I understand correctly), if p is a prime factor of k*2^n - 1, the multiplicative order of k (mod p) divides the multiplicative order of 2 (mod p). If p divides k*2^n + 1, the multiplicative order of -k (mod p) divides the multiplicative order of 2 (mod p). For a given k, these conditions exclude a positive proportion of the primes as potential factors.

[bur]

LaurV, that's an interesting piece of code, I'd probably have done some lame trial factoring with while(2^p-1 % n != 0) or something like that... :D

Dr Sardonicus, that's very good to know. I tried it with 5 | 2^3+1 and the MO of 3 (mod 5) = 4 and MO of 2 (mod 5 ) = 4. Also 13 | 3^2+1 with the MO of 3 and 2 (mod 13) being 6 and 12, respectively. What I don't understand is the distinction between k and -k, does it matter?



And in conclusion to the original question, there is no such database?

[axn]

Originally Posted by bur

And in conclusion to the original question, there is no such database?

Why bother? You can compute it faster than you can look it up.

forprime(p=3,oo, print(p, ":", znorder( Mod(2,p), p-1)))

[Dr Sardonicus]

Originally Posted by bur

<snip>
I tried it with 5 | 2^3+1 and the MO of 3 (mod 5) = 4 and MO of 2 (mod 5 ) = 4. Also 13 | 3^2+1 with the MO of 3 and 2 (mod 13) being 6 and 12, respectively.
<snip>

Last I checked, 5 didn't divide 9, and 13 didn't divide 10.

I agree with axn, computing is faster - especially with that extra p-1 in the function call, which helpfully tells Pari-GP that the required order is a divisor of p-1.

[bur]

Oy vey. I forgot the k = 3...

5 | 3*2^3+1 and 13 | 3*2^2+1.


You're right about computing it, I was thinking about large factors that take long to find, but for these the chance of them being a factor of "my" proth number is very slim.

[Dr Sardonicus]

Originally Posted by bur

Oy vey. I forgot the k = 3...

5 | 3*2^3+1 and 13 | 3*2^2+1.

Ahh, now I see. In future, just leave making the typos to me. Believe me, I make enough for everyone. But I can fix mine later on

I note that if p does not divide k, k and 1/k have the same multiplicative order (mod p); also -k and -1/k have the same multiplicative order (mod p).

If p divides the Sierpinski number k*2^n - 1, we have k*2^n - 1 == 0 (mod p), k*2^n == 1 (mod p), 2^n == 1/k (mod p). Since 1/k and k have the same multiplicative order, we have znorder(Mod(k, p)) divides znorder(Mod(2,p)).

If p divides the Proth number k*2^n + 1, we have k*2^n + 1 == 0 (mod p), k*2^n == -1 (mod p), 2^n == -1/k (mod p). Since -1/k and -k have the same multiplicative order, we have znorder(Mod(-k, p)) divides znorder(Mod(2,p)).

If you're willing to accept the result that for a given a > 1, the arithmetic progressions a*n + r, 0 < r < a, gcd(r, a) = 1 all have (asymptotically) the same proportion of the primes, then it is easy to prove my earlier assertion that for odd k a positive proportion of the primes p do not divide k*2^n + 1 for any n. This argument does NOT account for all such primes, but it excludes a quarter of congruence classes relatively prime to 8k.

If p == 1 or 7 (mod 8) then 2^((p-1)/2) == 1 (mod p), so znorder(Mod(2, p)) divides (p-1)/2. If -k is a quadratic non-residue (mod p), then znorder(Mod(-k,p)) does not divide (p-1)/2, so znorder(Mod(-k, p)) does not divide znorder(Mod(2, p)), so p can never divide k*2^n + 1. The condition "-k is a quadratic non-residue mod p" gives linear congruence conditions on p modulo either k or 4k. One then gets the possible p (mod 8k) by the Chinese Remainder Theorem.

Taking k = 3, we find that -3 is a quadratic non-residue (mod p) for p == 2 (mod 3), so that for p == 17 or 23 (mod 24), 2 is a quadratic residue but -3 is a quadratic non-residue (mod p). No such p can divide 3*2^n + 1. Appealing to the above-mentioned result, that's a quarter of all primes right there.

The same argument, mutatis mutandis, works for Sierpinski numbers k*2^n - 1. Here we want p == 1 or 7 (mod 8) and k a quadratic non-residue (mod p).

Taking k = 3, we have that 3 is a quadratic non-residue (mod p) for p == 5 or 7 (mod 12), and p == 7 or 17 (mod 24) can never divide 3*2^n - 1.

[bur]

What I don't get, isn't this

Originally Posted by Dr Sardonicus

we have znorder(Mod(k, p)) divides znorder(Mod(2,p))

true for any k and any p (as long as they are co-prime)? The multiplicative order of any base mod p is (p-1)/n. Them it would be nothing special for Riesel/Proth numbers to have that property.


And to help me understand the rest of your post better, we are trying to determine the multiplicative order of k*2 (mod p)? In other words, what is the smallest n for which p divides k*2^n-1? Or at least try and rule out certain primes that will never divide it?

[Dr Sardonicus]

Originally Posted by bur

What I don't get, isn't this

true for any k and any p (as long as they are co-prime)?

No. k = 3, p = 7.

The multiplicative order of any base mod p is (p-1)/n.

What is n?

And to help me understand the rest of your post better, we are trying to determine the multiplicative order of k*2 (mod p)?

In other words, what is the smallest n for which p divides k*2^n-1? Or at least try and rule out certain primes that will never divide it?

The divisibility condition on multiplicative order deals with the latter question. As to the finding the least exponent when the condition is satisfied, When znorder(Mod(k,p)) does divide znorder(Mod(2,p)), finding the least n for which p divides k*2^n - 1 is an interesting computation. Obviously, the least value is no larger than znorder(Mod(2,p)), hence no larger than p-1.

Assuming znorder(Mod(k,p)) divides znorder(Mod(2,p)), let znorder(Mod(2,p))/znorder(Mod(k,p)) = q. Then 2^q has the same multiplicative order as k, but alas, that's not much help.

The only way I know to find the correct exponent employs primitive roots and discrete logs. I'm not sure how expensive it is to find a primitive root. But even given a primitive root, finding discrete logs mod p can be computationally expensive unless the largest prime factor of p-1 is quite small. The following mindless Pari-GP script computes the requisite n with k = 3 (that is, the least n for which p divides 3*2^n - 1), for those primes p < 200 which satisfy the condition that znorder(Mod(3,p)) divides znorder(Mod(2,p)). I haven't checked it in detail, but have verified some of the output.

I leave figuring out what the script is trying to do as a homework problem.

? forprime(p=5,200,m3=znorder(Mod(3,p),p-1);m2=znorder(Mod(2,p),p-1);if(m2%m3==0,g=znprimroot(p);l2=znlog(Mod(2,p),g);lkinv=p-1-znlog(Mod(3,p),g);f=lkinv/l2;e=lift(Mod(f,m2));print(p" "e)))
5 1
11 2
13 8
19 5
23 3
29 23
37 10
47 4
53 35
59 8
61 54
67 27
71 19
83 10
97 29
101 31
107 36
131 58
139 97
149 61
163 61
167 35
173 145
179 70
181 124
191 6
193 54
197 15