Modulo vertailu

Kahden kokonaisluvun vertaileminen modulo luonnollinen luku on matemaattinen operaatio, jonka avulla voit vastata kysymykseen, antavatko kaksi valittua kokonaislukua saman jäännöksen jaettuna samalla luvulla . Mikä tahansa kokonaisluku jaettuna antaa yhden mahdollisista jäännöksistä: numero 0 - ; tämä tarkoittaa, että kaikki kokonaisluvut voidaan jakaa ryhmiin, joista jokainen vastaa tiettyä jäännöstä jaettuna . $m$ $m$ $m$ $m$ $m-1$ $m$ $m$

Aritmeettiset operaatiot lukujäännöksillä moduloivat kiinteämuotoista modulaarista aritmetiikkaa tai modulaarista aritmetiikkaa [1] [2] , jota käytetään laajalti matematiikassa , tietojenkäsittelytieteessä ja kryptografiassa [3] .

Historia

Edellytyksenä vertailuteorian luomiselle oli Diophantuksen teosten restaurointi , jotka julkaistiin alkuperäisenä ja latinalaisella käännöksellä Basha de Meziriakin ansiosta vuonna 1621 . Heidän tutkimuksensa johti Fermatin löytöihin, jotka olivat huomattavasti aikaansa edellä. Esimerkiksi kirjeessään Frenicle de Bessylle [4] 18. lokakuuta 1640 hän raportoi ilman todisteita lauseen , joka myöhemmin tuli tunnetuksi Fermat'n pienenä lauseena . Modernissa muotoilussa lause sanoo, että jos on alkuluku ja on kokonaisluku , joka ei ole jaollinen luvulla , niin $s$ $a$ $s$

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

Tämän lauseen ensimmäinen todistus kuuluu Leibnizille , lisäksi hän löysi tämän lauseen Fermatista riippumatta viimeistään vuonna 1683 ja ilmoitti tämän Bernoullin tarkalla todistuksella . Lisäksi Leibniz ehdotti prototyyppiä Wilsonin lauseen muotoiluun .

Myöhemmin lukuteorialle ja vertailuteorialle omistettujen kysymysten tutkimusta jatkoi Euler , joka esitteli vastavuoroisuuden toisen asteen lain ja yleisti Fermatin lauseen ja totesi, että

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

missä on Euler-funktio . $\varphi (n)$

Gauss esitteli vertailujen käsitteen ja symbolisen nimeämisen tärkeäksi työkaluksi aritmeettisen teoriansa perustelemiseen, jonka hän aloitti vuonna 1797. Tämän ajanjakson alussa Gauss ei ollut vielä tietoinen edeltäjiensä teoksista, joten hänen työnsä tulokset, jotka esitettiin hänen kirjansa Aritmeettiset tutkimukset ( 1801 ) kolmessa ensimmäisessä luvussa, olivat periaatteessa jo tiedossa, mutta menetelmät joita hän käytti todisteisiin, osoittautui täysin uudeksi, ja sillä oli suurin merkitys lukuteorian kehitykselle. Näillä menetelmillä Gauss muutti kaiken ennen häntä kertyneen modulo-vertailuoperaatioihin liittyvän tiedon koherentiksi teoriaksi, joka esiteltiin ensimmäisen kerran samassa kirjassa. Lisäksi hän opiskeli ensimmäisen ja toisen asteen vertailuja, neliötähteiden teoriaa ja siihen liittyvää neliöllistä vastavuoroisuuden lakia [5] .

Määritelmät

Jos kaksi kokonaislukua ja jaettuna arvolla antavat saman jäännöksen, niin niitä kutsutaan vertailukelpoisiksi (tai equiresiduaaliksi ) modulo luku [6] . $a$ $b$ $m$ $m$

Numeroiden vertailukelpoisuus ja kirjoitetaan kaavana ( vertailu ): $a$ $b$

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

Lukua kutsutaan vertailumoduuliksi . $m$

Numeroiden ja modulon vertailukelpoisuuden määritelmä vastaa mitä tahansa seuraavista lauseista: $a$ $b$ $m$

