Bazele de Teoria Numerelor Computational

Robert Campbell

---

Conținut

1.   Introducere

2.   Aritmetica modulara

o    GCD - Algoritmul lui Euclid

o    Exponentiala - Algoritmul Taranului rus

3.   Numere prime

o    Găsirea Primes

o    Comenzi Element

o    Factoring

4.   Structura Z _p

o    Elemente primitive și grupuri ciclice

o    Miller-Rabin primality de testare

o    Dovedind primality

5.   Alte câmpuri

o    Întregilor lui Gauss

o    Câmpurile Galois

Anexe

A.   De programare Note

B.   Referințe

C.  Glosar

---

Introducere

Acest document este o introducere blând la teoria numerelor de calcul. Planul lucrării este de a oferi mai întâi o privire de ansamblu rapidă de aritmetică în numere întregi modulare. De-a lungul, vom sublinia calcul și rezultatele practice, mai degrabă decât cercetând de ce. Programe simple, în general, în JavaScript, sunt disponibile pentru toate algoritmi menționate. La sfârșitul lucrării, vom introduce numerele întregi Gaussian și Galois Fields și să le compare cu numere întregi modulare. ziarele de companie, va examina teoria numerelor dintr-o perspectivă mult mai avansat.

---

Aritmetica modulara

Aritmetica modulara este aritmetica folosind numere întregi modulo un număr întreg fix N . Astfel, câteva exemple de operații modulo 12 sunt:

• 7 + 7 = 14 = 2 (mod 12)
• 5 * 7 = 35 = 11 (mod 12)

Alte exemple pot fi generate și verificat cu următoarele programe scurte. Rețineți că, în calitate de activarea JavaScript-nu se poate calcula cu numere întregi mai mari de 53 de biți, cea mai mare modulul permis este de 26,5 biți, sau aproximativ 94.9 milioane.

Partea superioară a machetei

 +  (MOD ) =  
 *  (MOD ) =  

Partea inferioară a machetei

Printre operațiunile de bază care le-am ratat operator de împărțire. Dacă am fost de lucru în numere întregi nu ne-ar fi aproape în măsură să definească un coeficient (excepția cazului în care răspunsul este în sine un întreg). În numere întregi modulare putem de multe ori, dar nu întotdeauna, să definească un coeficient:

• 11/5 = 7 (mod 12) ca 5 * 7 = 11 (mod 12)
• 5 ^(-1) = 1/5 = 17 (mod 21), în calitate de 5 * 17 = 85 = 1 (mod 21)
• 48/31 = 72 (mod 91), ca 31 * 72 = 48 (mod 91)
• 9/3 = 7 (mod 12) ca 3 * 7 = 21 = 9 (mod 12)

Ca de exemplu, punctele de pe ultimul loc, divizia modular nu produce întotdeauna un rezultat unic, pentru alte răspunsuri corecte sunt 3 și 11 (ca 3 * 3 = 9 (mod 12) și 3 * 11 = 33 = 9 (mod 12)). În special, în cazul în care modulul și cota divizor un factor comun (în acest caz 3 divide atât 3 și 12), răspunsul nu va fi unic, dacă există, la toate. Am trage două concluzii din aceasta - primul este acela că ne-am dori să fie în măsură să fața locului astfel de factori comuni, iar al doilea este că ne-am dori, pentru a evita astfel de situații. De obicei, vom evita situația vreodată să apară prin utilizarea doar modulele principale. Spotting situația este unul din rezultatele de secțiunea următoare.

GCD - Algoritmul lui Euclid

Algoritmul lui Euclid rezolvă două probleme ne-au reprezentat:

• Factorii comune - Având în vedere două numere n și m , găsit factori comuni care le pot avea.
• Inverse modulare - Având în vedere un număr n și un modul m , găsi inversă a n , adică numărul k astfel încât n * k = 1 (mod m ).

Cel mai mare număr care împarte două numere n și m este numit mare divizor comun de n și m , și notată cmmdc ( n , m ) .

Algoritm pentru a găsi cmmdc ( n , m ) execută ceva de genul:

1.   Notați atât n si m

2.   Reduceți mai mare modulo mici

3.   Se repetă pasul 2 până când rezultatul este zero

4.   Publică rezultatul precedent ca cmmdc ( n , m )

