Porovnání modulů

Porovnání dvou celých čísel modulo přirozené číslo je matematická operace, která vám umožní odpovědět na otázku, zda dvě vybraná celá čísla dávají stejný zbytek , když je děleno stejným . Jakékoli celé číslo při dělení dává jeden z možných zbytků: číslo od 0 do ; to znamená, že všechna celá čísla lze rozdělit do skupin, z nichž každá odpovídá určitému zbytku, když je děleno . $m$ $m$ $m$ $m$ $m-1$ $m$ $m$

Aritmetické operace se zbytky čísel modulo pevná forma modulární aritmetika nebo modulární aritmetika [1] [2] , která je široce používána v matematice , informatice a kryptografii [3] .

Historie

Předpokladem pro vytvoření teorie komparace bylo restaurování Diofantových děl , která byla v originále a s latinským překladem vydána zásluhou Baši de Meziriaka v roce 1621 . Jejich studie přivedla Fermata k objevům, které výrazně předběhly dobu. Například v dopise Frenicle de Bessy [4] z 18. října 1640 uvedl bez důkazu větu , která se později stala známou jako Fermatova malá věta . V moderní formulaci , teorém říká, že jestliže je prvočíslo a je celé číslo nedělitelné , pak $p$ $A$ $p$

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

První důkaz této věty patří Leibnizovi , navíc tuto větu objevil nezávisle na Fermatovi nejpozději v roce 1683 a uvedl to přesným důkazem Bernoulliho . Kromě toho Leibniz navrhl prototyp pro formulaci Wilsonova teorému .

Později ve studiu otázek věnovaných teorii čísel a teorii porovnávání pokračoval Euler , který zavedl kvadratický zákon reciprocity a zobecnil Fermatův teorém , čímž stanovil, že

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

kde je Eulerova funkce . $\varphi (n)$

Pojem a symbolické označení přirovnání zavedl Gauss jako důležitý nástroj pro doložení své aritmetické teorie, na níž začal v roce 1797. Na počátku tohoto období Gauss ještě neznal díla svých předchůdců, takže výsledky jeho práce, uvedené v prvních třech kapitolách jeho knihy Aritmetická vyšetřování ( 1801 ), byly v zásadě již známy, ale metody které používal pro důkazy, se ukázaly jako naprosto nové, mající nejvyšší význam pro rozvoj teorie čísel. Pomocí těchto metod Gauss převedl všechny znalosti nashromážděné před ním související s operacemi modulového porovnávání do koherentní teorie, která byla poprvé představena ve stejné knize. Kromě toho se zabýval srovnáním prvního a druhého stupně, teorií kvadratických reziduí a souvisejícím kvadratickým zákonem reciprocity [5] .

Definice

Jestliže dvě celá čísla a když je děleno dají stejný zbytek, pak se nazývají srovnatelné (nebo ekvidistivní ) modulo číslo [6] . $A$ $b$ $m$ $m$

Srovnatelnost čísel a je zapsána jako vzorec ( srovnání ): $A$ $b$

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

Číslo se nazývá modul porovnání. $m$

Definice srovnatelnosti čísel a modulo je ekvivalentní kterémukoli z následujících tvrzení: $A$ $b$ $m$

rozdíl čísel a dělí se beze zbytku; $A$ $b$ $m$
číslo může být reprezentováno jako , kde je nějaké celé číslo [7] . $A$ $a=b+k\cdot m$ $k$

Důkaz

Nezbytnost podmínek 1 a 2 je prokázána takto:

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

Pak za předpokladu, že

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

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

1 a 2 se provádějí :

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

(tj. rozdíl a dělí se beze zbytku);

A

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 ,

kde (to znamená, že může být reprezentováno jako ).

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

A

a=b+km

Dostatečnost podmínek 1 a 2 :

a=b+km.

Z důkazu nezbytné podmínky může být číslo reprezentováno jako: $b$

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

Pak

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

kde

n=k+n_{2}.

Takto

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

Je prokázáno , že definice je ekvivalentní podmínce 2 , která je ekvivalentní podmínce 1 .

