mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-03-07, 11:36   #1
JM Montolio A
 
Feb 2018

11000002 Posts
Question Whats is a fast algorithm for compute znorder(Mod(2,p)).

whats is a fast algorithm for compute znorder(Mod(2,p)).
for p prime but big.

Last fiddled with by JM Montolio A on 2018-03-07 at 11:45
JM Montolio A is offline   Reply With Quote
Old 2018-03-07, 11:40   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by JM Montolio A View Post
whats is a fast algorithm for compute nzorder(Mod(2,p)).
for p prime but big.
I think you mean znorder.
science_man_88 is offline   Reply With Quote
Old 2018-03-07, 11:46   #3
JM Montolio A
 
Feb 2018

6016 Posts
Default

You never sleeps ?
JM Montolio A is offline   Reply With Quote
Old 2018-03-07, 15:10   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by JM Montolio A View Post
whats is a fast algorithm for compute znorder(Mod(2,p)).
for p prime but big.
The basic idea is to factor m = p-1 into q_1^e_1 * q_2^e_2 * ... * q_k^e_k and then test if Mod(2,p)^(m/q_1), Mod(2,p)^(m/q_2), etc. are 1. If Mod(2,p)^(m/q_i) is 1 then try Mod(2,p)^(m/q_i^2), ..., until either you hit q_i^e_i or the residue is no longer 1. Divide m by the largest q_i^e that left a result of 1 and continue with q_{i+1}.

For example, let's try to find the order of 2 mod 101. m = 100 = 2^2 * 5^2, so we know that 2^100 = 1 mod 101. 2^(100/2) mod 101 is 100 which is not 1, so skip 2. 2^(100/5) = 95 which is not 1, so skip 5, and we're done: the order is 100.

Let's try 103. m = 102 = 2 * 3 * 17. 2^(102/2) = 1 mod 103, so m becomes 102/2 = 51. We don't have any more 2s though so we'll go on to 3. 2^(51/3) = 56 mod 103 which is not 1, and 2^(51/17) = 8 mod 103 which is also not 1, so we're done: the order of 2 mod 103 is 51.
CRGreathouse is offline   Reply With Quote
Old 2018-03-07, 17:15   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Of course to do that you'll need to know how to raise things to powers (binary exponentiation or sliding window, see wikipedia) and how to do modular arithmetic.
CRGreathouse is offline   Reply With Quote
Old 2019-06-12, 01:44   #6
hansl
 
hansl's Avatar
 
Apr 2019

5·41 Posts
Default

Um, if p is prime, isn't the answer always p-1?
edit: nevermind, i'm obviously confused

Last fiddled with by hansl on 2019-06-12 at 01:50
hansl is offline   Reply With Quote
Old 2019-06-12, 16:09   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by hansl View Post
Um, if p is prime, isn't the answer always p-1?
edit: nevermind, i'm obviously confused
If p is prime (which we are assuming), then the answer divides p-1. Figuring out which divisor it is, that’s the heart of the problem.
CRGreathouse is offline   Reply With Quote
Old 2019-06-12, 17:46   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
If p is prime (which we are assuming), then the answer divides p-1. Figuring out which divisor it is, that’s the heart of the problem.
No, the hard part is the factorization of p-1, if you know that then you need only polynomial time to find the order! One easy way, but you can still improve it a little: for each q^e exact primepower divisor of (p-1) find the exponent of q in the order by testing:
Code:
res_i=2^((p-1)/q^i) mod p for i=e,e-1,..1,0
if k=i is the largest i for that res_i=1 then the exponent of q in the order is e-k.
Multiply these primepowers to get the order.

Note that you really need some intelligence here also, because there could be more than polynomial number of divisors of p-1.
R. Gerbicz is offline   Reply With Quote
Old 2019-06-12, 19:02   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·5·229 Posts
Default

Quote:
Originally Posted by JM Montolio A View Post
whats is a fast algorithm for compute znorder(Mod(2,p)).
for p prime but big.
Fast algorithm (!) :
  • Open Pari/GP
  • Type: znorder(Mod(2,p))
  • ????
  • PROFIT!!!
Batalov is offline   Reply With Quote
Old 2019-06-13, 11:46   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

73438 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The basic idea is to factor m = p-1 into q_1^e_1 * q_2^e_2 * ... * q_k^e_k and then test if Mod(2,p)^(m/q_1), Mod(2,p)^(m/q_2), etc. are 1. If Mod(2,p)^(m/q_i) is 1 then try Mod(2,p)^(m/q_i^2), ..., until either you hit q_i^e_i or the residue is no longer 1. Divide m by the largest q_i^e that left a result of 1 and continue with q_{i+1}.

For example, let's try to find the order of 2 mod 101. m = 100 = 2^2 * 5^2, so we know that 2^100 = 1 mod 101. 2^(100/2) mod 101 is 100 which is not 1, so skip 2. 2^(100/5) = 95 which is not 1, so skip 5, and we're done: the order is 100.

Let's try 103. m = 102 = 2 * 3 * 17. 2^(102/2) = 1 mod 103, so m becomes 102/2 = 51. We don't have any more 2s though so we'll go on to 3. 2^(51/3) = 56 mod 103 which is not 1, and 2^(51/17) = 8 mod 103 which is also not 1, so we're done: the order of 2 mod 103 is 51.
The method of dividing prime factors out of the exponent p-1 is as fast as any I know of, with one exception.

As is well known (supplement to the quadratic reciprocity law), znorder(Mod(2,p)) divides (p-1)/2 if p == 1 or 7 (mod 8), but not otherwise. Since 101 == 5 (mod 8) we know that znorder(Mod(2,101)) does not divide 100/2 = 50. Since 103 = 7 (mod 8) we know that znorder(Mod(2,103)) does divide 102/2 = 51.

Alas, the classical criterion of when znorderMod(2,p)) divides (p-1)/4 when 8 divides p-1 [p = x^2 + 64*y^2] likely takes longer to decide than whether Mod(2,p)^((p-1)/4) == Mod(1,p).

Likewise, the classical criterion for whether znorder(Mod(2,p)) divides (p-1)/3 when 3 divides p-1 [p = x^2 + 27*y^2] is likely also slower than computing Mod(2,p)^(p-1)/3 when 3 divides p-1.
Dr Sardonicus is offline   Reply With Quote
Old 2019-06-14, 03:13   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
No, the hard part is the factorization of p-1, if you know that then you need only polynomial time
We’re not disagreeing here of course: the factorization takes up asymptotically all the time (in the worst/average case), but for me the heart of the problem is what I described in my post, and the factorization is a (difficult) subproblem that must be resolved before moving on to that core part.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
Whats the next prime? Dougal Puzzles 5 2009-08-23 20:16
Whats the best stress test settings for RAM stability? xtreme2k Hardware 6 2007-03-28 20:38
Whats going on in the background ltd Prime Sierpinski Project 2 2006-12-26 09:40
Whats the worst (harshest scenario) for torture test? xtreme2k Hardware 9 2004-07-14 18:41

All times are UTC. The time now is 17:36.

Sat Nov 28 17:36:49 UTC 2020 up 79 days, 14:47, 4 users, load averages: 1.85, 1.56, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.