Un exemplu al acestui algoritm este următorul calcul al gcd (120222):

120 222

120 222 - 120 = 102

120-102 = 18 102

18 102-5 * 18 = 12

18-12 = 6 12

6 12-2 * 6 = 0

     

Astfel gcd (120222) = 6.

Următorul program scurt va permite să vă calcula exemple ale algoritmului lui Euclid:

Partea superioară a machetei

gcd (, ) =  

Partea inferioară a machetei

Dacă te gândești atent la algoritmul lui Euclid, veți vedea că, la fiecare pas ambele numere sunt formate prin adăugarea unor multipli de numere originale. Astfel există unele numere, un și b , astfel încât cmmdc ( n , m ) = o * n + b * m . Algoritmul lui Euclid extins poate recupera nu numai cmmdc ( n , m ), dar, de asemenea, aceste numere o și b .

Algoritmul lui Euclid extins & inverse modulare

Algoritmul lui Euclid extins calculează nu numai cmmdc ( n , m ), dar, de asemenea, numerele returnează un și b astfel încât cmmdc ( n , m ) = o* n + b * m . Dacă cmmdc ( n , m ) = 1 se rezolvă problema de calcul inverse modulare.

Să presupunem că vrem să calculăm n ^(-1) (mod m ) și presupunem că cmmdc ( n , m ) = 1. Rula algoritmul lui Euclid extins pentru a obține o șib astfel încât o * n + b * m = 1. Reamenajarea acest rezultat, vom vedea că o * n = 1 - b * m , sau o * n = 1 (mod m ). Aceasta rezolvă problema de a găsi inversă modular de n , deoarece acest lucru demonstrează că n ^(-1) = a (mod m ).

Algoritmul lui Euclid extins nu este nimic mai mult decât algoritmul lui Euclid de obicei, cu calcule laterale pentru a urmări atent de ce combinatie de original numere n și m -au adăugat la fiecare pas. Algoritmul rulează în general, ca aceasta:

1.   Scrie n , m , iar două-vectori (1,0) și (0,1)

2.   Împărțiți mai mare dintre cele două numere de cea mai mică - numesc acest coeficient q

3.   Scădeți q ori mai mici, de la mare (adică reducerea modulo mai mic)

4.   Se scade q ori vectoriale corespunzătoare mai mică din vectorul corespunzătoare mărită

5.   Repetați pașii de la 2 la 4 până când rezultatul este zero

6.   Publică rezultatul precedent ca cmmdc ( n , m )

Un exemplu al acestui algoritm este următorul calcul de 30 ^(-1) (mod 53):

53 30 (1,0) (0,1)

53-1 * 30 = 23 30 (1,0) -1 * (0,1) = (1, -1) (0,1)

23 30-1 * 23 = 7 (1, -1) (0,1) -1 * (1, -1) = (-1,2)

23-3 * 7 = 2 7 (1, -1) -3 * (-1,2) = (4, -7) (-1,2)

7-03 februarie * 2 = 1 (4, -7) (-1,2) -3 * (4,7) = (-13,23)

2-2 * 1 = 0 1 (4, -7) -2 * (-13,23) = (30, -53) (-13,23)

     

Din aceasta vedem că GCD (30,53) = 1 și, reamenajarea punct de vedere, vedem că 1 = -13 * 53 23 * 30 , deci putem trage concluzia că 30^(-1) = 23 (mod 53). (Acest lucru poate fi confirmat prin verificarea faptului că 23 * 30 = 1 (mod 53).)

Următorul program scurt va permite să vă calcula exemple ale algoritmului lui Euclid extins:

Partea superioară a machetei

gcd (, ) =  

Partea inferioară a machetei

Exponentiala - Algoritmul Taranului rus

Când calcul o putere de un număr cu un modul finit există modalități eficiente de a face acest lucru și modalități ineficiente pentru a face acest lucru. În această secțiune vom sublinia o metodă eficientă frecvent utilizate, care are numele de curios "algoritmul Taranului rus".

Modul cel mai evident de a calcula 12 ¹⁰ (mod 23), este de a multiplica 12 un total de nouă ori, reducerea mod rezultat 23 la fiecare pas. O metodă mai eficientă, care durează doar patru înmulțirii este realizată prin primul observând că:

12 ² = 6 (mod 23) 
12 ⁴ = 6 ² = 13 (mod 23) 
12 ⁸ = 13 ² = 8 (mod 23)

