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

How is this true!

Expand Messages
  • bharath ERakajj
    Hi, Let p & q be primes such that q devides p-1. I want to find r & x when I know y, t in the following equation. y = r(x+t) mod q, Here, r,x,t all belong to
    Message 1 of 8 , May 30, 2002
    • 0 Attachment
      Hi,

      Let p & q be primes such that q devides p-1.
      I want to find r & x when I know y, t in the following equation.

      y = r(x+t) mod q,

      Here, r,x,t all belong to Zq* { multiplicative group}

      I came to know that there are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1.

      How is this true? I want to know the detailed explanation.


      Thanks,
      Lovebharath





      ---------------------------------
      Do You Yahoo!?
      Yahoo! - Official partner of 2002 FIFA World Cup

      [Non-text portions of this message have been removed]
    • Phil Carmody
      ... So if you fix q then you ve not uniquely defined p. ... So you ve fixed q, then? ... But p doesn t have a uniquely defined value, as as yet indeterminate.
      Message 2 of 8 , May 31, 2002
      • 0 Attachment
        --- bharath ERakajj <lovebharath@...> wrote:
        >
        > Hi,
        >
        > Let p & q be primes such that q devides p-1.

        So if you fix q then you've not uniquely defined p.

        > I want to find r & x when I know y, t in the following equation.
        >
        > y = r(x+t) mod q,
        >
        > Here, r,x,t all belong to Zq* { multiplicative group}

        So you've fixed q, then?

        > I came to know that there are totally p-1 pairs of keys to the
        > equation. so the probablity for finding x & r is : 1/p-1.

        But p doesn't have a uniquely defined value, as as yet indeterminate.


        Phil

        =====
        --
        "One cannot delete the Web browser from KDE without
        losing the ability to manage files on the user's own
        hard disk." - Prof. Stuart E Madnick, MIT.
        So called "expert" witness for Microsoft. 2002/05/02

        __________________________________________________
        Do You Yahoo!?
        Yahoo! - Official partner of 2002 FIFA World Cup
        http://fifaworldcup.yahoo.com
      • bharath ERakajj
        Infact I also expected the same way .. that is, there must be q-1 pairs of solutions .. but I was surprised when I found : There are totally p-1 pairs of keys
        Message 3 of 8 , Jun 2, 2002
        • 0 Attachment
          Infact I also expected the same way .. that is, there must be q-1 pairs of solutions .. but I was surprised when I found :
          "There are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1. "

          So I asked to help me .. So my problem is still a problem (which I am noting down here again) ..

          +++++++++++++++++++++++++++++++++
          Let p & q be primes such that q devides p-1.
          I want to find r & x when I know y, t in the following equation.

          y = r(x+t) mod q,

          Here, r,x,t all belong to Zq* { multiplicative group}

          I came to know that there are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1.

          How is this true? I want to know the detailed explanation. +++++++++++++++++++++++++++++++++++++++

          Thanks,
          Bharath

          Chris Nash <chris_nash@...> wrote: Hi there

          >I want to find r & x when I know y, t in the following equation.
          >y = r(x+t) mod q,

          For each value of r in Zq*, there is a unique s such that

          rs=1 mod q

          Multiply through the equation by s and so

          x=ys-t

          Hence for each of the q-1 values of r in Zq*, there is a single
          solution for x.

          Hope that helps

          Chris Nash
          Lexington KY
          UNITED STATES


          ---------------------------------
          Do You Yahoo!?
          Yahoo! - Official partner of 2002 FIFA World Cup

          [Non-text portions of this message have been removed]
        • Phil Carmody
          ... a) And what is your process of finding the pairs. Chris Nash s method generates one and exactly one x per r. There s no need to go out and find
          Message 4 of 8 , Jun 2, 2002
          • 0 Attachment
            --- bharath ERakajj <lovebharath@...> wrote:
            >
            > Infact I also expected the same way .. that is, there must be q-1
            > pairs of solutions .. but I was surprised when I found :
            > "There are totally p-1 pairs of keys to the equation. so the
            > probablity for finding x & r is : 1/p-1. "

            a) And what is your process of "finding" the pairs. Chris Nash's
            method generates one and exactly one x per r. There's no need to go
            out and find solutions, simply turn the handle.
            b) Likewise where do you think "probablity" enter into things?
            c) What is gcd(y,t)?
            d) 1/p-1 means (1/p)-1, not 1/(p-1).
            e) When you say "q divides p-1" you are saying "q divides into p-1",
            or "q|p-1". That is different from "q is divisible by p-1" or
            "p-1|q". You mean the latter.

            Phil


            =====
            --
            "One cannot delete the Web browser from KDE without
            losing the ability to manage files on the user's own
            hard disk." - Prof. Stuart E Madnick, MIT.
            So called "expert" witness for Microsoft. 2002/05/02

            __________________________________________________
            Do You Yahoo!?
            Yahoo! - Official partner of 2002 FIFA World Cup
            http://fifaworldcup.yahoo.com
          • Jon Perry
            ... So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench MVP for HTML and
            Message 5 of 8 , Jun 4, 2002
            • 0 Attachment
              >1/p-1 means (1/p)-1, not 1/(p-1).
              >When you say "q divides p-1" you are saying "q divides into p-1",
              >or "q|p-1". That is different from "q is divisible by p-1" or
              >"p-1|q". You mean the latter.

              So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

              Jon Perry
              perry@...
              http://www.users.globalnet.co.uk/~perry/maths
              BrainBench MVP for HTML and JavaScript
              http://www.brainbench.com


              -----Original Message-----
              From: Phil Carmody [mailto:thefatphil@...]
              Sent: 03 June 2002 06:56
              To: bharath ERakajj; numbertheory@yahoogroups.com;
              primenumbers@yahoogroups.com; primeform@yahoogroups.com;
              cryptography@yahoogroups.com; maththeorists@yahoogroups.com
              Subject: Re: [PrimeNumbers] Re: How is this true!


              --- bharath ERakajj <lovebharath@...> wrote:
              >
              > Infact I also expected the same way .. that is, there must be q-1
              > pairs of solutions .. but I was surprised when I found :
              > "There are totally p-1 pairs of keys to the equation. so the
              > probablity for finding x & r is : 1/p-1. "

              a) And what is your process of "finding" the pairs. Chris Nash's
              method generates one and exactly one x per r. There's no need to go
              out and find solutions, simply turn the handle.
              b) Likewise where do you think "probablity" enter into things?
              c) What is gcd(y,t)?
              d) 1/p-1 means (1/p)-1, not 1/(p-1).
              e) When you say "q divides p-1" you are saying "q divides into p-1",
              or "q|p-1". That is different from "q is divisible by p-1" or
              "p-1|q". You mean the latter.

              Phil


              =====
              --
              "One cannot delete the Web browser from KDE without
              losing the ability to manage files on the user's own
              hard disk." - Prof. Stuart E Madnick, MIT.
              So called "expert" witness for Microsoft. 2002/05/02

              __________________________________________________
              Do You Yahoo!?
              Yahoo! - Official partner of 2002 FIFA World Cup
              http://fifaworldcup.yahoo.com


              Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
              The Prime Pages : http://www.primepages.org



              Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
            • Phil Carmody
              ... Yup. One is multiplicative in precedence, the other is effectively equality/relational in precedence. It may superficially it looks like it s to do with
              Message 6 of 8 , Jun 4, 2002
              • 0 Attachment
                --- Jon Perry <perry@...> wrote:
                > >1/p-1 means (1/p)-1, not 1/(p-1).
                > >When you say "q divides p-1" you are saying "q divides into p-1",
                > >or "q|p-1". That is different from "q is divisible by p-1" or
                > >"p-1|q". You mean the latter.
                >
                > So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

                Yup.

                One is multiplicative in precedence, the other is effectively
                equality/relational in precedence. It may superficially it looks like
                it's to do with one of the multiplicative family of operators, but
                no, it's a logical predicate, indicating some kind of equality,
                namely (p-1)%q == 0 in C terms.

                Look at a few papers and books, you'll almost always see it used with
                a precedence similar to an equality/relational operator.

                Phil

                =====
                --
                "One cannot delete the Web browser from KDE without
                losing the ability to manage files on the user's own
                hard disk." - Prof. Stuart E Madnick, MIT.
                So called "expert" witness for Microsoft. 2002/05/02

                __________________________________________________
                Do You Yahoo!?
                Yahoo! - Official partner of 2002 FIFA World Cup
                http://fifaworldcup.yahoo.com
              • Jon Perry
                Surely then p-1|q implies p - (1|q)? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench MVP for HTML and JavaScript
                Message 7 of 8 , Jun 4, 2002
                • 0 Attachment
                  Surely then p-1|q implies p - (1|q)?

                  Jon Perry
                  perry@...
                  http://www.users.globalnet.co.uk/~perry/maths
                  BrainBench MVP for HTML and JavaScript
                  http://www.brainbench.com


                  -----Original Message-----
                  From: Phil Carmody [mailto:thefatphil@...]
                  Sent: 04 June 2002 13:30
                  To: primenumbers
                  Subject: RE: [PrimeNumbers] Re: How is this true!



                  --- Jon Perry <perry@...> wrote:
                  > >1/p-1 means (1/p)-1, not 1/(p-1).
                  > >When you say "q divides p-1" you are saying "q divides into p-1",
                  > >or "q|p-1". That is different from "q is divisible by p-1" or
                  > >"p-1|q". You mean the latter.
                  >
                  > So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

                  Yup.

                  One is multiplicative in precedence, the other is effectively
                  equality/relational in precedence. It may superficially it looks like
                  it's to do with one of the multiplicative family of operators, but
                  no, it's a logical predicate, indicating some kind of equality,
                  namely (p-1)%q == 0 in C terms.

                  Look at a few papers and books, you'll almost always see it used with
                  a precedence similar to an equality/relational operator.

                  Phil

                  =====
                  --
                  "One cannot delete the Web browser from KDE without
                  losing the ability to manage files on the user's own
                  hard disk." - Prof. Stuart E Madnick, MIT.
                  So called "expert" witness for Microsoft. 2002/05/02

                  __________________________________________________
                  Do You Yahoo!?
                  Yahoo! - Official partner of 2002 FIFA World Cup
                  http://fifaworldcup.yahoo.com


                  Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
                  The Prime Pages : http://www.primepages.org



                  Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                • Phil Carmody
                  ... What planet are you on, Jon? What types are the two operators (i.e. what types do they operate on, and what type do they evaluate to)? Sheesh. Phil =====
                  Message 8 of 8 , Jun 4, 2002
                  • 0 Attachment
                    --- Jon Perry <perry@...> wrote:
                    > Surely then p-1|q implies p - (1|q)?

                    What planet are you on, Jon?

                    What types are the two operators (i.e. what types do they operate on,
                    and what type do they evaluate to)?

                    Sheesh.

                    Phil

                    =====
                    --
                    "One cannot delete the Web browser from KDE without
                    losing the ability to manage files on the user's own
                    hard disk." - Prof. Stuart E Madnick, MIT.
                    So called "expert" witness for Microsoft. 2002/05/02

                    __________________________________________________
                    Do You Yahoo!?
                    Yahoo! - Official partner of 2002 FIFA World Cup
                    http://fifaworldcup.yahoo.com
                  Your message has been successfully submitted and would be delivered to recipients shortly.