Kruhová skupina multiplikativního zbytku

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. července 2021; ověření vyžaduje 1 úpravu .

Multiplikativní skupina zbytkového kruhu modulo m je multiplikativní skupina invertibilních prvků zbytkového kruhu modulo m . V tomto případě lze jakýkoli redukovaný systém zbytků modulo m považovat za soubor prvků .

Snížený systém srážek

Redukovaný systém zbytků modulo m je množina všech čísel úplného systému zbytků modulo m , která jsou relativně prvočísla k m . Jako redukovaný systém zbytků modulo m se obvykle berou čísla spojená s m od 1 do m-1 [1] .

Příklad : redukovaný systém zbytků modulo 42 by byl: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41}.

Vlastnosti

Množina libovolných φ( m ) ( φ(m) je Eulerova funkce ) čísel spolu s m a párově nesrovnatelné modulo m tvoří redukovaný systém zbytků [1] .
Je-li gcd ( a , m ) = 1 , pak množina hodnot ax , kde x prochází redukovaným systémem zbytků modulo m , je také redukovaným systémem zbytků modulo m [2] .
Pokud gcd( k , m ) = 1, pak množina hodnot kx + my , kde x prochází redukovaným zbytkovým systémem modulo m a y prochází redukovaným zbytkovým systémem modulo k , je redukovaný zbytkový systém modulo km [ 3] .
V případě, že číslo m je prvočíslo, redukovaný systém zbytků modulo m se liší od úplného systému zbytků absencí nuly [4] .
Je-li a prvkem redukovaného systému zbytků modulo m , pak pro libovolné b je srovnání rozhodnutelné vzhledem k x [4] . $ax\equiv b{\pmod {m))$

Redukovaný systém zbytků s multiplikačním modulem tvoří skupinu zvanou multiplikativní skupina nebo skupinu invertibilních prvků reziduálního kruhu modulo m , která se označuje nebo [4] . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

Pokud je m jednoduché, pak, jak je uvedeno výše, prvky 1, 2, ..., m - 1 jsou zahrnuty v . V tomto případě je pole [4] . ${\mathbb {Z}}_{m}^{{\times }}$ ${\mathbb {Z}}_{m}^{{\times }}$

Záznamové formuláře

Zbytkový kruhový modulo n je označen nebo . Jeho multiplikativní grupa, stejně jako v obecném případě skupin invertibilních prvků kruhů, je označena . $\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})$

Nejjednodušší případ

Abychom porozuměli struktuře grupy , můžeme zvážit speciální případ , kde je prvočíslo, a zobecnit jej. Zvažte nejjednodušší případ, kdy , tj . $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $p$ $a=1$ $n=p$

Věta: je cyklická grupa. [5] $U({\mathbb {Z}}/p{\mathbb {Z}})$

Příklad : Zvažte skupinu $U(\mathbb {Z} /9\mathbb {Z} )$

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

= {1,2,4,5,7,8} Generátor skupin je číslo 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}}

Jak vidíte, jakýkoli prvek skupiny může být reprezentován jako , kde . To znamená, že skupina je cyklická.

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

2^l

1\leq \ell <\varphi (m)

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

Obecný případ

Abychom zvážili obecný případ, je nutné definovat primitivní kořen . Primitivní kořenový modulo a prime je číslo, které spolu s třídou zbytku generuje skupinu . [5] $p$ $U({\mathbb {Z}}/p{\mathbb {Z}})$

Příklady: 2 - primitivní kořen modulo 11 ; 8 je primitivní kořenový modul 11 ; 3 není primitivní kořenový modul 11 .

V případě celého modulu je definice stejná. $n$

Struktura grupy je určena následující větou: Jestliže p je liché prvočíslo a l je kladné celé číslo, pak existují primitivní kořeny modulo , tedy cyklická grupa. $p^{{l}}$ $U({\mathbb {Z}}/p^{{l}}{\mathbb {Z}})$

Z čínské věty o zbytku vyplývá , že pro existuje izomorfismus ≈ . $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}})\krát U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\times \dots U({\mathbb {Z}}/p_{l}^{{a_{l}}}{\mathbb {Z}})$

Skupina je cyklická. Jeho pořadí je . $U({\mathbb {Z}}/p_{i}^{{a_{i}}}{\mathbb {Z}})$ $p_{i}^{{a_{i}-1}}(p_{i}-1)$

Skupina je také cyklická řádu a pro a=1 nebo a=2 . Pro , tato skupina není cyklická a je přímým produktem dvou cyklických skupin, řádů a . $U({\mathbb {Z}}/2^{{a}}{\mathbb {Z}})$ $a\geqslant 3$ $2$ $2^{{a-2}}$

Skupina je cyklická právě tehdy, když nebo nebo n = 2 nebo n = 4, kde p je liché prvočíslo. V obecném případě, jako abelovská skupina, je reprezentována jako přímý produkt cyklických primárních skupin izomorfních k . [5] $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $n=2p^{a}$ $U({\mathbb {Z}}/n{\mathbb {Z}})$ ${\mathbb {Z}}_{{u_{i}}}^{{+}}$

