Modulo sammenligning

At sammenligne to heltal modulo et naturligt tal er en matematisk operation, der giver dig mulighed for at besvare spørgsmålet om, hvorvidt to valgte heltal giver den samme rest , når de divideres med det samme . Ethvert heltal, når divideret med giver en af de mulige rester: et tal fra 0 til ; det betyder, at alle heltal kan opdeles i grupper, som hver svarer til en vis rest, når de divideres med . $m$ $m$ $m$ $m$ $m-1$ $m$ $m$

Aritmetiske operationer med rester af tal modulo en fast form modulær aritmetik eller modulær aritmetik [1] [2] , som er meget brugt i matematik , datalogi og kryptografi [3] .

Historie

Forudsætningen for skabelsen af teorien om sammenligninger var restaureringen af Diophantus ' værker , som blev udgivet i originalen og med en latinsk oversættelse, takket være Basha de Meziriak , i 1621 . Deres undersøgelse førte Fermat til opdagelser, der var betydeligt forud for deres tid. For eksempel rapporterede han i et brev til Frenicle de Bessy [4] den 18. oktober 1640 uden bevis en sætning , der senere blev kendt som Fermats lille sætning . I den moderne formulering siger sætningen , at hvis er et primtal og er et heltal , der ikke er deleligt med , så $s$ $-en$ $s$

a^{p-1}\equiv 1{\pmod {p}}

Det første bevis for denne sætning tilhører Leibniz , desuden opdagede han denne sætning uafhængigt af Fermat senest i 1683 og rapporterede dette med et nøjagtigt bevis for Bernoulli . Derudover foreslog Leibniz en prototype til formuleringen af Wilsons teorem .

Senere blev studiet af spørgsmål afsat til talteori og teorien om sammenligninger videreført af Euler , som introducerede den kvadratiske lov om gensidighed og generaliserede Fermats sætning , som fastslår, at

a^{\varphi (n)}\equiv 1{\pmod {n)),

hvor er Euler-funktionen . $\varphi (n)$

Konceptet og den symbolske betegnelse for sammenligninger blev introduceret af Gauss som et vigtigt værktøj til at underbygge hans aritmetiske teori, arbejde som han begyndte på i 1797. I begyndelsen af denne periode var Gauss endnu ikke klar over sine forgængeres værker, så resultaterne af hans arbejde, der er beskrevet i de første tre kapitler af hans bog Arithmetical Investigations ( 1801 ), var grundlæggende allerede kendt, men metoderne som han brugte til beviser, viste sig at være helt ny og havde den største betydning for udviklingen af talteori. Ved at bruge disse metoder transformerede Gauss al den viden, der var akkumuleret før ham, relateret til modulo-sammenligningsoperationer til en sammenhængende teori, som først blev præsenteret i samme bog. Derudover studerede han sammenligninger af første og anden grad, teorien om kvadratiske rester og den relaterede kvadratiske lov om gensidighed [5] .

Definitioner

Hvis to heltal og når divideret med giver den samme rest, kaldes de sammenlignelige (eller equiresidual ) modulo tallet [6] . $-en$ $b$ $m$ $m$

Sammenlignelighed af tal og er skrevet som en formel ( sammenligning ): $-en$ $b$

a\equiv b{\pmod {m)).

Tallet kaldes sammenligningsmodulet . $m$

Definitionen af sammenlignelighed af tal og modulo svarer til ethvert af følgende udsagn: $-en$ $b$ $m$

forskellen af tal og er divideret med uden en rest; $-en$ $b$ $m$
tal kan repræsenteres som , hvor er et eller andet heltal [7] . $-en$ $a=b+k\cdot m$ $k$

Bevis

Nødvendigheden af betingelser 1 og 2 bevises som følger:

a\equiv b{\pmod {m)).

Så under den antagelse, at

a=n_{1}m+r,\;0\leqslant r<m,

b=n_{2}m+r,\;0\leqslant r<m,

1 og 2 udføres :

ab=(n_{1}m+r)-(n_{2}m+r)=(n_{1}-n_{2})m

(det vil sige forskellen og divideres med uden en rest);