Například čísla 32 a -10 jsou kongruentní modulo 7, protože obě čísla, když jsou dělena 7, ponechají zbytek 4:

32=7\cdot 4+4;

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

Také čísla 32 a -10 jsou srovnatelné modulo 7, protože jejich rozdíl je dělitelný 7 a navíc existuje reprezentace $32-(-10)=42$

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

Vlastnosti srovnatelnosti modulo

Pro pevné přirozené číslo má vztah srovnatelnosti modulo následující vlastnosti: $m$ $m$

vlastnost reflexivity : pro libovolné celé číslo , $A$ $a\equiv a{\pmod {m));$
vlastnost symetrie : if then $a \equiv b \pmod m,$ $b\equiv a{\pmod {m));$
tranzitivní vlastnost : jestliže a pak $a\equiv b{\pmod m}$ $b \equiv c \pmod m,$ $a \equiv c \pmod m.$

Relace srovnatelnosti modulo je tedy relací ekvivalence na množině celých čísel [8] . $m$

Kromě výše uvedených vlastností platí pro srovnání následující tvrzení:

libovolná dvě celá čísla jsou kongruentní modulo 1;
jestliže čísla a jsou modulo srovnatelná a číslo je dělitel , pak a jsou modulo srovnatelné ; $A$ $b$ $m$ $d$ $m$ $A$ $b$ $d$

Důkaz

Nechat

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

tudíž

ab=mt,

kde je nějaké celé číslo.

t

Protože je dělitel čísla , pak $d$ $m$

m=cd,

kde je nějaké celé číslo.

C

tudíž

ab=mt=(cd)t=qd,

kde

q=ct,

a\equiv b{\pmod {d))

podle definice.

jestliže čísla a jsou srovnatelná v modulech , pak jsou srovnatelné v modulu rovném nejmenšímu společnému násobku modulů . $A$ $b$ $k$ ${m_{1},m_{2},...,m_{k)),$ ${m_1, m_2, ..., m_k}$

Důkaz

Nechat

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

kde

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

tudíž

ab=m_{i}t.

Protože rozdíl je násobkem každého , je také násobkem jejich nejmenšího společného násobku . $ab$ $m_i$

Následek: Aby čísla byla srovnatelná modulo , jehož kanonický rozklad na prvočinitele má tvar

A

b

m

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

nutné a dostatečné

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

kde [9] .

i=1,2,\ldots ,d

Operace s porovnáním

Srovnání modulo jedno a totéž mají mnoho vlastností běžných rovnosti. Lze je například sčítat, odečítat a násobit: jestliže čísla a jsou párově srovnatelné modulo , pak jejich součty a , stejně jako součiny a jsou také srovnatelné 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}}.

Tyto operace zároveň nelze provádět s porovnáním, pokud se jejich moduly neshodují [9] .

Do obou částí srovnání můžete přidat stejné číslo : $C$

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

Můžete také přenést číslo z jedné části srovnání do druhé se změnou znaménka:

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

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

Pokud jsou čísla a srovnatelné modulo , pak jejich síly a jsou také srovnatelné modulo pro jakékoli přirozené [7] : $A$ $b$ $m$ $a^k$ $b^{k}$ $m$ $k$

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

Ke kterékoli z částí srovnání můžete přidat celočíselný násobek modulu, to znamená, že pokud jsou čísla a srovnatelná modulo nějaké číslo , pak a je srovnatelné s modulo , kde a jsou libovolná celá čísla , která jsou násobky : $A$ $b$ $m$ $a + t_1$ $b+t_{2}$ $m$ $t_{1}$ $t_{2}$ $m$

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

Také obě části srovnání a modul lze vynásobit stejným číslem, to znamená, že pokud čísla a jsou srovnatelná modulo nějaké celé číslo , pak čísla a jsou srovnatelná modulo číslo , kde je celé číslo : $A$ $b$ $m$ $aq$ $bq$ $mq$ $q$

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

