Modulo összehasonlítás

Két egész szám modulo összehasonlítása egy természetes számmal egy matematikai művelet, amely lehetővé teszi annak a kérdésnek a megválaszolását, hogy két kiválasztott egész szám ugyanazt a maradékot adja-e, ha ugyanazzal osztjuk . Bármely egész szám, ha elosztjuk -val , akkor a lehetséges maradékok egyikét adja : egy szám 0-tól ; ez azt jelenti, hogy minden egész szám csoportokra osztható , amelyek mindegyike egy bizonyos maradéknak felel meg, ha elosztjuk -val . $m$ $m$ $m$ $m$ $m-1$ $m$ $m$

A számmaradványokkal végzett aritmetikai műveletek egy fix formájú moduláris aritmetika vagy moduláris aritmetika [1] [2] , amelyet széles körben használnak a matematikában , a számítástechnikában és a titkosításban [3] .

Történelem

Az összehasonlítás elméletének megalkotásának előfeltétele Diophantus műveinek restaurálása volt , amelyek eredetiben és latin fordításban jelentek meg Basha de Meziriak jóvoltából 1621- ben . Tanulmányaik olyan felfedezésekhez vezették Fermat , amelyek jelentősen megelőzték korukat. Például 1640. október 18-án Frenicle de Bessy [4] -nek írt levelében bizonyítás nélkül közölt egy tételt , amely később Fermat kis tételeként vált ismertté . A modern megfogalmazásban a tétel kimondja, hogy ha egy prímszám és egy egész szám , amely nem osztható -vel , akkor $p$ $a$ $p$

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

Ennek a tételnek az első bizonyítása Leibnizé , ráadásul legkésőbb 1683 -ban Fermattól függetlenül fedezte fel ezt a tételt, és Bernoulli pontos bizonyításával közölte . Ezenkívül Leibniz prototípust javasolt a Wilson-tétel megfogalmazásához .

Később a számelméletnek és az összehasonlítások elméletének szentelt kérdések tanulmányozását Euler folytatta , aki bevezette a reciprocitás másodfokú törvényét és általánosította Fermat tételét , megállapítva, hogy

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

hol van az Euler-függvény . $\varphi (n)$

Az összehasonlítások fogalmát és szimbolikus megjelölését Gauss vezette be aritmetikai elmélete alátámasztásának fontos eszközeként, amelyen 1797-ben kezdett el dolgozni. Ennek az időszaknak az elején Gauss még nem volt tisztában elődei munkáival, így Arithmetical Investigations ( 1801 ) című könyvének első három fejezetében megfogalmazott munkájának eredményei alapvetően már ismertek voltak, de a módszerek amit bizonyításra használt, teljesen újnak bizonyult, és a legnagyobb jelentőséggel bír a számelmélet fejlődése szempontjából. Ezekkel a módszerekkel Gauss a modulo-összehasonlítási műveletekkel kapcsolatos összes előtte felhalmozott tudást koherens elméletté alakította át, amelyet először ugyanabban a könyvben mutatott be. Emellett tanulmányozta az első és a másodfokú összehasonlításokat, a másodfokú maradékok elméletét és a kapcsolódó másodfokú reciprocitás törvényét [5] .

Definíciók

Ha két egész szám és osztva ugyanazt a maradékot adja, akkor összehasonlíthatónak (vagy equiresiduálisnak ) nevezzük őket modulo a [6] számnak . $a$ $b$ $m$ $m$

A számok összehasonlíthatósága és képletként írható fel ( összehasonlítás ): $a$ $b$

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

A számot összehasonlítási modulusnak nevezzük . $m$

A számok és a modulo összehasonlíthatóságának meghatározása megegyezik a következő állítások bármelyikével: $a$ $b$ $m$

a számok különbsége és maradék nélkül osztva ; $a$ $b$ $m$
szám ábrázolható , ahol valamilyen egész szám [7] . $a$ $a=b+k\cdot m$ $k$

Bizonyíték

Az 1. és 2. feltétel szükségességét a következőképpen bizonyítjuk:

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

Akkor abból a feltételezésből, hogy

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

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

Az 1. és 2. végrehajtásra kerül :

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

(vagyis a különbséget és maradék nélkül osztjuk el -vel);

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 ,

ahol (vagyis ként ábrázolható ).

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

a

a=b+km

Az 1. és 2. feltétel elégségessége :

a=b+km.

A szükséges feltétel igazolásából a szám a következőképpen ábrázolható: $b$

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