-en

b

m

a=n_{1}m+r=n_{1}m+r+(n_{2}m-n_{2}m)=b+(n_{1}-n_{2})m=b+ km ,

hvor (det vil sige kan repræsenteres som ).

{\displaystyle k=n_{1}-n_{2))

-en

a=b+km

Tilstrækkelighed af betingelser 1 og 2 :

a=b+km.

Fra beviset for den nødvendige betingelse kan nummeret repræsenteres som: $b$

b=n_{2}m+r,\;0\leqslant r<m.

Derefter

a=b+km=(n_{2}m+r)+km=nm+r,\;0\leqslant r<m,

hvor

n=k+n_{2}.

På denne måde

a\equiv b{\pmod {m)).

Det er bevist, at definitionen svarer til betingelse 2 , som svarer til betingelse 1 .

For eksempel er tallene 32 og -10 kongruente modulo 7, da begge tal, når de divideres med 7, efterlader en rest på 4:

32=7\cdot 4+4;

-10=7\cdot (-2)+4.

Også tallene 32 og -10 er sammenlignelige modulo 7, da deres forskel er delelig med 7 og desuden er der en repræsentation $32-(-10)=42$

32=6\cdot 7+(-10).

Egenskaber for sammenlignelighed modulo

For et fast naturligt tal har modulo-sammenlignelighedsrelationen følgende egenskaber: $m$ $m$

refleksivitetsegenskab : for ethvert heltal , $-en$ $a\equiv a{\pmod {m));$
symmetri egenskab : hvis da $a \equiv b \pmod m,$ $b\equiv a{\pmod {m));$
transitivitetsegenskab : hvis og derefter $a\equiv b{\pmod m}$ $b \equiv c \pmod m,$ $a \equiv c \pmod m.$

Således er modulo-sammenlignelighedsrelationen en ækvivalensrelation på sættet af heltal [8] . $m$

Ud over ovenstående egenskaber er følgende udsagn sande for sammenligninger:

vilkårlige to heltal er kongruente modulo 1;
hvis tallene og er modulo sammenlignelige , og tallet er en divisor , så er og modulo sammenlignelige ; $-en$ $b$ $m$ $d$ $m$ $-en$ $b$ $d$

Bevis

Lade

a\equiv b{\pmod {m)).

følgelig

ab=mt,

hvor er et helt tal.

t

Siden er en divisor af tallet , så $d$ $m$

m=cd,

hvor er et helt tal.

c

følgelig

ab=mt=(cd)t=qd,

hvor

q=ct,

a\equiv b{\pmod {d))

Per definition.

hvis tallene og er sammenlignelige i moduli , så er de sammenlignelige i modul lig med det mindste fælles multiplum af modulerne . $-en$ $b$ $k$ ${m_{1},m_{2},...,m_{k)),$ ${m_1, m_2, ..., m_k}$

Bevis

Lade

a\equiv b{\pmod {m_{i))},

hvor

i=1,2,...,k.

følgelig

ab=m_{i}t.

Da forskellen er et multiplum af hver , er det også et multiplum af deres mindste fælles multiplum . $ab$ $m_i$

Følge: For at tallene og skal være sammenlignelige modulo , hvis kanoniske nedbrydning i primfaktorer har formen

-en

b

m

m = \prod_{i=1}^d p_i^{\alpha_i},

nødvendigt og tilstrækkeligt til

a\equiv b{\pmod {p_{i}^{\alpha _{i))))),

hvor [9] .

i=1,2,\ldots ,d

Operationer med sammenligninger

Sammenligninger modulo en og samme har mange af egenskaberne ved almindelige ligheder. For eksempel kan de adderes, trækkes fra og ganges: hvis tal og er parvis sammenlignelige modulo , så deres summer og , samt produkter og er også sammenlignelige modulo : $a_{1},a_{2},\ldots,a_{n}$ $b_{1},b_{2},\ldots ,b_{n}$ $m$ $a_{1}+a_{2}+\ldots +a_{n}$ ${\displaystyle b_{1}+b_{2}+\ldots +b_{n))$ $a_1 \cdot a_2 \cdot ... \cdot a_n$ $b_1 \cdot b_2 \cdot ... \cdot b_n$ $m$

