Modulo jämförelse

Att jämföra två heltal modulo ett naturligt tal är en matematisk operation som låter dig svara på frågan om två valda heltal ger samma återstod när de divideras med detsamma . Ett heltal dividerat med ger en av de möjliga resterna: ett tal från 0 till ; detta innebär att alla heltal kan delas in i grupper, som var och en motsvarar en viss återstod när de divideras med . $m$ $m$ $m$ $m$ $m-1$ $m$ $m$

Aritmetiska operationer med rester av tal modulo en fast form modulär aritmetik eller modulär aritmetik [1] [2] , som används flitigt inom matematik , datavetenskap och kryptografi [3] .

Historik

Förutsättningen för skapandet av teorin om jämförelser var restaureringen av Diophantus verk , som släpptes i original och med en latinsk översättning, tack vare Basha de Meziriak , 1621 . Deras studie ledde Fermat till upptäckter som var betydligt före sin tid. Till exempel, i ett brev till Frenicle de Bessy [4] den 18 oktober 1640, rapporterade han utan bevis en sats som senare blev känd som Fermats lilla sats . I den moderna formuleringen säger satsen att om är ett primtal och är ett heltal som inte är delbart med , då $sid$ $a$ $sid$

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

Det första beviset för denna teorem tillhör Leibniz , dessutom upptäckte han denna teorem oberoende av Fermat senast 1683 och rapporterade detta med ett exakt bevis för Bernoulli . Dessutom föreslog Leibniz en prototyp för formuleringen av Wilsons teorem .

Senare fortsatte studien av frågor som ägnas åt talteori och teorin om jämförelser av Euler , som introducerade den kvadratiska lagen om ömsesidighet och generaliserade Fermats teorem , och slog fast att

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

var är Euler-funktionen . $\varphi (n)$

Konceptet och den symboliska beteckningen av jämförelser introducerades av Gauss som ett viktigt verktyg för att underbygga sin aritmetiska teori, arbete som han började med 1797. I början av denna period var Gauss ännu inte medveten om sina föregångares verk, så resultaten av hans arbete, som beskrivs i de tre första kapitlen i hans bok Arithmetical Investigations ( 1801 ), var i princip redan kända, men metoderna som han använde för bevis visade sig vara helt nytt, med den största betydelsen för utvecklingen av talteorin. Med hjälp av dessa metoder omvandlade Gauss all kunskap som ackumulerats före honom relaterad till modulo-jämförelseoperationer till en sammanhängande teori, som först presenterades i samma bok. Dessutom studerade han jämförelser av första och andra graden, teorin om kvadratiska rester och den relaterade kvadratiska lagen om ömsesidighet [5] .

Definitioner

Om två heltal och när de divideras med ger samma återstod, då kallas de jämförbara (eller equiresidual ) modulo talet [6] . $a$ $b$ $m$ $m$

Jämförbarhet av tal och skrivs som en formel ( jämförelse ): $a$ $b$

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

Talet kallas jämförelsemodulen . $m$

Definitionen av jämförbarhet av tal och modulo motsvarar något av följande påståenden: $a$ $b$ $m$

skillnaden mellan tal och divideras med utan rest; $a$ $b$ $m$
nummer kan representeras som , där är något heltal [7] . $a$ $a=b+k\cdot m$ $k$

Bevis

Nödvändigheten av villkor 1 och 2 bevisas enligt följande:

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

Då under antagandet att

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

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

1 och 2 exekveras :

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

(det vill säga skillnaden och delas med utan rest);

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 ,

där (det vill säga kan representeras som ).

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

a

a=b+km

Tillräcklighet med villkor 1 och 2 :

a=b+km.

Från beviset på det nödvändiga villkoret kan numret representeras som: $b$

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

Sedan

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

var

n=k+n_{2}.

På det här sättet

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

Definitionen har visat sig vara ekvivalent med villkor 2 , vilket är ekvivalent med villkor 1 .

