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.