Akkor

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

ahol

n=k+n_{2}.

Ily módon

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

A definícióról bebizonyosodott , hogy egyenértékű a 2. feltétellel , amely ekvivalens az 1. feltétellel .

Például a 32 és -10 egybevágó modulo 7, mivel mindkét szám 7-tel osztva 4-et hagy:

32=7\cdot 4+4;

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

Ezenkívül a 32 és -10 számok összehasonlíthatók modulo 7-tel, mivel különbségük osztható 7-tel, és van egy reprezentáció $32-(-10)=42$

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

Az összehasonlíthatóság tulajdonságai modulo

Rögzített természetes szám esetén a modulo összehasonlíthatósági reláció a következő tulajdonságokkal rendelkezik: $m$ $m$

reflexiós tulajdonság : bármely egész számra , $a$ $a\equiv a{\pmod {m));$
szimmetria tulajdonság : ha akkor $a \equiv b \pmod m,$ $b\equiv a{\pmod {m));$
tranzitivitási tulajdonság : ha és akkor $a\equiv b{\pmod m}$ $b \equiv c \pmod m,$ $a \equiv c \pmod m.$

Így a modulo összehasonlíthatósági reláció egy ekvivalencia reláció az egész számok halmazán [8] . $m$

A fenti tulajdonságokon kívül az alábbi állítások igazak az összehasonlításra:

bármely két egész szám egybevágó modulo 1;
ha a és számok modulo összehasonlíthatóak , és a szám osztó , akkor és modulo összehasonlíthatóak ; $a$ $b$ $m$ $d$ $m$ $a$ $b$ $d$

Bizonyíték

Hadd

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

Következésképpen

ab=mt,

hol van valami egész szám.

t

Mivel a szám osztója , akkor $d$ $m$

m=cd,

hol van valami egész szám.

c

Következésképpen

ab=mt=(cd)t=qd,

ahol

q=ct,

és

a\equiv b{\pmod {d))

definíció szerint.

ha a és számok modulusban összehasonlíthatók , akkor a modulok legkisebb közös többszörösével egyenlő modulusban is összehasonlíthatók . $a$ $b$ $k$ ${m_{1},m_{2},...,m_{k)),$ ${m_1, m_2, ..., m_k}$

Bizonyíték

Hadd

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

ahol

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

Következésképpen

ab=m_{i}t.

Mivel a különbség mindegyik többszöröse , ez a legkisebb közös többszörösük többszöröse is . $ab$ $m_i$

Következmény: Annak érdekében, hogy a számok összehasonlíthatóak legyenek modulo , amelynek kanonikus felbontása prímtényezőkre a következő formában van

a

b

m

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

szükséges és elegendő ahhoz

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

ahol [9] .

i=1,2,\ldots ,d

Műveletek összehasonlítással

A modulo egy és ugyanazon összehasonlítások a közönséges egyenlőségek számos tulajdonságával rendelkeznek. Például összeadhatók, kivonhatók és szorozhatók: ha a és a számok páronként összehasonlítható modulo , akkor összegük és , valamint szorzatuk és szintén összehasonlítható 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}}.

Ugyanakkor ezeket a műveleteket nem lehet összehasonlítással végrehajtani, ha a moduljaik nem egyeznek [9] .

Ugyanazt a számot hozzáadhatja az összehasonlítás mindkét részéhez : $c$

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

Előjelváltással is átvihet egy számot az összehasonlítás egyik részéből a másikba:

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

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

Ha a és a számok összehasonlíthatóak modulo , akkor a és hatványaik szintén összehasonlíthatók modulo bármely természetes [7] : $a$ $b$ $m$ $a^k$ $b^{k}$ $m$ $k$

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

Az összehasonlítás bármely részéhez hozzáadhatja a modulus egész számú többszörösét, vagyis ha a és számok összehasonlíthatók modulo valamilyen számmal , akkor és összehasonlítható a modulo -val , ahol és tetszőleges egész számok , amelyek többszörösei : $a$ $b$ $m$ $a + t_1$ ${\displaystyle b+t_{2))$ $m$ $t_{1}$ $t_{2}$ $m$

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

Továbbá az összehasonlítás és a modulus mindkét része megszorozható ugyanazzal a számmal, vagyis ha a és számok összehasonlíthatók modulo valamilyen egész számmal , akkor a és számok összehasonlíthatók modulo a számmal , ahol egy egész szám : $a$ $b$ $m$ $aq$ $bq$ $mq$ $q$

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

