3
$\begingroup$

This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$ Reading the linked question, I wondered if there is a "simple" description of the set of numbers $n$ that have this property. In particular, are there infinitely many such numbers?

$\endgroup$
  • $\begingroup$ Do you really want $\pmod{\varphi(n)}$ or rather $\pmod{\lambda(n)}$? $\endgroup$ – CodesInChaos Dec 22 '14 at 16:34
  • $\begingroup$ I actually want $\lambda(n)$, you're right. (The confusion arises from the fact that for products of distinct primes, these are equal.) $\endgroup$ – helloworld Dec 22 '14 at 16:36
  • 2
    $\begingroup$ "for products of distinct primes, these are equal" I don't think so. For odd primes (p-1) and (q-1) always share the factor two, so $\lambda$ is strictly smaller than $\varphi$. $\endgroup$ – CodesInChaos Dec 22 '14 at 16:38
6
$\begingroup$

I wondered if there is a "simple" description of the set of numbers n that have this property.

Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24. In other words, each prime must be a member of the set $\{2, 3, 5, 7, 13\}$

Why is this? Well, $e^2 \equiv 1 \mod \lambda(n)$ (for $e$ r.p. to $\lambda(n)$) is equivalent to $e^2 \equiv 1 \mod p_i-1 $ for all $i$ (for $e$ r.p. to $p_i-1$); this latter holds only if $p_i-1$ is a divisor of 24.

As a consequence, we see that there is only a finite number of such modulii; if we restrict ourselves to modulii with two factors, we see that 91 is the largest possible. If we include multiprimes, then the largest possible is $2730 = 2 \times 3 \times 5 \times 7 \times 13$

$\endgroup$
  • $\begingroup$ are you sure about the "square-free" thing ? $n = 45 = 3^2 5 \Rightarrow \lambda(n) = 12$; now $12 | 24$ thus $e^2 = 1 \bmod \lambda(45) \forall e $ coprime with $\lambda(45)$ and $n$ is part of this set, right ? $\endgroup$ – Cédric Van Rompay Jan 13 '16 at 12:52
  • 1
    $\begingroup$ @CédricVanRompay: for $n=45$, there are ciphertexts that cannot be uniquely decrypted (e.g. $c=36$), for any $e>1$, hence I would claim that is not a valid RSA modulus. $\endgroup$ – poncho Jan 13 '16 at 13:07

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.