La pregunta que estoy respondiendo actualmente se lee
Deje que [math] n [/ math] sea un producto grande de dos primos distintos (número RSA por ejemplo). ¿Es cierto para cada compuesto de este tipo, que siempre existe tal [matemática] a> \ sqrt {n} [/ matemática] que [matemática] a ^ 2 [/ matemática] mod [matemática] n [/ matemática] rinde 1?
Tal como está escrito, es cierto para todos los enteros positivos [matemática] n [/ matemática], ya sea que el producto de primos distintos o no – [matemática] a [/ matemática] podría ser simplemente [matemática] n + 1. [/ Matemática]
Incluso si restringe a números menores que [matemática] n [/ matemática], [matemática] a [/ matemática] podría ser [matemática] n-1 [/ matemática] (que, para [matemática] n> 2 [/ matemática ] le dará a [math] a> \ sqrt {n} [/ math])
- ¿Cuál es la mejor estrategia para la matemática mental de multiplicación de dos dígitos?
- ¿Cuál es la importancia de las matemáticas en una computadora?
- Cómo medir la confianza del alumno de 7º grado en la resolución de problemas matemáticos
- ¿Qué clases de matemáticas toman los arquitectos en la universidad?
- Cómo estudiar matemáticas de clase 11
Creo que esperas que los números [matemática] a [/ matemática] no sean congruentes con [matemática] \ pm 1 \ bmod n [/ matemática]?
¿Y probablemente quería [math] \ sqrt {n} <a <n [/ math]?
Esos siempre existen, ya que [math] a ^ 2 \ equiv 1 \ bmod n [/ math] es equivalente a [math] a \ equiv \ pm 1 \ bmod p [/ math] y [math] a \ equiv \ pm 1 \ bmod q [/ math] (donde [math] p [/ math] y [math] q [/ math] son esos dos primos distintos cuyo producto es [math] n [/ math])
que produce 4 casos
- [matemáticas] a \ equiv 1 \ bmod p [/ matemáticas] y [matemáticas] a \ equiv 1 \ bmod q [/ matemáticas]
- [matemáticas] a \ equiv 1 \ bmod p [/ matemáticas] y [matemáticas] a \ equiv -1 \ bmod q [/ matemáticas]
- [matemáticas] a \ equiv -1 \ bmod p [/ matemáticas] y [matemáticas] a \ equiv 1 \ bmod q [/ matemáticas]
- [matemáticas] a \ equiv -1 \ bmod p [/ matemáticas] y [matemáticas] a \ equiv -1 \ bmod q [/ matemáticas]
Según el teorema del resto chino, cada uno de estos tiene una solución única mod [math] n. [/ Math]
el primero produce 1 mod [matemática] n [/ matemática], el último produce -1 mod [matemática] n [/ matemática]. Los otros dos deben existir (es decir, tienen soluciones únicas mod [math] n [/ math] y su suma debe ser 0 mod [math] n [/ math]
Si sus soluciones entre 1 y [matemáticas] n [/ matemáticas] estaban ambas entre [matemáticas] 1 [/ matemáticas] y [matemáticas] \ sqrt {n} [/ matemáticas]
su suma sería como máximo [matemática] 2 \ sqrt {n} [/ matemática] que es menor que [matemática] n [/ matemática] si [matemática] n> 4 [/ matemática]