(a_{1}+a_{2}+\ldots +a_{n})\equiv (b_{1}+b_{2}+\ldots +b_{n}){\pmod {m)) ;

(a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n})\equiv (b_{1}\cdot b_{2}\cdot \ldots \cdot b_{n}){ \pmod{m}}.

Samtidig kan disse operationer ikke udføres med sammenligninger, hvis deres moduler ikke matcher [9] .

Du kan tilføje det samme tal til begge dele af sammenligningen : $c$

(a+c)\equiv (b+c){\pmod {m)).

Du kan også overføre et tal fra en del af sammenligningen til en anden med et fortegnsskift:

a\equiv (b+c){\pmod {m));

(ac)\equiv b{\pmod {m)).

Hvis tallene og er sammenlignelige modulo , så deres magter og er også sammenlignelige modulo for enhver naturlig [7] : $-en$ $b$ $m$ $a^k$ $b^{k}$ $m$ $k$

a^{k}\equiv b^{k}{\pmod {m)).

Til enhver af delene af sammenligningen kan du tilføje et heltalsmultiplum af modulet, det vil sige, hvis tallene og er sammenlignelige modulo nogle tal , så og er sammenlignelige med modulo , hvor og er vilkårlige heltal , der er multipla af : $-en$ $b$ $m$ $a + t_1$ $b+t_{2}$ $m$ $t_{1}$ $t_{2}$ $m$

(a+t_{1})\equiv (b+t_{2}){\pmod {m)).

Også begge dele af sammenligningen og modulet kan multipliceres med det samme tal, det vil sige, hvis tallene og er sammenlignelige modulo et heltal , så er tallene og sammenlignelige modulo tallet , hvor er et heltal : $-en$ $b$ $m$ $aq$ $bq$ $mq$ $q$

aq\equiv bq{\pmod {mq)).

Sammenligninger kan dog generelt set ikke divideres med hinanden eller med andre tal. Eksempel: Men efter at have reduceret med 2 gange får vi en fejlagtig sammenligning: . Reduktionsreglerne for sammenligninger er som følger. $14\equiv 20{\pmod {6}}$ $7\equiv 10{\pmod {6}}$

Det er muligt at dividere begge dele af sammenligningen med et tal, men kun coprime med modulet: hvis

{ad} \equiv {bd} \pmod m

og GCD derefter

{(d,m)=1},

a \equiv b \pmod m

Hvis tallet ikke er coprime med modulet, som det var i eksemplet ovenfor, så kan du ikke reducere med. $d$ $d$

Du kan samtidigt dividere begge dele af sammenligningen og modulet med deres fælles divisor:

hvis , så [9] . ${ac} \equiv {bc} \pmod {mc}$ $a \equiv b \pmod m$

Eksempel

Brugen af sammenligninger gør det nemt at opnå forskellige kriterier for delelighed . Lad os f.eks. udlede et delelighedstegn for et naturligt tal N med 7. Lad os skrive det på formen (det vil sige, at vi adskiller cifferet af enheder). Betingelsen, der er delelig med 7, kan skrives som: Gang denne sammenligning med $N$ $10a+b$ $N$ $10a+b\equiv 0{\pmod {7)).$ ${\displaystyle-2:}$

-20a-2b\equiv 0{\pmod {7)).

Eller ved at tilføje et multiplum af modulet til venstre: $21a,$

a-2b\equiv 0{\pmod {7)).

Dette indebærer følgende tegn på delelighed med 7: det er nødvendigt at trække det fordoblede antal enheder fra antallet af tiere, og gentag derefter denne operation, indtil der opnås et tocifret eller etcifret tal; hvis det er deleligt med 7, så er det oprindelige tal også deleligt. Lad os for eksempel tjekke algoritme [10] : $N=22624.$

N_{1}=2262-2\cdot 4=2254;\ N_{2}=225-2\cdot 4=217;N_{3}=21-2\cdot 7=7

Konklusion: 22624 er deleligt med 7.

Relaterede definitioner

Restklasser

