Factoring N with encryption keys

Question

I need help on part c

Assume $N = pq$ where $p$ and $q$ are distinct odd primes.

(a) If $d \equiv e^{-1}$ modulo $\phi (N)$ , show $ed - 1$ is an even number:

$ed\equiv 1$ modulo $\phi (N)$

$ed - 1 \equiv 0$ modulo $\phi (N)$ and since $\phi (N)$ is even for n > 2 we have $ed - 1 = 2k$

(b) If $gcd(m, N) = 1$, what is $m^{ed - 1}$ modulo N ?

$m^{ed -1}$

$m^{ed} m^{ -1}$

$mm^{-1} \equiv 1 $ modulo N

(c) If $ ed -1 \equiv 2^nL$, $ n \in \mathbb{N}$ and L is odd. If m has the property $m^L \not\equiv \pm 1$ modulo N and $m^{2L} \equiv 1$ modulo N. How can you find the factors of N?

For this question I'm not sure how to start it any help is appreciated

Answer 1

For part $(c)$, I think the problem is going for the following idea:

Suppose that $m^{L} \not \equiv \{ \pm 1\} \pmod{N}$, and $m^{2L} \equiv 1 \pmod{N}$. Then $0 \ne m^{2L}-1 = (m^{L}-1)(m^{L}+1) \equiv 0 \pmod{N}$. Then:

$\{ gcd(N,m^{L}+1) , gcd(N,m^{L}-1)\} = \{ p,q \}$ for $N = pq$ because $m^{L}+1 , m^{L}-1 \ne 0$ and $m^{L}+1 , m^{L}-1$ each contain exactly one but not both prime factors by the assumption that $m^{L} \not \equiv \{ \pm 1\} \pmod{N}$.

Let me know if you have any questions.