Az összehasonlítások azonban általában véve nem oszthatók sem egymással, sem más számokkal. Példa: 2-szeres csökkentés után hibás összehasonlítást kapunk: . Az összehasonlítások csökkentési szabályai a következők. $14\equiv 20{\pmod {6}}$ $7\equiv 10{\pmod {6}}$

Az összehasonlítás mindkét részét el lehet osztani egy számmal, de csak a koprím a modulussal: ha

{ad} \equiv {bd} \pmod m

és GCD akkor

{(d,m)=1},

a \equiv b \pmod m

Ha a szám nem másodlagos a modulussal, mint a fenti példában, akkor nem csökkentheti. $d$ $d$

Az összehasonlítás és a modulus mindkét részét egyidejűleg oszthatja közös osztójukkal:

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

Példa

Az összehasonlítások használata megkönnyíti az oszthatóság különféle kritériumainak megszerzését . Levezetjük például egy N természetes szám 7-tel oszthatóságának jelét. Írjuk alakba (azaz elválasztjuk az egységek számjegyét). A 7-tel osztható feltétel a következőképpen írható fel: Ezt az összehasonlítást szorozzuk meg ezzel $N$ $10a+b$ $N$ $10a+b\equiv 0{\pmod {7)).$ ${\displaystyle-2:}$

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

Vagy a bal oldali modulus többszörösének hozzáadásával : $21a,$

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

Ez a következő 7-tel osztható jelet vonja maga után: a tízesek számából ki kell vonni a megkétszerezett egységek számát, majd ezt a műveletet addig kell ismételni, amíg két- vagy egyjegyű számot nem kapunk; ha osztható 7-tel, akkor az eredeti szám is osztható. Például ellenőrizzük a [10] algoritmust : $N=22624.$

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

Következtetés: 22624 osztható 7-tel.

Kapcsolódó definíciók

Maradék osztályok

A modulo - val egybevágó összes szám halmazát modulo maradékosztálynak nevezzük , és általában vagy jelöli . Így az összehasonlítás egyenértékű a maradékosztályok egyenlőségével [11] . $a$ $m$ $a$ $m$ $[a]_m$ $\bar a_m$ $a\equiv b\pmod{m}$ $[a]_m=[b]_m$

Bármely osztályszámot modulo maradéknak nevezünk . Legyen a határozottság kedvéért a maradék, ha a kiválasztott osztály bármely képviselőjét elosztjuk -val , akkor ebből az osztályból bármely szám ábrázolható , ahol egy egész szám . A maradékkal egyenlő maradékot ( at ) a legkisebb nem negatív maradéknak , az abszolút értékben legkisebb maradékot ( ) pedig az abszolút legkisebb maradéknak nevezzük . Ha ezt megkapjuk , különben . Ha páros és , akkor [ 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}$

Mivel a modulo összehasonlíthatóság egy ekvivalencia reláció az egész számok halmazán , a modulo maradékosztályok ekvivalenciaosztályok ; számuk egyenlő . $m$ $\mathbb {Z}$ $m$ $m$

Az összes modulo maradékosztály halmazát [13] vagy [14 ] jelöli . $m$ $\mathbb {Z} _{m}$ $\mathbb{Z}/m\mathbb{Z}$ $\mathbb{Z}/(m)$

Az összeadás és szorzás műveletei indukálják a megfelelő műveleteket a halmazon : $\mathbb {Z}$ $\mathbb {Z} _{m}$

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

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

Ezekre a műveletekre nézve a halmaz egy véges gyűrű , egy egyszerűnél pedig egy véges mező [6] . $\mathbb {Z} _{m}$ $m$

Levonási rendszerek

A maradékrendszer lehetővé teszi számtani műveletek végrehajtását egy véges számhalmazon anélkül, hogy túllépnénk rajta. A modulo maradékok teljes rendszere páronként összehasonlíthatatlan modulo egész számok összessége . Általában a két halmaz egyikét a maradékok modulo teljes rendszerének tekintik : $m$ $m$ $m$ $m$

a legkisebb nem negatív maradékok , azaz számok:

0,1,\ldots ,m-1

vagy abszolút legkevésbé számokból álló maradékok

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

, páratlan , és számok esetén

m

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

páros esetben .

m