Am realizat acum trei squarings și, prin faptul că exponentul rupe în puteri de 2, 10 = 8 +2, putem rescrie calcul nostru:

12 ¹⁰ = 12 ^{(8 +2)}
= 12 ⁸ * 12 ²
= 8 * 6 = 2 (mod 23)

Deci, algoritmul nostru constă în scris exponent ca puterile lui doi. (Aceasta se poate face prin scrierea aceasta ca bază numărul 2 și citirea cifre succesive - de exemplu, 10 ₁₀ 1010 = ₂ .) Acum multiplica pătrate succesive ale numărului de bază pentru fiecare cifră a exponentului care este un "1".

Următorul program scurt va permite să vă calcula exemple de metode Taranului rus pentru exponentiala:

Partea superioară a machetei

^  (MOD ) =  

Partea inferioară a machetei

(Puțin criptic) de ieșire a acestui program poate fi citit ca:

1.   Cele bază două cifre ale exponent

2.   Cele squarings succesive ale bazei (adică b ² , b ⁴ , b ⁸ , ...)

3.   Produsul a pătratelor corespunzătoare

---

Numere prime

Un prim este un număr care nu are decât 1 divizori și numărul în sine.

Astfel, 13 este un prim dar 12 nu este - are divizori 2, 3, și 6. Un număr care nu este prim se spune că este compozit.

Ideea de numere prime ridică mai multe întrebări - cum nu o găsească un prim și cum a face tu a reduce un număr într-un produs de factori, principalul său (de exemplu, cum l-ai factor)?

Găsirea Primes

Există două modalități de a găsi numere prime. Cea mai veche este de a căuta un număr mare de numere, sortare afară non-prime numere (de exemplu compozit), lăsând doar numere prime. A doua metodă este de a testa un număr individual pentru primality.

Ciurul lui Eratostene este o metoda recent (datând din secolul 3 î.Hr.). Ideea este aceasta - scrie toate numerele întregi până la un anumit punct: 
. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
Acum, taie toate cele chiar mai mare decât 2: 
2 3 4 5 6 7 8 9 10 11 12 13 14 . 15 
Acum taie toți cei divizibil cu 3 (altele decât 3): 
2 3 4 5 6 7 8 9 10 11 12 13 14 15 . 
La fiecare pas pe care îl găsim următorul prim (număr nu barată) publica ca un prim și taie toate multipli sale. Deci, în acest exemplu, vom vedea că numerele 2, 3, 5, 7, 11, și 13 sunt prime.

În timp ce sita este un mijloc eficient de a găsi un număr mare de numere prime succesive nu poate fi folosit pentru a testa un număr arbitrar de primality. Acest lucru se poate face cu un test de pseudoprime.

Un test de pseudoprime ar fi mai corect numite un test compositeness ca atunci când se aplică la un număr întreg N returnează unul din cele două rezultate posibile:

• Reușește: N este cu siguranta compozit.
• Eșuează: N -ar putea fi prim (sau ar putea fi compozit)

Valoarea folosind un test pseudoprime a testa pentru primality este că acesta poate fi repetat. Dacă testul răspunde mereu că numărul ar putea fi prim, atunci veți obține o anumită încredere (dar nici o asigurare), care N este prim.

Următoarele este simplu test pseudoprime. În literatura de specialitate este în mod normal, nu i sa dat un nume, dar, deoarece se bazează pe Mica teorema a lui Fermat (precizat în secțiunea următoare), voi testul Fermat apel. Acest test se execută astfel:

1.   Alegeți o bază b pentru test.

2.   Dacă b ^( N -1) = 1 (mod N ), apoi N -ar putea fi prim, dacă acesta este orice altă valoare atunci N este cu siguranță compozit.

Vă permite să încercați câteva exemple:

1.   Testul 35 = 5 * 7 pentru primality:

1.   Alegeți de bază 2

2.   Calculați 2 ³⁴ (mod 35) = 9

3.   Ca urmare nu este 1 putem concluziona că 35 este compozit.

2.   Testul 31 (cunoscut pentru a fi prim) pentru primality:

1.   Alegeți de bază 2

2.   Calculați 2 ³⁰ (mod 31) = 1 
Deci, 31 este un pseudoprime de bază 2.

