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

Modulo order

Expand Messages
  • Jose Ramón Brox
    Hi: The order of a number n modulo p (with GCD(n,p)=1) is defined as the smallest exponent e such that n^e == 1 (mod p). Is there a straight way to find the
    Message 1 of 6 , Jul 3, 2004
    • 0 Attachment
      Hi:

      The order of a number n modulo p (with GCD(n,p)=1) is defined as the smallest exponent e such that n^e == 1 (mod p).

      Is there a straight way to find the order different from doing 1/n in base p and counting the length of the period?

      Jose Brox
      http://espanol.groups.yahoo.com/group/Telecomunicacion/
      (www.brox.tk)
      ambroxius@...
      MSN Messenger: artifex_ad_infinitum@...



      [Non-text portions of this message have been removed]
    • Joseph Moore
      ... Yes, somewhat. The order of n mod p is in the set of the proper divisors of p-1. However, finding *which* of the proper divisors of p-1 is an order of n
      Message 2 of 6 , Jul 3, 2004
      • 0 Attachment
        --- Jose_Ram�n_Brox <ambroxius@...> wrote:
        > Hi:
        >
        > The order of a number n modulo p (with GCD(n,p)=1)
        > is defined as the smallest exponent e such that n^e
        > == 1 (mod p).
        >
        > Is there a straight way to find the order different
        > from doing 1/n in base p and counting the length of
        > the period?

        Yes, somewhat. The order of n mod p is in the set of
        the proper divisors of p-1. However, finding *which*
        of the proper divisors of p-1 is an order of n can be
        a challenge. For instance, 4 has order 3 mod 7, while
        5 has order 6 mod 7.

        >
        > Jose Brox
        >



        __________________________________
        Do you Yahoo!?
        Take Yahoo! Mail with you! Get it on your mobile phone.
        http://mobile.yahoo.com/maildemo
      • joseph_osiecki
        Can someone give me some more details on working out the order of an element mod p when we have a factorization of p-1? Please use the following example p =
        Message 3 of 6 , Jul 6, 2004
        • 0 Attachment
          Can someone give me some more details on working out the order of an
          element mod p when we have a factorization of p-1?
          Please use the following example p = 176963110569601 =
          2^7*3*5^2*151*1367*89303 = 1. The order of 2 is 22120388821200.
          But why? How would I compute this from the factorization of p-1?


          --- In primenumbers@yahoogroups.com, Joseph Moore <jtpk@y...> wrote:
          > --- Jose_Ramón_Brox <ambroxius@t...> wrote:
          > > Hi:
          > >
          > > The order of a number n modulo p (with GCD(n,p)=1)
          > > is defined as the smallest exponent e such that n^e
          > > == 1 (mod p).
          > >
          > > Is there a straight way to find the order different
          > > from doing 1/n in base p and counting the length of
          > > the period?
          >
          > Yes, somewhat. The order of n mod p is in the set of
          > the proper divisors of p-1. However, finding *which*
          > of the proper divisors of p-1 is an order of n can be
          > a challenge. For instance, 4 has order 3 mod 7, while
          > 5 has order 6 mod 7.
          >
          > >
          > > Jose Brox
          > >
          >
          >
          >
          > __________________________________
          > Do you Yahoo!?
          > Take Yahoo! Mail with you! Get it on your mobile phone.
          > http://mobile.yahoo.com/maildemo
        • Joseph Moore
          First, I was partly wrong. *Any* factor of p-1 could be the order of n mod p. One thing to do is cycle through the factors of p-1. In this case,
          Message 4 of 6 , Jul 6, 2004
          • 0 Attachment
            First, I was partly wrong. *Any* factor of p-1 could
            be the order of n mod p.

            One thing to do is cycle through the factors of p-1.
            In this case, 22120388821200*8+1=p, so we see that 2
            has order 2^4*3*5^2*151*1367*89303. Note that the
            multiplicative inverse of n mod p has the same order
            as n mod p.

            I'm sure there's a more efficient way to get the order
            than by cycling through all the factors, but that's a
            start.

            Joseph.


            --- joseph_osiecki <osieckis@...> wrote:
            > Can someone give me some more details on working out
            > the order of an
            > element mod p when we have a factorization of p-1?
            > Please use the following example p = 176963110569601
            > =
            > 2^7*3*5^2*151*1367*89303 + 1. The order of 2 is
            > 22120388821200.
            > But why? How would I compute this from the
            > factorization of p-1?




            __________________________________
            Do you Yahoo!?
            Yahoo! Mail - Helps protect you from nasty viruses.
            http://promotions.yahoo.com/new_mail
          • elevensmooth
            ... an ... The best way I know is to start with N=p-1 and trial divide by each prime factor q of N. If 2^(N/q) = 1 mod p, then replace N by N/q and
            Message 5 of 6 , Jul 7, 2004
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "joseph_osiecki" <osieckis@n...>
              wrote:
              > Can someone give me some more details on working out the order of
              an
              > element mod p when we have a factorization of p-1?
              > Please use the following example p = 176963110569601 =
              > 2^7*3*5^2*151*1367*89303 = 1. The order of 2 is 22120388821200.
              > But why? How would I compute this from the factorization of p-1?

              The best way I know is to start with N=p-1 and trial divide by each
              prime factor "q" of N. If 2^(N/q) = 1 mod p, then replace N by N/q
              and continue. In your example, trial division by 2 works the first 3
              times. Trial division by the other primes fails.

              I do this whenever the ElevenSmooth Special Project finds a new
              divisor. These factors are found as divisors of 2^3326400-1, so I
              know the order is a divisor of GCD(3326400, p-1). I use this process
              to find the order of 2, which tells me for which Mersenne number the
              prime is a primitive factor. I then tell Will Edgington and post it
              on the ElevenSmooth factors page at
              http://ElevenSmooth.com/ElevenFactors.html

              William
              ==================
              ElevenSmooth http://ElevenSmooth.com
              Distributed Factoring of 2^3326400-1
            • Kevin Acres
              Hi, I have two experimental methods under investigation for this problem. One is the reverse algorithm as mentioned a week or so back. A second method
              Message 6 of 6 , Jul 7, 2004
              • 0 Attachment
                Hi,

                I have two experimental methods under investigation for this problem.

                One is the 'reverse algorithm' as mentioned a week or so back.

                A second method involves growing a 'binary tree'. This works from
                knowing that the final modulo result in a trial factorisation is 1.
                From this you can grow a tree, which will eventually give you the
                number that you want.

                The trick with the tree is to spot non-fruitful branches and to 'prune
                them'. You also need to control the growth of the tree, since there
                are many possible results, which are multiples of the one that you
                want. The terminal condition for any branch of the tree is to trial
                factor the number that you just generated and to check for a modulo 1
                result.

                Once you have grown a few trees then you will start to see the 1's and
                0's of the binary representation of a number as a series of decision
                points. From that you can start to appreciate that the final order 2
                is as much a result of the spacings of 1's and 0's of the original
                number as anything else.

                The whole trick with this approach is to grow each branch one level at
                a time. This prevents uncontrolled growth of any one branch. Another
                thing is to watch out for repeating sequences, these need weeding out
                too.

                Kevin.


                > --- In primenumbers@yahoogroups.com, "joseph_osiecki" <osieckis@n...>
                > wrote:
                > > Can someone give me some more details on working out the order of
                > an
                > > element mod p when we have a factorization of p-1?
                > > Please use the following example p = 176963110569601 =
                > > 2^7*3*5^2*151*1367*89303 = 1. The order of 2 is
                22120388821200.
                > > But why? How would I compute this from the factorization of p-1?
                >
                > The best way I know is to start with N=p-1 and trial divide by each
                > prime factor "q" of N. If 2^(N/q) = 1 mod p, then replace N by N/q
                > and continue. In your example, trial division by 2 works the first 3
                > times. Trial division by the other primes fails.
                >
                > I do this whenever the ElevenSmooth Special Project finds a new
                > divisor. These factors are found as divisors of 2^3326400-1, so I
                > know the order is a divisor of GCD(3326400, p-1). I use this process
                > to find the order of 2, which tells me for which Mersenne number the
                > prime is a primitive factor. I then tell Will Edgington and post it
                > on the ElevenSmooth factors page at
                > http://ElevenSmooth.com/ElevenFactors.html
                >
                > William
                > ==================
                > ElevenSmooth http://ElevenSmooth.com
                > Distributed Factoring of 2^3326400-1
                >
              Your message has been successfully submitted and would be delivered to recipients shortly.