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

Question on power residues...

Expand Messages
  • David Cleaver
    Hello everyone, I was wondering if there was a way to use power residues to factor numbers. Let me give an example: Lets say we happen to know that: 2^23 ==
    Message 1 of 6 , Jun 2, 2004
    • 0 Attachment
      Hello everyone,

      I was wondering if there was a way to use power residues to factor numbers.
      Let me give an example:
      Lets say we happen to know that:
      2^23 == 536 mod 1071
      2^695 == 536 mod 1071
      2^71 == 536 mod 1071

      I was wondering if there was a way we could use any of the above
      information to factor the number 1071. I know 1071 = 3*3*7*17, but I want
      to develop a general algorithm, and in order to do so I have to figure out
      this part first.

      I know that gcd(x, 1071) = 1071
      [where x = {2^71 - 2^23, 2^695 - 2^71, 2^695 - 2^23}] so that doesn't give
      us any useful information. Taking the first x, 2^71 - 2^23, we could
      divide out 2^23 and get 2^48-1. After this we would have:
      2^48 == 1 mod 1071.
      Could we use this info to somehow factor the number?

      Also, something I just noticed, can we use the exponents in the gcd to get
      factors? Because:
      gcd(71 - 23, 1071) = 3
      gcd(695 - 71, 1071) = 3
      gcd(695 - 23, 1071) = 21
      I'm not necessarily looking for prime factors, just any factor will do.
      Will this property with the exponents always hold whenever we have
      congruences that are equal. Thanks for any info.

      -David C.
    • richard_heylen
      ... numbers. ... From this we know that 2^48 == 1 mod 1071 and I believe that the vast majority of the time, once you know the non-trivial order of any number
      Message 2 of 6 , Jun 7, 2004
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
        wrote:
        > Hello everyone,
        >
        > I was wondering if there was a way to use power residues to factor
        numbers.
        > Let me give an example:
        > Lets say we happen to know that:
        > 2^23 == 536 mod 1071
        > 2^71 == 536 mod 1071

        From this we know that 2^48 == 1 mod 1071 and I believe that the vast
        majority of the time, once you know the non-trivial order of any
        number modulo a composite then the composite is easily factored.

        I'm not sure that this result is completely in the bag in the cases
        where you know the highly composite order of some base to which the
        number is a strong psuedoprime. For instance, you may know that
        2 ^ 242 == 1 mod 2047 but gcd((2^121-1),2047) does not give a factor.
        In my current sleep-deprived state, it's not clear to me what the
        best way is to proceed in this case in general.

        Richard Heylen

        Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69,
        103-109, 1996.
      • David Cleaver
        ... Yeah, it looks like this method will not work when the numbers is of the form ((2^prime) - 1). However, this may be the only class of numbers that this
        Message 3 of 6 , Jun 8, 2004
        • 0 Attachment
          richard_heylen wrote:
          >
          > David Cleaver wrote:
          > > Hello everyone,
          > >
          > > I was wondering if there was a way to use power residues to factor
          > numbers.
          > > Let me give an example:
          > > Lets say we happen to know that:
          > > 2^23 == 536 mod 1071
          > > 2^71 == 536 mod 1071
          >
          > > From this we know that 2^48 == 1 mod 1071 and I believe that the vast
          > > majority of the time, once you know the non-trivial order of any
          > > number modulo a composite then the composite is easily factored.
          >
          > I'm not sure that this result is completely in the bag in the cases
          > where you know the highly composite order of some base to which the
          > number is a strong psuedoprime. For instance, you may know that
          > 2 ^ 242 == 1 mod 2047 but gcd((2^121-1),2047) does not give a factor.
          > In my current sleep-deprived state, it's not clear to me what the
          > best way is to proceed in this case in general.
          >
          > Richard Heylen
          >
          > Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69,
          > 103-109, 1996.

          Yeah, it looks like this method will not work when the numbers is of the
          form ((2^prime) - 1). However, this may be the only class of numbers that
          this method is unnable to factor. If you can think of any other numbers
          that might have this property, or if you know of any numbers that can never
          be factored by the pollard-rho algorithm, please let me know. Thanks for
          your input so far.

          -David C.
        • richard_heylen
          ... As I implied, any strong base 2 psuedoprime will do. So from http://www.research.att.com/cgi- bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
          Message 4 of 6 , Jun 8, 2004
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
            wrote:
            >
            > Yeah, it looks like this method will not work
            > when the numbers is of the form ((2^prime) - 1).
            > However, this may be the only class of numbers
            > that this method is unnable to factor. If you
            > can think of any other numbers that might have
            > this property, or if you know of any numbers that
            > can never be factored by the pollard-rho algorithm,
            > please let me know. Thanks for your input so far.

            As I implied, any strong base 2 psuedoprime will do.
            So from

            http://www.research.att.com/cgi-
            bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262

            2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
            65281,74665,80581,85489,88357,90751,104653,130561,196093,
            220729,233017,252601,253241,256999,271951,280601,314821,
            357761,390937,458989,476971,486737

            Richard Heylen
          • Milton Brown
            Residues for the Powers of Prime numbers are discussed in detail in Elementary Number Theory by Jones and Jones with a separate section on page 135. You
            Message 5 of 6 , Jun 8, 2004
            • 0 Attachment
              Residues for the Powers of Prime numbers are discussed
              in detail in "Elementary Number Theory" by Jones and Jones
              with a separate section on page 135.

              You should look there, instead of suggesting that some new
              theory is being developed here.

              Milton L. Brown
              miltbrown at earthlink.net
              miltbrown@...


              > [Original Message]
              > From: richard_heylen <rick.heylen@...>
              > To: <primenumbers@yahoogroups.com>
              > Date: 6/8/2004 5:24:23 AM
              > Subject: [PrimeNumbers] Re: Question on power residues...
              >
              > --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
              > wrote:
              > >
              > > Yeah, it looks like this method will not work
              > > when the numbers is of the form ((2^prime) - 1).
              > > However, this may be the only class of numbers
              > > that this method is unnable to factor. If you
              > > can think of any other numbers that might have
              > > this property, or if you know of any numbers that
              > > can never be factored by the pollard-rho algorithm,
              > > please let me know. Thanks for your input so far.
              >
              > As I implied, any strong base 2 psuedoprime will do.
              > So from
              >
              > http://www.research.att.com/cgi-
              > bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
              >
              > 2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
              > 65281,74665,80581,85489,88357,90751,104653,130561,196093,
              > 220729,233017,252601,253241,256999,271951,280601,314821,
              > 357761,390937,458989,476971,486737
              >
              > Richard Heylen
              >
              >
              >
              >
              >
              > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              > The Prime Pages : http://www.primepages.org/
              >
              >
              > Yahoo! Groups Links
              >
              >
              >
              >
            • pbtoau
              Milton, Your first paragraph is very helpful. Your second paragraph has an unfortunate condescending tone. I know people are frequently thinking they have
              Message 6 of 6 , Jun 8, 2004
              • 0 Attachment
                Milton,

                Your first paragraph is very helpful. Your second paragraph has an
                unfortunate condescending tone. I know people are frequently
                thinking they have discovered something new that is 400 years old.
                It is great to point them to the earlier work, but I do not want
                people to be afraid to post to the list because they might be subtly
                ridiculed.

                Best regards,

                David

                --- In primenumbers@yahoogroups.com, "Milton Brown" <miltbrown@e...>
                wrote:
                >
                > Residues for the Powers of Prime numbers are discussed
                > in detail in "Elementary Number Theory" by Jones and Jones
                > with a separate section on page 135.
                >
                > You should look there, instead of suggesting that some new
                > theory is being developed here.
                >
                > Milton L. Brown
                > miltbrown at earthlink.net
                > miltbrown@e...
                >
                >
                > > [Original Message]
                > > From: richard_heylen <rick.heylen@m...>
                > > To: <primenumbers@yahoogroups.com>
                > > Date: 6/8/2004 5:24:23 AM
                > > Subject: [PrimeNumbers] Re: Question on power residues...
                > >
                > > --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
                > > wrote:
                > > >
                > > > Yeah, it looks like this method will not work
                > > > when the numbers is of the form ((2^prime) - 1).
                > > > However, this may be the only class of numbers
                > > > that this method is unnable to factor. If you
                > > > can think of any other numbers that might have
                > > > this property, or if you know of any numbers that
                > > > can never be factored by the pollard-rho algorithm,
                > > > please let me know. Thanks for your input so far.
                > >
                > > As I implied, any strong base 2 psuedoprime will do.
                > > So from
                > >
                > > http://www.research.att.com/cgi-
                > > bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
                > >
                > > 2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
                > > 65281,74665,80581,85489,88357,90751,104653,130561,196093,
                > > 220729,233017,252601,253241,256999,271951,280601,314821,
                > > 357761,390937,458989,476971,486737
                > >
                > > Richard Heylen
                > >
                > >
                > >
                > >
                > >
                > > Unsubscribe by an email to: primenumbers-
                unsubscribe@yahoogroups.com
                > > The Prime Pages : http://www.primepages.org/
                > >
                > >
                > > Yahoo! Groups Links
                > >
                > >
                > >
                > >
              Your message has been successfully submitted and would be delivered to recipients shortly.