Multiplikativ restringgruppe

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. juli 2021; verifikation kræver 1 redigering .

Den multiplikative gruppe af restringen modulom er den multiplikative gruppe af inverterbare elementer af restringen modulom . I dette tilfælde kan ethvert reduceret system af rester modulo m betragtes som et sæt af elementer .

Reduceret system af fradrag

Det reducerede system af rester modulom er mængden af alle tal af det komplette system af rester modulom , der er relativt prime til m . Som et reduceret system af rester modulo m tages sædvanligvis tal coprime med m fra 1 til m - 1 [1] .

Eksempel : det reducerede system af rester modulo 42 ville være: {1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41}.

Ejendomme

Et sæt af ethvert φ( m ) ( φ(m) er Euler-funktionen ) tal coprimer til m og parvis uforlignelige modulo m danner et reduceret system af rester [1] .
Hvis gcd ( a , m ) = 1 , så er værdisættet ax , hvor x løber gennem et reduceret system af rester modulo m , også et reduceret system af rester modulo m [2] .
Hvis gcd( k , m ) = 1, så er værdisættet kx + my , hvor x løber gennem det reducerede restsystem modulo m og y løber gennem det reducerede restsystem modulo k , et reduceret restsystem modulo km [ 3] .
I det tilfælde, hvor tallet m er primtal, adskiller det reducerede system af rester modulo m sig fra det komplette system af rester ved fraværet af nul [4] .
Hvis a er et element i det reducerede system af rester modulo m , så kan sammenligningen for enhver b afgøres med hensyn til x [4] . $ax\equiv b{\pmod {m))$

Det reducerede system af rester med multiplikationsmodulo m danner en gruppe kaldet multiplikationsgruppen eller gruppen af inverterbare elementer i restringen modulo m , som er betegnet med eller [4] . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

Hvis m er simpel, så er, som nævnt ovenfor, elementerne 1, 2, ..., m -1 inkluderet i . I dette tilfælde er feltet [4] . ${\mathbb {Z}}_{m}^{{\times }}$ ${\mathbb {Z}}_{m}^{{\times }}$

Optagelsesformularer

Resterende ring modulo n er betegnet med eller . Dens multiplikative gruppe, som i det generelle tilfælde af grupper af inverterbare elementer af ringe, er betegnet 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 enkleste tilfælde

For at forstå strukturen af gruppen , kan vi overveje et særligt tilfælde , hvor er et primtal, og generalisere det. Overvej det enkleste tilfælde, når , dvs. $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $s$ $a=1$ $n=p$

Sætning: er en cyklisk gruppe. [5] $U({\mathbb {Z}}/p{\mathbb {Z}})$

Eksempel : Overvej en gruppe $U(\mathbb {Z} /9\mathbb {Z} )$

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

= {1,2,4,5,7,8} Gruppegeneratoren er 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 ethvert element i gruppen repræsenteres som , hvor . Det vil sige, at gruppen er cyklisk.

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

2^l

1\leq \ell <\varphi (m)

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

Generel sag

For at overveje det generelle tilfælde er det nødvendigt at definere en primitiv rod . En primitiv rod modulo a prim er et tal, der sammen med sin restklasse genererer en gruppe . [5] $s$ $U({\mathbb {Z}}/p{\mathbb {Z}})$

Eksempler: 2 - primitiv rod modulo 11 ; 8 er en primitiv rodmodulo 11 ; 3 er ikke en primitiv rodmodulo 11 .

I tilfælde af et helt modul er definitionen den samme. $n$

Gruppens struktur bestemmes af følgende sætning: Hvis p er et ulige primtal, og l er et positivt heltal, så er der primitive rødder modulo , altså en cyklisk gruppe. $p^{{l}}$ $U({\mathbb {Z}}/p^{{l}}{\mathbb {Z}})$

Det følger af den kinesiske restsætning , at der er en isomorfisme ≈ . $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}})\ gange U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\ gange \dots U({\mathbb {Z}}/p_{l}^{{a_{l}}}{\mathbb {Z}})$

Gruppen er cyklisk. Dens rækkefølge er . $U({\mathbb {Z}}/p_{i}^{{a_{i}}}{\mathbb {Z}})$ $p_{i}^{{a_{i}-1}}(p_{i}-1)$

Gruppen er også cyklisk af orden a for a=1 eller a=2 . For denne gruppe er ikke cyklisk og er et direkte produkt af to cykliske grupper, ordrer og . $U({\mathbb {Z}}/2^{{a}}{\mathbb {Z}})$ $a\geqslant 3$ $2$ $2^{{a-2}}$

En gruppe er cyklisk, hvis og kun hvis eller eller n = 2 eller n = 4, hvor p er et ulige primtal. I det generelle tilfælde, som en abelsk gruppe, er den repræsenteret som et direkte produkt af cykliske primære grupper, der er isomorfe til . [5] $U({\mathbb {Z}}/n{\mathbb {Z}})$ $n=p^{a}$ $n=2p^{a}$ $U({\mathbb {Z}}/n{\mathbb {Z}})$ ${\mathbb {Z}}_{{u_{i}}}^{{+}}$

Simplicity vidne undergruppe

Lade være et ulige tal større end 1. Tallet er entydigt repræsenteret som , hvor er ulige. Et heltal , , kaldes et primtalsvidne , hvis en af følgende betingelser er opfyldt: $m$ $m-1$ $m-1=2^{s}\cdot t$ $t$ $-en$ $1<a<m$ $m$

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