3.   De asemenea, calcula: 
3 ³⁰ (mod 31) = 1 
5 ³⁰ (mod 31) = 1

4.   Din aceasta vedem că 31 este un pseudoprime pentru baze de 2, 3 și 5, și am ajuns la concluzia că 31 este , probabil, prim.

3.   Testul 341 = 11 * 31 pentru primality:

1.   Alegeți de bază 2

2.   Calculați 2 ³⁴⁰ (mod 341) = 1 
Deci, 341 este un pseudoprime de bază 2.

3.   Alegeți de bază 3

4.   Calculați 3 ³⁴⁰ (mod 341) = 56 
Deci, 341 este cu siguranta compozit.

Ultimul exemplu ar trebui să fie oarecum deranjant, deoarece arată că un număr compozit poate să treacă drept un prim sub testului pseudoprime Fermat. Pentru aceasta nu este atât vești bune și vești proaste.

• Prima veste bună este că marea majoritate a pseudoprimes sunt de fapt prime.
• Următoarea veste bună este că pseudoprimes cel mai compozit va fi descoperit ca compozit, după foarte puține baze au încercat.
• Vestea proastă este că există unele numere compuse care sunt pseudoprimes (deghizat ca prime) pentru toate bazele. Aceste numere rare sunt numite numere Carmichael .

Mai multe exemple de acest test poate fi calculată folosind metoda de exponențială rapidă menționat anterior:

Partea superioară a machetei

^  (MOD ) =  

Partea inferioară a machetei

Comenzi Element

De ce a facut munca de testare primality? Testul Fermat pseudoprime, precum și un număr de alții , depinde de o proprietate simplă a primelor primul observat de către Pierre Fermat, în 17 ^-lea secol:

Teorema: (Mica teorema a lui Fermat) Dacă p este prim și 0 < b < p apoi b ^( p -1) = 1 (mod p ) .

În scopul de a vântura prime de la non-prime vom face uz de faptul că pentru un prim p acest lucru este valabil pentru orice baza b , în timp ce pentru un non-prime q și o bază de ales b valoarea b ^( q -1) ( mod q ) este arbitrară și rareori egală cu 1.

Mai mic exponent diferită de zero e astfel încât un ^e = 1 (mod N ) este ordinea de un mod N . Acest lucru este, în general, notată o ( a) (mod N ).

O consecință a Mica teorema lui Fermat este ca, pentru prim p și 0 < a < p , ordinul de un mod p divide ( p -1).

Factoring

Cel mai simplu mod de a factor de un întreg proces este de a împărți prin toate numerele prime mai puțin de rădăcină pătrată. Pentru un număr mare aceasta este o metodă foarte ineficient, totuși. O serie de metode mai bune s-au dezvoltat în timpul mijlocul și sfârșitul secolului 20, deși.Vom descrie p-1 algoritmul lui Pollard.

Pentru a utiliza p-1 Metoda de factoring Pollard de la factorul A număr compozit N :

1.   Alegeți o bază b .

2.   Începeți cu un exponent de e = 2.

1.   Înlocuiți b cu b ^e (MOD N )

2.   Dacă cmmdc ( N , b -1) nu este 1, se publica ca un factor și STOP .

3.   Adauga 1 la e .

Principiul din spatele acestei metode este din nou Micul teorema lui Fermat. Să presupunem pentru simplitate că numărul compozit N are doi factori primi, p și q , deci N = pq . Să presupunem că b nu se divide p (o circumstanță puțin probabil). Acum știm că b ^( p -1) = 1 (mod p ) . Daca putem gasi magic un exponent E astfel încât ( p -1) împarte E , spune E = k ( p -1) , apoi b ^E = b ^k = 1 (mod p ) . O potențială problemă este că nu știm valoarea p în avans. Am obține în jurul valorii de care presupunând că cel mai mare factor prim ( p -1) este ceva legat B . Dacă acest lucru este adevărat, atunci de B ^-lea pas al algoritmului, am calculat cmmdc ( N , b ^{2 * 3 * ... * B} -1). Ne asteptam ca b ^{2 * 3 * ... * B} = 1 (mod p ),deci b ^{2 * 3 * ... * B} -1 = 0 (mod p ) , și b ^{2 * 3 * ... * B} -1 (mod N ) , trebuie să fie un multiplu de q . Astfel, ne așteptăm cmmdc ( N , b ^{2 * 3 * ... * B} -1) va fi q .

