Fordított értékek modulo
Egy egyszerű szám egy olyan nagyobb, mint egy, amelynek egyetlen tényezője 1, és maga: nem osztható semmilyen más számmal. A kettő főszám. Egyszerűek is a 73, 2521, 2365347734339 és 2756839-1. Végtelenül sok elsőszámú szám van. A titkosítás, különösen a nyilvános kulcsokkal történő kriptográfia gyakran nagy prímszámokat használ (512 bit vagy több).
A legnagyobb közös osztó
Két szám azt mondják, hogy viszonylag elsődleges, ha nincs közös multiplikátoruk, kivéve 1. Más szóval, ha az a és n legnagyobb közös osztója 1, akkor ezt írjuk:
GCD (a, n) = 1
Kölcsönösen egyszerűek a 15. és 28. számok. A 15 és a 27 nem kölcsönösen elsődlegesek, 13 és 500 pedig. A prímszám viszonylag elsődleges az összes többi számnál, kivéve azokat a számokat, amelyek egy adott prímszám többszörösei.
A két szám legnagyobb közös osztójának kiszámításának egyik módja az euklideszi algoritmus. Euclid leírta ezt az algoritmust Kr.e. 300-ban írt Elemek című könyvében. Nem találta fel. A történészek úgy vélik, hogy ez az algoritmus 200 évvel idősebb. Ez a legrégebbi, nem triviális algoritmus, amely napjainkig jött, és még mindig jó. Knut leírta az algoritmust és annak modern módosításait.
Fordított értékek modulo
Emlékszel, melyek az ellenkező értékek? A 4-es érték kölcsönös értéke 1/4, mert 4 * 1/4 = 1. A maradványok világában a probléma bonyolultabbá válik:
4 * x = 1 (mod 7)
Ez az egyenlet megegyezik az x és k észlelésével, így
4x = 7k + 1
ahol x és k egész számok. Az általános probléma az, hogy megtaláljuk x-et, így
1 = (a * x) mod n
Ezt írható is
a-1 = x (mod n)
A modul inverz értékeinek problémája nem könnyű megoldani. Néha megoldást talál, néha nem. Például az 5 modulo 14 inverz értéke 3. Másrészt a 2-es számnak nincs inverz 14-es értéke.
Általában az a-1 = x (mod n) egyenlet esetében létezik egy egyedi megoldás, ha a és n viszonylag elsődleges. Ha a és n nem coprime, akkor a-1 = x (mod n) nincs megoldás. Ha n egy elsődleges szám, akkor az 1-től n-1-ig terjedő számok viszonylag elsődlegesek az n-hez és pontosan egy fordított értékű modulo n-t tartalmaznak.
Szóval jó. És most hogyan fogod keresni a modulo n inverzét? Kétféleképpen lehet. Az modulo n inverz értéke kiszámítható az euklideszi algoritmus segítségével. Néha ezt nevezik Euclid kiterjesztett algoritmusa.
Az algoritmus iteratív, és lassan dolgozhat nagyszámú. Knuth azt mutatta, hogy az algoritmus által végzett megosztások átlagos száma:
0,843 * log2 (n) + 1,47.
Az együtthatók megoldása
Az Euklideszi algoritmus az alábbi problémák megoldására is használható: M x1, x2 változók mátrixának adata. xm, keresse meg a m koefficiensek sorát, ul, u2. ööö, ilyen
ul * x1 +. + um * xm, = 1
A kínai maradék tétel
Ha az n szám bomlása egyszerű tényezőkre ismert, akkor a kínai maradék tétel használható a teljes egyenletrendszer megoldására. Ennek a tételnek az alapváltozatát az első században a kínai Sun Jie matematikus fedezte fel.
Általános esetben, ha az n szám bomlása egyszerű tényezőként p1 * p2 *. * pt, akkor az egyenletek rendszere
(x mod pi) = ai, ahol i = 1, 2. t
egyedülálló megoldása van, x, kisebb mint n. (Vegyük észre, hogy néhány prímszám többször is megjelenhet, például p1 egyenlő lehet a p2-vel.) Más szavakkal, egy számot (kevesebb, mint több prím termékét) egyedileg határozzák meg annak maradékai, hogy ezeket a prímeket elosztják.
Például, vegye be a 3. és az 5., valamint a 14. főszámot az adott számnak. 14 mod 3 = 2 és 14 mod 5 = 4. Egyetlen szám kevesebb, mint 3 * 5 = 15, ilyen maradékokkal: 14. Két maradék egyedileg határozza meg a számot.
Ezért önkényes a
x = a (mod p), és x = b (mod q)
Ahhoz, hogy x-t kapjunk, először az Euclid algoritmust találjuk, hogy megtaláljuk az u-t
u * q 1 (mod p)
Ezután kiszámolja:
x = (((a - b) * u) mod p) * q + b
A kínai maradék tétel inverzióját használhatjuk fel a következő probléma megoldására: ha p és q prímszámok, és p kisebb, mint q, akkor egyedülálló x kisebb, mint pq,
a = x (mod p), és b = x (mod q)
Ha a> = b mod p, akkor
x = (((a - (b mod p)) * u) mod p) * q + b
Ha a x = (((a + p - (b mod p)) * u) mod p) * q + b