Multiplikativ restringgrupp

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 juli 2021; verifiering kräver 1 redigering .

Den multiplikativa gruppen av restringen modulom är den multiplikativa gruppen av inverterbara element i restringen modulom . I detta fall kan varje reducerat system av rester modulo m betraktas som en uppsättning element .

Minskat system för avdrag

Det reducerade systemet av rester modulom är mängden av alla tal i det kompletta systemet av rester modulom som är relativt primtal till m . Som ett reducerat system av rester modulo m , tas siffror coprime med m från 1 till m-1 vanligtvis [1] .

Exempel : det reducerade systemet av rester modulo 42 skulle vara: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41}.

Egenskaper

En uppsättning av alla φ( m ) ( φ(m) är Euler-funktionen ) tal coprime till m och parvis ojämförliga modulo m bildar ett reducerat system av rester [1] .
Om gcd ( a , m ) = 1 så är värdeuppsättningen ax , där x går genom ett reducerat system av rester modulo m , också ett reducerat system av rester modulo m [2] .
Om gcd( k , m ) = 1, så är uppsättningen av värden kx + my , där x löper genom det reducerade restsystemet modulo m och y går genom det reducerade restsystemet modulo k , ett reducerat restsystem modulo km [ 3] .
I det fall då talet m är primtal, skiljer sig det reducerade systemet av rester modulo m från det fullständiga systemet av rester genom frånvaron av noll [4] .
Om a är ett element i det reducerade systemet av rester modulo m , så är jämförelsen för varje b avgörbar med avseende på x [4] . $ax\equiv b{\pmod {m))$

Det reducerade systemet av rester med multiplikationsmodulo m bildar en grupp som kallas den multiplikativa gruppen eller gruppen av inverterbara element i restringen modulo m , som betecknas med eller [4] . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

Om m är enkel, så ingår, som noterats ovan, elementen 1, 2, ..., m -1 i . I det här fallet är fältet [4] . ${\mathbb {Z}}_{m}^{{\times }}$ ${\mathbb {Z}}_{m}^{{\times }}$

Inspelningsformulär

Återstodsringen modulo n betecknas med eller . Dess multiplikativ grupp, som i det allmänna fallet med grupper av inverterbara element av ringar, betecknas med . $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} _{n}$ $({\mathbb {Z}}/n{\mathbb {Z}})^{*},$ $({\mathbb {Z}}/n{\mathbb {Z}})^{\times },$ $U({\mathbb {Z}}/n{\mathbb {Z}}),$ $E(\mathbb {Z} /n\mathbb {Z} ),$ $\mathbb {Z} _{n}^{\times },$ $U({\mathbb {Z}}_{n})$

Det enklaste fallet

För att förstå gruppens struktur kan vi överväga ett specialfall , där är ett primtal, och generalisera det. Tänk på det enklaste fallet när , det vill säga . $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $sid$ $a=1$ $n=p$

Sats: är en cyklisk grupp. [5] $U({\mathbb {Z}}/p{\mathbb {Z}})$

Exempel : Betrakta en grupp $U(\mathbb {Z} /9\mathbb {Z} )$

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

= {1,2,4,5,7,8} Gruppgeneratorn är nummer 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}}

Som du kan se kan alla element i gruppen representeras som , där . Det vill säga gruppen är cyklisk.

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

2^l

1\leq \ell <\varphi (m)

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

Allmänt fall

För att överväga det allmänna fallet är det nödvändigt att definiera en primitiv rot . En primitiv rot modulo ett primtal är ett tal som tillsammans med sin restklass genererar en grupp . [5] $sid$ $U({\mathbb {Z}}/p{\mathbb {Z}})$

Exempel: 2 - primitiv rot modulo 11 ; 8 är en primitiv rotmodulo 11 ; 3 är inte en primitiv rotmodulo 11 .

När det gäller en hel modul är definitionen densamma. $n$

Gruppens struktur bestäms av följande teorem: Om p är ett udda primtal och l är ett positivt heltal, så finns det primitiva rötter modulo , det vill säga en cyklisk grupp. $p^{{l}}$ $U({\mathbb {Z}}/p^{{l}}{\mathbb {Z}})$