Această metodă, de obicei funcționează în cazul în care sunteți dispus să ruleze suficient pentru valori suficient de mari ale exponent. Uneori ești norocos, ( p -1) are doar factorii de mici, și factorizare este ușor. Uneori ești ghinionist, ( p -1) are un factor prim mare și este nevoie de o mulțime de lucru pentru factor N .

Partea superioară a machetei

Factor  cu Pollard p metoda -1 utilizarea de bază ... pentru a obține un factor de  

Partea inferioară a machetei

---

Structura Z _p

Elemente primitive și grupuri ciclice

Un număr g este primitiv mod p dacă ordinul g mod p este ( p -1).

Dacă p este prim, Micul teorema lui Fermat, care, pentru orice g nu divizibil cu p , g ^( p -1) = 1 (mod p ). Dacă r nu este prim, spune r = pq , atunci nu există elemente primitive MOD R . În schimb, acesta este (destul de) simplu pentru a dovedi că există elemente de primitiv mod orice prim- p .

Atunci când p este prim, există multe elemente care sunt primitive mod p , dar nu există nici o modalitate de a spune ce elemente sunt primitive scurt de a găsi ordinea lor. Astfel 2 nu este mod primitiv 7 (2 ¹ = 2, 2 ² = 4 și 2 ³ = 8 = 1 (mod 7), astfel încât ordinea de 2 mod 7 este 3), dar 3 este mod primitiv 7 (3 ¹ = 3, 3 ² = 9 = 2, 3 ³ = 27 = 6, 3 ⁴ = 81 = 4, 3 ⁵ = 243 = 5, astfel ordinul a 3 mod 7 este 6).

(Strict vorbind, nu am dat definiția corectă a primitivismului. O definiție mai corectă este ca g este mod primitiv N dacă puterile succesive de gMOD N produc toate numere întregi mai puțin de N și prime între ele la N . Această definiție clară ne permite să afirmă că există elemente de primitiv mod N , dacă și numai dacă N este de forma p , p ⁿ , sau 2 p ⁿ , unde p este prim.)

Acum gândiți-vă un număr care nu este prim, spune N = pq , unde atât p și q sunt prime. Considerare unele o care este prime între ele atât p șiq (cu alte cuvinte, 0 < a (mod p ) < p , și în mod similar pentru q ). Astfel, de la Little teorema lui Fermat știm căo ^{( p -1) ( q -1)} = ( a ^( p -1) ) ^( q -1) = 1 ^( q -1) = 1 (mod p ), și în mod similar un ^{( p -1) ( q -1)} = 1 (mod q ) . Astfel un ^{( p -1) ( q -1)} = 1 . Ordinea un modPQ trebuie să împartă ( p -1) ( q -1). În special, așa cum ( p -1) ( q -1) <( pq -1), știm că dacă N = PQ nu este prim, atunci nici un element nu are ordine N -1. Vom folosi aceasta pentru a dovedi că un număr este prim.

Printre altele, am arătat următoarele, care este un sub-caz a ceea ce se numește Teorema lui Euler. (Una dintre cele mai multe teoreme numit "Teorema lui Euler".)

Teorema: Dacă N = pq , unde atât p și q sunt prime, iar în cazul în care b este ales astfel încât cmmdc ( b , N ) = 1, atuncib ^{( p -1) ( q -1)} = 1 (mod N ) .

Miller-Rabin primality de testare

Testul primality Miller-Rabin este, cum ar fi testul Fermat, un test de pseudoprime. Acesta folosește o consecință a structurii grupului de unități - că doar rădăcinile pătrate de 1 mod un prim p sunt 1 și -1, dar mod orice compozit ciudat N cu n factori de prim distincte, există 2 ⁿ pătrat rădăcinile 1 . Astfel, testul Miller-Rabin caută rădăcini pătrate de 1, declarând N compozit cazul în care constată una alta decât 1 sau -1.

Partea superioară a machetei

Este prim? →  

Partea inferioară a machetei

Dovedind primality

Până în prezent, fiecare test a fost un test pseudoprime - se identifică în mod pozitiv numere compuse, dar pot identifica prime în cel mai bun, cu un risc de eroare. Putem folosi ceea ce stim acum pentru a produce un test care dovedește că unele număr este prim. Știm că:

