Grupo de anillos de residuos multiplicativos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 31 de julio de 2021; la verificación requiere 1 edición .

El grupo multiplicativo del anillo de residuos módulo m es el grupo multiplicativo de elementos invertibles del anillo de residuos módulo m . En este caso, cualquier sistema reducido de residuos módulo m puede ser considerado como un conjunto de elementos .

Sistema reducido de deducciones

El sistema reducido de residuos módulo m es el conjunto de todos los números del sistema completo de residuos módulo m que son primos relativos a m . Como sistema reducido de residuos módulo m , se suelen tomar números coprimos con m de 1 a m - 1 [1] .

Ejemplo : el sistema reducido de residuos módulo 42 sería: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 }.

Propiedades

Un conjunto de cualquier φ( m ) ( φ(m) es la función de Euler ) números coprimos a m y módulo m incomparable por pares forman un sistema reducido de residuos [1] .
Si mcd ( a , m ) = 1 , entonces el conjunto de valores ax , donde x pasa por un sistema reducido de residuos módulo m , también es un sistema reducido de residuos módulo m [2] .
Si mcd( k , m ) = 1, entonces el conjunto de valores kx + my , donde x pasa por el sistema de residuos reducidos módulo m y y pasa por el sistema de residuos reducidos módulo k , es un sistema de residuos reducidos módulo km [ 3] .
En el caso de que el número m sea primo, el sistema reducido de residuos módulo m difiere del sistema completo de residuos por la ausencia de cero [4] .
Si a es un elemento del sistema reducido de residuos módulo m , entonces para cualquier b la comparación es decidible con respecto a x [4] . $hacha\equiv b{\pmod {m))$

El sistema reducido de residuos con multiplicación módulo m forma un grupo denominado grupo multiplicativo o grupo de elementos invertibles del anillo de residuos módulo m , que se denota por o [4] . ${\mathbb {Z}}_{m}^{{\veces}}$ $U({\mathbb{Z}}_{m})$

Si m es simple, entonces, como se indicó anteriormente, los elementos 1, 2, ..., m -1 están incluidos en . En este caso, es el campo [4] . ${\mathbb {Z}}_{m}^{{\veces}}$ ${\mathbb {Z}}_{m}^{{\veces}}$

Formas de registro

El módulo de anillo residual n se denota por o . Su grupo multiplicativo, como en el caso general de grupos de elementos invertibles de anillos, se denota por . $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} _{n}$ $({\mathbb {Z}}/n{\mathbb {Z}})^{*},$ $({\mathbb {Z}}/n{\mathbb {Z}})^{\veces},$ $U({\mathbb {Z}}/n{\mathbb {Z}}),$ $E(\mathbb {Z} /n\mathbb {Z} ),$ $\mathbb {Z} _{n}^{\times},$ $U({\mathbb {Z}}_{n})$

El caso más simple

Para comprender la estructura del grupo , podemos considerar un caso especial , donde es un número primo, y generalizarlo. Considere el caso más simple cuando , es decir . $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $pags$ $un=1$ $n = pag$

Teorema: es un grupo cíclico. [5] $U({\mathbb {Z}}/p{\mathbb {Z}})$

Ejemplo : Considere un grupo $U(\mathbb {Z} /9\mathbb {Z} )$

U(\mathbb {Z} /9\mathbb {Z} )

= {1,2,4,5,7,8} El generador de grupo es el número 2.

2^{1}\equiv 2\ {\pmod {9}}

2^{2}\equiv 4\ {\pmod {9}}

2^{3}\equiv 8\ {\pmod {9}}

2^{4}\equiv 7\ {\pmod {9}}

2^{5}\equiv 5\ {\pmod {9}}

2^{6}\equiv 1\ {\pmod {9}}

Como puede ver, cualquier elemento del grupo se puede representar como , donde . Es decir, el grupo es cíclico.

U(\mathbb {Z} /9\mathbb {Z} )

2^l

{\ estilo de visualización 1 \ leq \ ell <\ varphi (m)}

U(\mathbb {Z} /9\mathbb {Z} )

Caso general

Para considerar el caso general, es necesario definir una raíz primitiva . Una raíz primitiva módulo a primo es un número que, junto con su clase residual, genera un grupo . [5] $pags$ $U({\mathbb {Z}}/p{\mathbb {Z}})$

Ejemplos: 2 - raíz primitiva módulo 11 ; 8 es un módulo raíz primitivo 11 ; 3 no es un módulo raíz primitivo 11 .

En el caso de un módulo completo , la definición es la misma. $norte$