Det följer av den kinesiska restsatsen att för , det finns en isomorfism ≈ . $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}})\ gånger U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\times \dots U({\mathbb {Z}}/p_{l}^{{a_{l}}}{\mathbb {Z}})$

Gruppen är cyklisk. Dess ordning är . $U({\mathbb {Z}}/p_{i}^{{a_{i}}}{\mathbb {Z}})$ $p_{i}^{{a_{i}-1}}(p_{i}-1)$

Gruppen är också cyklisk av ordningen a för a=1 eller a=2 . För denna grupp är inte cyklisk och är en direkt produkt av två cykliska grupper, order och . $U({\mathbb {Z}}/2^{{a}}{\mathbb {Z}})$ $a\geqslant 3$ $2$ $2^{{a-2}}$

En grupp är cyklisk om och endast om eller eller n = 2 eller n = 4, där p är ett udda primtal. I det allmänna fallet, som en Abelisk grupp, representeras den som en direkt produkt av cykliska primära grupper som är isomorfa till . [5] $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $n=2p^{a}$ $U({\mathbb {Z}}/n{\mathbb {Z}})$ ${\mathbb {Z}}_{{u_{i}}}^{{+}}$

Enkelhetsvittnesundergrupp

Låta vara ett udda tal större än 1. Antalet representeras unikt som , där är udda. Ett heltal , , kallas ett primtalsvittne om något av följande villkor är uppfyllt: $m$ $m-1$ $m-1=2^{s}\cdot t$ $t$ $a$ $1<a<m$ $m$

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

eller

det finns ett heltal , , sådan att $k$ $0\leq k<s$ $a^{2^{k}t}\equiv m-1{\pmod {m)).$

Om numret är sammansatt finns det en undergrupp av den multiplikativa gruppen av restringen, som kallas undergruppen av vittnen till primalitet. Dess element upphöjda till kraften sammanfaller med modulo . $m$ $m-1$ $ett$ $m$

Exempel :. Det finnsrester relativt bra till, dettaoch. ekvivalentmodulo, betyderekvivalentmodulo. Därför,och är vittnen till enkelheten i numret. I det här fallet är {1, 8} en delmängd av enkelhetsvittnen. [6] $m=9$ $6$ $9$ $1,2,4,5,7$ $åtta$ $åtta$ $-ett$ $9$ $8^{{8}}$ $ett$ $9$ $ett$ $åtta$ $9$

Egenskaper

Grupputställare

Gruppexponenten är lika med Carmichael-funktionen . $\lambda (n)=$ $\textstyle \operatörsnamn {lcm}$ $(p_{1}^{a_{1}-1}(p_{1}-1),\cdots ,p_{s}^{a_{s}-1}(p_{s}-1) )$

Grupporder

Ordningen på gruppen är lika med Euler-funktionen: . Härifrån och från isomorfismen ≈ , kan man få ett annat sätt att bevisa likheten för [5] $|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ $U({\mathbb {Z}}/m{\mathbb {Z}})$ $U({\mathbb {Z}}/p_{1}^{{a_{1}}}{\mathbb {Z}})\ gånger U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\ gånger ...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}$

Genereringsuppsättning

$U({\mathbb {Z}}/n{\mathbb {Z}})$ är en cyklisk grupp om och endast om I fallet med en cyklisk grupp kallas generatorn en primitiv rot . $\varphi(n)=\lambda(n).$

Exempel