lukujen ero ja jaetaan ilman jäännöstä; $a$ $b$ $m$
numero voidaan esittää muodossa , jossa on jokin kokonaisluku [7] . $a$ $a=b+k\cdot m$ $k$

Todiste

Ehtojen 1 ja 2 tarpeellisuus todistetaan seuraavasti:

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

Sitten sillä oletuksella, että

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

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

1 ja 2 suoritetaan :

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

(eli ero ja jaetaan ilman jäännöstä);

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 ,

jossa (eli voidaan esittää muodossa ).

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

a

a=b+km

Ehtojen 1 ja 2 riittävyys :

a=b+km.

Tarvittavan ehdon todistuksesta numero voidaan esittää seuraavasti: $b$

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

Sitten

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

missä

n=k+n_{2}.

Tällä tavalla

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

Määritelmän on osoitettu vastaavan ehtoa 2 , joka vastaa ehtoa 1 .

Esimerkiksi luvut 32 ja −10 ovat yhteneväisiä modulo 7:llä, koska molemmat luvut jaettuna 7:llä jättävät 4:n jäännöksen:

32=7\cdot 4+4;

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

Myös luvut 32 ja -10 ovat vertailukelpoisia modulo 7:llä, koska niiden ero on jaollinen 7:llä ja lisäksi on olemassa esitys $32-(-10)=42$

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

Vertailukelpoisuuden ominaisuudet modulo

Kiinteän luonnollisen luvun moduulivertailurelaatiolla on seuraavat ominaisuudet: $m$ $m$

heijastusominaisuus : mille tahansa kokonaisluvulle , $a$ $a\equiv a{\pmod {m));$
symmetriaominaisuus : jos sitten $a \equiv b \pmod m,$ $b\equiv a{\pmod {m));$
transitiivisuusominaisuus : jos ja sitten $a\equiv b{\pmod m}$ $b \equiv c \pmod m,$ $a \equiv c \pmod m.$

Siten modulo-vertailurelaatio on ekvivalenssirelaatio kokonaislukujen joukossa [8] . $m$

Yllä olevien ominaisuuksien lisäksi seuraavat väitteet ovat totta vertailuissa:

mitkä tahansa kaksi kokonaislukua ovat kongruenttia modulo 1;
jos luvut ja ovat modulo vertailukelpoisia ja luku on jakaja , niin ja ovat modulo vertailukelpoisia ; $a$ $b$ $m$ $d$ $m$ $a$ $b$ $d$

Todiste

Päästää

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

Näin ollen

ab=mt,

missä on jokin kokonaisluku.

t

Koska on luvun jakaja , niin $d$ $m$

m=cd,

missä on jokin kokonaisluku.

c

Näin ollen

ab=mt=(cd)t=qd,

missä

q=ct,

a\equiv b{\pmod {d))

määritelmän mukaan.

jos luvut ja ovat vertailukelpoisia moduuleissa , niin ne ovat vertailukelpoisia moduulien pienimmän yhteisen kerrannaisen kanssa . $a$ $b$ $k$ ${m_{1},m_{2},...,m_{k)),$ ${m_1, m_2, ..., m_k}$

Todiste

Päästää

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

missä

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

Näin ollen

ab=m_{i}t.

Koska ero on jokaisen kerrannainen , se on myös niiden pienimmän yhteisen kerrannainen . $ab$ $mi$

Seuraus: Jotta luvut olisivat vertailukelpoisia modulo , jonka kanoninen hajoaminen alkutekijöiksi on muotoa

a

b

m

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

tarpeellista ja riittävää

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

missä [9] .

i=1,2,\ldots ,d

Operaatiot vertailuilla

Vertailuilla modulo yksi ja sama on monia tavallisten yhtäläisyyksien ominaisuuksia. Niitä voidaan esimerkiksi lisätä, vähentää ja kertoa: jos luvut ja ovat pareittain vertailukelpoisia modulo , niin niiden summat ja , sekä tulot ja ovat myös vertailukelpoisia 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}}.

