Raíz primitiva módulo n

Concepto de aritmética modular

En aritmética modular , un número g es una raíz primitiva módulo  n si todo número a coprimo con n es congruente con una potencia de g módulo n . Es decir, g es una raíz primitiva módulo  n si para todo entero a coprimo con n , existe algún entero k para el cual g ^k ≡ a (mod  n ). Tal valor k se denomina índice o logaritmo discreto de a en base g módulo n . Por lo tanto, g es una raíz primitiva módulo  n si y solo si g es un generador del grupo multiplicativo de los enteros módulo n .

Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde atribuyó a Euler la invención del término. En el artículo 56 afirmó que Lambert y Euler las conocían, pero él fue el primero en demostrar rigurosamente que existen raíces primitivas para un primo n . De hecho, las Disquisitiones contienen dos pruebas: la del artículo 54 es una prueba de existencia no constructiva , mientras que la del artículo 55 es constructiva .

Existe una raíz primitiva si y solo si n es 1, 2, 4, p ^k o 2 p ^k , donde p es un primo impar y k > 0 . Para todos los demás valores de n el grupo multiplicativo de los enteros módulo n no es cíclico . ^{[1] [2] [3]} Esto fue demostrado por primera vez por Gauss . ^[4]

Ejemplo elemental

El número 3 es una raíz primitiva módulo 7 ^[5] porque $${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}}$$

Aquí vemos que el periodo de 3 ^k módulo 7 es 6. Los restos en el periodo, que son 3, 2, 6, 4, 5, 1, forman un reordenamiento de todos los restos distintos de cero módulo 7, lo que implica que 3 es de hecho una raíz primitiva módulo 7. Esto se deriva del hecho de que una secuencia ( g ^k módulo  n ) siempre se repite después de algún valor de k , ya que el módulo  n produce un número finito de valores. Si g es una raíz primitiva módulo  n y n es primo, entonces el periodo de repetición es n − 1. Se ha demostrado que las permutaciones creadas de esta manera (y sus desplazamientos circulares) son matrices de Costas .

Definición

Si n es un entero positivo, los números enteros de 1 a n − 1 que son coprimos con n (o equivalentemente, las clases de congruencia coprimos con n ) forman un grupo , con multiplicación módulo n como operación; se denota por ${\displaystyle \mathbb {Z} }$^×
_en, y se denomina grupo de unidades módulo n , o grupo de clases primitivas módulo n . Como se explica en el artículo grupo multiplicativo de números enteros módulo n , este grupo multiplicativo ( ${\displaystyle \mathbb {Z} }$^×
_en) es cíclico si y solo si n es igual a 2, 4, p ^k o 2 p ^k donde p ^k es una potencia de un número primo impar . ^{[6] [7] [8]} Cuando (y solo cuando) este grupo ${\displaystyle \mathbb {Z} }$^×
_enes cíclico, un generador de este grupo cíclico se llama raíz primitiva módulo n ^[9] (o en un lenguaje más completo raíz primitiva de unidad módulo n , enfatizando su papel como una solución fundamental de las raíces de ecuaciones polinomiales unitarias X^metro
− 1 en el anillo _n ), o simplemente un elemento primitivo de ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$^×
_en.

Cuando ${\displaystyle \mathbb {Z} }$^×
_enno es cíclico, por lo que no existen elementos primitivos módulo n . En cambio, cada componente primo de n tiene sus propias raíces subprimitivas (ver 15 en los ejemplos siguientes).

Para cualquier n (sea o no ${\displaystyle \mathbb {Z} }$^×
_enes cíclico), el orden de ${\displaystyle \mathbb {Z} }$^×
_ense da por la función totiente de Euler φ ( n ) (secuencia A000010 en la OEIS ). Y luego, el teorema de Euler dice que a ^{φ ( n )} ≡ 1 (mod n ) para cada a coprimo con n ; la potencia más baja de a que es congruente con 1 módulo n se llama orden multiplicativo de a módulo n . En particular, para que a sea una raíz primitiva módulo n , a ^{φ ( n )} tiene que ser la potencia más pequeña de a que es congruente con 1 módulo n .

