Re: slow method for the order of 2
- --- In firstname.lastname@example.org,
"rach" <maths_forall@...> wrote:
> this conjectureThe 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:
[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:
This took 8 microseconds. Your method took 8 seconds.