Podskupina svědků jednoduchosti

Nechť je liché číslo větší než 1. Číslo je jednoznačně reprezentováno jako , kde je liché. Celé číslo , se nazývá prvočíslo , pokud je splněna jedna z následujících podmínek: $m$ $m-1$ $m-1=2^{s}\cdot t$ $t$ $A$ $1<a<m$ $m$

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

nebo

existuje celé číslo , , takové, že $k$ $0\leq k<s$ $a^{2^{k}t}\equiv m-1{\pmod {m)).$

Pokud je číslo složené, existuje podskupina multiplikativní skupiny zbytkového kruhu, nazývaná podskupina svědků primality. Jeho prvky zvednuté k výkonu se shodují s modulem . $m$ $m-1$ $jeden$ $m$

Příklad :. Existujízbytky relativně prvočíslo, totoa. ekvivalentnímodulo, znamenáekvivalentnímodulo. Protoa jsou svědky jednoduchosti čísla. V tomto případě je {1, 8} podmnožinou svědků jednoduchosti. [6] $m=9$ $6$ $9$ $1,2,4,5,7$ $osm$ $osm$ $-jeden$ $9$ $8^{{8}}$ $jeden$ $9$ $jeden$ $osm$ $9$

Vlastnosti

Skupinový vystavovatel

Skupinový exponent je roven Carmichaelově funkci . $\lambda (n)=$ $\textstyle \operatorname {lcm}$ $(p_{1}^{a_{1}-1}(p_{1}-1),\cdots ,p_{s}^{a_{s}-1}(p_{s}-1) )$

Skupinové pořadí

Pořadí skupiny se rovná Eulerově funkci: . Odtud a z izomorfismu ≈ lze získat jiný způsob, jak dokázat rovnost pro [5] $|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ $U({\mathbb {Z}}/m{\mathbb {Z}})$ $U({\mathbb {Z}}/p_{1}^{{a_{1}}}{\mathbb {Z}})\krát U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\times ...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}$

Generující sada

$U({\mathbb {Z}}/n{\mathbb {Z}})$ je cyklická skupina právě tehdy, když V případě cyklické skupiny se generátor nazývá primitivní kořen . $\varphi(n)=\lambda(n).$

Příklad

Redukovaný systém zbytků modulo se skládá z tříd zbytků: . S ohledem na násobení definované pro třídy zbytků, tvoří navíc skupinu a jsou vzájemně inverzní (tj . ) a jsou inverzní samy k sobě. $deset$ $čtyři$ $[1]_{{10}},[3]_{{10}},[7]_{{10}},[9]_{{10}}$ $[3]_{{10}}$ $[7]_{{10}}$ $[3]_{{10}}{\cdot }[7]_{{10}}=[1]_{{10}}$ $[1]_{{10}}$ $[9]_{{10}}$

Struktura skupiny

Záznam znamená "cyklická skupina řádu n". $C_{n}$

Struktura skupiny (Z/ n Z) ×

