Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
OEIS to the rescue... –  Asaf Karagila Feb 3 at 22:11

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.