mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-05-20, 15:48   #1
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default 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.
bur is offline   Reply With Quote
Old 2021-05-20, 18:12   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

1024510 Posts
Default

A "snail way" to print that, define a function in pari:
Code:
/*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:
Code:
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.

Last fiddled with by LaurV on 2021-05-20 at 18:16
LaurV is offline   Reply With Quote
Old 2021-05-21, 11:42   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3,049 Posts
Default

Quote:
Originally Posted by bur View Post
<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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-05-22, 07:12   #4
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

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?

Last fiddled with by bur on 2021-05-22 at 07:13 Reason: "Quick reply" always adds additional blank lines, is that a bug?
bur is offline   Reply With Quote
Old 2021-05-22, 07:42   #5
axn
 
axn's Avatar
 
Jun 2003

34·67 Posts
Default

Quote:
Originally Posted by bur View Post
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)))
axn is offline   Reply With Quote
Old 2021-05-22, 11:32   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

17D216 Posts
Default

Quote:
Originally Posted by bur View Post
<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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-05-25, 07:11   #7
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

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.
bur is offline   Reply With Quote
Old 2021-05-25, 12:14   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3,049 Posts
Default

Quote:
Originally Posted by bur View Post
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.

Last fiddled with by Dr Sardonicus on 2021-05-25 at 12:16 Reason: xingif optsy
Dr Sardonicus is offline   Reply With Quote
Old 2021-05-25, 18:44   #9
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

25916 Posts
Default

What I don't get, isn't this
Quote:
Originally Posted by Dr Sardonicus View Post
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?

Last fiddled with by Dr Sardonicus on 2021-05-26 at 13:41 Reason: Providing reference for quotation
bur is offline   Reply With Quote
Old 2021-05-26, 13:53   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

137228 Posts
Default

Quote:
Originally Posted by bur View Post
What I don't get, isn't this
Quote:
Originally Posted by Dr Sardonicus View Post
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)?
No. k = 3, p = 7.
Quote:
The multiplicative order of any base mod p is (p-1)/n.
What is n?


Quote:
And to help me understand the rest of your post better, we are trying to determine the multiplicative order of k*2 (mod p)?
Quote:
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.

Code:
? 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
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
order of a function =/= p-1 bhelmes Math 5 2018-09-13 16:23
Number of groups for given order Raman Puzzles 6 2010-09-05 17:43
Conjecture about multiplicative order of 3 modulo a Mersenne prime T.Rex Math 9 2007-03-26 17:35
Forum order? Xyzzy Forum Feedback 5 2007-01-28 10:35
general form of the multiplicative order juergen Math 1 2004-03-16 11:43

All times are UTC. The time now is 00:06.


Sat Dec 3 00:06:23 UTC 2022 up 106 days, 21:34, 0 users, load averages: 0.87, 0.84, 0.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