Mængden af alle tal kongruent med modulo kaldes modulo -restklassen og betegnes normalt med eller . Således er sammenligning ækvivalent med lighed af restklasser [11] . $-en$ $m$ $-en$ $m$ $[er$ $\bar a_m$ $a\equiv b\pmod{m}$ $[a]_m=[b]_m$

Ethvert klassenummer kaldes en modulo - rest . Lad, for bestemthed , være resten af at dividere nogen af repræsentanterne for den valgte klasse med , Så ethvert tal fra denne klasse kan repræsenteres som , Hvor er et heltal . Den rest, der er lig med resten ( at ) kaldes den mindste ikke-negative rest , og resten ( ), den mindste i absolutte værdi, kaldes den absolut mindste rest . Når vi får det , ellers . Hvis er lige og , så [12] . $m$ $r$ $m$ $q$ $q = mt + r$ $t$ $r$ $q=r$ $t=0$ $\rho$ $q=\rho$ $r<{\frac {m}{2}}$ $\rho=r$ $\rho = r - m$ $m$ $r = \frac{m}{2}$ $\rho = -\frac{m}{2}$

Da modulo-sammenlignelighed er en ækvivalensrelation på sættet af heltal , er modulo- restklasserne ækvivalensklasser ; deres antal er lige meget . $m$ $\mathbb {Z}$ $m$ $m$

Sættet af alle restklasser modulo er angivet med enten [13] eller [14] . $m$ $\mathbb {Z} _{m}$ $\mathbb{Z}/m\mathbb{Z}$ $\mathbb{Z}/(m)$

Operationerne med addition og multiplikation på inducerer de tilsvarende operationer på sættet : $\mathbb {Z}$ $\mathbb {Z} _{m}$

[a]_{m}+[b]_{m}=[a+b]_{m};

[a]_{m}\cdot [b]_{m}=[a\cdot b]_{m}.

Med hensyn til disse operationer er sættet en endelig ring , og for en simpel ring er det et begrænset felt [6] . $\mathbb {Z} _{m}$ $m$

Fradragssystemer

Restsystemet giver dig mulighed for at udføre aritmetiske operationer på et begrænset sæt tal uden at gå ud over det. Et komplet system af rester modulo er ethvert sæt af parvis uforlignelige modulo - heltal. Normalt tages et af to sæt som et komplet system af rester modulo : $m$ $m$ $m$ $m$

de mindste ikke-negative rester , dvs. tal:

0,1,\ldots ,m-1

eller absolut mindst rester bestående af tal

0,\pm 1,\pm 2,\ldots ,\pm {\frac {m-1}{2))

, i tilfælde af ulige , og tal

m

0,\pm 1,\pm 2,\ldots ,\pm \left({\frac {m}{2}}-1\right),-{\frac {m}{2}}

i det lige tilfælde .

m

Det maksimale sæt af parvis uforlignelige modulo tal coprime med kaldes det reducerede system af modulo rester . Ethvert reduceret system af rester modulo indeholder elementer, hvor er Euler-funktionen [12] . $m$ $m$ $m$ $m$ $\varphi(m)$ $\varphi (\cdot)$

For et tal kan det komplette system af rester f.eks. repræsenteres af tallene 0, 1, 2, 3, ..., 21, 22, 23, ..., 39, 40, 41 og det reducerede system kan repræsenteres af 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. $m=42$

Sammenligninger i en polynomialring over et felt

Ringen af polynomier over feltet betragtes . To polynomier , der hører til den valgte ring, kaldes sammenlignelige modulo polynomiet , hvis deres forskel er delelig med uden rest. Sammenligningen er angivet som følger: $K[x]$ $K$ $g_{1}$ $g_{2}$ $f$ $g_1-g_2$ $f$

g_{1}\equiv g_{2}{\pmod {f)).

Ligesom i ringen af heltal, kan sådanne sammenligninger lægges til, trækkes fra og ganges [15] .

Løsning af sammenligninger

Sammenligninger af første grad

Inden for talteori , kryptografi og andre videnskabsområder opstår ofte problemet med at finde løsninger til en sammenligning af formens første grad.

a\cdot x\equiv b{\pmod {m)).

Løsningen af en sådan sammenligning begynder med beregningen af gcd . I dette tilfælde er to tilfælde mulige: $d=$ $(er)$

hvis ikke et multiplum af , så har sammenligningen ingen løsninger; $b$ $d$
hvis er et multiplum af , så har sammenligningen en unik løsning modulo , eller tilsvarende løsninger modulo . I dette tilfælde vil en reduktion af den oprindelige sammenligning med n resultere i en sammenligning: $b$ $d$ $\frac{m}{d}$ $d$ $m$ $d$

a_{1}x\equiv b_{1}{\pmod {m_{1))},

hvor og er heltal , og og er coprime . Derfor kan et tal inverteres modulo , det vil sige finde et tal sådan, at (med andre ord, ). Nu findes løsningen ved at gange den resulterende sammenligning med :

a_{1}={\frac {a}{d)),

b_1 = \frac{b}{d}

m_1 = \frac{m}{d}

a_{1}

m_1

a_{1}

m_1

c

{\displaystyle c\cdot a_{1}\equiv 1{\pmod {m_{1))))

{\displaystyle c\equiv a_{1}^{-1}{\pmod {m_{1))))

c

x\equiv ca_{1}x\equiv cb_{1}\equiv a_{1}^{-1}b_{1}{\pmod {m_{1))}.

Praktisk udregning af værdien kan gøres på forskellige måder: ved hjælp af Eulers sætning , Euklids algoritme , teorien om fortsatte brøker (se algoritme ) osv. Især Eulers sætning giver dig mulighed for at skrive værdien i formen: $c$ $c$

{\displaystyle c\equiv a_{1}^{-1}\equiv a_{1}^{\varphi (m_{1})-1}{\pmod {m_{1))))

[16] . Eksempler

Eksempel 1. Til sammenligning

6x\equiv 26{\pmod {22}}

vi har derfor modulo 22, sammenligningen har to løsninger. Lad os erstatte 26 med 4, hvilket er sammenligneligt modulo 22, og så annullere alle tre tal med 2: $d=2$

3x\equiv 2{\pmod {11}}

Da 3 er coprime modulo 11, kan den vendes modulo 11 og findes

3^{-1}\equiv 4{\pmod {11))

Ved at gange sammenligningen med 4 får vi løsningen modulo 11:

x\equiv 8{\pmod {11}}

svarende til sættet af to løsninger modulo 22:

x\equiv 8{\pmod {22}}

og .

x\equiv 19{\pmod {22}}

Eksempel 2. Der gives en sammenligning:

100 x \equiv 41\pmod {65537}.

Bemærk, at modulet er et primtal.

65537

Den første måde at løse er at bruge Bezout-relationen . Ved at bruge Euclid-algoritmen eller programmet givet i artiklen om Bezout-forholdet finder vi, at dette forhold for tal og har formen: $100$ $65537$

17695\cdot 100+(-27)\cdot 65537=1,

eller

17695 \cdot 100 \equiv 1 \pmod {65537}

Hvis vi multiplicerer begge sider af denne sammenligning med 41, får vi:

100 \cdot 725495 \equiv 41 \pmod {65537}

Det følger heraf, at der er en løsning på den oprindelige sammenligning. Det er mere bekvemt at erstatte det med noget, der kan sammenlignes med det (resten af at dividere med ). Svar: $725495$ $4588$ $725495$ $65537$ $x \equiv 4588 \pmod {65537}.$

Den anden løsning, enklere og hurtigere, kræver ikke konstruktionen af Bezout-relationen, men svarer også til den euklidiske algoritme.

Trin 1. Divider modulet med koefficienten x med resten: . Multiplicer begge sider af den oprindelige sammenligning med kvotienten og tilføj ; vi får: , men venstre side er et multiplum af , det vil sige sammenlignelig med nul, hvorfra: $65537=100 \cdot 655+37$ $655$ $37x$ $65537x\equiv 26855+37x{\pmod {65537}}$ $65537$

37x\equiv -26855{\pmod {65537}}

Vi fik en koefficient på 37 i stedet for 100 for kl. Ved hvert næste trin falder vi på samme måde, indtil vi får en. $x$

Trin 2. På samme måde dividerer vi med en ny koefficient ved x :. Gang begge dele af sammenligningen opnået i det foregående trin med kvotienten og tilføj ; igen erstatter venstre side med nul, får vi: $65537=37 \cdot 1771+10$ $1771$ $10x$

10x \equiv 47560205 \pmod {65537}

$47560205$ erstattes med resten, når divideret med lig : $65537,$ $45880$

10x \equiv 45880 \pmod {65537}

Så ville det være muligt at lave yderligere 5 trin på samme måde, men det er nemmere at dividere begge dele af sammenligningen med 10 og straks få resultatet: $x \equiv 4588 \pmod {65537}.$

Sammenligninger af anden grad

Sammenligninger af anden grads modulo m har følgende generelle form:

c_0x^2+c_1x+c \equiv 0\pmod {m}.

Dette udtryk kan bringes til formen

(x+b)^{2}\equiv a{\pmod {m)),

og når det udskiftes, forenkler det til $z = x + b$

z^{2}\equiv a{\pmod {m)).

At løse denne sammenligning kommer ned til at finde ud af, om det givne tal er en kvadratisk rest (ved at bruge den kvadratiske reciprocitetslov ) og derefter beregne kvadratroden modulo denne [17] . For at beregne kvadratroden fra en kvadratisk rest er der en probabilistisk Berlekamp-metode og en deterministisk Tonelli-Shanks-algoritme .

Sammenligningssystemer

Den kinesiske restsætning siger, at et system af kongruenser med parvise coprime - moduler er: $m_{1},m_{2},\ldots ,m_{n}$

{\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\ldots \\x\ svarende til_{n}{\pmod {m_{n}}}\end{cases}}

er altid løselig, og dens løsning er unik modulo . ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n))$

