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

thanks david

Expand Messages
  • rach
    yes david but differences between these two methods ! for example n = 23 with my method = 23 11 5 2 12 17 8 15 7 3 1 then 2^11-1 = 0 mod 23 I searsh the
    Message 1 of 2 , Jun 3, 2010
    • 0 Attachment
      yes david

      but differences between these two methods !
      for example

      n = 23
      with my method
      = 23 11 5 2 12 17 8 15 7 3 1
      then 2^11-1 = 0 mod 23
      I searsh the nearest divider


      using your method
      n = 23 = 2 1 6 3 13 18 9 8 4 2 1 12 6 3 13 18 9 8 4 2 1
      is the opposite of your method
      ----------------------------

      > http://www.1athlet.com

      For odd n > 1, the application computes the order
      of 2 modulo n by the following very slow method:

      ord(n)=local(m=n,c);while(m,c++;m=(m+if(m%2,0,n)-1)/2);c;

      With n = 8988229, it took 8 seconds:

      gettime;print(ord(8988229)" in "round(gettime/10^3)" seconds");
      8988228 in 8 seconds

      By comparison, Pari-GP's "znorder" is 500000 times faster,
      as I here show by computing the order 1000 times:

      gettime;for(k=1,1000,ans=znorder(Mod(2,8988229)));
      print(ans" in "gettime" microseconds");
      8988228 in 15 microseconds

      Here is a test that the slow method works up to n = 33333:

      forstep(n=3,33333,2,if(ord(n)!=znorder(Mod(2,n)),print(n)));
      [the rest is silence]

      David
    • djbroadhurst
      ... Not so. This was my encoding of your ultra-slow method: ord(n)=local(m=n,c);while(m,c++;m=(m+if(m%2,0,n)-1)/2);c; Let s add some print statements:
      Message 2 of 2 , Jun 3, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "rach" <maths_forall@...> wrote:

        > but differences between these two methods

        Not so. This was my encoding of your ultra-slow method:

        ord(n)=local(m=n,c);while(m,c++;m=(m+if(m%2,0,n)-1)/2);c;

        Let's add some print statements:

        {ord2(n)=local(m=n,c);
        while(m,c++;print1(m" ");m=(m+if(m%2,0,n)-1)/2);
        print(": order of 2 modulo "n" = "c);c;}

        Then, with n=23, we obtain:

        ord2(23);
        23 11 5 2 12 17 8 15 7 3 1 : order of 2 modulo 23 = 11

        which is /precisely/ your ultra-slow method.

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