Till exempel är talen 32 och −10 kongruenta modulo 7, eftersom båda talen, när de divideras med 7, lämnar en rest av 4:

32=7\cdot 4+4;

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

Dessutom är siffrorna 32 och -10 jämförbara modulo 7, eftersom deras skillnad är delbar med 7 och dessutom finns en representation $32-(-10)=42$

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

Jämförbarhetsegenskaper modulo

För ett fast naturligt tal har modulo-jämförbarhetsrelationen följande egenskaper: $m$ $m$

reflexivitetsegenskap : för vilket heltal som helst , $a$ $a\equiv a{\pmod {m));$
symmetriegenskap : om då $a \equiv b \pmod m,$ $b\equiv a{\pmod {m));$
transitivitetsegenskap : om och då $a\equiv b{\pmod m}$ $b \equiv c \pmod m,$ $a \equiv c \pmod m.$

Således är modulo-jämförbarhetsrelationen en ekvivalensrelation på uppsättningen av heltal [8] . $m$

Förutom ovanstående egenskaper är följande påståenden sanna för jämförelser:

vilka två heltal som helst är kongruenta modulo 1;
om talen och är modulojämförbara och talet är en divisor , då är och modulojämförbara ; $a$ $b$ $m$ $d$ $m$ $a$ $b$ $d$

Bevis

Låta

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

Följaktligen

ab=mt,

var är något heltal.

t

Eftersom är en divisor av talet , alltså $d$ $m$

m=cd,

var är något heltal.

c

Följaktligen

ab=mt=(cd)t=qd,

var

q=ct,

och

a\equiv b{\pmod {d))

per definition.

om siffrorna och är jämförbara i moduli , så är de jämförbara i modul lika med den minsta gemensamma multipeln av modulerna . $a$ $b$ $k$ ${m_{1},m_{2},...,m_{k)),$ ${m_1, m_2, ..., m_k}$

Bevis

Låta

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

var

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

Följaktligen

ab=m_{i}t.

Eftersom skillnaden är en multipel av varje , är den också en multipel av deras minsta gemensamma multipel . $ab$ $mi$

Följd: För att talen och siffrorna ska vara jämförbara modulo , vars kanoniska uppdelning i primtal har formen

a

b

m

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

nödvändigt och tillräckligt för att

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

där [9] .

i=1,2,\ldots ,d

Operationer med jämförelser

Jämförelser modulo en och samma har många av egenskaperna hos vanliga likheter. Till exempel kan de adderas, subtraheras och multipliceras: om siffror och är parvis jämförbara modulo , då deras summor och , såväl som produkter och är också jämförbara 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}}.

Samtidigt kan dessa operationer inte utföras med jämförelser om deras moduler inte matchar [9] .

Du kan lägga till samma nummer i båda delarna av jämförelsen : $c$

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

Du kan också överföra ett nummer från en del av jämförelsen till en annan med ett teckenbyte:

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

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

Om siffrorna och är jämförbara modulo , då deras styrkor och är också jämförbara modulo för alla naturliga [7] : $a$ $b$ $m$ $a^k$ $b^{k}$ $m$ $k$

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

Till någon av delarna av jämförelsen kan du lägga till en heltalsmultipel av modulen, det vill säga om talen och är jämförbara modulo något nummer , då och är jämförbart med modulo , där och är godtyckliga heltal som är multiplar av : $a$ $b$ $m$ $a + t_1$ $b+t_{2}$ $m$ $t_{1}$ $t_{2}$ $m$

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

Dessutom kan båda delarna av jämförelsen och modulen multipliceras med samma tal, det vill säga om talen och är jämförbara modulo något heltal , då är talen och jämförbara modulo talet , där är ett heltal : $a$ $b$ $m$ $aq$ $bq$ $mq$ $q$

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

Jämförelser kan dock generellt sett inte delas med varandra eller med andra tal. Exempel: , men efter att ha minskat med 2 gånger får vi en felaktig jämförelse: . Nedsättningsreglerna för jämförelser är följande. $14\equiv 20{\pmod {6}}$ $7\ekvivalent 10{\pmod {6}}$