La estructura del grupo está determinada por el siguiente teorema: si p es un número primo impar y l es un número entero positivo, entonces hay raíces primitivas módulo , es decir , un grupo cíclico. $pag^{{l}}$ $U({\mathbb {Z}}/p^{{l}}{\mathbb {Z}})$

Del teorema chino del resto se deduce que para , existe un isomorfismo ≈ . $n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{l}^{a_{l}}$ $U({\mathbb {Z}}/n{\mathbb {Z}})$ $U({\mathbb {Z}}/p_{1}^{{a_{1}}}{\mathbb {Z}})\times U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\times \dots U({\mathbb {Z}}/p_{l}^{{a_{l}}}{\mathbb {Z}})$

El grupo es cíclico. Su orden es . $U({\mathbb {Z}}/p_{i}^{{a_{i}}}{\mathbb {Z}})$ $p_{i}^{{a_{i}-1}}(p_{i}-1)$

El grupo también es cíclico de orden a para a=1 o a=2 . Para , este grupo no es cíclico y es un producto directo de dos grupos cíclicos, órdenes y . $U({\mathbb {Z}}/2^{{a}}{\mathbb {Z}})$ $a \ geqslant 3$ $2$ $2^{{a-2}}$

Un grupo es cíclico si y sólo si o o n = 2 o n = 4, donde p es un número primo impar. En el caso general, como grupo abeliano, se representa como un producto directo de grupos primarios cíclicos isomorfos a . [5] $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $n=2p^{un}$ $U({\mathbb {Z}}/n{\mathbb {Z}})$ ${\matemáticas {Z}}_{{u_{i}}}^{{+}}$

Subgrupo de testigos de simplicidad

Sea un número impar mayor que 1. El número se representa únicamente como , donde es impar. Un número entero , se llama testigo de número primo si se cumple una de las siguientes condiciones: $metro$ $m-1$ $m-1=2^{s}\cdot t$ $t$ $a$ ${\ estilo de visualización 1<a<m}$ $metro$

$a^{t}\equiv 1{\pmod {m))$

hay un entero , , tal que $k$ $0\leq k<s$ $a^{2^{k}t}\equiv m-1{\pmod {m)).$

Si el número es compuesto, existe un subgrupo del grupo multiplicativo del anillo residual, llamado subgrupo de testigos de primalidad. Sus elementos elevados a la potencia coinciden con el módulo . $metro$ $m-1$ $una$ $metro$

Ejemplo :. Hayrestos relativamente primos de, estey. móduloequivalente, significamóduloequivalente. Por lo tanto,y son testigos de la sencillez del número. En este caso, {1, 8} es un subconjunto de testigos de simplicidad. [6] $metro=9$ $6$ $9$ ${\ estilo de visualización 1,2,4,5,7}$ $ocho$ $ocho$ $-una$ $9$ $8^{{8}}$ $una$ $9$ $una$ $ocho$ $9$

Propiedades

Expositor colectivo

El exponente del grupo es igual a la función de Carmichael . ${\ estilo de visualización \ lambda (n) =}$ ${\ estilo de visualización \ estilo de texto \ nombre del operador {lcm} }$ $(p_{1}^{a_{1}-1}(p_{1}-1),\cdots,p_{s}^{a_{s}-1}(p_{s}-1) )$

Orden de grupo

El orden del grupo es igual a la función de Euler: . De aquí y del isomorfismo ≈ , se puede obtener otra forma de probar la igualdad para [5] $|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ $U({\mathbb {Z}}/m{\mathbb {Z}})$ $U({\mathbb {Z}}/p_{1}^{{a_{1}}}{\mathbb {Z}})\times U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\veces ...U({\mathbb {Z}}/p_{l}^{{a_{l}}}{\mathbb {Z}})$ $\varphi (m)=\varphi (m_{1})\varphi (m_{2})...\varphi (m_{t})$ $m=m_{1}m_{2}...m_{t}$

Grupo electrógeno

$U({\mathbb {Z}}/n{\mathbb {Z}})$ es un grupo cíclico si y sólo si En el caso de un grupo cíclico, el generador se llama raíz primitiva . $\varphi(n)=\lambda(n).$

Ejemplo

El sistema reducido de residuos modulo consta de clases de residuos: . Con respecto a la multiplicación definida para las clases de residuos, forman un grupo, además, y son mutuamente inversas (es decir ), y son inversas a sí mismas. $diez$ $cuatro$ $[1]_{{10}},[3]_{{10}},[7]_{{10}},[9]_{{10}}$ $[3]_{{10}}$ $[7]_{{10}}$ $[3]_{{10}}{\cdot }[7]_{{10}}=[1]_{{10}}$ $[1]_{{10}}$ $[9]_{{10}}$

Estructura del grupo

La entrada significa "grupo cíclico de orden n". $C_{n}$