• Dacă N este prim, există o anumită 0 < a < N , care este primitiv, cu alte cuvinte are scopul exact ( N -1) MOD N .
• Dacă N este compozit, atunci pentru orice 0 < o < N , fie cmmdc ( b , N ) = 1 (ușor de verificat) sau are ordin strict mai mică de ( N -1) mod N .

Astfel, dacă putem găsi un element de un astfel încât acesta are scopul exact ( N -1) mod N , apoi ne-au dovedit că N este prim. Abordarea noastră este forța brută - vom încerca valori succesive de o și a vedea dacă fiecare este primitiv. Lucrarea nu este asa de rau cum pare, totuși.Pentru orice o vom confirma întâi că o ^( N -1) = 1 (mod N ). Acum știm că adevărata ordine a unui este un divizor de N -1. Verificarea un ⁿpentru fiecare divizor n de N -1 nu este rău. Există un al doilea truc se poate aplica totuși. Dacă comanda de un este strict mai mică de N -1, atunci trebuie să existe un prim divizor p din N -1 astfel încât o ^{( N -1) / p} = 1 (mod N ) . Astfel, algoritmul nostru este:

1.   Factor ( N -1) = p ₁ ^e ₁ ... p _K ^e _k , unde fiecare p _i este prim

2.   Pentru unii secvență de o s ( o = 2,3,4,5, ... este, probabil, destul de bun)

o    Pentru fiecare p _i , în cazul în care un ^{( N -1) / p} = 1 (mod N ), respinge un

În cazul în care un ^{( N -1) / p} ≠ 1 (MOD N ) pentru toate p _i , atunci un e primitiv și N este prim.

Uneori, mai ușor de zis decât de făcut, în special în partea în care factorul ( N -1).

---

Alte grupuri și inele

Teoria numerelor este studiul de mai mult decât numere întregi. Acest lucru este valabil atât pentru diverse alte structuri algebrice sunt generalizări naturale de numere întregi și, de asemenea, deoarece ele ne dau de multe ori informații despre numere întregi.

Întregilor lui Gauss

Prima generalizare a întregi ne vom atinge pe este întregilor lui Gauss, o extindere a întregi de i , rădăcina pătrată de unul negativ.

Elementele de numere întregi Gaussian sunt toate numerele de forma n + m I , în cazul în care atât n și m sunt numere întregi. Plus și de multiplicare se face în mod obișnuit.

Lucrurile devin interesante atunci când încercăm să decidem ce vrem să spunem prin apostroful în numere întregi Gaussian. Observație simplă, care (2 + i ) (2 - i ) = 4 - (-1) = 5 arată că nu orice întreg, care este prim în numere întregi este prim în numere întregi Gaussian.

Câmpurile Galois

Câmpuri Galois (mentionat ca domenii finite) sunt extensii ale intregi modulo un prim p. .

Vom începe cu numere întregi modulo p și unele polinomul care nu poate fi rezolvată (de exemplu, luat) în acest domeniu. Vă permite să continue cu un două exemple concrete:

Exemplu: GF (2 ³ ) = Z ₂ [ x ] / < x ³ + x +1>

Exemplul nostru va începe cu numere întregi modulo 2 (care conține doar două numere 0 și 1). În conformitate cu notația obișnuită, vom numi acest F ₂ . Având în vedere acest domeniu avem acum scoate din pălărie noastre polinomul x ³ + x +1 . Nici 0 nici 1 satisface această polinom mod 2. Acum, pretinde că există o soluție sau rădăcină a polinomului, o numesc o și adăuga acest simbol pentru domeniul nostru inițial. Lucru pe care acum avem este numit F ₂ [ o ]. Elementele de acest lucru au forma n + m a + k un ² . Rețineți că nu există elemente care sunt cubi într-o ca un ³ pot fi înlocuite cu - un -1 ca o sa presupus a fi o rădăcină a polinomului originale. De fapt, așa cum ne sunt de lucru modulo 2, deci +1 și -1 sunt la fel, putem înlocui un ³ de un 1. Enumera 2 ³ = 8 elemente avem {0, 1, o , o 1, o ² , un ² +1, un ² + o , o ² + un +1} .

Exemplu: GF (5 ⁴ ) = Z ₅ [ x ] / < x ⁴ +2 x ³ +3 x ² + x +1>