Det är möjligt att dela båda delarna av jämförelsen med ett tal, men bara samprima med modulen: om

{ad} \equiv {bd} \pmod m

och GCD då

{(d,m)=1},

a \equiv b \pmod m

Om talet inte är coprime med modulen, som det var i exemplet ovan, kan du inte minska med. $d$ $d$

Du kan samtidigt dividera båda delarna av jämförelsen och modulen med deras gemensamma divisor:

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

Exempel

Användningen av jämförelser gör det enkelt att få fram olika kriterier för delbarhet . Låt oss till exempel härleda ett tecken på delbarhet av ett naturligt tal N med 7. Låt oss skriva det i formen (det vill säga vi separerar siffran av enheter). Villkoret som är delbart med 7 kan skrivas som: Multiplicera denna jämförelse med $N$ $10a+b$ $N$ $10a+b\equiv 0{\pmod {7)).$ ${\displaystyle-2:}$

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

Eller genom att lägga till en multipel av modulen till vänster: $21a,$

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

Detta innebär följande tecken på delbarhet med 7: det är nödvändigt att subtrahera det fördubblade antalet enheter från antalet tiotal, upprepa sedan denna operation tills ett tvåsiffrigt eller ensiffrigt tal erhålls; om det är delbart med 7, är det ursprungliga talet också delbart. Låt oss till exempel kontrollera algoritmen [10] : $N=22624.$

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

Slutsats: 22624 är delbart med 7.

Relaterade definitioner

Restklasser

Mängden av alla tal som är kongruenta med modulo kallas modulo -restklassen och betecknas vanligtvis med eller . Således är jämförelse ekvivalent med jämlikhet mellan restklasser [11] . $a$ $m$ $a$ $m$ $[a]_m$ $\bar a_m$ $a\equiv b\pmod{m}$ $[a]_m=[b]_m$

Varje klassnummer kallas en modulo- rest . Låt, för bestämdhet , vara resten av att dividera någon av representanterna för den valda klassen med , då alla nummer från denna klass kan representeras som , där är ett heltal . Resten som är lika med resten ( at ) kallas den minsta icke-negativa resten , och resten ( ), den minsta i absoluta värde, kallas den absolut minsta resten . När vi får det , annars . Om är jämnt och , då [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}$

Eftersom modulo-jämförbarhet är en ekvivalensrelation på uppsättningen av heltal , är modulo- restklasserna ekvivalensklasser ; deras antal är lika . $m$ $\mathbb {Z}$ $m$ $m$

Uppsättningen av alla restklasser modulo betecknas med antingen [13] eller [14] . $m$ $\mathbb {Z} _{m}$ $\mathbb{Z}/m\mathbb{Z}$ $\mathbb{Z}/(m)$

Operationerna med addition och multiplikation på inducerar motsvarande operationer på uppsättningen : $\mathbb {Z}$ $\mathbb {Z} _{m}$

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

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

Med avseende på dessa operationer är uppsättningen en finit ring , och för en enkel sådan är den ett finit fält [6] . $\mathbb {Z} _{m}$ $m$

Avdragssystem

Restsystemet låter dig utföra aritmetiska operationer på en ändlig uppsättning tal utan att gå utöver den. Ett komplett system av rester modulo är vilken uppsättning av parvis ojämförliga modulo heltal som helst. Vanligtvis tas en av två uppsättningar som ett komplett system av rester modulo : $m$ $m$ $m$ $m$

de minsta icke-negativa resterna , d.v.s. siffror:

0,1,\ldots ,m-1

eller absolut minst rester som består av siffror

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

, vid udda , och siffror

m

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

i det jämna fallet .

m

Den maximala uppsättningen av parvis ojämförbara modulo - tal som samprimeras med kallas det reducerade systemet av modulo- rester . Varje reducerat system av rester modulo innehåller element, där är Euler-funktionen [12] . $m$ $m$ $m$ $m$ $\varphi(m)$ $\varphi (\cdot )$