Samanaikaisesti näitä operaatioita ei voida suorittaa vertailuilla, jos niiden moduulit eivät täsmää [9] .

Voit lisätä saman numeron vertailun molempiin osiin : $c$

{\näyttötyyli (a+c)\equiv (b+c){\pmod {m)).}

Voit myös siirtää luvun vertailun osasta toiseen etumerkin muutoksella:

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

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

Jos luvut ja ovat vertailukelpoisia modulo , niin niiden tehot ja ovat myös vertailukelpoisia modulo mille tahansa luonnolliselle [7] : $a$ $b$ $m$ $a^k$ $b^{k}$ $m$ $k$

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

Mihin tahansa vertailun osaan voit lisätä moduulin kokonaislukukerran, toisin sanoen jos luvut ja ovat vertailukelpoisia modulo jokin luku , niin ja on verrattavissa modulo , jossa ja ovat mielivaltaisia kokonaislukuja , jotka ovat kerrannaisia : $a$ $b$ $m$ $a + t_1$ ${\näyttötyyli b+t_{2))$ $m$ $t_{1}$ $t_{2}$ $m$

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

Myös vertailun molemmat osat ja moduuli voidaan kertoa samalla luvulla, eli jos luvut ja ovat vertailukelpoisia modulo jokin kokonaisluku , niin luvut ja ovat vertailukelpoisia modulo luku , jossa on kokonaisluku : $a$ $b$ $m$ $aq$ $bq$ $mq$ $q$

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

Vertailuja ei kuitenkaan voida yleisesti ottaen jakaa keskenään tai muilla luvuilla. Esimerkki: 2 kertaa vähennettynä saamme kuitenkin virheellisen vertailun: . Vertailujen vähennyssäännöt ovat seuraavat. $14\equiv 20{\pmod {6}}$ $7\equiv 10{\pmod {6}}$

On mahdollista jakaa molemmat vertailun osat luvulla, mutta vain koprime moduulilla: if

{ad} \equiv {bd} \pmod m

ja GCD sitten

{(d,m)=1},

a \equiv b \pmod m

Jos luku ei ole moduulin kanssa alkuluku, kuten yllä olevassa esimerkissä, et voi pienentää. $d$ $d$

Voit jakaa samanaikaisesti molemmat vertailun osat ja moduulin niiden yhteisellä jakajalla:

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

Esimerkki

Vertailujen avulla on helppo hankkia erilaisia jaotettavuuskriteereitä . Johdetaan esimerkiksi luonnollisen luvun N jaollisuusmerkki 7:llä. Kirjoitetaan se muotoon (eli erotetaan yksiköiden numero). Ehto, joka on jaollinen 7:llä, voidaan kirjoittaa seuraavasti: Kerro tämä vertailu luvulla $N$ $10a+b$ $N$ $10a+b\equiv 0{\pmod {7)).$ ${\displaystyle-2:}$

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

Tai lisäämällä vasemmalla olevan moduulin kerrannainen: $21a,$

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

Tämä tarkoittaa seuraavaa jaollisuuden merkkiä 7:llä: on tarpeen vähentää kaksinkertainen yksiköiden määrä kymmenien lukumäärästä, sitten toistaa tämä toimenpide, kunnes saadaan kaksi- tai yksinumeroinen luku; jos se on jaollinen 7:llä, niin alkuperäinen luku on myös jaollinen. Tarkastetaan esimerkiksi algoritmi [10] : $N=22624.$

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

Johtopäätös: 22624 on jaollinen seitsemällä.

Aiheeseen liittyvät määritelmät

Jäännösluokat

