Results 1 to 2 of 2

Math Help - encryption question

  1. #1
    Junior Member
    Joined
    Jun 2009
    Posts
    25

    encryption question

    let a=pq for some prime numbers p<q. Put b=phi(a). Find p,q in terms of a and b.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    \phi(a)=\phi(pq)=(p-1)(q-1)=pq-p-q+1=a-p-q+1

    So

    a-\phi(a)-1=(p-1)+(q-1)

    Now forget this problem for a second and suppose m=cd, n=c+d; then we can find c,d by solving for the roots of the quadratic x^2-n+m; so we have \{c,d\}\: =\frac{n \pm \sqrt{n^2-4m}}{2}.

    Now put m=(p-1)(q-1)=\phi(a)
    n=(p-1)+(q-1)=a-\phi(a)-1

    and you get

    \{p-1,q-1\}=\frac{a-\phi(a)-1 \pm \sqrt{(a-\phi(a)-1)^2-4\phi(a)}}{2}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. RSA Encryption
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 18th 2011, 06:52 PM
  2. Encryption
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2010, 04:47 AM
  3. encryption vig
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 11th 2010, 10:31 PM
  4. RSA Encryption
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2006, 10:28 AM
  5. RSA encryption
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2006, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum