mersenneforum.org Whats is a fast algorithm for compute znorder(Mod(2,p)).
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-07, 11:36 #1 JM Montolio A   Feb 2018 25·3 Posts 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
2018-03-07, 11:40   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

202618 Posts

Quote:
 Originally Posted by JM Montolio A whats is a fast algorithm for compute nzorder(Mod(2,p)). for p prime but big.
I think you mean znorder.

 2018-03-07, 11:46 #3 JM Montolio A   Feb 2018 11000002 Posts You never sleeps ?
2018-03-07, 15:10   #4
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by JM Montolio A 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.

 2018-03-07, 17:15 #5 CRGreathouse     Aug 2006 2×2,969 Posts 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.
 2019-06-12, 01:44 #6 hansl     Apr 2019 110011012 Posts 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
2019-06-12, 16:09   #7
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by hansl 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.

2019-06-12, 17:46   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2019-06-12, 19:02   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·32·509 Posts

Quote:
 Originally Posted by JM Montolio A 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!!!

2019-06-13, 11:46   #10
Dr Sardonicus

Feb 2017
Nowhere

24×239 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2019-06-14, 03:13   #11
CRGreathouse

Aug 2006

134628 Posts

Quote:
 Originally Posted by R. Gerbicz 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 35 2016-12-11 00:57 Dougal Puzzles 5 2009-08-23 20:16 xtreme2k Hardware 6 2007-03-28 20:38 ltd Prime Sierpinski Project 2 2006-12-26 09:40 xtreme2k Hardware 9 2004-07-14 18:41

All times are UTC. The time now is 03:01.

Tue Dec 1 03:01:57 UTC 2020 up 82 days, 12 mins, 1 user, load averages: 1.52, 1.61, 1.75