Pornind de la presupunerea naivă că polinomul definirea x ⁴ +2 x ³ +3 x ² + x +1 este într-adevăr ireductibil mod 5 (și, astfel, că acesta este un domeniu finit), suntem în poziția de a încerca de calcul în acest domeniu :

Partea superioară a machetei

GF cu poli:  (MOD ) = 
Adauga poligoane:  *  =  (Sau ) 
Mult poligoane: *  =  (Sau ) 

Partea inferioară a machetei

Un pic mai interesant este calculul puteri de elemente. La fel ca în cazul de calcul cu numere întregi, se poate calcula eficient folosind algoritmul Țăranului rus de cuadratura și înmulțirea.

Un exemplu în acest sens multiplicare eficient este calcul un ²⁶ :

• Ca 26 = 16 +8 +2, putem scrie în baza 2, 26 = 11010 ₂
• Astfel o ²⁶ = ( a ¹⁶ ) ( un ⁸ ) ( a ² )
• Calcul: o ² : o ² = o ² o ⁴ : ( a ² ) ² = 3 o ³ + 2 o ² + 4 o + 4 o ⁸ : ( a ⁴ ) ² = (3 o ³ + 2 o ² + 4 a + 4) ² = 3 o ³ + 3 o ¹⁶ : ( a ⁸ ) ² = (3 o ³ + 3) ² = 2 o ² + 4 o
  
  
  
• Astfel o ²⁶ = ( a ¹⁶ ) ( un ⁸ ) ( a ² ) = (2 o ² + 4 a ) (3 o ³ + 3) ( a ² ) = 3 o ³ + 2 un + 4

Partea superioară a machetei

GF cu poli:  (MOD ) = 
Putere:  ^  =  (Sau ) 

Partea inferioară a machetei

Există un număr de moduri diferite în care putem folosi algoritmul de bază Țărănesc rusă. Următoarele abordare ușor diferită este un pic mai greu de înțeles, dar mai curat pentru programul, deoarece nu are nevoie de variabile temporare:

• Ca 26 = 11010 ₂ se poate scrie 26 = 0 +2 (1 +2 (0 +2 (1 +2 (1))))
• și un ²⁶ = un ^{(0 +2 (1 +2 (0 +2 (1 +2 (1)))))} = ( a (( a ( a ) ² ) ² ) ² ) ²
• Calcul: 
  ( a ) ² = o ² 
  a ( a ) ² = o ³ (care este un ³ = a ( a ) ² ) 
  ( a ³ ) ² = 3 o ³ + 3 a ² + a + 4 (care este un ⁶ = ( a ( a ) ² ) ² ) 
  (3 o ³ + 3 a ² + a + 4) ² = 2 a ² + 3 (care este o ¹² = (( a ( a ) ² ) ² ) ² ) un (2 o ² + 3) = (2 o ³ + 3 a ) (care este o ¹³ = o (( a ( a ) ² ) ² ) ² ) (2o ³ + 3 a ) ² = 3 o ³ + 2 un + 4 (care este o ²⁶ = ( a (( a ( a ) ² ) ² ) ² ) ² ) 
• Astfel o ²⁶ = 3 o ³ + 2 un + 4

În cele din urmă, suntem în poziția de a vedea dacă polinomul nostru este ireductibil mod 5 (fără de fapt, de factoring este - o problemă pentru o altă zi). Structura de corpuri finite este similară cu cea a Z _p într-un număr de moduri. Un analog de ​​Mica teorema a lui Fermat există, deci pentru orice element b ∈ GF (5 ⁴ ), trebuie să avem b ^(5 4 -1) = 1. O altă asemănare este că orice domeniu Galois este garantat de a avea elemente primitive. În acest caz, există 5 ⁴ = 625 elemente, dintre care (5 ⁴ -1) = 624 sunt non-zero. Astfel, un element primitiv va avea comanda exact 624. Ca și în cazul întreg, vom verifica acest lucru prin faptul că 624 are prim factorization 624 = (2 ⁴ ) (3) (13).