Estructura del grupo (Z/ n Z) ×

$norte\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varfi (n)$	$\lambda(n)\;$	generador de grupos	$norte\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varfi (n)$	$\lambda(n)\;$	generador de grupos	$norte\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varfi (n)$	$\lambda(n)\;$	generador de grupos	$norte\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varfi (n)$	$\lambda(n)\;$	generador de grupos
una	C1 _	una	una	0	33	C2 × C10 _	veinte	diez	2, 10	sesenta y cinco	C4 × C12 _	48	12	2, 12	97	C96 _	96	96	5
2	C1 _	una	una	una	34	16 _	dieciséis	dieciséis	3	66	C2 × C10 _	veinte	diez	5, 7	98	C42 _	42	42	3
3	C2 _	2	2	2	35	C2 × C12 _	24	12	2, 6	67	C66 _	66	66	2	99	C2 × C30 _	60	treinta	2.5
cuatro	C2 _	2	2	3	36	C2 × C6 _	12	6	5, 19	68	C2 × C16 _	32	dieciséis	3, 67	100	C2 × C20 _	40	veinte	3.99
5	C4 _	cuatro	cuatro	2	37	36 _	36	36	2	69	C2 × C22 _	44	22	2, 68	101	C 100	100	100	2
6	C2 _	2	2	5	38	18 _	Dieciocho	Dieciocho	3	70	C2 × C12 _	24	12	3, 69	102	C2 × C16 _	32	dieciséis	5, 101
7	C6 _	6	6	3	39	C2 × C12 _	24	12	2, 38	71	C70 _	70	70	7	103	102 _	102	102	5
ocho	C2 × C2 _	cuatro	2	3, 5	40	C2 × C2 × C4 _	dieciséis	cuatro	3, 11, 39	72	C2 × C2 × C6 _	24	6	5, 17, 19	104	C2 × C2 × C12 _	48	12	3, 5, 103
9	C6 _	6	6	2	41	C40 _	40	40	6	73	C72 _	72	72	5	105	C2 × C2 × C12 _	48	12	2, 29, 41
diez	C4 _	cuatro	cuatro	3	42	C2 × C6 _	12	6	5, 13	74	36 _	36	36	5	106	52 _	52	52	3
once	C 10	diez	diez	2	43	C42 _	42	42	3	75	C2 × C20 _	40	veinte	2, 74	107	106 _	106	106	2
12	C2 × C2 _	cuatro	2	5, 7	44	C2 × C10 _	veinte	diez	3, 43	76	C2 × C18 _	36	Dieciocho	3, 37	108	C2 × C18 _	36	Dieciocho	5, 107
13	C 12	12	12	2	45	C2 × C12 _	24	12	2, 44	77	C2 × C30 _	60	treinta	2.76	109	108 _	108	108	6
catorce	C6 _	6	6	3	46	22 _	22	22	5	78	C2 × C12 _	24	12	5, 7	110	C2 × C20 _	40	veinte	3, 109
quince	C2 × C4 _	ocho	cuatro	2, 14	47	C46 _	46	46	5	79	C78 _	78	78	3	111	C 2 × C 36	72	36	2, 110
dieciséis	C2 × C4 _	ocho	cuatro	3, 15	48	C2 × C2 × C4 _	dieciséis	cuatro	5, 7, 47	80	C2 × C4 × C4 _	32	cuatro	3, 7, 79	112	C2 × C2 × C12 _	48	12	3, 5, 111
17	16 _	dieciséis	dieciséis	3	49	C42 _	42	42	3	81	54 _	54	54	2	113	112 _	112	112	3
Dieciocho	C6 _	6	6	5	cincuenta	C 20	veinte	veinte	3	82	C40 _	40	40	7	114	C2 × C18 _	36	Dieciocho	5, 37
19	18 _	Dieciocho	Dieciocho	2	51	C2 × C16 _	32	dieciséis	5.50	83	C82 _	82	82	2	115	C 2 × C 44	88	44	2, 114
veinte	C2 × C4 _	ocho	cuatro	3, 19	52	C2 × C12 _	24	12	7.51	84	C2 × C2 × C6 _	24	6	5, 11, 13	116	C2 × C28 _	56	28	3, 115
21	C2 × C6 _	12	6	2, 20	53	52 _	52	52	2	85	C4 × C16 _	64	dieciséis	2, 3	117	C6 × C12 _	72	12	2, 17
22	C 10	diez	diez	7	54	18 _	Dieciocho	Dieciocho	5	86	C42 _	42	42	3	118	58 _	58	58	once
23	22 _	22	22	5	55	C2 × C20 _	40	veinte	2, 21	87	C2 × C28 _	56	28	2, 86	119	C 2 × C 48	96	48	3, 118
24	C2 × C2 × C2 _	ocho	2	5, 7, 13	56	C2 × C2 × C6 _	24	6	3, 13, 29	88	C2 × C2 × C10 _	40	diez	3, 5, 7	120	C2 × C2 × C2 × C4 _	32	cuatro	7, 11, 19, 29
25	C 20	veinte	veinte	2	57	C2 × C18 _	36	Dieciocho	2, 20	89	88 _	88	88	3	121	C 110	110	110	2
26	C 12	12	12	7	58	28 _	28	28	3	90	C2 × C12 _	24	12	7, 11	122	C60 _	60	60	7
27	18 _	Dieciocho	Dieciocho	2	59	58 _	58	58	2	91	C6 × C12 _	72	12	2, 3	123	C2 × C40 _	80	40	7, 83
28	C2 × C6 _	12	6	3, 13	60	C2 × C2 × C4 _	dieciséis	cuatro	7, 11, 19	92	C2 × C22 _	44	22	3, 91	124	C2 × C30 _	60	treinta	3, 61
29	28 _	28	28	2	61	C60 _	60	60	2	93	C2 × C30 _	60	treinta	11, 61	125	C 100	100	100	2
treinta	C2 × C4 _	ocho	cuatro	7, 11	62	C 30	treinta	treinta	3	94	C46 _	46	46	5	126	C6 × C6 _	36	6	5, 13
31	C 30	treinta	treinta	3	63	C6 × C6 _	36	6	2.5	95	C 2 × C 36	72	36	2, 94	127	126 _	126	126	3
32	C2 × C8 _	dieciséis	ocho	3, 31	64	C2 × C16 _	32	dieciséis	3, 63	96	C2 × C2 × C8 _	32	ocho	5, 17, 31	128	C 2 × C 32	64	32	3, 127