eller

der er et heltal , , sådan at $k$ $0\leq k<s$ $a^{2^{k}t}\equiv m-1{\pmod {m)).$

Hvis tallet er sammensat, er der en undergruppe af den multiplikative gruppe af restringen, kaldet undergruppen af vidner til primalitet. Dens elementer hævet til magten falder sammen med modulo . $m$ $m-1$ $en$ $m$

Eksempel :. Der errester relativt prime til, detteog. ækvivalentmodulo, betyderækvivalentmodulo. Derfor,og er vidner til enkelheden af antallet. I dette tilfælde er {1, 8} en delmængde af enkelhedsvidner. [6] $m=9$ $6$ $9$ $1,2,4,5,7$ $otte$ $otte$ $-en$ $9$ $8^{{8}}$ $en$ $9$ $en$ $otte$ $9$

Egenskaber

Gruppeudstiller

Gruppeeksponenten er lig med Carmichael-funktionen . $\lambda (n)=$ $\textstyle \operatørnavn {lcm}$ $(p_{1}^{a_{1}-1}(p_{1}-1),\cdots ,p_{s}^{a_{s}-1}(p_{s}-1) )$

Gruppeordre

Rækkefølgen af gruppen er lig med Euler-funktionen :. Herfra og fra isomorfien ≈ , kan man opnå en anden måde at bevise ligheden for [5] $|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ $U({\mathbb {Z}}/m{\mathbb {Z}})$ $U({\mathbb {Z}}/p_{1}^{{a_{1}}}{\mathbb {Z}})\ gange U({\mathbb {Z}}/p_{2}^{{ a_{2}}}{\mathbb {Z}})\ gange ...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}$

Genereringssæt

$U({\mathbb {Z}}/n{\mathbb {Z}})$ er en cyklisk gruppe, hvis og kun hvis I tilfælde af en cyklisk gruppe kaldes generatoren en primitiv rod . $\varphi(n)=\lambda(n).$

Eksempel

Det reducerede system af rester modulo består af restklasser: . Med hensyn til multiplikationen, der er defineret for restklasserne, danner de desuden en gruppe og er gensidigt inverse (det vil sige ), og er omvendte til sig selv. $ti$ $fire$ $[1]_{{10}},[3]_{{10}},[7]_{{10}},[9]_{{10}}$ $[3]_{{10}}$ $[7]_{{10}}$ $[3]_{{10}}{\cdot [7]_{{10}}=[1]_{{10}}$ $[1]_{{10}}$ $[9]_{{10}}$

Gruppestruktur

Indtastningen betyder "cyklisk gruppe af orden n". $C_{n}$

Gruppestruktur (Z/ n Z) ×

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

Ansøgning

Den kryptografiske styrke af ElGamal-chiffersystemet er baseret på kompleksiteten af den diskrete logaritme i den multiplikative gruppe af restringen . [7]

Historie

Bidraget til undersøgelsen af strukturen af den multiplikative gruppe af restringen blev lavet af Artin , Bielharz, Brouwer , Wilson, Gauss , Lagrange , Lemaire, Waring , Fermat, Hooley, Euler . Lagrange beviste lemmaet, at hvis , og k er et felt, så har f højst n distinkte rødder, hvor n er potensen af f. Han beviste også en vigtig konsekvens af dette lemma, som er sammenligningen ≡ . Euler beviste Fermats lille sætning . Waring formulerede Wilsons teorem , og Lagrange beviste det. Euler foreslog eksistensen af primitive rødder modulo et primtal. Gauss beviste det. Artin fremsatte sin hypotese om eksistensen og kvantificeringen af primtal modulo, hvor et givet heltal er en primitiv rod. Brouwer bidrog til undersøgelsen af problemet med eksistensen af sæt af på hinanden følgende heltal, som hver er den kth potens modulo p. Bielhartz beviste en analog til Artins formodning. Hooley beviste Artins formodning med den antagelse, at den udvidede Riemann-hypotese er gyldig i algebraiske talfelter. [5] $f(x)\i k[x]$ $x^{{p-1}}-1$ $(x-1)(x-2)...(x-p+1)mod(p)$

Noter

↑ 1 2 I. M. Vinogradov Grundlæggende om talteori. udg. 9., revideret, M .: Nauka. 1981
↑ Sagalovich Yu. L. Introduktion til algebraiske koder. 2011.
↑ Bukhshtab, 1966 .
↑ 1 2 3 4 V. Boss Forelæsninger om matematik. Bind 14. Talteori. 2014.
↑ 1 2 3 4 5 Irland, Rosen, 1987 .
↑ Erdős, Paul ; Pomerance, Carl. Om antallet af falske vidner for et sammensat tal // Math . Comput. : journal. - 1986. - Bd. 46 . - S. 259-279 .
↑ Alferov et al., 2002 .

Litteratur

Ireland K., Rosen M. En klassisk introduktion til moderne talteori. — M .: Mir, 1987.
Alferov A.P., Zubov A.Yu., Kuzmin A.S. Cheremushkin A.V. Grundlæggende om kryptografi. - Moskva: "Helios ARV", 2002.
Rostovtsev A.G., Makhovenko E.B. Teoretisk kryptografi. - St. Petersborg: NPO "Professional", 2004.