• Încercați o ∈ GF (5 ⁴ )
• o ^(5 4 -1) = 1
• o ^{(5 4 -1) / 2} = 1 (deci un nu este primitiv - de fapt, o are ordin 39)
• Incercati ( a +1) ∈ GF (5 ⁴ )
• ( a +1) ^(5 4 -1) = 1
• ( a +1) ^{(5 4 -1) / 2} = 4 ≠ 1
• ( a +1) ^{(5 4 -1) / 3} = 3 +3 o +3 un ² +3 un ³ ≠ 1
• ( a +1) ^{(5 4 -1) / 13} = o + o ² + un ³ ≠ 1

Deci, ( a +1) are scopul de exact 624 și este primitiv. Astfel, am arătat că polinomul x ⁴ +2 x ³ +3 x ² + x +1 este ireductibil.

---

Anexe

De bază de programare A. Note

Dimensiunea & precizie multipla

Unele dintre cele mai interesante întrebări în teorie număr de calcul implica un număr mare. Acest lucru poate fi o problema ca cele mai multe limbi și mașini acceptă numai numere întregi până la o anumită dimensiune fixă, de obicei 2 ^{64 de} biți (aproximativ 1,6 × 10 ¹⁹ ) sau 2 ^{32 de} biți (aproximativ 4 × 10 ⁹ ).

Această limită este redusă în continuare de faptul că cele mai multe dintre algoritmi necesită calculul rezultatelor intermediare două ori mai mare număr de interes. De exemplu, calculul mod ( a * b , m ) este de obicei găsite, în cazul în care fiecare dintre un și b sunt aproximativ aceeași mărime ca m . Pentru acest calcul să funcționeze, valoarea intermediară a * b trebuie să fie mai mică decât limita întreg al mașinii.Astfel, pe o mașină de 32-biți, cea mai mare valoare de m pentru care acest lucru poate fi realizat este de 2 ¹⁶ = 65536. Exemplele din această lucrare sunt scrise în JavaScript, care permite calculele 53-biți pe orice mașină, permițând astfel m pentru a lua valori la fel de mare ca 2 ^26,5 = 94906265.

Limbaje de programare

Următoarele sunt simple limbi interpretate în care le-am scris programele de bază teoria numerelor, potrivite pentru utilizarea clasă și modificare.

• JavaScript - JavaScript este un limbaj de scripting interpretat acceptat de browsere web moderne. Standardul de activarea JavaScript / ECMAScript sprijină utilizarea de numere intregi pozitive de până la 53 de biți în dimensiune.
• Python - Python este disponibil gratuit pentru orice arhitectură și este deja instalat pe majoritatea sistemelor de OSX / Linux / UNIX.Acesta permite utilizarea de orice dimensiune întreg și este o potrivire foarte bună pentru teoria numerelor simplu. Programe de punere în aplicare multe dintre algoritmi sunt disponibile aici .
• HyperCard - Programul HyperCard este disponibil pe mașini Macintosh și permite utilizarea de numere intregi pozitive de până la 63 de biți în dimensiune. Programe de punere în aplicare multe dintre algoritmi sunt disponibile aici .
• QBasic - interpret QBasic este disponibil pe MS-DOS și mașini Windows livrate în ultimii ani, și permite utilizarea de numere intregi pozitive de până la 31 de biți în dimensiune. Programe de punere în aplicare multe dintre algoritmi sunt disponibile aici .
• TI Calculator - Texas Instruments Familia de calculatoare programabile are un limbaj de programare simplu și permite utilizarea de numere întregi până la 46 de biți în dimensiune. Programe de punere în aplicare multe dintre algoritmi sunt disponibile aici .

Mai multe detalii despre programarea pentru teoria numerelor pot fi găsite într-un document legat aici .

---

B. Referințe

• O Introducere beton la Algebra superior , Lindsay Childs, Springer-Verlag, 1979. O bună acoperire din același material ca și acest document, cu accent pe algoritmi, dar nici un cod de exemplu.
• PRIMES și de programare , Peter Giblin, Cambridge Univ Press, 1993. O bună introducere în teoria numerelor cu un accent puternic pe algoritmi - conține codul PASCAL implementarea cele mai multe algoritmi.
• Factorizarea și primality testare , David Bressoud, Springer-Verlag, 1989. Acoperă factoring cele mai actuale și algoritmi de testare primality, precum și acele elemente de teorie numărul necesar pentru ei. Conține implementari pseudocod de cele mai multe algoritmi.

---

Robert Campbell

Ultima modificare: 29 ianuarie 2010