Till exempel, för ett tal, kan hela systemet av rester representeras av siffrorna 0, 1, 2, 3, ..., 21, 22, 23, ..., 39, 40, 41 och det reducerade systemet kan representeras av 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. $m=42$

Jämförelser i en polynomring över ett fält

Ringen av polynom över fältet betraktas . Två polynom och som hör till den valda ringen kallas jämförbara modulo polynomet om deras skillnad är delbar med utan rest. Jämförelsen betecknas som följer: $K[x]$ $K$ $g_{1}$ $g_{2}$ $f$ $g_1-g_2$ $f$

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

Precis som i ringen av heltal kan sådana jämförelser adderas, subtraheras och multipliceras [15] .

Lösa jämförelser

Jämförelser av första graden

Inom talteori , kryptografi och andra vetenskapsområden uppstår ofta problemet med att hitta lösningar för en jämförelse av den första graden av formen

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

Lösningen av en sådan jämförelse börjar med beräkningen av gcd . I det här fallet är två fall möjliga: $d=$ $(a,m)$

om inte en multipel av , så har jämförelsen inga lösningar; $b$ $d$
om är en multipel av , då har jämförelsen en unik lösning modulo , eller, ekvivalent, lösningar modulo . I det här fallet resulterar en minskning av den ursprungliga jämförelsen med n i en jämförelse: $b$ $d$ $\frac{m}{d}$ $d$ $m$ $d$

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

där och är heltal , och och är coprime . Därför kan ett tal inverteras modulo , det vill säga hitta ett tal så att (med andra ord, ). Nu hittas lösningen genom att multiplicera den resulterande jämförelsen 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 beräkning av värdet kan göras på olika sätt: med Eulers sats , Euklides algoritm , teorin om fortsatta bråktal (se algoritm ), etc. I synnerhet låter Eulers sats dig skriva värdet i formen: $c$ $c$

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

[16] . Exempel

Exempel 1. För jämförelse

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

vi har därför modulo 22, jämförelsen har två lösningar. Låt oss ersätta 26 med 4, vilket är jämförbart modulo 22, och sedan avbryta alla tre talen med 2: $d=2$

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

Eftersom 3 är coprime modulo 11, kan den inverteras modulo 11 och hittas

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

Genom att multiplicera jämförelsen med 4 får vi lösningen modulo 11:

x\equiv 8{\pmod {11}}

motsvarar uppsättningen av två lösningar modulo 22:

x\equiv 8{\pmod {22}}

och .

x\equiv 19{\pmod {22}}

Exempel 2. En jämförelse ges:

100 x \equiv 41\pmod {65537}.

Observera att modulen är ett primtal.

65537

Det första sättet att lösa är att använda Bezout-relationen . Med hjälp av Euclid-algoritmen eller programmet som ges i artikeln om Bezout-förhållandet, finner vi att detta förhållande för tal och har formen: $100$ $65537$

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

eller

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

Om vi multiplicerar båda sidor av denna jämförelse med 41 får vi:

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

Härav följer att det finns en lösning på den ursprungliga jämförelsen. Det är bekvämare att ersätta det med något som är jämförbart med det (återstoden av att dividera med ). Svar: $725495$ $4588$ $725495$ $65537$ $x \equiv 4588 \pmod {65537}.$

Den andra lösningen, enklare och snabbare, kräver inte konstruktionen av Bezout-relationen, utan är också likvärdig med den euklidiska algoritmen.

Steg 1. Dividera modulen med koefficienten x med resten: . Multiplicera båda sidorna av den ursprungliga jämförelsen med kvoten och lägg till ; vi får: , men vänster sida är en multipel av , det vill säga jämförbar med noll, varav: $65537=100 \cdot 655+37$ $655$ $37x$ $65537x\equiv 26855+37x{\pmod {65537}}$ $65537$

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

Vi fick en koefficient på 37 istället för 100 för at. Vid varje nästa steg minskar vi på samma sätt tills vi får en. $x$