Det reducerade systemet av rester modulo består av restklasser: . Med avseende på multiplikationen som definieras för restklasserna, bildar de dessutom en grupp och är ömsesidigt inversa (det vill säga ), och är inversa till sig själva. $tio$ $fyra$ $[1]_{{10}},[3]_{{10}},[7]_{{10}},[9]_{{10}}$ $[3]_{{10}}$ $[7]_{{10}}$ $[3]_{{10}}{\cdot [7]_{{10}}=[1]_{{10}}$ $[1]_{{10}}$ $[9]_{{10}}$

Gruppstruktur

Posten betyder "cyklisk grupp av ordning n". $C_{n}$

Gruppstruktur (Z/ n Z) ×

$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Gruppgenerator	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Gruppgenerator	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Gruppgenerator	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Gruppgenerator
ett	C1 _	ett	ett	0	33	C2 × C10 _	tjugo	tio	2, 10	65	C4 × C12 _	48	12	2, 12	97	C96 _	96	96	5
2	C1 _	ett	ett	ett	34	C 16	16	16	3	66	C2 × C10 _	tjugo	tio	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	trettio	2.5
fyra	C2 _	2	2	3	36	C2 × C6 _	12	6	5, 19	68	C2 × C16 _	32	16	3, 67	100	C2 × C20 _	40	tjugo	3,99
5	C4 _	fyra	fyra	2	37	C 36	36	36	2	69	C2 × C22 _	44	22	2, 68	101	C 100	100	100	2
6	C2 _	2	2	5	38	C 18	arton	arton	3	70	C2 × C12 _	24	12	3, 69	102	C2 × C16 _	32	16	5, 101
7	C6 _	6	6	3	39	C2 × C12 _	24	12	2, 38	71	C70 _	70	70	7	103	C 102	102	102	5
åtta	C2 × C2 _	fyra	2	3, 5	40	C2 × C2 × C4 _	16	fyra	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
tio	C4 _	fyra	fyra	3	42	C2 × C6 _	12	6	5, 13	74	C 36	36	36	5	106	C 52	52	52	3
elva	C 10	tio	tio	2	43	C42 _	42	42	3	75	C2 × C20 _	40	tjugo	2, 74	107	C 106	106	106	2
12	C2 × C2 _	fyra	2	5, 7	44	C2 × C10 _	tjugo	tio	3, 43	76	C2 × C18 _	36	arton	3, 37	108	C2 × C18 _	36	arton	5, 107
13	C 12	12	12	2	45	C2 × C12 _	24	12	2, 44	77	C2 × C30 _	60	trettio	2,76	109	C 108	108	108	6
fjorton	C6 _	6	6	3	46	C 22	22	22	5	78	C2 × C12 _	24	12	5, 7	110	C2 × C20 _	40	tjugo	3, 109
femton	C2 × C4 _	åtta	fyra	2, 14	47	C46 _	46	46	5	79	C78 _	78	78	3	111	C 2 × C 36	72	36	2, 110
16	C2 × C4 _	åtta	fyra	3, 15	48	C2 × C2 × C4 _	16	fyra	5, 7, 47	80	C2 × C4 × C4 _	32	fyra	3, 7, 79	112	C2 × C2 × C12 _	48	12	3, 5, 111
17	C 16	16	16	3	49	C42 _	42	42	3	81	C 54	54	54	2	113	C 112	112	112	3
arton	C6 _	6	6	5	femtio	C 20	tjugo	tjugo	3	82	C40 _	40	40	7	114	C2 × C18 _	36	arton	5, 37
19	C 18	arton	arton	2	51	C2 × C16 _	32	16	5,50	83	C82 _	82	82	2	115	C 2 × C 44	88	44	2, 114
tjugo	C2 × C4 _	åtta	fyra	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	C 52	52	52	2	85	C4 × C16 _	64	16	2, 3	117	C6 × C12 _	72	12	2, 17
22	C 10	tio	tio	7	54	C 18	arton	arton	5	86	C42 _	42	42	3	118	C 58	58	58	elva
23	C 22	22	22	5	55	C2 × C20 _	40	tjugo	2, 21	87	C2 × C28 _	56	28	2, 86	119	C 2 × C 48	96	48	3, 118
24	C2 × C2 × C2 _	åtta	2	5, 7, 13	56	C2 × C2 × C6 _	24	6	3, 13, 29	88	C2 × C2 × C10 _	40	tio	3, 5, 7	120	C2 × C2 × C2 × C4 _	32	fyra	7, 11, 19, 29
25	C 20	tjugo	tjugo	2	57	C2 × C18 _	36	arton	2, 20	89	C 88	88	88	3	121	C 110	110	110	2
26	C 12	12	12	7	58	C 28	28	28	3	90	C2 × C12 _	24	12	7, 11	122	C60 _	60	60	7
27	C 18	arton	arton	2	59	C 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 _	16	fyra	7, 11, 19	92	C2 × C22 _	44	22	3, 91	124	C2 × C30 _	60	trettio	3, 61
29	C 28	28	28	2	61	C60 _	60	60	2	93	C2 × C30 _	60	trettio	11, 61	125	C 100	100	100	2
trettio	C2 × C4 _	åtta	fyra	7, 11	62	C 30	trettio	trettio	3	94	C46 _	46	46	5	126	C6 × C6 _	36	6	5, 13
31	C 30	trettio	trettio	3	63	C6 × C6 _	36	6	2.5	95	C 2 × C 36	72	36	2, 94	127	C 126	126	126	3
32	C2 × C8 _	16	åtta	3, 31	64	C2 × C16 _	32	16	3, 63	96	C2 × C2 × C8 _	32	åtta	5, 17, 31	128	C 2 × C 32	64	32	3, 127

Applikation

Den kryptografiska styrkan hos ElGamal-chiffersystemet är baserad på komplexiteten hos den diskreta logaritmen i den multiplikativa gruppen av restringen . [7]

Historik

Bidraget till studiet av strukturen av den multiplikativa gruppen av restringen gjordes av Artin , Bielharz, Brouwer , Wilson, Gauss , Lagrange , Lemaire, Waring , Fermat, Hooley, Euler . Lagrange bevisade lemmat att om , och k är ett fält, så har f högst n distinkta rötter, där n är potensen av f. Han visade också en viktig följd av detta lemma, som är jämförelsen ≡ . Euler bevisade Fermats lilla teorem . Waring formulerade Wilsons teorem , och Lagrange bevisade det. Euler föreslog förekomsten av primitiva rötter modulo ett primtal. Gauss bevisade det. Artin lade fram sin hypotes om existensen och kvantifieringen av primtal modulo där ett givet heltal är en primitiv rot. Brouwer bidrog till studiet av problemet med förekomsten av uppsättningar av på varandra följande heltal, som var och en är den kth power modulo p. Bielhartz visade sig vara en analog till Artins gissningar. Hooley bevisade Artins gissningar med antagandet att den utökade Riemann-hypotesen är giltig i algebraiska talfält. [5] $f(x)\i k[x]$ $x^{{p-1}}-1$ $(x-1)(x-2)...(x-p+1)mod(p)$

Anteckningar

↑ 1 2 I. M. Vinogradov Fundamentals of Number Theory. ed. 9:e, reviderad, M .: Nauka. 1981
↑ Sagalovich Yu. L. Introduktion till algebraiska koder. 2011.
↑ Bukhshtab, 1966 .
↑ 1 2 3 4 V. Boss Föreläsningar om matematik. Volym 14. Talteori. 2014.
↑ 1 2 3 4 5 Irland, Rosen, 1987 .
↑ Erdős, Paul ; Pomerance, Carl. Om antalet falska vittnen för ett sammansatt nummer // Math . Comput. : tidskrift. - 1986. - Vol. 46 . - S. 259-279 .
↑ Alferov et al., 2002 .

Litteratur

Ireland K., Rosen M. En klassisk introduktion till modern talteori. — M .: Mir, 1987.
Alferov A.P., Zubov A.Yu., Kuzmin A.S. Cheremushkin A.V. Grunderna i kryptografi. - Moskva: "Helios ARV", 2002.
Rostovtsev A.G., Makhovenko E.B. Teoretisk kryptografi. - St. Petersburg: NPO "Professional", 2004.

Länkar

Bukhshtab A. A. Talteori . - M . : Utbildning, 1966.
Weisstein, Eric W. Modulo Multiplication Group (engelska) på Wolfram MathWorld- webbplatsen .