3
$\begingroup$

Given $p = nq$, $n \not\equiv q$, and $\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \bmod \lambda(n)$? My idea was to show it using the $k$ exponent, but I got stuck. So:

From Fermat's Little Theorem we know, that $$ m^p = m \bmod p $$ $ m^{\lambda(n)} = 1 \bmod n$ (Carmichael theorem)

$$\forall m, m^k \equiv 1 \bmod n$$ so I add $k$: $$m^{\lambda(n) \cdot k} \equiv 1 \bmod n$$

In other words: $$m^{kλ(n)+1} \equiv m \bmod n$$ $$ed = k\lambda(n)+1$$ so: $$m^{ed} = m \bmod n$$ How then do I show that $ed \equiv 1 \bmod \lambda(n)$?

$\endgroup$
5
$\begingroup$

Given $n=pq$ and $\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \pmod {\lambda(n)}$?

Well, the most straightforward approach is first to show that we must have both:

$$ed \equiv 1 \pmod{p-1}$$

$$ed \equiv 1 \pmod{q-1}$$

We can combine these equivalancies into one, using the Chinese Remainder Theorem; however as $p-1$ and $q-1$ are not relatively prime, we get:

$$ed \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$

This turns out to be a necessary and sufficient condition. Sometimes, we denote $\lambda(pq) = \text{lcm}(p-1, q-1)$; you'll sometimes see this formulation.

| improve this answer | |
$\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.