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

[JM Montolio A]

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

[science_man_88]

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.

[JM Montolio A]

You never sleeps ?

[CRGreathouse]

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.

[CRGreathouse]

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.

[hansl]

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

[CRGreathouse]

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.

[R. Gerbicz]

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:

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.

[Batalov]

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!!!

[Dr Sardonicus]

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.

[CRGreathouse]

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.