Ejemplos

Por ejemplo, si n = 14 entonces los elementos de ${\displaystyle \mathbb {Z} }$^×
_enson las clases de congruencia {1, 3, 5, 9, 11, 13}; hay φ (14) = 6 de ellas. Aquí hay una tabla de sus potencias módulo 14:

xx, x 2 , x 3 , ... (mód 14) 1:1 3:3, 9, 13, 11, 5, 1 5:5, 11, 13, 9, 3, 1 9:9, 11, 111:11, 9, 113:13, 1

El orden de 1 es 1, los órdenes de 3 y 5 son 6, los órdenes de 9 y 11 son 3, y el orden de 13 es 2. Por lo tanto, 3 y 5 son las raíces primitivas módulo 14.

Para un segundo ejemplo, sea n = 15. Los elementos de ${\displaystyle \mathbb {Z} }$^×
₁₅son las clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hay φ (15) = 8 de ellas.

xx, x 2 , x 3 , ... (mód 15) 1:1 2:2, 4, 8, 1 4:4, 1 7:7, 4, 13, 1 8:8, 4, 2, 111:11, 113:13, 4, 7, 114:14, 1

Como no existe ningún número cuyo orden sea 8, no existen raíces primitivas módulo 15. En efecto, λ (15) = 4 , donde λ es la función de Carmichael . (secuencia A002322 en la OEIS )

Tabla de raíces primitivas

Los números que tienen una raíz primitiva tienen la forma ${\displaystyle n}$

${\displaystyle n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},}$

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^[10]

Éstos son los números que también se mantienen en la secuencia A033948 en la OEIS . ${\displaystyle n}$ ${\displaystyle \varphi (n)=\lambda (n),}$

La siguiente tabla enumera las raíces primitivas módulo n hasta : ${\displaystyle n=31}$

Propiedades

Gauss demostró ^[11] que para cualquier número primo p (con la única excepción de p = 3), el producto de sus raíces primitivas es congruente con 1 módulo p .

También demostró ^[12] que para cualquier número primo p , la suma de sus raíces primitivas es congruente con μ ( p − 1) módulo p , donde μ es la función de Möbius .

Por ejemplo,

Por ejemplo, el producto de las últimas raíces primitivas es , y su suma es . ${\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}$ ${\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}}$

Si es una raíz primitiva módulo el primo , entonces . ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

La conjetura de Artin sobre las raíces primitivas establece que un entero dado a que no es ni un cuadrado perfecto ni −1 es una raíz primitiva módulo infinitos primos .

Encontrando raíces primitivas

No se conoce ninguna fórmula general sencilla para calcular raíces primitivas módulo n . ^{[a] [b]} Sin embargo, existen métodos para localizar una raíz primitiva que son más rápidos que simplemente probar todos los candidatos. Si el orden multiplicativo (su exponente ) de un número m módulo n es igual a (el orden de ${\displaystyle \varphi (n)}$ ${\displaystyle \mathbb {Z} }$^×
_en), entonces es una raíz primitiva. De hecho, lo inverso es cierto: si m es una raíz primitiva módulo n , entonces el orden multiplicativo de m es Podemos usar esto para probar un candidato m para ver si es primitivo. ${\displaystyle \varphi (n)=\lambda (n)~.}$

Primero , calcule. Luego, determine los diferentes factores primos de , digamos p ₁ , ..., p _k . Finalmente, calcule ${\displaystyle n>1}$ ${\displaystyle \varphi (n)~.}$ ${\displaystyle \varphi (n)}$

${\displaystyle g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}$

utilizando un algoritmo rápido para la exponenciación modular, como la exponenciación por cuadrado . Un número g para el cual estos k resultados son todos diferentes de 1 es una raíz primitiva.