Srovnání však nelze, obecně řečeno, dělit mezi sebou nebo jinými čísly. Příklad: , ale po 2násobném snížení dostaneme chybné srovnání: . Pravidla snížení pro srovnání jsou následující. $14\ekviv 20{\pmod {6}}$ $7\ekviv 10{\pmod {6}}$

Obě části srovnání je možné vydělit číslem, ale pouze společně s modulem: if

{ad} \equiv {bd} \pmod m

a pak GCD

{(d,m)=1},

a \equiv b \pmod m

Pokud číslo není společné s modulem, jak tomu bylo ve výše uvedeném příkladu, pak nelze snížit o. $d$ $d$

Obě části srovnání a modul můžete současně vydělit jejich společným dělitelem:

pokud , tak [9] . ${ac} \equiv {bc} \pmod {mc}$ $a \equiv b \pmod m$

Příklad

Použití srovnání usnadňuje získání různých kritérií pro dělitelnost . Odvoďme například znaménko dělitelnosti přirozeného čísla N 7. Zapišme jej ve tvaru (tedy oddělíme číslici jednotek). Podmínku , která je dělitelná 7, lze zapsat jako: Vynásobte toto srovnání číslem $N$ $10a+b$ $N$ $10a+b\equiv 0{\pmod {7)).$ ${\displaystyle-2:}$

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

Nebo přidáním násobku modulu vlevo: $21a,$

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

Z toho vyplývá následující znaménko dělitelnosti 7: je nutné odečíst zdvojnásobený počet jednotek od počtu desítek, pak tuto operaci opakovat, dokud nezískáte dvoumístné nebo jednomístné číslo; pokud je dělitelné 7, pak je dělitelné i původní číslo. Podívejme se například na kontrolní algoritmus [10] : $N=22624.$

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

Závěr: 22624 je dělitelné 7.

Související definice

Třídy reziduí

Množina všech čísel shodných s modulo se nazývá třída zbytků modulo a obvykle se označuje nebo . Srovnání je tedy ekvivalentní rovnosti tříd zbytků [11] . $A$ $m$ $A$ $m$ $[dopoledne$ $\bar a_m$ $a\equiv b\pmod{m}$ $[a]_m=[b]_m$

Jakékoli číslo třídy se nazývá modulo zbytek . Nechť, pro definitivnost , je zbytek dělení kteréhokoli ze zástupců vybrané třídy , pak libovolné číslo z této třídy může být reprezentováno jako , kde je celé číslo . Zbytek rovný zbytku ( at ) se nazývá nejmenší nezáporný zbytek a zbytek ( ), nejmenší v absolutní hodnotě, se nazývá absolutně nejmenší zbytek . Když to dostaneme , jinak . Pokud je sudé a , pak [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}$

Protože modulo srovnatelnost je vztah ekvivalence na množině celých čísel , třídy zbytků modulo jsou třídy ekvivalence ; jejich počet je stejný . $m$ $\mathbb {Z}$ $m$ $m$

Množina všech tříd zbytků modulo je označena buď [13] nebo [14] . $m$ $\mathbb {Z} _{m}$ $\mathbb{Z}/m\mathbb{Z}$ $\mathbb{Z}/(m)$

Operace sčítání a násobení vyvolávají odpovídající operace na množině : $\mathbb {Z}$ $\mathbb {Z} _{m}$

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

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

S ohledem na tyto operace je množina konečným kruhem a pro jednoduchou je to konečné pole [6] . $\mathbb {Z} _{m}$ $m$

Odpočtové systémy

Systém zbytků vám umožňuje provádět aritmetické operace na konečné množině čísel, aniž byste ji překračovali. Kompletní systém reziduí modulo je jakákoliv sada párově nesrovnatelných modulo celých čísel. Obvykle se jedna ze dvou sad bere jako úplný systém reziduí modulo : $m$ $m$ $m$ $m$

nejmenší nezáporné zbytky , tj. čísla:

0,1,\ldots ,m-1

nebo absolutně nejmenší zbytky sestávající z čísel

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

, v případě lichých a čísel

m

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

v sudém případě .

m

Maximální množina párově nesrovnatelných modulo čísel , se kterými se spojuje , se nazývá redukovaný systém modulo zbytků . Libovolný redukovaný systém reziduí modulo obsahuje prvky, kde je Eulerova funkce [12] . $m$ $m$ $m$ $m$ $\varphi(m)$ $\varphi (\cdot)$

Například pro číslo může být úplný systém zbytků reprezentován čísly 0, 1, 2, 3, ..., 21, 22, 23, ..., 39, 40, 41 a redukovaným systémem může být reprezentováno 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. $m=42$

Srovnání v polynomickém kruhu nad polem

Uvažuje se prstenec polynomů nad polem . Dva polynomy a náležející ke zvolenému okruhu se nazývají srovnatelný modulo polynom , pokud je jejich rozdíl beze zbytku dělitelný . Srovnání je označeno takto: $K[x]$ $K$ $g_{1}$ $g_{2}$ $F$ $g_1-g_2$ $F$

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

Stejně jako v kruhu celých čísel lze taková srovnání sčítat, odečítat a násobit [15] .

Řešení srovnání

Srovnání prvního stupně

V teorii čísel , kryptografii a dalších vědních oborech často vyvstává problém najít řešení pro srovnání prvního stupně tvaru.

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

Řešení takového srovnání začíná výpočtem gcd . V tomto případě jsou možné dva případy: $d=$ $(dopoledne)$

pokud není násobkem , pak srovnání nemá řešení; $b$ $d$
pokud je násobkem , pak má porovnání jedinečné řešení modulo , nebo ekvivalentně řešení modulo . V tomto případě zmenšení původního srovnání o n povede k porovnání: $b$ $d$ $\frac{m}{d}$ $d$ $m$ $d$

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

kde a jsou celá čísla a a jsou coprime . Proto může být číslo invertováno modulo , to znamená, najít číslo takové, že (jinými slovy, ). Nyní je řešení nalezeno vynásobením výsledného srovnání :

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))}.

