7
$\begingroup$

I was using some low primes for RSA encryption today, and noticed that for $p=5$, $q=7$, and ANY valid encryption key value, encrypt(encrypt(message)) = message. I thought this was an interesting property, so I found this sequence: $3, 8, 12, 24$. It can be described using these rules:

$N$ is a member of the sequence if and only if: For each prime number $p$, such that $\sqrt{N} \le p < N$: $p^2 \equiv 1 \bmod N$

Unfortunately, I have only been able to find 4 members of the sequence: $3, 8, 12$ and $24$. Are there any other members? I have tried all numbers up to 75 million. If there's a proof why this is impossible, I'd love to see it!

$\endgroup$
  • $\begingroup$ OEIS to the rescue... $\endgroup$ – Asaf Karagila Feb 3 '14 at 22:11
5
$\begingroup$

I assume that you are looking for numbers $N \in \Bbb N$ satisfying $x^2 \equiv 1 \bmod N$ for all $1\le x \le N$ such that $(x,N)=1$. This is a necessary condition for $N=\varphi(M)$ to have the described property for RSA-encryption with modulus $M$. Algebraically speaking this means that any element of the multiplicative group $(\Bbb Z/N \Bbb Z)^\times$ has order $2$.

  • If $N=2^k$ is a power of $2$, the group is $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/2 \Bbb Z)\times(\Bbb Z/2^{k-2} \Bbb Z)$.
  • If $N = p^k$ is a power of a prime $p>2$, the group is $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/(p-1) \Bbb Z)\times (\Bbb Z/p^{k-1} \Bbb Z)$
  • If $N = \prod p_i^{k_i}$ is composite, the group is the product of the groups corresponding to the prime powers, that is $(\Bbb Z/N \Bbb Z)^\times = \prod (\Bbb Z/p_i^{k_i} \Bbb Z)^\times$

As $N$ satisfies the described property iff $(\Bbb Z/N \Bbb Z)^\times$ can be written as a product of copies of $(\Bbb Z / 2\Bbb Z)$:

  • the highest power of $2$ dividing $N$ is $3$
  • the highest power of $3$ dividing $N$ is $1$
  • no other prime divides $N$

So $24$ is the maximal number of the sequence.

$\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.