Teoría de números: ¿Cuál es la forma más motivadora de introducir residuos cuadráticos?

Answer 1

¿Por qué se considera la Ley de Reciprocidad Cuadrática como una de las más importantes en la teoría de números?

Probablemente, la razón principal por la cual la reciprocidad cuadrática se considera una de las más importantes en la teoría de números es que la reciprocidad cuadrática es una de las razones por las cuales uno de los problemas fundacionales encontrados en la “teoría de números” es una disciplina separada.

Como problema, tiene mucha gravedad histórica, ya que la reciprocidad cuadrática era el “teorema favorito de Gauss” y siguió obteniendo diferentes pruebas de ello, pero también condujo a muchas de las ideas que impulsan la teoría de números como disciplina.

¿Cuál es la forma más motivadora de introducir residuos cuadráticos?

No es el tipo de resultado que es inmediatamente obvio y que a menudo se reinventa en todas las culturas, y proporciona muchas conexiones muy poco obvias. Muestra la relación entre los símbolos Legendre (p / q) y (q / p). Nos da el hecho de que los divisores primos de los valores de los polinomios cuadráticos caen en clases de residuos en primer lugar, que comienzan a sentirse tan fundamentales y tan bien comportados como las nociones más naturales de “par” e “impar” a pesar de que usted ¡llegue allí comenzando con polinomios que rompan cosas con la suma y la multiplicación de una manera aparentemente arbitraria!

Empujar la idea de clases de residuos hasta llegar a anillos de enteros algebraicos le brinda una puerta de entrada a una gran cantidad de teoría básica de números, por lo que también hay un aspecto fundamental del problema: ¡no es solo que a Gauss le haya gustado! También te da una intuición que puedes usar para jugar con el teorema de Dirichlet.

¿Hay ejemplos de la vida real de residuos cuadráticos?

En cuanto a las aplicaciones prácticas de reciprocidad cuadrática, inmediatamente conduce al criptosistema Goldwasser-Micali.

Answer 2

Aquí hay un ejemplo que uso en mi clase de posgrado, pero puede usarse en una clase de pregrado:

Sabemos que la ley puede usarse para determinar si cualquier ecuación cuadrática módulo un número primo tiene una solución. Esto es importante en criptografía y en seguridad informática. La reciprocidad cuadrática es una herramienta particularmente útil cuando quieres ver si un número es un mod cuadrado p (p prime).

Un criptosistema en particular que requiere la ayuda de la Reciprocidad cuadrática es el criptosistema de clave pública Goldwasser-Micali; este es el caso porque plantea la siguiente pregunta basada en la siguiente información:
Deje que p, q sean primos (secretos) y que se dé N = pq. Para un entero dado a, determine si a es un mod cuadrado N, es decir, determine si existe un entero u que satisfaga u ^ 2 = un mod N.

En particular, es especialmente fácil para Bob, el receptor del mensaje que sabe factorizar N, resolver este problema porque a es un mod cuadrado pq iff (a / p) = 1 y (a / q) = 1.

Puede encontrar más en el libro de Springer titulado Una Introducción a la Criptografía Matemática por Hoffstein, Pipher y Silverman (Capítulo 3, creo …)

No es muy difícil encontrar ejemplos para hacer en clase. Creo que mi N fue inferior a 5 millones.

Answer 3

Los residuos cuadráticos primero me llamaron la atención en una charla en PasswordsCon LV14 de Thomas Pornin sobre el esquema de hash de contraseña de Makwa.

Tal vez lo había visto mencionado antes, pero aquí es donde llegué a creer que se trataba de un tipo especial de magia.

La charla está aquí:

Como alguien que realmente no fue más allá del cálculo en la universidad, me falta capacitación en estas cosas. Y me encantaría saber cómo puedo aprender más.

Answer 4

Agregando a la respuesta de Edward, escribí un conjunto de notas motivando el estudio de la reciprocidad cuadrática aquí http://www.mathisbeauty.org/prel …