Med andre ord siger den kinesiske restsætning, at en restring modulo produktet af flere parvise coprimtal er det direkte produkt af restringene svarende til faktorerne.

Ansøgning

Modulær aritmetik bruges inden for talteori , gruppeteori , ringteori , knudeteori , generel algebra , kryptografi , datalogi , kemi og andre områder.

For eksempel bruges sammenligninger ofte til at beregne kontrolsummer, der bruges i identifikatorer. Så for at bestemme fejl ved indtastning af et internationalt bankkontonummer bruges sammenligning modulo 97 [18] .

I kryptografi kan sammenligninger findes i offentlige nøglesystemer ved hjælp af for eksempel RSA-algoritmen eller Diffie-Hellman-protokollen . Modulær aritmetik giver også endelige felter, over hvilke elliptiske kurver så bygges , og bruges i forskellige symmetriske nøgleprotokoller ( AES , IDEA ) [19] .

I kemi er det sidste ciffer i CAS-registreringsnummeret kontrolsumværdien , som beregnes ved at lægge det sidste ciffer i tallet ganget med 1, det andet ciffer fra højre ganget med 2, det tredje ciffer ganget med tre, og så på op til det første ciffer fra venstre, der slutter med beregningen af resten af divisionen med 10 [20]

Se også

Noter

