# Thread: encryption question

1. ## encryption question

let a=pq for some prime numbers p<q. Put b=phi(a). Find p,q in terms of a and b.

2. $\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}$