Kaikkien modulon kanssa yhteensopivien lukujen joukkoa kutsutaan modulo - jäännösluokiksi , ja sitä merkitään yleensä tai . Siten vertailu vastaa jäämäluokkien yhtäläisyyttä [11] . $a$ $m$ $a$ $m$ $[olen$ $\bar a_m$ $a\equiv b\pmod{m}$ $[a]_m=[b]_m$

Mitä tahansa luokkanumeroa kutsutaan modulo- jäännökseksi . Olkoon määrällisyyden vuoksi jakojäännös minkä tahansa valitun luokan edustajista luvulla , niin mikä tahansa tämän luokan luku voidaan esittää muodossa , jossa on kokonaisluku . Jäännöstä , joka on yhtä suuri kuin jäännös ( at ), kutsutaan pienimmäksi ei-negatiiviseksi jäännökseksi ja jäännöstä ( ), joka on absoluuttisen arvon pienin, kutsutaan ehdottoman pienimmäksi jäännökseksi . Kun saamme sen , muuten . Jos on parillinen ja , niin [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}$

Koska modulo-vertailu on ekvivalenssirelaatio kokonaislukujen joukossa , modulo-jäännösluokat ovat ekvivalenssiluokkia ; niiden lukumäärä on yhtä suuri . $m$ $\mathbb {Z}$ $m$ $m$

Kaikkien jäännösluokkien joukko modulo on merkitty joko [13] tai [14] . $m$ $\mathbb {Z} _{m}$ $\mathbb{Z}/m\mathbb{Z}$ $\mathbb{Z}/(m)$

Summa- ja kertolaskuoperaatiot indusoivat vastaavat operaatiot joukkoon : $\mathbb {Z}$ $\mathbb {Z} _{m}$

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

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

Näiden operaatioiden osalta joukko on äärellinen rengas , ja yksinkertaiselle se on äärellinen kenttä [6] . $\mathbb {Z} _{m}$ $m$

Vähennysjärjestelmät

Jäännösjärjestelmän avulla voit suorittaa aritmeettisia operaatioita rajalliselle lukujoukolle ylittämättä sitä. Täydellinen jäännösjärjestelmä modulo on mikä tahansa joukko pareittain vertailemattomia modulo - kokonaislukuja. Yleensä toinen kahdesta sarjasta pidetään täydellisenä jäännösjärjestelmänä modulo : $m$ $m$ $m$ $m$

pienimmät ei-negatiiviset tähteet , eli luvut:

0,1,\ldots ,m-1

tai ehdottomasti vähiten luvuista koostuvia tähteitä

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

, parittoman , ja numeroiden tapauksessa

m

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

parillisessa tapauksessa .

m

Pareittain vertailemattomien moduulilukujen maksimijoukkoa, jonka kanssa koprime , kutsutaan pelkistetyksi modulojäännösten järjestelmäksi . Mikä tahansa pelkistetty jäännösjärjestelmä modulo sisältää elementtejä, joissa on Euler-funktio [12] . $m$ $m$ $m$ $m$ $\varphi(m)$ $\varphi (\cdot )$

Esimerkiksi luvulle täydellinen jäännösjärjestelmä voidaan esittää numeroilla 0, 1, 2, 3, ..., 21, 22, 23, ..., 39, 40, 41 ja pelkistetyllä järjestelmällä. voidaan esittää numeroilla 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. $m = 42$

Vertailut polynomirenkaassa kentän päällä

Polynomien rengasta kentän päällä tarkastellaan . Kahta polynomia ja valittuun renkaaseen kuuluvaa kutsutaan polynomin vertailukelpoiseksi modulo , jos niiden ero on jaollinen ilman jäännöstä. Vertailu on merkitty seuraavasti: $K[x]$ $K$ $g_{1}$ $g_{2}$ $f$ $g_1-g_2$ $f$

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

Aivan kuten kokonaislukujen renkaassa, tällaisia vertailuja voidaan lisätä, vähentää ja kertoa [15] .

Vertailujen ratkaiseminen

Ensimmäisen asteen vertailut

Numeroteoriassa , kryptografiassa ja muilla tieteenaloilla ongelmana on usein löytää ratkaisuja muodon ensimmäisen asteen vertailuun.

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

Tällaisen vertailun ratkaisu alkaa gcd :n laskemisesta . Tässä tapauksessa kaksi tapausta on mahdollista: $d=$ $(olen)$

jos ei monikerta , niin vertailulla ei ole ratkaisuja; $b$ $d$
jos on kerrannainen , niin vertailulla on ainutlaatuinen ratkaisu modulo , tai vastaavasti ratkaisut modulo . Tässä tapauksessa alkuperäisen vertailun pienentäminen n:llä johtaa vertailuun: $b$ $d$ $\frac{m}{d}$ $d$ $m$ $d$

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

missä ja ovat kokonaislukuja , ja ja ovat koprime . Siksi luku voidaan kääntää modulo , eli löytää sellainen luku , että (toisin sanoen ). Nyt ratkaisu löytyy kertomalla tuloksena saatu vertailu luvulla :

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

Käytännön arvon laskenta voidaan tehdä eri tavoilla: käyttämällä Eulerin lausetta , Euklidin algoritmia , jatkuvien murtolukujen teoriaa (katso algoritmi ) jne. Erityisesti Eulerin lause sallii arvon kirjoittamisen muodossa: $c$ $c$

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

[16] . Esimerkkejä

Esimerkki 1. Vertailun vuoksi

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

meillä on siis modulo 22, vertailussa on kaksi ratkaisua. Korvataan 26 luvulla 4, joka on vertailukelpoinen modulo 22, ja kumotaan sitten kaikki kolme numeroa kahdella: $d = 2$

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

Koska 3 on koprime modulo 11, se voidaan kääntää modulo 11 ja löytää

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

Kerrotaan vertailu 4:llä, saadaan ratkaisu modulo 11:

x\equiv 8{\pmod {11}}

vastaa kahden ratkaisun joukkoa modulo 22:

x\equiv 8{\pmod {22}}

ja .

x\equiv 19{\pmod {22}}

Esimerkki 2. Vertailu annetaan:

100 x \equiv 41\pmod {65537}.

Huomaa, että moduuli on alkuluku.

65537

Ensimmäinen tapa ratkaista se on käyttää Bezout-relaatiota . Käyttämällä Euclid-algoritmia tai Bezout-suhdetta käsittelevässä artikkelissa annettua ohjelmaa huomaamme, että tämä lukujen suhde on muotoa: $100$ $65537$

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

tai

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

Kun tämän vertailun molemmat puolet kerrotaan 41:llä, saadaan:

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

Tästä seuraa, että alkuperäiseen vertailuun on ratkaisu. On helpompaa korvata se jollain siihen verrattavalla (jäännös jakamalla luvulla ). Vastaus: $725495$ $4588$ $725495$ $65537$ $x \equiv 4588 \pmod {65537}.$

Toinen ratkaisu, yksinkertaisempi ja nopeampi, ei vaadi Bezout-relaation rakentamista, mutta vastaa myös euklidelaista algoritmia.

Vaihe 1. Jaa moduuli x:n kertoimella jäännöksellä: . Kerro alkuperäisen vertailun molemmat puolet osamäärällä ja lisää ; saamme: , mutta vasen puoli on :n kerrannainen , eli verrattavissa nollaan, mistä: $65537=100 \cdot 655+37$ $655$ $37x$ $65537x\equiv 26855+37x{\pmod {65537}}$ $65537$

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

Saimme at:lle kertoimen 37 100:n sijaan. Jokaisessa seuraavassa vaiheessa vähennämme samalla tavalla, kunnes saamme yhden. $x$

Vaihe 2. Samalla tavalla jaamme uudella kertoimella kohdassa x: . Kerro edellisessä vaiheessa saadun vertailun molemmat osat osamäärällä ja lisää ; korvaamalla vasemman puolen jälleen nollalla, saamme: $65537=37 \cdot 1771+10$ $1771$ $10x$

10x \equiv 47560205 \pmod {65537}

$47560205$ korvaa sen jäännöksellä, kun se jaetaan yhtä suurella : $65537,$ $45880$

10x \equiv 45880 \pmod {65537}

Sitten olisi mahdollista tehdä vielä 5 vaihetta samalla tavalla, mutta on helpompi jakaa molemmat vertailun osat 10:llä ja saada heti tulos: $x \equiv 4588 \pmod {65537}.$

Toisen asteen vertailut

Toisen asteen modulo m -vertailuilla on seuraava yleinen muoto:

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

Tämä lauseke voidaan viedä muotoon

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

ja kun se vaihdetaan, se yksinkertaistuu $z = x + b$

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

Tämän vertailun ratkaiseminen edellyttää, että selvitetään, onko annettu luku neliöjäännös (käyttäen toisen asteen vastavuoroisuuslakia ) ja lasketaan sitten neliöjuuren modulo [17] . Neliöjuuren laskemiseksi kvadraattisesta jäännöksestä on olemassa todennäköisyyspohjainen Berlekamp-menetelmä ja deterministinen Tonelli-Shanks-algoritmi .

Vertailujärjestelmät

Kiinan jäännöslause sanoo, että kongruenssijärjestelmä parittaisten koprimemoduulien kanssa on: $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\ equiv a_{n}{\pmod {m_{n}}}\end{cases}}