Steg 2. På samma sätt dividerar vi med en ny koefficient vid x: . Multiplicera båda delarna av jämförelsen som erhölls i föregående steg med kvoten och lägg till ; genom att återigen ersätta vänster sida med noll får vi: $65537=37 \cdot 1771+10$ $1771$ $10x$

10x \equiv 47560205 \pmod {65537}

$47560205$ ersätt med resten när det divideras med lika : $65537,$ $45880$

10x \equiv 45880 \pmod {65537}

Då skulle det vara möjligt att göra ytterligare 5 steg på samma sätt, men det är lättare att dela båda delarna av jämförelsen med 10 och omedelbart få resultatet: $x \equiv 4588 \pmod {65537}.$

Jämförelser av andra graden

Jämförelser av andra gradens modulo m har följande allmänna form:

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

Detta uttryck kan föras till formen

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

och när det byts ut förenklar det till $z = x + b$

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

Att lösa denna jämförelse handlar om att ta reda på om det givna talet är en kvadratisk rest (med hjälp av kvadratisk reciprocitetslagen ) och sedan beräkna kvadratroten modulo detta [17] . För att beräkna kvadratroten från en kvadratisk rest finns det en probabilistisk Berlekamp-metod och en deterministisk Tonelli-Shanks-algoritm .

Jämförelsesystem

Den kinesiska restsatsen säger att ett system av kongruenser med parvisa coprime -moduler är: $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\ ekvivalent a_{n}{\pmod {m_{n}}}\end{cases}}

är alltid lösbar och dess lösning är unik modulo . ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n))$

Med andra ord, den kinesiska restsatsen säger att en restring modulo produkten av flera parvisa samprimtal är den direkta produkten av restringarna som motsvarar faktorerna.

Applikation

Modulär aritmetik används inom talteori , gruppteori , ringteori , knutteori , allmän algebra , kryptografi , datavetenskap , kemi och andra områden.

Till exempel används ofta jämförelser för att beräkna kontrollsummor som används i identifierare. Så för att fastställa fel vid inmatning av ett internationellt bankkontonummer används jämförelsemodulo 97 [18] .

Inom kryptografi kan jämförelser hittas i system med offentliga nyckel som använder till exempel RSA-algoritmen eller Diffie-Hellman-protokollet . Modulär aritmetik ger också finita fält över vilka elliptiska kurvor sedan byggs och används i olika symmetriska nyckelprotokoll ( AES , IDEA ) [19] .

Inom kemi är den sista siffran i CAS-registreringsnumret kontrollsummans värde , vilket beräknas genom att lägga till den sista siffran i talet multiplicerat med 1, den andra siffran från höger multiplicerad med 2, den tredje siffran multiplicerad med tre, och så på upp till den första siffran från vänster, slutar med beräkningen av resten av divisionen med 10 [20]

Se även

Anteckningar

