20210520, 15:48  #1 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
Database of multiplicative order of 2 mod p
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. 
20210520, 18:12  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10245_{10} Posts 
A "snail way" to print that, define a function in pari:
Code:
/*get smallest p such as n divides 2^p1*/ 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); } and call it with: Code:
forstep(q=3,10^3,2,print(q": "getp(q))) 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. Last fiddled with by LaurV on 20210520 at 18:16 
20210521, 11:42  #3  
Feb 2017
Nowhere
2·3,049 Posts 
Quote:
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. 

20210522, 07:12  #4 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
LaurV, that's an interesting piece of code, I'd probably have done some lame trial factoring with while(2^p1 % 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? Last fiddled with by bur on 20210522 at 07:13 Reason: "Quick reply" always adds additional blank lines, is that a bug? 
20210522, 07:42  #5 
Jun 2003
3^{4}·67 Posts 

20210522, 11:32  #6  
Feb 2017
Nowhere
17D2_{16} Posts 
Quote:
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 p1 in the function call, which helpfully tells PariGP that the required order is a divisor of p1. 

20210525, 07:11  #7 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
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. 
20210525, 12:14  #8 
Feb 2017
Nowhere
2×3,049 Posts 
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^((p1)/2) == 1 (mod p), so znorder(Mod(2, p)) divides (p1)/2. If k is a quadratic nonresidue (mod p), then znorder(Mod(k,p)) does not divide (p1)/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 nonresidue 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 nonresidue (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 nonresidue (mod p). No such p can divide 3*2^n + 1. Appealing to the abovementioned 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 nonresidue (mod p). Taking k = 3, we have that 3 is a quadratic nonresidue (mod p) for p == 5 or 7 (mod 12), and p == 7 or 17 (mod 24) can never divide 3*2^n  1. Last fiddled with by Dr Sardonicus on 20210525 at 12:16 Reason: xingif optsy 
20210525, 18:44  #9 
Aug 2020
79*6581e4;3*2539e3
259_{16} Posts 
What I don't get, isn't this
true for any k and any p (as long as they are coprime)? The multiplicative order of any base mod p is (p1)/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^n1? Or at least try and rule out certain primes that will never divide it? Last fiddled with by Dr Sardonicus on 20210526 at 13:41 Reason: Providing reference for quotation 
20210526, 13:53  #10  
Feb 2017
Nowhere
13722_{8} Posts 
Quote:
Quote:
Quote:
Quote:
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 p1 is quite small. The following mindless PariGP 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. Code:
? forprime(p=5,200,m3=znorder(Mod(3,p),p1);m2=znorder(Mod(2,p),p1);if(m2%m3==0,g=znprimroot(p);l2=znlog(Mod(2,p),g);lkinv=p1znlog(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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
order of a function =/= p1  bhelmes  Math  5  20180913 16:23 
Number of groups for given order  Raman  Puzzles  6  20100905 17:43 
Conjecture about multiplicative order of 3 modulo a Mersenne prime  T.Rex  Math  9  20070326 17:35 
Forum order?  Xyzzy  Forum Feedback  5  20070128 10:35 
general form of the multiplicative order  juergen  Math  1  20040316 11:43 