A páronként össze nem hasonlítható modulo számok maximális halmazát, amellyel párhuzamosan prímáljuk , a modulo maradékok redukált rendszerének nevezzük . Bármely redukált modulo rendszer tartalmaz elemeket, ahol az Euler függvény [12] . $m$ $m$ $m$ $m$ $\varphi(m)$ $\varphi (\cdot )$

Például egy szám esetében a maradékok teljes rendszere a 0, 1, 2, 3, ..., 21, 22, 23, ..., 39, 40, 41 számokkal és a redukált rendszerrel ábrázolható. 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 jelölheti. $m=42$

Összehasonlítások polinomgyűrűben egy mező felett

A polinomok mező feletti gyűrűjét tekintjük . A választott gyűrűhöz tartozó két polinomot összehasonlítható modulo polinomnak nevezzük , ha különbségük osztható maradék nélkül. Az összehasonlítást a következőképpen jelöljük: $K[x]$ $K$ $g_{1}$ $g_{2}$ $f$ $g_1-g_2$ $f$

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

Csakúgy, mint az egész számok gyűrűjében, az ilyen összehasonlítások összeadhatók, kivonhatók és szorozhatók [15] .

Összehasonlítások megoldása

Összehasonlítások az első fokú

A számelméletben , a kriptográfiában és más tudományterületeken gyakran felmerül a probléma megoldása a forma első fokának összehasonlítására.

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

Egy ilyen összehasonlítás megoldása a gcd kiszámításával kezdődik . Ebben az esetben két eset lehetséges: $d=$ $(a, m)$

ha nem többszöröse , akkor az összehasonlításnak nincs megoldása; $b$ $d$
ha többszöröse , akkor az összehasonlításnak egyedi megoldása modulo , vagy ezzel egyenértékű megoldás modulo . Ebben az esetben az eredeti összehasonlítás n-nel való csökkentése összehasonlítást eredményez : $b$ $d$ $\frac{m}{d}$ $d$ $m$ $d$

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

ahol és az egész számok , és és a koprím . Ezért egy szám megfordítható modulo , azaz olyan számot találhatunk , amely (más szóval ). Most a megoldást úgy találjuk meg, hogy az eredményül kapott összehasonlítást megszorozzuk a következővel :

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

Az érték gyakorlati kiszámítása többféleképpen történhet: az Euler-tétel segítségével , az Euklidész-algoritmussal , a folytonos törtek elméletével (lásd az algoritmust ), stb. Az Euler-tétel különösen lehetővé teszi, hogy az értéket a következő formában írjuk fel: $c$ $c$

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

[16] . Példák

1. példa Összehasonlításképpen

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

van tehát modulo 22, az összehasonlításnak két megoldása van. Cseréljük le a 26-ot 4-gyel, ami hasonló a modulo 22-hez, majd töröljük mindhárom számot 2-vel: $d=2$

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

Mivel a 3 a coprime modulo 11, megfordítható modulo 11, és meg lehet találni

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

Az összehasonlítást 4-gyel megszorozva a 11-es modulo megoldást kapjuk:

x\equiv 8{\pmod {11}}

egyenértékű a modulo 22 két megoldás halmazával:

x\equiv 8{\pmod {22}}

és .

x\equiv 19{\pmod {22}}

2. példa Az összehasonlítást adjuk meg:

100 x \equiv 41\pmod {65537}.

Vegye figyelembe, hogy a modulus egy prímszám.

65537

A megoldás első módja a Bezout reláció használata . Az Euklidész algoritmus vagy a Bezout-arányról szóló cikkben megadott program segítségével azt találjuk, hogy ez a számarány a következőképpen alakul: $100$ $65537$

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

vagy

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

Az összehasonlítás mindkét oldalát megszorozva 41-gyel, a következőt kapjuk:

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

Ebből következik, hogy van megoldás az eredeti összehasonlításra. Kényelmesebb valami hasonlóra cserélni (az osztás maradéka -val ) . Válasz: $725495$ $4588$ $725495$ $65537$ $x \equiv 4588 \pmod {65537}.$

A második, egyszerűbb és gyorsabb megoldás nem igényli a Bezout-reláció felépítését, de egyenértékű az euklideszi algoritmussal is.

1. lépés. Ossza el a modulust x együtthatójával a maradékkal: . Szorozzuk meg az eredeti összehasonlítás mindkét oldalát a hányadossal és adjuk össze ; kapjuk: , de a bal oldal többszöröse , azaz nullához hasonlítható, ahonnan: $65537=100 \cdot 655+37$ $655$ $37x$ $65537x\equiv 26855+37x{\pmod {65537}}$ $65537$

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