↑ Welshenbach M. Kapitel 5. Modulær matematik: Beregning i restklasser. // Kryptografi i C og C++ i aktion . - M . : "Triumph", 2004. - S. 81 -95. — 464 s. — ISBN 5-89392-083-X .
↑ Materialer fra den internationale videnskabelige konference "Modular aritmetik" . Virtuelt computermuseum (2005). Dato for adgang: 31. juli 2010. Arkiveret fra originalen den 5. oktober 2007. (ubestemt)
↑ Egorov A. A. Modulo sammenligninger og resterende aritmetik // Kvant . - 1970. - Nr. 5 . - S. 28-33 . Arkiveret fra originalen den 4. marts 2016.
↑ Fransk matematiker, medlem af det franske videnskabsakademi siden 1666 .
↑ Vileitner G. Kapitel III. Talteori // Matematikkens historie fra Descartes til midten af XIX / overs. med ham. under. udg. A.P. Yushkevich. - M .: Statens forlag for fysisk og matematisk litteratur, 1960. - S. 69-84. — 467 s. Arkiveret 24. september 2015 på Wayback Machine
↑ 1 2 Stepanov S. A. Kapitel 1. Grundlæggende begreber // Sammenligninger . - M . : "Viden", 1975. - S. 3-9. — 64 s. Arkiveret 24. august 2015 på Wayback Machine
↑ 1 2 Vinogradov I.M. Grundlæggende om talteori . - M. - L . : Stat. udg. teknisk og teoretisk litteratur, 1952. - S. 41-45. - 180 s. Arkiveret 1. juli 2020 på Wayback Machine
↑ Siziy, 2008 , s. 88.
↑ 1 2 3 Sagalovich, 2010 , s. 25-29.
↑ Nesterenko, 2008 , s. 86-87.
↑ Bukhshtab A. A. Kapitel 8. Klasser // Talteori . - M . : "Oplysning", 1966. - S. 77-78. — 384 s. Arkiveret 20. november 2015 på Wayback Machine
↑ 1 2 Sagalovich, 2010 , s. 29-32.
↑ Siziy, 2008 , s. 87-88,91.
↑ Lidl R., Niederreiter G. Finite fields. I 2 bind. - M .: Mir, 1998. - S. 27 (Eksempel 1.37). — 430 s. — ISBN 5-03-000065-8 .
↑ Fadeev D.K. Kapitel VII. Sammenligning i ringen af polynomier og feltudvidelser // Forelæsninger om algebra. - M . : "Nauka", 1984. - S. 197-198. — 416 s.
↑ Siziy, 2008 , s. 105-109.
↑ Bukhshtab A. A. Kapitel 21. Sammenligninger af 2. grads modulo-primtal, Kapitel 22. Sammenligninger af anden grads modulo-sammensætning // Talteori . - M . : "Oplysning", 1966. - S. 172-201. — 384 s. Arkiveret 20. november 2015 på Wayback Machine
↑ Harald Niederreiter, Arne Winterhof. Anvendt talteori. - "Springer", 2015. - S. 369. - 442 s. — ISBN 978-3-319-22321-6 .
↑ Koblitz N. Kursus i talteori og kryptografi / oversættelse. fra engelsk. M. A. Mikhailova og V. E. Tarakanov, red. A. M. Zubkova. - M . : Videnskabeligt forlag TVP, 2001. - S. 96, 105-109, 200-209. — 262 s. — ISBN 5-85484-012-X .
↑ Tjek cifferbekræftelse af CAS- registreringsnumre . Arkiveret fra originalen den 8. december 2015.

