1
$\begingroup$

This is actually from a past year exam question for a computer security module, which I am doing to prepare for my upcoming test.

The question provides $pq = 1669806207577$ (for ease of reference, I will refer to it as $n$.

Define $\phi(n) = n \left(1-\frac{1}{p_1}\right) \cdots \left(1-\frac{1}{p_k}\right)$ as the the Euler Phi function, where $p_1, \cdots, p_k$ are the prime factors of $n$.

The question asks us to find $\phi(pq) \text{ mod } (p+q)$.

My approach is as follows,

$\phi(pq) = (p-1)(q-1) = pq - p - q + 1$

I have tried to express $2pq$ as $(p+q)^2 - p^2 - q^2$ and substituting it to the above, such that,

$\phi(pq) = pq - p - q + 1 = [(p+q)^2- p^2 - q^2]/2 - (p+q) + 1$.

But now, I do not know how to proceed.

$\endgroup$
  • 5
    $\begingroup$ You have $\varphi(pq)=pq+1-(p+q)\equiv pq+1\pmod {p+q}$ already. $\endgroup$ – lulu Sep 30 at 12:38
3
$\begingroup$

This is the basis of the RSA cryptosystem and there is no known parametric solution for this in terms of $p$ and $q$ which is less than $pq+1$ otherwise you will have cracked the RSA encryption system. So the best you can hope for is a brute force computer attack to factorize $n$ and find $p$ and $q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.