0

Let N = pq be a product of two distinct primes. Show that if N and an integer d, where d is defined as :

3d = 1 mod ($\phi(N)$)

then it is possible to compute p and q in polynomial time in the equation :

$p^2$ + p(($\phi(N) - 1) - N) + N = 0$

Hint: Obtain a small list of possibilities for $\phi(N)$

I believe the solution is : $\phi(N)$ = {1 ..i.. N - 1}, where i(mod(3)) $\neq$ 0, but I don't know how to express this in a formal definition or in an equation.

$\phi(N^P)$ = $(N - 1)N^{P - 1}$, where N is a prime number

I'm more looking for a direction rather than a solution, but any help would be wonderful.

user3317647
  • 1
  • $\phi(n)$ must be a divisor of $3d-1$ , so you only need to consider the divisors of $3d-1$ to find out $p$ and $q$. Note that we can compute $p$ and $q$ immediately, if $\phi(n)$ is known. – Peter Dec 04 '16 at 23:42
  • $(N,e)$ is an RSA-encryption system, where $d$ is its decrption exponent. FInd out that allows one to factor $N$ in polynomial time, and hence find $\phi(N)$ as well.. – Henno Brandsma Dec 05 '16 at 07:07
  • In my last comment $e=3$ of course. – Henno Brandsma Dec 08 '16 at 10:30

0 Answers0