Hay más números en esta entero secuencia? 3, 8, 12, 24

Question

Yo estaba usando algunas bajas primos de cifrado RSA de hoy, y se dio cuenta de que para $p=5$, $q=7$, y CUALQUIER válidos valor de clave de cifrado, cifrar(encriptar(mensaje)) = mensaje. Pensé que esto era una propiedad interesante, así que me encontré con esta secuencia: $3, 8, 12, 24$. Puede ser descrito utilizando estas reglas:

$N$ es un miembro de la secuencia si y sólo si: Para cada número primo $p$, de tal manera que $\sqrt{N} \le p < N$: $p^2 \equiv 1 \bmod N$

Por desgracia, sólo he sido capaz de encontrar los 4 miembros de la secuencia: $3, 8, 12$$24$. Hay otros miembros? He intentado todos los números de hasta 75 millones de euros. Si hay una prueba de por qué esto es imposible, me encantaría verlo!

Answer 1

Supongo que usted está buscando para los números de $N \in \Bbb N$ satisfacción $x^2 \equiv 1 \bmod N$ todos los $1\le x \le N$ tal que $(x,N)=1$. Esta es una condición necesaria para $N=\varphi(M)$ a tienen la propiedad descrita por RSA cifrado con el módulo de $M$. Algebraicamente hablando, esto significa que cualquier elemento del grupo multiplicativo $(\Bbb Z/N \Bbb Z)^\times$ orden $2$.

• Si $N=2^k$ es una potencia de $2$, el grupo es $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/2 \Bbb Z)\times(\Bbb Z/2^{k-2} \Bbb Z)$.
• Si $N = p^k$ es una potencia de un primo $p>2$, el grupo es $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/(p-1) \Bbb Z)\times (\Bbb Z/p^{k-1} \Bbb Z)$
• Si $N = \prod p_i^{k_i}$ es compuesto, el grupo es el producto de los grupos correspondientes al primer poderes, que es $(\Bbb Z/N \Bbb Z)^\times = \prod (\Bbb Z/p_i^{k_i} \Bbb Z)^\times$

Como $N$ satisface la propiedad descrita iff $(\Bbb Z/N \Bbb Z)^\times$ se puede escribir como un producto de copias de $(\Bbb Z / 2\Bbb Z)$:

• el mayor poder de $2$ dividiendo $N$ $3$
• el mayor poder de $3$ dividiendo $N$ $1$
• ningún otro primer divide $N$

Por lo $24$ es el máximo número de la secuencia.