Praktický výpočet hodnoty lze provést různými způsoby: pomocí Eulerovy věty , Euklidova algoritmu , teorie spojitých zlomků (viz algoritmus ) atd. Zejména Eulerova věta umožňuje zapsat hodnotu ve tvaru: $C$ $C$

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

[16] . Příklady

Příklad 1. Pro srovnání

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

máme tedy modulo 22, srovnání má dvě řešení. Nahradíme 26 4, což je srovnatelné modulo 22, a pak všechna tři čísla zrušme 2: $d=2$

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

Protože 3 je coprime modulo 11, lze jej převrátit modulo 11 a nalézt

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

Vynásobením srovnání 4 dostaneme řešení modulo 11:

x\equiv 8{\pmod {11}}

ekvivalentní množině dvou řešení modulo 22:

x\equiv 8{\pmod {22}}

a .

x\equiv 19{\pmod {22}}

Příklad 2. Je uvedeno srovnání:

100 x \ekviv 41\pmod {65537}.

Všimněte si, že modul je prvočíslo.

65537

Prvním způsobem řešení je použití vztahu Bezout . Pomocí Euklidova algoritmu nebo programu uvedeného v článku o Bezoutově poměru zjistíme, že tento poměr pro čísla a má tvar: $100$ $65537$

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

nebo

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

Vynásobením obou stran tohoto srovnání číslem 41 dostaneme:

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

Z toho vyplývá, že existuje řešení původního srovnání. Je vhodnější jej nahradit něčím srovnatelným (zbytek po dělení ) . Odpovědět: $725495$ $4588$ $725495$ $65537$ $x \equiv 4588 \pmod {65537}.$

Druhé řešení, jednodušší a rychlejší, nevyžaduje konstrukci Bezoutova vztahu, ale je také ekvivalentní Euklidovu algoritmu.

Krok 1. Vydělte modul koeficientem x se zbytkem: . Vynásobte obě strany původního srovnání kvocientem a přidejte ; dostaneme: , ale levá strana je násobkem , tedy srovnatelná s nulou, odkud: $65537=100 \cdot 655+37$ $655$ $37x$ $65537x\equiv 26855+37x{\pmod {65537}}$ $65537$

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

