Re: slow method for the order of 2

Expand Messages
• ... The proof that your method works is very easy. For odd n 1, the k-th term in your sequence is congruent to 2^(1-k) - 1 modulo n, as is easily proven by
Message 1 of 2 , Jun 3, 2010
"rach" <maths_forall@...> wrote:

> this conjecture

The proof that your method works is very easy.
For odd n > 1, the k-th term in your sequence is congruent to
2^(1-k) - 1 modulo n, as is easily proven by induction.
Thus the first term that is congruent to 1 modulo n occurs
when k is the order of 2 modulo n.

Example, with n = 23:

print(vector(11,k,2^(1-k)-1)%23);
[0, 11, 5, 2, 12, 17, 8, 15, 7, 3, 1]

So there is no "conjecture": just a trivial proof that you
find the correct order by performing a total number of
divisions by 2 that is one less than the order.

As I remarked, Pari-GP is 500000 times faster in the case of
n = 8988229, because it exploits the fact that znorder(Mod(2,n))
is a divisor of eulerphi(n). In this case, n is prime and
hence the order is a divisor of
eulerphi(n) = n - 1 = 2^2*3^2*61*4093.
To prove that the order is in fact n - 1, in this case,
we need to prove that 2^((n-1)/d) is not congruent to 1 modulo n
for any of the prime divisors d = 2, 3, 61, 4093 of eulerphi(n).
We do may do this by binary modular exponentiation:

n=8988229;
for(j=1,4,d=[2,3,61,4093][j];if(Mod(2,n)^((n-1)/d)==1,print(fail)));

[no failures]

This took 8 microseconds. Your method took 8 seconds.

David
Your message has been successfully submitted and would be delivered to recipients shortly.