Az at 100 helyett 37-et kaptunk . Minden következő lépésnél ugyanúgy csökkentjük, amíg egyet nem kapunk. $x$

2. lépés Hasonlóképpen osztunk egy új együtthatóval x-nél: . Az előző lépésben kapott összehasonlítás mindkét részét megszorozzuk a hányadossal , és összeadjuk ; a bal oldalt ismét nullára cserélve a következőket kapjuk: $65537=37 \cdot 1771+10$ $1771$ $10x$

10x \equiv 47560205 \pmod {65537}

$47560205$ cserélje ki maradékával, ha egyenlővel osztjuk : $65537,$ $45880$

10x \equiv 45880 \pmod {65537}

Ekkor ugyanígy további 5 lépést is meg lehetne tenni, de egyszerűbb az összehasonlítás mindkét részét elosztani 10-zel, és azonnal megkapni az eredményt: $x \equiv 4588 \pmod {65537}.$

A másodfokú összehasonlítások

A másodfokú modulo m összehasonlításának általános formája a következő:

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

Ez a kifejezés formába hozható

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

cseréjekor pedig leegyszerűsödik $z = x + b$

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

Ennek az összehasonlításnak a megoldása abból adódik, hogy meg kell állapítani, hogy az adott szám másodfokú maradék -e (a másodfokú reciprocitás törvénye alapján ), majd ki kell számítani ennek modulo négyzetgyökét [17] . A négyzetgyök másodfokú maradékból való kiszámításához létezik egy valószínűségi Berlekamp-módszer és egy determinisztikus Tonelli-Shanks algoritmus .

Összehasonlító rendszerek

A kínai maradéktétel kimondja, hogy egy kongruenciarendszer páronkénti koprímmodulokkal : $m_{1},m_{2},\ldots ,m_{n}$

{\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\lpontok \\x\ ekvivalens a_{n}{\pmod {m_{n}}}\end{cases}}

mindig megoldható, megoldása pedig egyedi modulo . ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n))$

Más szóval, a kínai maradéktétel kimondja, hogy a több páronkénti másodperemszám szorzata modulo maradékgyűrű a faktoroknak megfelelő maradékgyűrűk közvetlen szorzata .

Alkalmazás

A moduláris aritmetikát a számelmélet , a csoportelmélet , a gyűrűelmélet , a csomóelmélet , az általános algebra , a kriptográfia , a számítástechnika , a kémia és más területeken használják.

Például gyakran használnak összehasonlításokat az azonosítókban használt ellenőrző összegek kiszámításához. Tehát a nemzetközi bankszámlaszám megadásakor előforduló hibák meghatározásához a 97 [18] összehasonlító modult használjuk .

A kriptográfiában az összehasonlítások megtalálhatók a nyilvános kulcsú rendszerekben , például az RSA algoritmus vagy a Diffie-Hellman protokoll használatával . Ezenkívül a moduláris aritmetika véges mezőket biztosít, amelyekre elliptikus görbék épülnek , és különféle szimmetrikus kulcsprotokollokban ( AES , IDEA ) használják [19] .

A kémiában a CAS regisztrációs szám utolsó számjegye az ellenőrzőösszeg értéke , amelyet úgy számítanak ki, hogy összeadják a szám utolsó számjegyét szorozva 1-gyel, a jobb oldali második számjegyet megszorozva 2-vel, a harmadik számjegyet megszorozva hárommal, és így balról az első számjegyig, a 10-zel való osztás maradékának kiszámításával végződve [20]

Lásd még

Jegyzetek

