Loading ...
Sorry, an error occurred while loading the content.
 

Re: slow method for the order of 2

Expand Messages
  • djbroadhurst
    ... 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
      --- In primenumbers@yahoogroups.com,
      "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.