on aina ratkaistavissa, ja sen ratkaisu on ainutlaatuinen modulo . ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n))$

Toisin sanoen kiinalainen jäännöslause sanoo, että jäännösrengas modulo useiden parittaisten koprimelukujen tulo on tekijöitä vastaavien jäännösrenkaiden suora tulo.

Sovellus

Modulaarista aritmetiikkaa käytetään lukuteoriassa , ryhmäteoriassa , rengasteoriassa , solmuteoriassa , yleisalgebrassa , kryptografiassa , tietojenkäsittelytieteessä , kemiassa ja muilla aloilla.

Vertailuja käytetään usein esimerkiksi tunnisteissa käytettävien tarkistussummien laskemiseen. Joten kansainvälisen pankkitilin numeron syöttämisen virheiden määrittämiseen käytetään vertailumoduulia 97 [18] .

Salaustekniikassa vertailut löytyvät julkisen avaimen järjestelmistä , joissa käytetään esimerkiksi RSA-algoritmia tai Diffie-Hellman-protokollaa . Modulaarinen aritmetiikka tarjoaa myös äärelliset kentät , joiden päälle sitten rakennetaan elliptisiä käyriä , ja sitä käytetään erilaisissa symmetrisissä avainprotokollissa ( AES , IDEA ) [19] .