Získali jsme koeficient 37 místo 100 pro at. V každém dalším kroku stejným způsobem klesáme, dokud nedosáhneme jedničky. $X$

Krok 2. Podobně dělíme novým koeficientem v x: . Vynásobte obě části srovnání získané v předchozím kroku kvocientem a sečtěte ; opět nahrazením levé strany nulou, dostaneme: $65537=37 \cdot 1771+10$ $1771$ $10x$

10x \equiv 47560205 \pmod {65537}

$47560205$ nahradit jeho zbytkem, když je děleno rovným : $65537,$ $45880$

10x \equiv 45880 \pmod {65537}

Pak by bylo možné udělat dalších 5 kroků stejným způsobem, ale je jednodušší vydělit obě části srovnání 10 a okamžitě získat výsledek: $x \equiv 4588 \pmod {65537}.$

Srovnání druhého stupně

Srovnání druhého stupně modulo m mají následující obecný tvar:

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

Tento výraz lze přenést do formuláře

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

a po výměně se zjednoduší $z = x + b$

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

Řešení tohoto srovnání spočívá ve zjištění, zda dané číslo je kvadratickým zbytkem (pomocí kvadratického zákona reciprocity ) a poté výpočtem druhé odmocniny modulo this [17] . Pro výpočet druhé odmocniny z kvadratického zbytku existuje pravděpodobnostní Berlekampova metoda a deterministický Tonelli-Shanksův algoritmus .

Srovnávací systémy

Čínská věta o zbytku říká, že systém kongruencí s párovými coprime moduly je: $m_{1},m_{2},\ldots ,m_{n}$

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

je vždy řešitelné a jeho řešení je unikátní modulo . ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n))$

Jinými slovy, čínská věta o zbytku říká, že zbytkový kruh modulo součin několika párových koprimých čísel je přímým součinem zbytkových kruhů odpovídajících faktorům.

Aplikace

Modulární aritmetika se používá v teorii čísel , teorii skupin , teorii prstenů , teorii uzlů , obecné algebře , kryptografii , informatice , chemii a dalších oborech.

Porovnání se například často používá k výpočtu kontrolních součtů používaných v identifikátorech. Pro zjištění chyb při zadávání mezinárodního čísla bankovního účtu se tedy používá srovnávací modulo 97 [18] .

V kryptografii lze srovnání nalézt v systémech s veřejným klíčem pomocí například algoritmu RSA nebo protokolu Diffie-Hellman . Modulární aritmetika také poskytuje konečná pole , nad nimiž se potom sestavují eliptické křivky , a používá se v různých protokolech symetrických klíčů ( AES , IDEA ) [19] .

V chemii je poslední číslice v registračním čísle CAS hodnota kontrolního součtu , která se vypočítá sečtením poslední číslice čísla vynásobené 1, druhé číslice zprava vynásobené dvěma, třetí číslice vynásobené třemi atd. až po první číslici zleva, končící výpočtem zbytku dělení 10 [20]

Viz také

Poznámky