↑ Welshenbach M. Kapitel 5. Modulär matematik: Beräkning i restklasser. // Kryptografi i C och C++ i aktion . - M . : "Triumph", 2004. - S. 81 -95. — 464 sid. — ISBN 5-89392-083-X .
↑ Material från den internationella vetenskapliga konferensen "Modular aritmetik" . Virtuella datormuseet (2005). Tillträdesdatum: 31 juli 2010. Arkiverad från originalet den 5 oktober 2007. (obestämd)
↑ Egorov A. A. Modulo-jämförelser och restaritmetik // Kvant . - 1970. - Nr 5 . - S. 28-33 . Arkiverad från originalet den 4 mars 2016.
↑ Fransk matematiker, medlem av den franska vetenskapsakademin sedan 1666 .
↑ Vileitner G. Kapitel III. Talteori // Matematikens historia från Descartes till mitten av XIX / övers. med honom. under. ed. A.P. Jusjkevitj. - M .: Statens förlag för fysisk och matematisk litteratur, 1960. - S. 69-84. — 467 sid. Arkiverad 24 september 2015 på Wayback Machine
↑ 1 2 Stepanov S. A. Kapitel 1. Grundläggande begrepp // Jämförelser . - M . : "Kunskap", 1975. - S. 3-9. — 64 sid. Arkiverad 24 augusti 2015 på Wayback Machine
↑ 1 2 Vinogradov I.M. Fundamentals of number theory . - M. - L . : Stat. ed. teknisk och teoretisk litteratur, 1952. - S. 41-45. — 180 s. Arkiverad 1 juli 2020 på Wayback Machine
↑ Siziy, 2008 , sid. 88.
↑ 1 2 3 Sagalovich, 2010 , sid. 25-29.
↑ Nesterenko, 2008 , sid. 86-87.
↑ Bukhshtab A. A. Kapitel 8. Klasser // Talteori . - M . : "Upplysning", 1966. - S. 77-78. — 384 sid. Arkiverad 20 november 2015 på Wayback Machine
↑ 1 2 Sagalovich, 2010 , sid. 29-32.
↑ Siziy, 2008 , sid. 87-88,91.
↑ Lidl R., Niederreiter G. Finita fält. I 2 vol. - M .: Mir, 1998. - S. 27 (Exempel 1.37). — 430 sid. — ISBN 5-03-000065-8 .
↑ Fadeev D.K. Kapitel VII. Jämförelse i ringen av polynom och fältförlängningar // Föreläsningar om algebra. - M . : "Nauka", 1984. - S. 197-198. — 416 sid.
↑ Siziy, 2008 , sid. 105-109.
↑ Bukhshtab A. A. Kapitel 21. Jämförelser av 2:a gradens modulo primtal, Kapitel 22. Jämförelser av andra gradens modulo komposit // Talteori . - M . : "Upplysning", 1966. - S. 172-201. — 384 sid. Arkiverad 20 november 2015 på Wayback Machine
↑ Harald Niederreiter, Arne Winterhof. Tillämpad talteori. - "Springer", 2015. - S. 369. - 442 sid. — ISBN 978-3-319-22321-6 .
↑ Koblitz N. Kurs i talteori och kryptografi / transl. från engelska. M. A. Mikhailova och V. E. Tarakanov, red. A. M. Zubkova. - M . : Vetenskapligt förlag TVP, 2001. - S. 96, 105-109, 200-209. — 262 sid. — ISBN 5-85484-012-X .
↑ Kontrollera sifferverifiering av CAS- registernummer . Arkiverad från originalet den 8 december 2015.

Litteratur

Bukhshtab A. A. Talteori . - M . : "Upplysning", 1966. - 384 sid.
Weil, A. Fundamentals of Number Theory . — M .: Mir, 1972.
Vilenkin N. Ya. Kongruenser och restklasser // Kvant . - 1978. - Nr 10 . - S. 4-8 .
Vinogradov I.M. Grunderna i talteorin . - M. - L . : Stat. ed. teknisk och teoretisk litteratur, 1952. - 180 sid.
Koblitz N. En kurs i talteori och kryptografi / per. från engelska. M. A. Mikhailova och V. E. Tarakanov, red. A. M. Zubkova. - M . : Vetenskapligt förlag TVP, 2001. - 254 sid. — ISBN 5-85484-012-X .
Handlingar från den internationella vetenskapliga konferensen "Modulär aritmetik" . Virtuella datormuseet (2005). Hämtad: 31 juli 2010. (obestämd)
Nesterenko Yu. V. Talteori. - M . : Publishing Center "Academy", 2008. - S. 132-133. — 272 sid. — ISBN 9785769546464 .
Sagalovich Yu. L. Introduktion till algebraiska koder - 2nd ed. - M. : IPPI RAN , 2010. - 320 sid. — ISBN 978-5-901158-14-2
Siziy S. V. §4. Jämförelseteori // Föreläsningar om talteori. - M. : Fizmatlit, 2008. - 192 sid. - ISBN 978-5-9221-0741-9 .