El número de raíces primitivas módulo n , si las hay, es igual a ^[13]

${\displaystyle \varphi \left(\varphi (n)\right)}$

ya que, en general, un grupo cíclico con r elementos tiene generadores. ${\displaystyle \varphi (r)}$

Para el primo n , esto es igual a , y dado que los generadores son muy comunes entre {2, ..., n −1}, es relativamente fácil encontrar uno. ^[14] ${\displaystyle \varphi (n-1)}$ ${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$

Si g es una raíz primitiva módulo p , entonces g también es una raíz primitiva módulo todas las potencias p ^k a menos que g ^{p −1} ≡ 1 (mod p ² ); en ese caso, g + p es. ^[15]

Si g es una raíz primitiva módulo p ^k , entonces g también es una raíz primitiva módulo todas las potencias más pequeñas de p .

Si g es una raíz primitiva módulo p ^k , entonces g o g + p ^k (cualquiera que sea impar) es una raíz primitiva módulo 2 p ^k . ^[15]

Encontrar raíces primitivas módulo p también es equivalente a encontrar las raíces del ( p − 1)° polinomio ciclotómico módulo p .

Orden de magnitud de las raíces primitivas

La raíz menos primitiva g _p módulo p (en el rango 1, 2, ..., p − 1 ) es generalmente pequeña.

Límites superiores

Burgess (1962) demostró ^{[16] [17]} que para cada ε > 0 existe una C tal que ${\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.}$

Grosswald (1981) demostró ^{[16] [18]} que si , entonces ${\displaystyle p>e^{e^{24}}\approx 10^{11504079571}}$ ${\displaystyle g_{p}<p^{0.499}~.}$

Shoup (1990, 1992) demostró, ^[19] asumiendo la hipótesis de Riemann generalizada , que g _p = O(log ⁶ p ).

Límites inferiores

Fridlander (1949) y Salié (1950) demostraron ^[16] que existe una constante positiva C tal que para infinitos primos g _p > C log p .

Se puede demostrar ^[16] de manera elemental que para cualquier entero positivo M existen infinitos primos tales que M < g _p < p − M .

Aplicaciones

En los generadores de números pseudoaleatorios ^[20] y en la criptografía , incluido el esquema de intercambio de claves Diffie-Hellman , se suele utilizar una raíz primitiva módulo n . Los difusores de sonido se han basado en conceptos de teoría de números, como raíces primitivas y residuos cuadráticos . ^{[21] [22]}

Véase también

• Personaje de Dirichlet
• Primera repetición completa
• Generalización de Gauss del teorema de Wilson
• Orden multiplicativo
• Residuos cuadráticos
• Raíz de la unidad módulo n

Notas al pie

1. "Uno de los problemas no resueltos más importantes en la teoría de campos finitos es el diseño de un algoritmo rápido para construir raíces primitivas. von zur Gathen & Shparlinski 1998, pp. 15-24
2. "No existe una fórmula conveniente para calcular [la raíz menos primitiva]". Robbins 2006, p. 159

Referencias

1. Weisstein, Eric W. "Grupo de multiplicación de módulo". MathWorld .
2. Raíz primitiva, Enciclopedia de Matemáticas
3. (Vinogradov 2003, págs. 105-121, § VI RAÍCES E ÍNDICES PRIMITIVOS)
4. (Gauss 1986, artículos 52-56, 82-891)
5. Stromquist, Walter. "¿Qué son las raíces primitivas?". Matemáticas. Bryn Mawr College. Archivado desde el original el 2017-07-03 . Consultado el 2017-07-03 .
6. Weisstein, Eric W. "Grupo de multiplicación de módulo". MathWorld .
7. Raíz primitiva, Enciclopedia de Matemáticas .
8. Vinogradov 2003, págs. 105–121, § VI Raíces primitivas e índices.
9. Vinogradov 2003, pág. 106.
10. Gauss 1986, artículo 92.
11. Gauss 1986, artículos 80.
12. Gauss 1986, artículo 81.
13. (secuencia A010554 en la OEIS )
14. Knuth, Donald E. (1998). Algoritmos seminuméricos . El arte de la programación informática. Vol. 2 (3.ª ed.). Addison–Wesley. Sección 4.5.4, página 391.
15. Cohen, Henri (1993). Un curso de teoría algebraica computacional de números . Berlín: Springer . pág. 26. ISBN. 978-3-540-55640-4.
16. Ribenboim, Paulo (1996). El nuevo libro de registros de números primos . Nueva York, NY: Springer . pág. 24. ISBN. 978-0-387-94457-9.
17. Burgess, DA (1962). "Sobre sumas de caracteres y raíces primitivas †". Actas de la London Mathematical Society . s3-12 (1): 179–192. doi :10.1112/plms/s3-12.1.179.
18. Grosswald, E. (1981). "Sobre el límite de Burgess para raíces primitivas módulo primos y una aplicación a Γ(p)". American Journal of Mathematics . 103 (6): 1171–1183. doi :10.2307/2374229. ISSN  0002-9327. JSTOR  2374229.
19. Bach y Shallit 1996, pág. 254.
20. Gentle, James E. (2003). Generación de números aleatorios y métodos de Monte Carlo (2.ª ed.). Nueva York: Springer. ISBN 0-387-00178-6.OCLC 51534945  .
21. Walker, R. (1990). El diseño y la aplicación de elementos modulares de difusión acústica (PDF) . Departamento de Investigación de la BBC (Informe). British Broadcasting Corporation . Consultado el 25 de marzo de 2019 .
22. Feldman, Eliot (julio de 1995). "Una rejilla de reflexión que anula la reflexión especular: un cono de silencio". J. Acoust. Soc. Am . 98 (1): 623–634. Bibcode :1995ASAJ...98..623F. doi :10.1121/1.413656.

Fuentes

• Bach, Eric; Shallit, Jeffrey (1996). Algoritmos eficientes . Teoría algorítmica de números. Vol. I. Cambridge, MA: The MIT Press . ISBN 978-0-262-02405-1.

• Carella, NA (2015). "Raíces primitivas mínimas". Revista internacional de matemáticas y ciencias de la computación . 10 (2): 185–194. arXiv : 1709.01172 .

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre reciprocidad bicuadrática y notas inéditas.

• Gauss, Carl Friedrich (1986) [1801]. Disquisiciones Arithmeticae . Traducido por Clarke, Arthur A. (segunda edición corregida). Nueva York, Nueva York: Springer . ISBN 978-0-387-96254-2.

• Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [ Estudios de aritmética superior ] (en alemán). Traducido por Maser, H. (2ª ed.). Nueva York, Nueva York: Chelsea. ISBN 978-0-8284-0191-3.

• Robbins, Neville (2006). Introducción a la teoría de números. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

• Vinogradov, IM (2003). "§ VI Raíces primitivas e índices". Elementos de teoría de números . Mineola, NY: Dover Publications. pp. 105–121. ISBN. 978-0-486-49530-9.

• von zur Gathen, Joachim ; Shparlinski, Igor (1998). "Órdenes de períodos de Gauss en cuerpos finitos". Álgebra aplicable en ingeniería, comunicación y computación . 9 (1): 15–24. CiteSeerX  10.1.1.46.5504 . doi :10.1007/s002000050093. MR  1624824. S2CID  19232025.

Lectura adicional

• Ore, Oystein (1988). Teoría de números y su historia. Dover. Págs. 284-302. ISBN. 978-0-486-65620-5..

Enlaces externos

• Weisstein, Eric W. "Raíz primitiva". MundoMatemático .
• Holt. "Residuos cuadráticos y raíces primitivas". Matemáticas. Michigan Tech.
• "Calculadora de raíces primitivas". BlueTulip .