$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Generátor skupin	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Generátor skupin	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Generátor skupin	$n\;$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times ))$	$\varphi (n)$	$\lambda(n)\;$	Generátor skupin
jeden	C1 _	jeden	jeden	0	33	C2 × C10 _	dvacet	deset	2, 10	65	C4 × C12 _	48	12	2, 12	97	C96 _	96	96	5
2	C1 _	jeden	jeden	jeden	34	C 16	16	16	3	66	C2 × C10 _	dvacet	deset	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	třicet	2.5
čtyři	C2 _	2	2	3	36	C2 × C6 _	12	6	5, 19	68	C2 × C16 _	32	16	3, 67	100	C2 × C20 _	40	dvacet	3,99
5	C4 _	čtyři	čtyři	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	osmnáct	osmnáct	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
osm	C2 × C2 _	čtyři	2	3, 5	40	C2 × C2 × C4 _	16	čtyři	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
deset	C4 _	čtyři	čtyři	3	42	C2 × C6 _	12	6	5, 13	74	C 36	36	36	5	106	C 52	52	52	3
jedenáct	C 10	deset	deset	2	43	C42 _	42	42	3	75	C2 × C20 _	40	dvacet	2, 74	107	C 106	106	106	2
12	C2 × C2 _	čtyři	2	5, 7	44	C2 × C10 _	dvacet	deset	3, 43	76	C2 × C18 _	36	osmnáct	3, 37	108	C2 × C18 _	36	osmnáct	5, 107
13	C 12	12	12	2	45	C2 × C12 _	24	12	2, 44	77	C2 × C30 _	60	třicet	2,76	109	C 108	108	108	6
čtrnáct	C6 _	6	6	3	46	C 22	22	22	5	78	C2 × C12 _	24	12	5, 7	110	C2 × C20 _	40	dvacet	3, 109
patnáct	C2 × C4 _	osm	čtyři	2, 14	47	C46 _	46	46	5	79	C78 _	78	78	3	111	C 2 × C 36	72	36	2, 110
16	C2 × C4 _	osm	čtyři	3, 15	48	C2 × C2 × C4 _	16	čtyři	5, 7, 47	80	C2 × C4 × C4 _	32	čtyři	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
osmnáct	C6 _	6	6	5	padesáti	C 20	dvacet	dvacet	3	82	C40 _	40	40	7	114	C2 × C18 _	36	osmnáct	5, 37
19	C 18	osmnáct	osmnáct	2	51	C2 × C16 _	32	16	5,50	83	C82 _	82	82	2	115	C 2 × C 44	88	44	2, 114
dvacet	C2 × C4 _	osm	čtyři	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	deset	deset	7	54	C 18	osmnáct	osmnáct	5	86	C42 _	42	42	3	118	C 58	58	58	jedenáct
23	C 22	22	22	5	55	C2 × C20 _	40	dvacet	2, 21	87	C2 × C28 _	56	28	2, 86	119	C 2 × C 48	96	48	3, 118
24	C2 × C2 × C2 _	osm	2	5, 7, 13	56	C2 × C2 × C6 _	24	6	3, 13, 29	88	C2 × C2 × C10 _	40	deset	3, 5, 7	120	C2 × C2 × C2 × C4 _	32	čtyři	7, 11, 19, 29
25	C 20	dvacet	dvacet	2	57	C2 × C18 _	36	osmnáct	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	osmnáct	osmnáct	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	čtyři	7, 11, 19	92	C2 × C22 _	44	22	3, 91	124	C2 × C30 _	60	třicet	3, 61
29	C 28	28	28	2	61	C60 _	60	60	2	93	C2 × C30 _	60	třicet	11, 61	125	C 100	100	100	2
třicet	C2 × C4 _	osm	čtyři	7, 11	62	C 30	třicet	třicet	3	94	C46 _	46	46	5	126	C6 × C6 _	36	6	5, 13
31	C 30	třicet	třicet	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	osm	3, 31	64	C2 × C16 _	32	16	3, 63	96	C2 × C2 × C8 _	32	osm	5, 17, 31	128	C 2 × C 32	64	32	3, 127

Aplikace

Kryptografická síla šifrovacího systému ElGamal je založena na složitosti diskrétního logaritmu v multiplikativní skupině zbytkového kruhu . [7]

Historie

Ke studiu struktury multiplikativní skupiny zbytkového kruhu přispěli Artin , Bielharz, Brouwer , Wilson, Gauss , Lagrange , Lemaire, Waring , Fermat, Hooley, Euler . Lagrange dokázal lemma, že jestliže , ak je pole, pak f má nejvýše n různých kořenů, kde n je mocnina f. Dokázal také důležitý důsledek tohoto lemmatu, kterým je srovnání ≡ . Euler dokázal Fermatovu malou větu . Waring formuloval Wilsonovu větu a Lagrange to dokázal. Euler navrhl existenci primitivních kořenů modulo prvočíslo. Gauss to dokázal. Artin předložil svou hypotézu o existenci a kvantifikaci prvočísel modulo, kde dané celé číslo je primitivní kořen. Brouwer přispěl ke studiu problému existence množin po sobě jdoucích celých čísel, z nichž každé je k-tou mocninou modulo p. Bielhartz dokázal analogii Artinovy domněnky. Hooley dokázal Artinovu domněnku s předpokladem, že rozšířená Riemannova hypotéza platí v algebraických číselných polích. [5] $f(x)\in k[x]$ $x^{{p-1}}-1$ $(x-1)(x-2)...(x-p+1)mod(p)$

Poznámky

↑ 1 2 I. M. Vinogradov Základy teorie čísel. vyd. 9., revidováno, M .: Nauka. 1981
↑ Sagalovich Yu.L. Úvod do algebraických kódů. 2011.
↑ Bukhshtab, 1966 .
↑ 1 2 3 4 V. Šéf Přednášky z matematiky. Svazek 14. Teorie čísel. 2014.
↑ 1 2 3 4 5 Irsko, Rosen, 1987 .
↑ Erdős, Paul ; Pomerance, Carle. O počtu falešných svědků pro složené číslo // Math . Počítat. : deník. - 1986. - Sv. 46 . - str. 259-279 .
↑ Alferov a kol., 2002 .

Literatura

Ireland K., Rosen M. Klasický úvod do moderní teorie čísel. — M .: Mir, 1987.
Alferov A.P., Zubov A.Yu., Kuzmin A.S. Cheremushkin A.V. Základy kryptografie. - Moskva: "Helios ARV", 2002.
Rostovtsev A.G., Makhovenko E.B. Teoretická kryptografie. - Petrohrad: NPO "Professional", 2004.

Odkazy

Bukhshtab A. A. Teorie čísel. - M .: Vzdělávání, 1966.
Weisstein, Eric W. Modulo Multiplication Group (anglicky) na webových stránkách Wolfram MathWorld .