Aplicación

La fuerza criptográfica del sistema de cifrado ElGamal se basa en la complejidad del logaritmo discreto en el grupo multiplicativo del anillo residual . [7]

Historia

La contribución al estudio de la estructura del grupo multiplicativo del anillo residual fue realizada por Artin , Bielharz, Brouwer , Wilson, Gauss , Lagrange , Lemaire, Waring , Fermat, Hooley, Euler . Lagrange demostró el lema de que si , y k es un campo, entonces f tiene como máximo n raíces distintas, donde n es la potencia de f. También demostró un importante corolario de este lema, que es la comparación ≡ . Euler demostró el pequeño teorema de Fermat . Waring formuló el teorema de Wilson y Lagrange lo demostró. Euler sugirió la existencia de raíces primitivas módulo un número primo. Gauss lo demostró. Artin planteó su hipótesis sobre la existencia y cuantificación de los números primos módulo en el que un entero dado es una raíz primitiva. Brouwer contribuyó al estudio del problema de la existencia de conjuntos de números enteros consecutivos, cada uno de los cuales es el k-ésimo módulo de potencia p. Bielhartz demostró un análogo de la conjetura de Artin. Hooley probó la conjetura de Artin con la suposición de que la hipótesis extendida de Riemann es válida en campos numéricos algebraicos. [5] $f(x)\en k[x]$ $x^{{p-1}}-1$ $(x-1)(x-2)...(x-p+1)mod(p)$

Notas

↑ 1 2 I. M. Vinogradov Fundamentos de la teoría de números. edición 9º, revisado, M.: Nauka. 1981
↑ Sagalovich Yu. L. Introducción a los códigos algebraicos. 2011.
↑ Bukhshtab, 1966 .
↑ 1 2 3 4 V. Boss Conferencias sobre matemáticas. Volumen 14. Teoría de números. 2014.
↑ 1 2 3 4 5 Irlanda, Rosen, 1987 .
↑ Erdős, Paul ; Pomerancia, Carl. Sobre el número de falsos testigos para un número compuesto // Matemáticas . computar : diario. - 1986. - vol. 46 . - pág. 259-279 .
↑ Alferov et al., 2002 .

Literatura

Ireland K., Rosen M. Una introducción clásica a la teoría de números moderna. — M .: Mir, 1987.
Alferov A.P., Zubov A.Yu., Kuzmin A.S. Cheremushkin A. V. Fundamentos de criptografía. - Moscú: "Helios ARV", 2002.
Rostovtsev A.G., Makhovenko E.B. Criptografía teórica. - San Petersburgo: NPO "Professional", 2004.

Enlaces

Bukhshtab A. A. Teoría de números. - M. : Educación, 1966.
Weisstein, Eric W. Modulo Multiplication Group (inglés) en el sitio web de Wolfram MathWorld .