Litteratur

Bukhshtab A. A. Talteori . - M . : "Oplysning", 1966. - 384 s.
Weil, A. Fundamentals of Number Theory . — M .: Mir, 1972.
Vilenkin N. Ya. Kongruenser og restklasser // Kvant . - 1978. - Nr. 10 . - S. 4-8 .
Vinogradov I.M. Grundlæggende om talteori . - M. - L . : Stat. udg. teknisk og teoretisk litteratur, 1952. - 180 s.
Koblitz N. Et kursus i talteori og kryptografi / pr. fra engelsk. M. A. Mikhailova og V. E. Tarakanov, red. A. M. Zubkova. - M . : Videnskabeligt forlag TVP, 2001. - 254 s. — ISBN 5-85484-012-X .
Proceedings fra den internationale videnskabelige konference "Modular aritmetik" . Virtuelt computermuseum (2005). Hentet: 31. juli 2010. (ubestemt)
Nesterenko Yu. V. Talteori. - M . : Publishing Center "Academy", 2008. - S. 132-133. — 272 s. — ISBN 9785769546464 .
Sagalovich Yu. L. Introduktion til algebraiske koder - 2. udg. - M. : IPPI RAN , 2010. - 320 s. — ISBN 978-5-901158-14-2
Siziy S. V. §4. Teori om sammenligninger // Forelæsninger om talteori. - M. : Fizmatlit, 2008. - 192 s. - ISBN 978-5-9221-0741-9 .