↑ Welshenbach M. 5. fejezet Moduláris matematika: Számítás maradékosztályokban. // Kriptográfia C és C++ nyelven működés közben . - M . : "Triumph", 2004. - S. 81 -95. — 464 p. — ISBN 5-89392-083-X .
↑ A "Moduláris aritmetika" nemzetközi tudományos konferencia anyagai . Virtuális Számítógép Múzeum (2005). Hozzáférés dátuma: 2010. július 31. Az eredetiből archiválva : 2007. október 5.. (határozatlan)
↑ Egorov A. A. Modulo-összehasonlítások és maradékszámítás // Kvant . - 1970. - 5. sz . - S. 28-33 . Az eredetiből archiválva: 2016. március 4.
↑ Francia matematikus, 1666 óta a Francia Tudományos Akadémia tagja .
↑ Vileitner G. III. fejezet. Számelmélet // A matematika története Descartes-tól XIX. közepéig / ford. vele. alatt. szerk. A. P. Juskevics. - M .: Állami Fizikai és Matematikai Irodalmi Kiadó, 1960. - S. 69-84. — 467 p. Archiválva : 2015. szeptember 24. a Wayback Machine -nál
↑ 1 2 Stepanov S. A. 1. fejezet. Alapfogalmak // Összehasonlítások . - M . : "Tudás", 1975. - S. 3-9. — 64 p. Archiválva : 2015. augusztus 24. a Wayback Machine -nál
↑ 1 2 Vinogradov I.M. A számelmélet alapjai . - M. - L. : Állítsa be. szerk. műszaki és elméleti irodalom, 1952. - S. 41-45. — 180 s. Archiválva 2020. július 1-én a Wayback Machine -nél
↑ Siziy, 2008 , p. 88.
↑ 1 2 3 Sagalovich, 2010 , p. 25-29.
↑ Neszterenko, 2008 , p. 86-87.
↑ Bukhshtab A. A. 8. fejezet. Osztályok // Számelmélet . - M . : "Felvilágosodás", 1966. - S. 77-78. — 384 p. Archiválva : 2015. november 20. a Wayback Machine -nál
↑ 1 2 Sagalovich, 2010 , p. 29-32.
↑ Siziy, 2008 , p. 87-88,91.
↑ Lidl R., Niederreiter G. Véges mezők. 2 kötetben. - M .: Mir, 1998. - S. 27 (1.37. példa). — 430 p. — ISBN 5-03-000065-8 .
↑ Fadeev D.K. VII. fejezet. Összehasonlítás polinomok és mezőbővítések gyűrűjében // Lectures on Algebra. - M . : "Nauka", 1984. - S. 197-198. — 416 p.
↑ Siziy, 2008 , p. 105-109.
↑ Bukhshtab A. A. 21. fejezet. A 2. fokú modulo prím összehasonlítása, 22. fejezet. A másodfokú modulo összetett összehasonlítása // Számelmélet . - M . : "Felvilágosodás", 1966. - S. 172-201. — 384 p. Archiválva : 2015. november 20. a Wayback Machine -nál
↑ Harald Niederreiter, Arne Winterhof. Alkalmazott számelmélet. - "Springer", 2015. - S. 369. - 442 p. — ISBN 978-3-319-22321-6 .
↑ Koblitz N. Számelmélet és kriptográfia tanfolyam / ford. angolról. M. A. Mihajlova és V. E. Tarakanov, szerk. A. M. Zubkova. - M . : TVP Tudományos Kiadó, 2001. - S. 96, 105-109, 200-209. — 262 p. — ISBN 5-85484-012-X .
↑ A CAS regisztrációs számok ellenőrző számjegyű ellenőrzése . Az eredetiből archiválva: 2015. december 8.

Irodalom

Bukhshtab A. A. Számelmélet . - M . : "Felvilágosodás", 1966. - 384 p.
Weil, A. A számelmélet alapjai . - M .: Mir, 1972.
Vilenkin N. Ya. Kongruenciák és maradékosztályok // Kvant . - 1978. - 10. sz . - 4-8 . o .
Vinogradov I.M. A számelmélet alapjai . - M. - L. : Állítsa be. szerk. műszaki és elméleti irodalom, 1952. - 180 p.
Koblitz N. Számelmélet és kriptográfia tanfolyam / per. angolról. M. A. Mihajlova és V. E. Tarakanov, szerk. A. M. Zubkova. - M . : TVP Tudományos Kiadó, 2001. - 254 p. — ISBN 5-85484-012-X .
A „Moduláris aritmetika” nemzetközi tudományos konferencia anyaga . Virtuális Számítógép Múzeum (2005). Letöltve: 2010. július 31. (határozatlan)
Neszterenko Yu. V. Számelmélet. - M . : "Akadémia" Kiadói Központ, 2008. - S. 132-133. — 272 p. — ISBN 9785769546464 .
Sagalovich Yu. L. Bevezetés az algebrai kódokba - 2. kiadás. - M. : IPPI RAN , 2010. - 320 p. — ISBN 978-5-901158-14-2
Siziy S. V. 4. §. Összehasonlítások elmélete // Előadások a számelméletről. - M. : Fizmatlit, 2008. - 192 p. - ISBN 978-5-9221-0741-9 .