Kemiassa CAS-rekisteröintinumeron viimeinen numero on tarkistussumman arvo , joka lasketaan lisäämällä luvun viimeinen numero kerrottuna 1:llä, toinen numero oikealta kerrottuna 2:lla, kolmas numero kerrottuna kolmella ja niin ensimmäiseen numeroon asti vasemmalta, joka päättyy 10:llä jaon jäännösosan laskemiseen [20]

Katso myös

Muistiinpanot

↑ Welshenbach M. Luku 5. Modulaarinen matematiikka: Laskenta jäännösluokissa. // Kryptografia C:ssä ja C++:ssa toiminnassa . - M . : "Triumph", 2004. - S. 81 -95. — 464 s. — ISBN 5-89392-083-X .
↑ Kansainvälisen tieteellisen konferenssin "Modulaarinen aritmetiikka" materiaalit . Virtuaalinen tietokonemuseo (2005). Käyttöönottopäivä: 31. heinäkuuta 2010. Arkistoitu alkuperäisestä 5. lokakuuta 2007. (määrätön)
↑ Egorov A. A. Modulo-vertailut ja jäännösaritmetiikka // Kvant . - 1970. - Nro 5 . - S. 28-33 . Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
↑ Ranskalainen matemaatikko, Ranskan tiedeakatemian jäsen vuodesta 1666 .
↑ Vileitner G. Luku III. Numeroteoria // Matematiikan historia Descartesista XIX-luvun puoliväliin / käännös. hänen kanssaan. alla. toim. A. P. Juskevitš. - M .: Valtion fyysisen ja matemaattisen kirjallisuuden kustantaja, 1960. - S. 69-84. — 467 s. Arkistoitu 24. syyskuuta 2015 Wayback Machineen
↑ 1 2 Stepanov S. A. Luku 1. Peruskäsitteet // Vertailut . - M . : "Tieto", 1975. - S. 3-9. - 64 s. Arkistoitu 24. elokuuta 2015 Wayback Machineen
↑ 1 2 Vinogradov I.M. Lukuteorian perusteet . - M. - L .: Valtio. toim. tekninen ja teoreettinen kirjallisuus, 1952. - S. 41-45. – 180 s. Arkistoitu 1. heinäkuuta 2020 Wayback Machinessa
↑ Siziy, 2008 , s. 88.
↑ 1 2 3 Sagalovich, 2010 , s. 25-29.
↑ Nesterenko, 2008 , s. 86-87.
↑ Bukhshtab A. A. Luku 8. Luokat // Numeroteoria . - M . : "Enlightenment", 1966. - S. 77-78. — 384 s. Arkistoitu 20. marraskuuta 2015 Wayback Machineen
↑ 1 2 Sagalovich, 2010 , s. 29-32.
↑ Siziy, 2008 , s. 87-88,91.
↑ Lidl R., Niederreiter G. Äärilliset kentät. 2 osassa - M .: Mir, 1998. - S. 27 (esimerkki 1.37). - 430 s. — ISBN 5-03-000065-8 .
↑ Fadeev D.K. Luku VII. Vertailu polynomien ja kenttälaajennusten renkaassa // Algebran luentoja. - M .: "Nauka", 1984. - S. 197-198. — 416 s.
↑ Siziy, 2008 , s. 105-109.
↑ Bukhshtab A. A. Luku 21. 2. asteen moduulialkuluvun vertailut, Luku 22. Vertailut toisen asteen modulo-komposiittiin // Numeroteoria . - M . : "Enlightenment", 1966. - S. 172-201. — 384 s. Arkistoitu 20. marraskuuta 2015 Wayback Machineen
↑ Harald Niederreiter, Arne Winterhof. Sovellettu lukuteoria. - "Kevät", 2015. - S. 369. - 442 s. — ISBN 978-3-319-22321-6 .
↑ Koblitz N. Lukuteorian ja kryptografian kurssi / käännös. englannista. M. A. Mikhailova ja V. E. Tarakanov, toim. A. M. Zubkova. - M . : Tieteellinen kustantaja TVP, 2001. - S. 96, 105-109, 200-209. — 262 s. — ISBN 5-85484-012-X .
↑ CAS-rekisterinumeroiden tarkistusnumeroiden tarkistus . Arkistoitu alkuperäisestä 8. joulukuuta 2015.

