7

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!

benh
  • 6,605
user125957
  • 73

1 Answers1

5

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.

benh
  • 6,605