↑ Welshenbach M. Kapitola 5. Modulární matematika: Výpočet ve třídách reziduí. // Kryptografie v C a C++ v akci . - M .: "Triumph", 2004. - S. 81 -95. — 464 s. — ISBN 5-89392-083-X .
↑ Materiály mezinárodní vědecké konference "Modulární aritmetika" . Muzeum virtuálních počítačů (2005). Datum přístupu: 31. července 2010. Archivováno z originálu 5. října 2007. (neurčitý)
↑ Egorov A. A. Modulo srovnání a zbytková aritmetika // Kvant . - 1970. - č. 5 . - S. 28-33 . Archivováno z originálu 4. března 2016.
↑ Francouzský matematik, od roku 1666 člen Francouzské akademie věd .
↑ Vileitner G. Kapitola III. Teorie čísel // Historie matematiky od Descarta do poloviny XIX . / přel. s ním. pod. vyd. A. P. Juškevič. - M .: Státní nakladatelství fyzikální a matematické literatury, 1960. - S. 69-84. — 467 s. Archivováno 24. září 2015 na Wayback Machine
↑ 1 2 Stepanov S. A. Kapitola 1. Základní pojmy // Srovnání . - M .: "Znalosti", 1975. - S. 3-9. — 64 str. Archivováno 24. srpna 2015 na Wayback Machine
↑ 1 2 Vinogradov I.M. Základy teorie čísel . - M. - L . : Stát. vyd. technická a teoretická literatura, 1952. - S. 41-45. — 180 s. Archivováno 1. července 2020 na Wayback Machine
↑ Siziy, 2008 , str. 88.
↑ 1 2 3 Sagalovich, 2010 , str. 25-29.
↑ Nesterenko, 2008 , str. 86-87.
↑ Bukhshtab A. A. Kapitola 8. Třídy // Teorie čísel . - M .: "Osvícení", 1966. - S. 77-78. — 384 s. Archivováno 20. listopadu 2015 na Wayback Machine
↑ 1 2 Sagalovich, 2010 , str. 29-32.
↑ Siziy, 2008 , str. 87-88,91.
↑ Lidl R., Niederreiter G. Konečná pole. Ve 2 sv. - M .: Mir, 1998. - S. 27 (příklad 1.37). — 430 s. — ISBN 5-03-000065-8 .
↑ Fadeev D.K. Kapitola VII. Srovnání v kruhu polynomů a rozšíření pole // Přednášky o algebře. - M .: "Nauka", 1984. - S. 197-198. — 416 s.
↑ Siziy, 2008 , str. 105-109.
↑ Bukhshtab A. A. Kapitola 21. Srovnání prvočísel modulo 2. stupně, Kapitola 22. Srovnání modulo kompozitu druhého stupně // Teorie čísel . - M .: "Osvícení", 1966. - S. 172-201. — 384 s. Archivováno 20. listopadu 2015 na Wayback Machine
↑ Harald Niederreiter, Arne Winterhof. Aplikovaná teorie čísel. - "Springer", 2015. - S. 369. - 442 s. — ISBN 978-3-319-22321-6 .
↑ Koblitz N. Kurz teorie čísel a kryptografie / přel. z angličtiny. M. A. Michajlova a V. E. Tarakanov, ed. A. M. Zubková. - M . : Vědecké nakladatelství TVP, 2001. - S. 96, 105-109, 200-209. — 262 s. — ISBN 5-85484-012-X .
↑ Kontrola číslicového ověření registračních čísel CAS . Archivováno z originálu 8. prosince 2015.

Literatura

Bukhshtab A. A. Teorie čísel . - M .: "Osvícení", 1966. - 384 s.
Weil, A. Základy teorie čísel . — M .: Mir, 1972.
Vilenkin N. Ya. Kongruence a třídy reziduí // Kvant . - 1978. - č. 10 . - str. 4-8 .
Vinogradov I.M. Základy teorie čísel . - M. - L . : Stát. vyd. technická a teoretická literatura, 1952. - 180 s.
Koblitz N. Kurz teorie čísel a kryptografie / per. z angličtiny. M. A. Michajlova a V. E. Tarakanov, ed. A. M. Zubková. - M . : Vědecké nakladatelství TVP, 2001. - 254 s. — ISBN 5-85484-012-X .
Sborník příspěvků z mezinárodní vědecké konference "Modulární aritmetika" . Muzeum virtuálních počítačů (2005). Staženo: 31. července 2010. (neurčitý)
Nesterenko Yu. V. Teorie čísel. - M . : Publikační středisko "Akademie", 2008. - S. 132-133. — 272 s. — ISBN 9785769546464 .
Sagalovich Yu.L. Úvod do algebraických kódů - 2. vyd. - M. : IPPI RAN , 2010. - 320 s. — ISBN 978-5-901158-14-2
Siziy S. V. §4. Teorie porovnávání // Přednášky o teorii čísel. - M. : Fizmatlit, 2008. - 192 s. - ISBN 978-5-9221-0741-9 .