Kirjallisuus

Bukhshtab A. A. Numeroteoria . - M . : "Valaistus", 1966. - 384 s.
Weil, A. Numeroteorian perusteet . - M .: Mir, 1972.
Vilenkin N. Ya. Kongruenssit ja jäännösluokat // Kvant . - 1978. - Nro 10 . - s. 4-8 .
Vinogradov I.M. Lukuteorian perusteet . - M. - L .: Valtio. toim. tekninen ja teoreettinen kirjallisuus, 1952. - 180 s.
Koblitz N. Lukuteorian ja kryptografian kurssi / per. englannista. M. A. Mikhailova ja V. E. Tarakanov, toim. A. M. Zubkova. - M . : Tieteellinen kustantaja TVP, 2001. - 254 s. — ISBN 5-85484-012-X .
Kansainvälisen tieteellisen konferenssin "Modulaarinen aritmetiikka" aineisto . Virtuaalinen tietokonemuseo (2005). Haettu: 31. heinäkuuta 2010. (määrätön)
Nesterenko Yu. V. Numeroteoria. - M . : Publishing Center "Academy", 2008. - S. 132-133. — 272 s. — ISBN 9785769546464 .
Sagalovich Yu. L. Johdatus algebrallisiin koodeihin - 2. painos. - M. : IPPI RAN , 2010. - 320 s. — ISBN 978-5-901158-14-2
Siziy S. V. §4. Vertailuteoria // Lukuteorian luentoja. - M. : Fizmatlit, 2008. - 192 s. - ISBN 978-5-9221-0741-9 .