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

Is there a quick method of doing this

Expand Messages
  • Kevin Acres
    I am wondering if there is a quick way to work out all numbers such that: x^2 = y mod(z) where x is any positive integer less than z? Kevin.
    Message 1 of 11 , Jul 11, 2004
      I am wondering if there is a quick way to work out all numbers such
      that:

      x^2 = y mod(z)

      where x is any positive integer less than z?


      Kevin.
    • Kevin Acres
      Hi Mark, Thanks for responding. So I have to go to floating point for this then? I do know both y and z, and the limits on x are that it must be less than z.
      Message 2 of 11 , Jul 11, 2004
        Hi Mark,

        Thanks for responding.

        So I have to go to floating point for this then?

        I do know both y and z, and the limits on x are that it must be less
        than z.

        Just so you know, I am implementing an algorithm that finds the
        smallest exponent in a given base such that a divides (b^n)-1. Whether
        this will ever turn out to be useful or not, I have no idea. However,
        the algorithm works, it's just pretty slow at the moment.


        Best Regards,

        Kevin.



        > On Sunday, July 11, 2004, at 06:56 PM, Kevin Acres wrote:
        > > I am wondering if there is a quick way to work out all numbers such
        > > that:
        > >
        > > x^2 = y mod(z)
        > >
        > > where x is any positive integer less than z?
        > >
        > >
        > > Kevin.
        >
        > If you know y and z, then you can use a discrete log.
        >
        >
        >
      • Mark Rodenkirch
        ... No, a discrete log can be easily written with the use of floating point. The following link explains discrete logs and few ways to code them.
        Message 3 of 11 , Jul 11, 2004
          On Sunday, July 11, 2004, at 07:31 PM, Kevin Acres wrote:

          > Hi Mark,
          >
          > Thanks for responding.
          >
          > So I have to go to floating point for this then?
          >
          > I do know both y and z, and the limits on x are that it must be less
          > than z.
          >
          > Just so you know, I am implementing an algorithm that finds the
          > smallest exponent in a given base such that a divides (b^n)-1. Whether
          > this will ever turn out to be useful or not, I have no idea. However,
          > the algorithm works, it's just pretty slow at the moment.
          >
          >
          > Best Regards,
          >
          > Kevin.

          No, a discrete log can be easily written with the use of floating
          point. The following link explains discrete logs and few ways to code
          them.

          http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf

          --Mark
        • Carl Devore
          ... I think the more significant point is that link, in section 3.5, explains in great detail how to compute square roots in Z[n].
          Message 4 of 11 , Jul 11, 2004
            On Sun, 11 Jul 2004, Mark Rodenkirch wrote:
            > No, a discrete log can be easily written with the use of floating
            > point. The following link explains discrete logs and few ways to code
            > them.
            >
            > http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf

            I think the more significant point is that link, in section 3.5, explains
            in great detail how to compute square roots in Z[n].
          • Kevin Acres
            Hi, One of my main problems here is that I haven t studied any maths for about 30 years now. So I ve a little bit of catching up to do. Having said that, I
            Message 5 of 11 , Jul 12, 2004
              Hi,

              One of my main problems here is that I haven't studied any maths for about
              30 years now. So I've a little bit of catching up to do.

              Having said that, I noticed that I can take a shortcut to most of what I
              wanted to do insomuch as I only need to calculate the instances of:

              x^2 = 1 mod y

              for x less than y

              Obviously the trivial results are x = 1 and x = y-1, I just need to find
              out how to determine the others (if any).

              Regards,

              Kevin.




              At 03:47 PM 12/07/2004, Carl Devore wrote:
              >On Sun, 11 Jul 2004, Mark Rodenkirch wrote:
              > > No, a discrete log can be easily written with the use of floating
              > > point. The following link explains discrete logs and few ways to code
              > > them.
              > >
              > > http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf
              >
              >I think the more significant point is that link, in section 3.5, explains
              >in great detail how to compute square roots in Z[n].
              >
              >
              >
              >
              >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              >The Prime Pages : http://www.primepages.org/
              >
              >
              >Yahoo! Groups Links
              >
              >
              >
              >
            • Carl Devore
              ... There will never be any other solutions.
              Message 6 of 11 , Jul 12, 2004
                On Mon, 12 Jul 2004, Kevin Acres wrote:
                > I only need to calculate the instances of:
                > x^2 = 1 mod y
                > Obviously the trivial results are x = 1 and x = y-1, I just need to find
                > out how to determine the others (if any).

                There will never be any other solutions.
              • Paul Leyland
                ... Do you really, really mean that? What is 4^2 mod 15? What is 11^2 mod 15? Explain your reasoning. I do, of course, know what is going on. It will be
                Message 7 of 11 , Jul 12, 2004
                  On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
                  > On Mon, 12 Jul 2004, Kevin Acres wrote:
                  > > I only need to calculate the instances of:
                  > > x^2 = 1 mod y
                  > > Obviously the trivial results are x = 1 and x = y-1, I just need to find
                  > > out how to determine the others (if any).
                  >
                  > There will never be any other solutions.

                  Do you really, really mean that?

                  What is 4^2 mod 15? What is 11^2 mod 15?

                  Explain your reasoning.


                  I do, of course, know what is going on. It will be educational for all
                  concerned if Carl and Kevin work it out for themselves.


                  Paul
                • Paul Leyland
                  ... Since dashing off that rapid response, it s occurred to me that it would also be educational to work out why the Rabin cryptosystem works and why there are
                  Message 8 of 11 , Jul 12, 2004
                    On Mon, 2004-07-12 at 13:27, Paul Leyland wrote:
                    > On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
                    > > On Mon, 12 Jul 2004, Kevin Acres wrote:
                    > > > I only need to calculate the instances of:
                    > > > x^2 = 1 mod y
                    > > > Obviously the trivial results are x = 1 and x = y-1, I just need to find
                    > > > out how to determine the others (if any).
                    > >
                    > > There will never be any other solutions.
                    >
                    > Do you really, really mean that?
                    >
                    > What is 4^2 mod 15? What is 11^2 mod 15?
                    >
                    > Explain your reasoning.
                    >
                    >
                    > I do, of course, know what is going on. It will be educational for all
                    > concerned if Carl and Kevin work it out for themselves.

                    Since dashing off that rapid response, it's occurred to me that it would
                    also be educational to work out why the Rabin cryptosystem works and why
                    there are certain composite numbers that the Quadratic Sieve algorithm
                    can not factor.


                    Paul
                  • Carl Devore
                    ... Of course I was wrong. I neglected the casea where y is not prime. In general, you must factor y.
                    Message 9 of 11 , Jul 12, 2004
                      On 12 Jul 2004, Paul Leyland wrote:
                      > On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
                      > > On Mon, 12 Jul 2004, Kevin Acres wrote:
                      > > > I only need to calculate the instances of:
                      > > > x^2 = 1 mod y
                      > > > Obviously the trivial results are x = 1 and x = y-1, I just need to find
                      > > > out how to determine the others (if any).
                      > > There will never be any other solutions.
                      >
                      > Do you really, really mean that?
                      > What is 4^2 mod 15? What is 11^2 mod 15?
                      > Explain your reasoning.

                      Of course I was wrong. I neglected the casea where y is not prime. In
                      general, you must factor y.
                    • Paul Leyland
                      ... Well done! Not only have you explained your mistake, you have done so in a manner that has given away the minimum necessary, thereby letting others work it
                      Message 10 of 11 , Jul 12, 2004
                        On Mon, 2004-07-12 at 17:48, Carl Devore wrote:

                        > > Do you really, really mean that?
                        > > What is 4^2 mod 15? What is 11^2 mod 15?
                        > > Explain your reasoning.
                        >
                        > Of course I was wrong. I neglected the casea where y is not prime. In
                        > general, you must factor y.

                        Well done!

                        Not only have you explained your mistake, you have done so in a manner
                        that has given away the minimum necessary, thereby letting others work
                        it out for themselves without too many clues.


                        Paul
                      • Kevin Acres
                        Hi, I ll explain what is happening and hence why the question. Since re-discovering Will s reverse algorithm I have been trying to implement a faster
                        Message 11 of 11 , Jul 12, 2004
                          Hi,

                          I'll explain what is happening and hence why the question.

                          Since re-discovering Will's 'reverse algorithm' I have been trying to
                          implement a faster version. Although I have been re-creating the
                          smallest a^n - 1 that is divisible by a given number in less than a
                          second for a^n-1 up to about 2^50,000,000 - 1.

                          My latest attempt was to build a binary tree that reversed the trial
                          division method. i.e. start up with x^2 = 1 mod y and work up from
                          there.

                          Then I realised that for non-primes I was getting four entries in the
                          first level of the tree. Notably x = 1 and x = y -1.

                          Looking at specifics I noticed that the first level for 2047 gave me
                          1, 622, 1425 and 2046. A little investigation showed me that gcd
                          (2047, 622+1) gave me 89 and gcd(2047, 622-1) gave me 23 or the
                          factors of 2047.

                          This tends to suggest that I've just re-arrived at the factoring
                          problem from a different direction.

                          But, being a novice at this, it was interesting whilst it lasted :-)

                          Kevin.


                          > On Mon, 2004-07-12 at 13:27, Paul Leyland wrote:
                          > > On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
                          > > > On Mon, 12 Jul 2004, Kevin Acres wrote:
                          > > > > I only need to calculate the instances of:
                          > > > > x^2 = 1 mod y
                          > > > > Obviously the trivial results are x = 1 and x = y-1, I just
                          need to find
                          > > > > out how to determine the others (if any).
                          > > >
                          > > > There will never be any other solutions.
                          > >
                          > > Do you really, really mean that?
                          > >
                          > > What is 4^2 mod 15? What is 11^2 mod 15?
                          > >
                          > > Explain your reasoning.
                          > >
                          > >
                          > > I do, of course, know what is going on. It will be educational
                          for all
                          > > concerned if Carl and Kevin work it out for themselves.
                          >
                          > Since dashing off that rapid response, it's occurred to me that it
                          would
                          > also be educational to work out why the Rabin cryptosystem works and
                          why
                          > there are certain composite numbers that the Quadratic Sieve
                          algorithm
                          > can not factor.
                          >
                          >
                          > Paul
                          >
                          >
                          >
                          >
                          > ------------------------ Yahoo! Groups Sponsor --------------------~-
                          ->
                          > Yahoo! Domains - Claim yours for only $14.70
                          > http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/8HYolB/TM
                          > --------------------------------------------------------------------
                          ~->
                          >
                          > 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.