Nevezetes prímtesztelő algoritmusok

Szerző: Némedy Varga András (CC2A7Q) 
                  másodéves matematikus hallgató

<< 
      NumberTheory`NumberTheoryFunctions`

Bevezetés:

A matematika egyik legősibb ága a számelmélet. Ez a tudomány évszázadok óta szolgáltat szép eredményeket, és nehéz problémákat, sejtéseket a matematikusok számára. Fontos gyakorlati alkalmazásai is ismeretesek, főleg a kriptográfia területén. Kiemelkedő szerepe van benne a prímszámoknak, ezekkel fogunk foglalkozni ebben a  notebookban.

A továbbiakban közöljük a megértéséhez szükséges elméleti anyagot, majd négy prímtesztelési eljárást.

1. Prímszámok:

Először az egész számok gyűrűjében definiálunk két fontos tulajdonságot:

- Definíció: Legyen \(TraditionalForm\`p ∈ ℤ\{\(-1\), 0, 
            1}\). A p szám felbonthatatlan (irreducibilis), ha p =  a b-ből következik, hogy a = {1, -1} vagy b = {1, -1} valamelyikével.

- Definíció: Legyen \(TraditionalForm\`p ∈ ℤ\{\(-1\), 0, 
            1}\). A p szám prím, ha p | a b-ből következik, hogy p | a vagy p | b. 
- Megjegyzés: ez többtényezős szorzatra is igaz.

- Állítás: ℤ-ben ha p felbonthatatlan ⇔ p prím.

- Bizonyítás: 
  Először ⇒ irányt:
      p | a b, de tegyük fel, hogy p ∤ a. Be kell látni, hogy ekkor p | b teljesül.
      (p, a) | p, vagyis (p, a)  = 1 vagy p, de p nem lehet, mert p  ∤  a, vagyis (p, a) = 1. De p | a b és (p, a) = 1-ből következik, hogy p | b, és így p prím.
        Most ⇐ irányban:
      p = a b, akkor persze p | a b. Mivel p prím a feltevés szerint, ezért p | a vagy p | b  és így a b | a vagy a b | b, ami viszont csak úgy lehet, ha b = {1, -1} vagy a = {1, -1} valamelyikével. Ez azt jelenti, hogy p irreducibilis.

A prímszámoknak rengeteg alkalmazása van a matematikában, főleg a számelméletben játszanak fontos szerepet.

Ezt mutatja például a számelmélet alaptétele is, melyet most bizonyítás nélkül mondunk ki:
    \(TraditionalForm\`∀ \ 
        a ∈ ℤ\ \{\(-1\), 0, 1}\), szám felbontható véges sok irreducibilis (vagyis prím) szám szorzatára. A felbontás {1, -1}szorzóktól és a sorrendtől eltekintve egyértelmű.
      Megjegyzés: Ha a > 0 és a ≠ 1, akkor pozitív prímek szorzatára bontva és azokat nagyság szerinti sorrendbe rendezve, a felbontás egység szorzótól eltekintve egyértelmű.

További fontos alkalmazásokat találunk a kriptográfiában. Ezekről később esik majd szó.

2. Kongruenciák, maradékosztályok:

- Definíció: a ∈ ℤ és \(TraditionalForm\`m ∈ ℤ\{0}\) esetén a mod m jelenti a-nak m-mel vett legkisebb nemnegatív osztási maradékát.
            (Ez jól definiált ℕ jólrendezettsége miatt)

- Definíció: \(TraditionalForm\`m ∈ ℤ\{0}\)esetén azt mondjuk, hogy a kongruens b-vel modulo m, ha a  mod m  =  b  mod m. Jele: a ≡ b  (m) 
(Megjegyzés: ha a  mod m ≠  b  mod m, akkor inkongruensek. Jele: a ≢ b  (m))

- A kongruencia tulajdonságai: 
    1. a ≡ b  (m) ⇔ b ≡ a  (m) ⇔ a - b ≡ 0  (m) ⇔ m | a - b 
    2. A kongruencia ekvivalencia reláció, azaz reflexív, szimmetrikus és tranzitív.
    3. Ha f (x) egy egész együtthatós polinom és a ≡ b  (m), akkor f (a)  ≡  
        f (b)  (m)

- Kongruenciák kapcsolata: 
1. a x ≡ a y (m) ⇔ x≡y  ((m/((a,m))))
    2. x≡y  ((Subscript[m, i]))  i=1  ...  r  ⇔ x≡y  ([(Subscript[m, 1]),(Subscript[m, 2]),...,(Subscript[m, r])])

- Maradékosztályok:
    - Definíció: Az x-szel kongruens mod m számokat az x által reprezentált mod m maradékosztálynak nevezzük. 
    - Definíció: Ha minden maradékosztályból kiveszünk egy reprezentánst, akkor a kapott számhalmaz egy mod m teljes maradékrendszer.

Standard teljes maradékrendszer mod m:

stm[m_] := Range[m - 1]

stm[28]

- Definíció: Az x-szel reprezentált mod m maradékosztályt redukált maradékosztálynak nevezzük, ha (x, m) = 1.
- Definíció: Ha minden redukált maradékosztályból kiveszünk egy reprezentánst, akkor a kapott számhalmaz egy mod m redukált maradékrendszer.

Standard redukált maradékrendszer mod m:

srm[m_] := Select[Range[m], (GCD[#, m] == 1) &]

srm[28]

3. Az Euler-féle φ függvény:

- Definíció: A mod m redukált maradékrendszer elemeinek számát φ (m) jelöli. Ezt a függvényt Euler-féle φ függvénynek nevezik. 
          Megjegyzés: φ (m) tehát az m-nél nem nagyobb, m-hez relatív prímek száma.

Ez azt jelenti, hogy ha p prím,akkor φ(p)=p-1 és φ((p^r))=(p^r)-(p^(r - 1)).

ra = Random[Integer, {1, 50}]

EulerPhi[ra] == Length[srm[ra]]

- Tétel (φ kiszámítása ): φ(m)= φ((∏_(i = 1)^r)(((Subscript[p, i]))^((Subscript[α, i])))) = (∏_(i = 1)^r)((((Subscript[p, i]))^((Subscript[α, i])))-(((Subscript[p, i]))^((Subscript[α, i]) - 1))) = m (∏_(i = 1)^r)(1-(1/((Subscript[p, i])))) , ahol  m=(∏_(i = 1)^r)(((Subscript[p, i]))^((Subscript[α, i]))) .

- Bizonyítás:Logikai szita formulával bizonyítjuk.m-ben a (Subscript[p, i]) többszöröseinek száma (m/((Subscript[p, i]))). Ezeket levonjuk  m-ből .  Ekkor azonban kétszer vontuk le (Subscript[p, i])(Subscript[p, j]) többszöröseit tehát ezeket hozzáadjuk és így tovább:
φ(m)=m-(m/((Subscript[p, 1])))-(m/((Subscript[p, 2])))-...-(m/((Subscript[p, r])))+(m/((Subscript[p, 1]) (Subscript[p, 2])))+...+(m/((Subscript[p, r - 1]) (Subscript[p, r])))-...+(((-1))^r) (m/((Subscript[p, 1]) (Subscript[p, 2]) ...(Subscript[p, r])))= m (∏_(i = 1)^r)(1-(1/((Subscript[p, i])))) , ahol m=(∏_(i = 1)^r)((Subscript[p, i])^((Subscript[α, i])))

-Tétel: Ha  (a, b) = 1, akkor  φ(
          a b) = φ(a)  φ(b)

Maradékrendszerek tulajdonságai:
1. T⊂ℤ teljes maradékrendszer mod m ⇔        a. |T|=m
                                                                                                           b. (Subscript[r, i]) ,(Subscript[r, j]) ∈ T-re  (Subscript[r, i])≢ (Subscript[r, j])   (m)  ha  i≠j
    2. R⊂ℤ redukált maradékrendszer mod m ⇔     a. |R|=φ(m)
						              b. (Subscript[r, i]) , (Subscript[r, j]) ∈ R  esetén (Subscript[r, i])≢ (Subscript[r, j])  (m)  ha  i≠ j
							c. ((Subscript[r, i]),m)=1

- Tétel: Ha (a,m)=1 és {(Subscript[r, 1]),...,(Subscript[r, k])} teljes (vagy redukált) maradékrendszer mod m,akkor {a (Subscript[r, 1]),...,a (Subscript[r, k])} is teljes (vagy redukált) maradékrendszer mod m.

- Bizonyítás: Egyszerűen ellenőrizni kell {a (Subscript[r, 1]),...,a (Subscript[r, k])}-ra a fenti tulajdonságokat,\(melyek\ triviálisan\ \(\(teljesülnek\)\(.\)\)\)

- Tétel: Ha  T={(Subscript[r, 1]),...,(Subscript[r, k])} teljes maradékrendszer mod m, akkor {(Subscript[r, 1])+a,...,(Subscript[r, k])+a} is az mod m.

- Bizonyítás: Megint ellenőrizni kell az előbbi tulajdonságokat, melyek egyszerűen látszanak.

Invertálás:

- Definíció: (a^(-1)) az a elem inverze modulo m,ha a (a^(-1))≡1  (m). Az a elem invertálható modulo m,ha létezik inverze.

-Tétel: a invertálható modulo m ⇔ (a, m) = 1. Ha a-nak létezik inverze modulo m, akkor az egyértelmű modulo m.

Euler és Fermat tételei:

- Tétel (Euler): Ha (a,m)=1 ,akkor (a^(φ(m)))≡1  (m) .

- Bizonyítás: Legyen {(Subscript[r, 1]),...,(Subscript[r, φ(m)])} redukált maradékrendszer mod m. Már beláttuk,hogy ekkor {a (Subscript[r, 1]),...,a (Subscript[r, φ(m)])} is redukált maradékrendszer mod m. Most ezen két halmaz elemeit párokba rendezzük úgy,hogy (Subscript[r, i]) párja az az a (Subscript[r, j]),amire (Subscript[r, i])≡a (Subscript[r, j])  (m) és i=1.  .. φ(m) . Így (∏_(i = 1)^(φ(m)))(Subscript[r, i])≡(∏_(j = 1)^(φ(m)))a (Subscript[r, j])  (m). Ebből következik,hogy (∏_(i = 1)^(φ(m)))(Subscript[r, i])≡(a^(φ(m)))(∏_(j = 1)^(φ(m)))(Subscript[r, j])  (m). A produktumok mindkét oldalon egy redukált maradékrendszer összes elemének szorzatát adják,tehát kongruensek egymással mod m. Így viszont 1≡(a^(φ(m)))  (m).

-Tétel (kis Fermat): a, p∤a és p prím,akkor (a^(p-1))≡1  (p)
                                             b, Ha p prím és a tetszőleges egész ,akkor (a^p)≡a  (p)

- Bizonyítás: a, Következik az Euler-tételből.
                       b, Ha a≡0  (p),akkor triviálisan teljesül az állítás .  Ha a≢0  (p),akkor p∤a . Az előzőek miatt (a^(p-1))≡1  (p) és így (a^p)≡a  (p).

4. Egy elem rendje mod m:

- Definíció: m>0,m és a∈ℤ ,(a,m)=1,valamint (a^k)≡1  (m),de (a^l)≢1  (m), ha 0<l<k . Ekkor k az a elem rendje mod m  és jele: (Subscript[ord, m])a=k.

- Állítás:  (Subscript[ord, m])a=g , (a^k)≡1  (m) ⇔ g|k .

- Bizonyítás:
Először => irányban: k=g b +r  (maradékos osztás) . (a^k)=(a^(g b+r))=((((a^k)))^b)(a^r)≡(a^r)≡1  (m). Mivel r<g és (Subscript[ord, m])a=g,ezért ez csak úgy lehetséges,ha r=0.

                          ⇐ irányban: k:=g b. Ekkor (a^k)=(a^(g b))=((((a^g)))^b)≡(1^b)≡1  (m).

- Tétel:  (Subscript[ord, m])a=k =>  (Subscript[ord, m])(a^g)=(k/((k,g))) .

- Bizonyítás: ((((a^g)))^j)≡1  (m) ⇔ k|g j ⇔ (k/((k,g)))|(g/((k,g)))j,de (k/((k,g))) és (g/((k,g))) nyilván relatív prímek, ezért a fenti oszthatóságban (k/((k,g)))|j. Ez pedig az előbb belátott állítás alapján igazolja,hogy (Subscript[ord, m])(a^g)=(k/((k,g))).

- Definíció: Egy g elemet primitív gyöknek nevezünk mod m,ha  (Subscript[ord, m])g=φ(m).
Primitív gyök nem feltétlenül létezik egy m∈ℕ számra .

Bizonyítás nélkül közlünk egy tételt a primitív gyök létezésére vonatkozóan:
-Tétel: m>1,akkor létezik primitív gyök mod  m ⇔ m=2,4,(p^α),2 (p^α) valamelyike,ahol α>0 és p>2 prím.

5. Mire jók a nagy prímek?

Mint már korábban említettük a nagy prímeknek a kriptográfiában van fontos szerepük többek között. Ez azzal hozható kapcsolatba, hogy a titkosításokban olyan számelméleti függvényeket használnak, melyek egyirányúak, azaz egy számnak nehéz visszakeresni az ősképét. Íme egy-két példa ilyen függvényre:

1. Prímfaktorizáció: n = p q, ahol p és q nagy prímek. Ekkor n kiszámolása egy egyszerű szorzás, azonban csupán n ismeretében p és q meghatározása mai ismereteink szerint reménytelenül nehéz.

2. Diszkrét logaritmus: p egy nagy prím és egy g elemnek sok különböző hatványa van mod p. Ekkor egy a=(g^i) mod p szám kiszámolása gyorsan megy,az úgynevezett gyorshatványozással, ami azt jelenti, hogy tekintjük i-\(nek\ a\ kettes\ számrendszerbeli\ alakját\ és\ úgy\ hatványozunk\),hogy (g^(2 ))után (g^(4 ))= ((((g^2) mod p))^2), (g^8)=((((g^4)))^2)=(((((((g^2) mod p))^2)))^2) és így tovább, majd ezekből felhasználva a kettes számrendszerbeli alakot összerakjuk (g^i)-t  .  Azonban ha csak p-t és (g^i)-t ismerjük,akkor ezek alapján megmondani i értékét nagyon nehéz.

Ez a gyorshatványozás megtalálható a Mathematicában is:
         Első esetben előbb hatványozunk majd az eredményt tekintjük mod n:
(Megjegyzés: a,b és n értékei megváltoztathatóak ,itt példaként (3^10000000) - 
                  et számoljuk ki modulo 7. )

Simahatvány[a_, b_, n_] := Mod[(a^b), n]

Timing[
      Simahatvány[a, b, n] /. {a -> 3, b -> 100000000, 
          n -> 7}]

Most pedig a fent leírt módon gyorsítva számol a program:
    (Megjegyzés: a, b és n értékeivel itt is lehet kísérletezni, példaként ugyanaz szerepel mint az előbb, hogy a módszerek sebességét össze lehessen hasonlítani)

Gyorshatvány[a_, b_, n_] := PowerMod[a, b, n]

Timing[
      Gyorshatvány[a, b, n] /. {a -> 3, b -> 100000000, 
          n -> 7}]

3. Négyzetre emelés: p,q nagy prímek és n=p q ,akkor y≡(x^2)  (n) az x megadása után gyorsan számolható,de pusztán y és n ismeretében x-\(et\ kiszámolni\ \(\(reménytelen\)\(.\)\)\)

4. Végül az egyik legismertebb és legfontosabb titkosítási alkalmazása a prímeknek az RSA -módszer.
Nevét a kitalálóinak kezdőbetűiből kapta (Rives - Shamir - Adlemann) . 
A módszer különlegessége,\(hogy\ a\ titkosítás\ nyilvános\ kulcsú\),\(azaz\ közzé\ lehet\ tenni\ a\ titkosító\ függvényt\),mert annak segítségével még nem lehet dekódolni az üzenetet . 
Az eljárás a következő: Választunk két nagyon nagy prímet .  Legyenek ezek p és q. Képezzük az n=p q  számot .  Ekkor tudjuk,hogy φ(n) =(p-1)(q-1) . Most még választunk egy olyan e számot is, amire 1≤e≤n és amelyre  (e,φ(n))=1 . Végül megoldjuk az e d ≡1  ( φ(n)) kongruenciát.
Ezután a C(x) kódolófüggvényünk legyen a C :x→ y≡(x^e) (n).
A dekódolófüggvény D(y) amire D:y→(y^d). Ezt úgy bizonyítjuk,hogy belátjuk az (y^d)≡x  (n) kongruencia igaz voltát.
(y^d)≡((((x^e)))^d)=(x^(h φ(n)+1))=((((x^(φ(n)))))^h) x ≡x  (n). Vagyis D(y) tényleg a \(dekódolófüggvény . 
C\)(x)-\(et\ nyilvánosságra\ hozva\ bárki\ tud\ nekünk\ kódolt\ üzenetet\ küldeni\),ám dekódolni csak mi tudjuk azt,\(mivel\ a\ dekódolófüggvény\ paramétereit\ mások\ nem\ tudják\ kiszámolni\),ahhoz ugyanis faktorizálni kéne n-et .  Végül egy megjegyzés, hogy ez csak úgy használható, ha az elküldeni kívánt x szám relatív prím n-hez .  
            Ezt megtehetjük pl .  úgy, hogy x-\(hez\ hozzáveszünk\ egy\ utolsó\ számjegyet\ úgy\), hogy a kapott x' számra (x',n)=1 teljesüljön.

6. Mik azok a prímtesztek és miért van szükség rájuk?

A prímtesztek olyan algoritmusok, melyekkel nagyon nagy számokról is gyorsan el lehet dönteni, hogy prímek-e vagy sem. Ezekre azért kell külön módszereket kidolgozni, mert jelen ismereteink szerint egy nagyon nagy szám prímtényezős felbontását (kanonikus alak) nem lehet rövid idő alatt megállapítani, és mint láttuk a nagy prímekre szükség van a titkosítási módszereknél.

Prímtesztek: Mind a négy esetben a prímek valamely tulajdonságát felhasználva próbálunk meg eljárást adni egy szám prím voltának ellenőrzésére. Ehhez először az elméleti hátteret ismertetjük, majd felépítjük az algoritmust lépésenként és végül elemezzük annak eredményét.

1. A Lucas-Lehmer teszt:

- Állítás:Ha (a^(n-1))≡1  (n),de n-1 minden q prímosztójára (a^(((n-1))/q))≢1  (n),akkor n prím.

- Bizonyítás: Ha (a^(n-1))≡1  (n),akkor (Subscript[ord, n])a|n-1. Legyen ((n-1)/((Subscript[ord, n])a))=k. Ha q a k szám egy prímosztója,akkor (a^((n-1)/q))≡(a^((k (Subscript[ord, n])a)/q))≡((((a^((Subscript[ord, n])a))))^(k/q))≡1  (n). Ez ellentmond az állítás feltételeinek,azaz k csak 1 lehet,és így (Subscript[ord, n])a=n-1.  Az Euler-tétel szerint (a^(φ(n)))≡1  (n) és azt is láttuk korábban,hogy ekkor (Subscript[ord, n])a|φ(n),ezért jelen esetben φ(n)≥n-1 adódik .  De a definíciója szerint  φ(n)≤n-1,vagyis φ(n)=n-1, azaz n prímszám.

Az algoritmus:

Először készítünk egy listát n-1 prímosztóiból, ahol az input az n  (!!!) szám:

Prímosztók[n_] := 
      First[Transpose[FactorInteger[n - 1]]]

A függvény megkapja n-et  .  Először képezi n-1 prímfelbontását .  Ez {{(Subscript[p, 1]),(Subscript[α, 1])},...,{(Subscript[p, r]),(Subscript[α, r])}} alakú lesz,ahol n-1=(∏_(i = 1)^r)((Subscript[p, i])^((Subscript[α, i]))). Ebből aztán kiválogatja  n-1 prímosztóit.

Prímosztók[(2*5*5*7*43*43*53) + 1]

Ezek után csak annyi kell még,hogy az így kapott lista minden (Subscript[q, i]) elemére megnézzük az (a^((n-1)/(Subscript[q, i]))) számot modulo n,\(gyorshatványozással . \ 
          Ha\ ezeket\ az\ eredményeket\ tároljuk\ egy\ listában\),akkor az állítás szerint, ha ebben nem szerepel az 1 - 
        es és teljesül,hogy (a^(n-1))≡1  (n),akkor n prím .  Az a számot véletlenül választjuk 2 és n-1 között.

\(LucasLehmer1[n_] := 
      Module[
{Prímosztók, a, 
          eredmenyek}, 
Prímosztók[n] := 
          First[Transpose[FactorInteger[n - 1]]]; 
a = 
          Random[Integer, {2, 
              n - 1}]; 
eredmenyek := \(PowerMod[
                a, \(n - 1\)\/#, n] &\) /@ 
            Prímosztók[n]; 
If[
          PowerMod[a, n - 1, n] == 1 && 
            MemberQ[eredmenyek, 1] == False, 
          Print[n, " prímszám"], 
          Print[n, "-ről nem bizonyosodott be,hogy prím"]]
]\)

LucasLehmer1[1000003]

Timing[LucasLehmer1[1000003]]

Az így kapott algoritmus hátránya,hogy az az állítás,\(mely\ az\ elméleti\ alapját\ adja\ fordítva\ nem\ igaz\),vagyis ha n prím,abból még nem következik,hogy az eredménylistában nincs egyes .  Például n=7-re ha a=2,akkor n-1=6 = 2*3 és (2^((6/2))) = 
            8 ≡ 1  (7),tehát lesz 1 - 
        es a listában.

Úgy tehetjük hatékonyabbá a tesztet ha több a számmal is elvégezzük:

Az algoritmus ezen javításában két input van: n a szám amiről meg akarjuk tudni, hogy prím-e, k pedig az a szám ahányszor elvégezzük  a tesztet. Minthogy modulo n csak n-1 szám van, ezért k≤n-1 választással elég dolgozni. Minél nagyobb k értéke annál valószínűbb, hogy ha n prím, akkor az algoritmus ezt igazolja. Azt, hogy mely k darab számra fogja kiszámolni a hatványokat egy különböző elemekből álló, k hosszú, véletlen lista határozza majd meg. Ennek minden egyes elemére elvégzi az előző eljárást és a végén egy indikátor listában tárolja, hogy az egyes lefutásoknak mi lett az eredménye. Így a végén elég megnézni, hogy az indikátor listában van-e 1-es, amely n prímségét igazolja. Ha nincs, akkor ez még nem jelenti azt, hogy n összetett, csupán azt, hogy az algoritmus nem bizonyította n prím voltát.

\(LucasLehmer2[n_, k_] := 
      Module[
{prímosztók, a, listak, 
          indikator, 
          randomlist}, 
indikator = {}; 
randomlist[m_, j_] := 
          Module[
{A}, 
If[j < m - 1, 
              A = {Random[Integer, {2, m - 1}]}; 
While[\ 
                Length[A] < j, 
A = 
                  Union[A, {\ 
                      Random[Integer, {2, 
                          m - 1}]\ }]]; 
Return[
                A], \(Print[j, " nem kisebb,mint ", 
                  m - 1];\)]
]; 
a = 
          randomlist[n, k]; 
prímosztók := 
          First[Transpose[
              FactorInteger[
                n - 1]]]; 
listak = \(PowerMod[#, \(n - 1\)\/prímosztók, n] &\) /@ a; 
For[l = 1, 
          l < Length[listak] + 1, \(l++\), 
          If[PowerMod[a[\([l]\)], n - 1, n] == 1 && 
              MemberQ[listak[\([l]\)], 1] == False, 
            AppendTo[indikator, 1], 
            AppendTo[indikator, 0]]]; 
If[
          MemberQ[indikator, 1], Print[n, " prímszám"], 
          Print[n, "-ről nem bizonyosodott be,hogy prím"]]
]\)

LucasLehmer2[100000007, 20]

Ennek a tesztnek azonban van egy óriási hátránya: ahhoz hogy n-ről eldöntsük, hogy prím-e, n-1-et faktorizálnunk kell. Ezt a beépített függvény gyorsan elvégzi ugyan, de csak nem túl nagy számokra. A cél pedig pont az lenne, hogy nagyon nagy számokra is jegyen jó algoritmusunk.

2. A Solovay-Strassen teszt:

- Definíció: Legyen (a,m)=1.Az a szám kvadratikus maradék modulo m,ha (x^2)≡a  (m)-\(nek\ létezik\ \(\(megoldása\)\(.\)\)\)

- Definíció: Ha p>2 prím,akkor a Legendre szimbólumot definájuk az alábbi módon:
((a/p))={({{1 ha a kvadratikus maradék}, {({{-1 ha a nem kvadratikus maradék}, {0 ha a≡0  (p)}})}})

- A Legendre szimbólum tulajdonságai:
a. ((a/p))≡(a^((p-1)/2))  (p)
       b. ((a/p))((b/p))=(((a b)/p))  \((Megjegyzés : \ 
              ez\ többtényezős\ szorzatra\ is\ igaz)\)
       c.  a≡b  (p)  => ((a/p))=((b/p))
      d.  (a,p)=1  => (((a^2)/p))=1  és ((((a^2) b)/p))=((b/p))
      e.  ((1/p))=1 és (((-1)/p))=(((p-1)/p))=(((-1))^((p-1)/2))={({{1 ha p=4 k +1}, {-1 ha p=4 k-1}})
      f.  ((2/p))=(((-1))^(((p^2)-1)/8))={({{1 ha p≡±1  (8)}, {-1 ha p≡±3  (8)}})
     g.  \((Gauss\ kvadratikus\ reciprocitási\ tétele)\): Ha p és q különböző páratlan prímek,akkor ((p/q))((q/p))=(((-1))^(((p-1)/2)((q-1)/2))), vagy másképp ((p/q))={({{-((q/p)) ha p és q is 4k-1 alakú}, {((q/p)) ha p és q legalább egyike 4k+1 alakú}})

Az (x^2)≡a  (p) konguencia megoldhatóságát jellemzi a Legendre szimbólum értéke.

- Definíció: m∈ℕ, m>1 páratlan,m=(Subscript[p, 1])(Subscript[p, 2])...(Subscript[p, r]) nem feltétlenül különböző pozitív prímek szorzata és (a,m)=1.Ekkor a Jacobi szimbólum  ((a/m))=(∏_(i = 1)^r)((a/(Subscript[p, i]))) .

- Megjegyzés: (x^2)≡a  (m) megoldhatósága nem jellemezhető ((a/m)) segítségével!!!
Ha (x^2)≡a  (m)-nek van megoldása,akkor ((a/m))=1,\(de\ fordítva\ nem\ feltétlenül\ igaz . \ Azokat\ a\ számokat\),melyekre ((a/m))=1,de a nem kvadratikus maradék, \(álnégyzetnek\ \(\(nevezzük\)\(.\)\)\)

- A Jacobi szimbólum tulajdonságai:
          a.  a≡b  (m) => ((a/m))=((b/m))
                     b.  (((a b)/m))=((a/m))((b/m))  és ((a/(m n)))=((a/m))((a/n))  \((Megjegyzés : \ 
                ez\ többtényezős\ szorzatra\ is\ igaz)\)
                      c.  (((-1)/m))={({{1 ha m≡1  (4)}, {-1 ha m≡-1  (4)}})
       d.  ((2/m))={({{1 ha m≡±1  (8)}, {-1 ha m≡±3  (8)}}) 
e.  ((m/n))={({{-((n/m))  ha n≡m≡-1  (4)}, {((n/m)) egyébként}})

- Az algoritmus:

\(Az\ eljárás\ a\ Legendre\ szimbólumra\ épül\),\(pontosabban\ annak\ első\ tulajdonságára . \ 
            Ezúttal\ rögtön\ úgy\ írjuk\ meg\),hogy az input tartalmazza a teszt lefutásainak számát is .  Legyen n a szám amit tesztelünk és legyenek (Subscript[a, 1]),...(Subscript[a, k])  n-nél kisebb pozitív egészek .  Ezeket megint egy véletlen lista fogja tartalmazni és k,azaz a lista hossza lesz a másik input n mellett .  Az algoritmus ellenőrzi az 
((Subscript[a, j])^((n-1)/2))≡(((Subscript[a, j])/n))  (n) kongruenciákat .  Ha ezek közül bármelyik nem teljesül az ellentmond a Legendre szimbólum első tulajdonságának és így n összetett,ekkor a program kiírja ezt és kilép .  Ha n prím,\(akkor\ nyilván\ mindegyik\ teljesül . \ 
          Nem\ tudunk\ azonban\ biztos\ eredményt\ garantálni\),ugyanis attól,hogy n összetett,\(még\ teljesülhet\ mindegyik\ kongruencia . \ 
          Azonban\ bizonyítás\ nélkül\ megjegyezzük\),\(hogy\ ennek\ a\ valószínűsége\ kisebb\),mint ((((1/2)))^k),ahol tehát k a lefutások száma.

Az (((Subscript[a, j])/n)) Jacobi szimbólumokat a program beépített függvényével,JacobiSymbol[(Subscript[a, j]),n]-nel  fogjuk kiszámolni .  Mivel ez páratlan n-ekre van értelmezve,ezért a páros inputot kiszűrjük .  Ha nem bizonyosodott be n-ről,hogy összetett,akkor a végén 25 tizedesjegy pontosságig megadjuk n prímségének \(\(valószínűségét\)\(.\)\)

SolovayStrassen[n_, k_] := 
      Module[
{a, val, randomlist}, 
If[
          OddQ[n], 
          randomlist[m_, j_] := 
            Module[
{A}, 
If[j < m - 1, 
                A = {Random[Integer, {2, m - 1}]}; 
While[ 
                  Length[A] < j, 
A = 
                    Union[A, { 
                        Random[
                          Integer, {2, 
                            m - 1}] }]]; 
Return[
                  A], Print[j, " nem kisebb,mint ", 
                    m - 1];]
]; 
a = 
            randomlist[n, k]; 
val = 
            N[1 - ((((1/2)))^k), 25]; 
If[
            PowerMod[a, ((n - 1)/2), n] == Mod[JacobiSymbol[a, n], n], 
            Print["A(z) ", n, " legalább ", 
              val, " valószínűséggel \
prím"], 
            Print[n, " összetett"]], 
Print[
            n, " páros szám.Ha 2,akkor prím,egy\
ébként összetett"]]
]

SolovayStrassen[100000007, 20]

SolovayStrassen[
      44792712230380015153004252571676639199064264242458204943933304177375933234124537299443542401921213023812318630140733232379707115581124642830572487340790521257344442028966696868302096598442754894011, 20]

Ez az algoritmus nem faktorizál, ezért nagy számokra is lefuttatható, viszont nem garantál tökéletes végeredményt csak nagy valószínűségűt.

3. A Fermat-teszt:

Korábban láttuk,hogy ha p prím,akkor minden 0<a<p  egészre (a^(p-1))≡1  (p),vagyis ha ez nem teljesül,akkor az n szám összetett .  A Fermat-teszt egyszerűen a fenti kongruencia érvényességét ellenőrzi az n szám prímségének tesztelésére .  Azonban itt is meg kell jegyeznünk,hogy abból,hogy (a^(n-1))≡1  (n) teljesül,még nem következik,hogy n prím,így ekkor a teszt nem hoz eredményt .  Ilyenkor újabb a választásával próbálkozunk.

- Definíció: Legyen n összetett és (a,n)=1.  Ekkor azt mondjuk,hogy a az n szám összetettségének Fermat-tanúja,ha (a^(n-1))≢1  (n). Ha (a^(n-1))≡1  (n),akkor a az n szám Fermat-cinkosa,és ilyenkor n-et a-\(alapú\ álprímnek\ \(\(nevezzük\)\(.\)\)\)

- Megjegyzés: Bizonyított tény, hogy minden a-ra, ahol (a,n)=1, végtelen sok a-alapú pszeudoprím (álprím) létezik. 
      341 a legkisebb 2-, 91 a legkisebb 3-, és 15 a legkisebb 5-álprím.

Ha elvégezzük a tesztet egy számmal, amely összetett, akkor a cél az, hogy nem túl sok a választásával találjunk egy tanút, amely ezt bizonyítja. Sajnos azonban nem minden összetet számhoz létezik ilyen tanú.

- Definíció: Egy n összetett számot Carmichael-\(számnak\ vagy\ univerzális\ álprímnek\ nevezünk\),ha  minden (a,n)=1 esetén (a^(n-1))≡1  (n). Ekkor n összetettségének egyetlen Fermat-tanúja sincs.

- Megjegyzés: A prímtesztelési eljárás szempontjából rossz hír, hogy 1992-ben Alford, Granville és Pomerance bebizonyították, hogy végtelen sok Carmichael-szám létezik.

- Példa univerzális álprímre:
-Állítás: Az 561 Carmichael - 
                szám .  (Ez a legkisebb) 
       -Bizonyítás:   (a^2)≡1  (3)       (a^560)≡((((a^2)))^280)≡1  (3)
                                     (a^10)≡1  (11)    (a^560)≡((((a^10)))^56)≡1  (11)
                                     (a^16)≡1  (17)    (a^560)≡((((a^16)))^35)≡1  (17)
Ezek alapján (a^560)≡1  (561) minden a-ra,amire (a,561)=1,\(vagyis\ az\ 561\ univerzális\ \(\(álprím\)\(.\)\)\)

A Fermat-teszt azonban ezen számoktól eltekintve hatékony. Belátjuk, hogy ha n összetett, de nem Carmichael-szám, akkor a teszt "nagy valószínűséggel" lebuktatja.

- Tétel: Ha  n-hez van Fermat-tanú,akkor van legalább ((φ(n))/2).

- Bizonyítás: Legyen (SuperStar[(Subscript[Z, n])])={a ∈ℤ:(a,n)=1  és 0≤a<n},továbbá legyen C={a∈(SuperStar[(Subscript[Z, n])]) : (a^(n-1))≡1  (n) }. Vagyis (SuperStar[(Subscript[Z, n])]) a standard redukált maradékrendszer modulo n és C az n szám Fermat-cinkosainak halmaza. A feltevés szerint létezik tanú n-hez, vagyis C⊂ (SuperStar[(Subscript[Z, n])]) és C≠(SuperStar[(Subscript[Z, n])]). Legyen t∈(SuperStar[(Subscript[Z, n])]) egy tanú .  Ekkor minden a∈C esetén t a is tanú,ugyanis (((t a))^(n-1))≡(t^(n-1))(a^(n-1))≡(t^(n-1))≢1  (n),hiszen t tanú .  Továbbá ha a≠a' két C-beli elem,akkor t a≢t a' (n),hiszen t∈(SuperStar[(Subscript[Z, n])]) invertálható .  Ezek szerint a t a alakú elemek adnak legalább |C| Fermat - tanút, tehát az n-\(hez\ relatív\ prím\ maradékosztályok\ közül\ legalább\ annyi\ tanú\ van\),mint cinkos. |(SuperStar[(Subscript[Z, n])])|=φ(n), vagyis legalább ((φ(n))/2) tanú van.

- Megjegyzés: \(Még\ egyszerűbb\ a\ bizonyítást\ az\ algebra\ eszközeivel\ megfogalmazni . \ 
              Könnyű\ látni\),hogy (SuperStar[(Subscript[Z, n])]) a modulo n szorzásra nézve csoport, aminek C részcsoportja .  Lagrange tétele szerint egy csoport részcsoportjának elemszáma osztója a csoport elemszámának,azaz jelen esetben |C| osztja |(SuperStar[(Subscript[Z, n])])| -ot .  Mivel C≠(SuperStar[(Subscript[Z, n])]),\(az\ állítás\ ebből\ már\ \(\(látszik\)\(.\)\)\)

Legyen n összetett,de nem Carmichael-szám .  Válasszunk egy n-\(nél\ kisebb\ a\ számot . \ 
            Az\ előbbi\ tétel\ alapján\ annak\ a\ valószínűsége\),hogy cinkost választottunk legfeljebb ((φ(n))/(2n))<(1/2) .  Ismételjük meg ezt az eljárást k-szor,\(így\ annak\ a\ valószínűsége\),hogy mindig cinkost választunk kisebb,mint (1/(2^k)),vagyis viszonylag kevés a kipróbálásával igen nagy eséllyel találunk tanút n összetettségére .  Az egyetlen problémát a korábban említett Carmichael-számok jelentik,\(hiszen\ ezekre\ a\ teszt\ ugyanazt\ az\ eredményt\ adja\),mint prímekre.

- Az algoritmus:

Két input lesz ismét: n és k. n a szám amit tesztelünk és k jelenti azt,hogy hányszor,azaz,hogy hány a számra fogjuk megnézni az (a^(n-1))≡1  (n) kongruencia teljesülését .  Ezeket a számokat ismét egy véletlen lista fogja generálni .  Ha valamelyik számra nem teljesül a kongruencia,\(akkor\ az\ algoritmus\ leáll\ és\ kiírja\),hogy n összetett .  Ha végig fut,\(akkor\ ezt\ egy\ indikátor\ jelzi\ és\ az\ eljárás\ kiírja\),hogy n mekkora valószínűséggel prím,illetve,hogy n lehet Carmichael-szám.

Fermattest[n_, k_] := 
      Module[
{randomlist, a, 
          val}, 
randomlist[m_, j_] := 
          Module[
{A}, 
If[j < m - 1, 
              A = {Random[Integer, {2, m - 1}]}; 
While[ 
                Length[A] < j, 
A = 
                  Union[A, { 
                      Random[Integer, {2, 
                          m - 1}] }]]; 
Return[
                A], Print[j, " nem kisebb,mint ", 
                  m - 1];]
]; 
a = 
          randomlist[n, k]; 
val = 
          N[1 - ((((1/2)))^k), 25]; 
If[
          PowerMod[a, n - 1, n] == Table[1, {k}], 
          Print["A(z) ", n, " legalább ", 
            val, " valószínűséggel pr\
ím ,vagy Carmichael-szám"], 
          Print[n, " összetett"]];
]

Fermattest[100000007, 20]

Fermattest[
      44792712230380015153004252571676639199064264242458204943933304177375933234124537299443542401921213023812318630140733232379707115581124642830572487340790521257344442028966696868302096598442754894011, 20]

Az algoritmus gyors nagyon nagy számokra is, viszont nem ad biztos eredményt n prímségére és a Carmichael-számokat sem tudja kiszűrni.

4. A Rabin-Miller-teszt:

Legyen n páratlan egész, n-1 = (2^r)s,ahol s szintén páratlan és legyen (a,n)=1.  Ekkor 
(a^(n-1))-1=(a^((2^r)s))-1=((a^((2^(r-1))s))-1)((a^((2^(r-1))s))+1)=...=((a^s)-1)((a^s)+1)((a^(2s))+1)((a^((2^2)s))+1)...((a^((2^(r-1))s))+1)

Ha n prím,akkor (a^(n-1))-1≡0  (n) és így az előbbi szorzat valamelyik tényezője osztható n-nel,azaz ha az (a^s)≡1  (n), (a^((2^i)s))≡-1  (n)  (i=0,1,...,r-1) kongruenciák közül egyik sem teljesül,akkor n összetett .  Ha teljesülnek,akkor még nem biztos,hogy az n szám prím ezért új a-val kell próbálkozni.

- Definíció: Legyen n páratlan összetett szám és n-1=(2^r)s, ahol s páratlan és legyen (a,n)=1.Az a szám, n összetettségének Rabin-Miller-tanúja,ha (a^s)≢1  (n),továbbá (a^((2^i)s))≢-1  (n) egyetlen 0≤i<r esetén sem .  Egyébként a Rabin-Miller-cinkos,és ekkor az n összetett számot erős a-\(álprímnek\ \(\(nevezzük\)\(.\)\)\)

- Példa: Az 561 nem erős 2-álprím. (Azaz hiába Carmichael-szám, a teszt kiszűri a=2 esetén)

- Bizonyítás: 560=35*(2^4),azaz r=4,s=35.
(2^35) ≡ 263  (561), (2^70) ≡ 166  (561), (2^140) ≡ 67  (561), (2^280) ≡ 1   (561), vagyis  az a=2 választás bizonyította,\(hogy\ 561\ nem\ erős\ 2 - \(\(álprím\)\(.\)\)\)

Ez az algoritmus tehát kiszűri az univerzális álprímeket is, és a hatékonysága is jobb, mint a Fermat-teszté.

\(Bizonyítás\ nélkül\ közöljük\),hogy ha n páratlan összetett szám,akkor legfeljebb ((n-1)/4) Rabin-Miller-cinkosa van .  
            Annak a valószínűsége,hogy k különböző,n-nél kisebb pozitív szám mindegyikére nézve n erős álprím legyen kisebb,mint (1/(4^k)).

\(Ezen\ állítást\ \(1\/4\) helyett 
           1\/2 - re\ könnyen\ bizinyíthatnánk . \ Ehhez\ azt\ kéne\ belátni\),\(hogy\ minden\ páratlan\ összetett\ számhoz\ létezik\ Rabin - Miller - 
        tanú . \ Ezután\ azt\), hogy ha egy van, akkor van legalább ((φ(n))/2) is,\(a\ Fermat - 
        tesztre\ vonatkozó\ tételhez\ hasonlóan\ \(\(bizonyíthatnánk\)\(.\)\)\)

Legyen tehát n páratlan egész szám .  Ha n összetett, \(akkor\ több\ mint\ 3\/4\ valószínűséggel\ találunk\ hozzá\ egy\ Rabin - 
        Miller - tanút\), tehát az eljárást k-szor ismételve kevesebb, mint (1/(4^k))a valószínűsége,hogy csupa cinkost választottunk.

- Az algoritmus:

Input az n szám amit tesztelünk és k a tesztek száma .  Először kiszűrjük a páros n inputot .  Ezután felbontjuk (n-1)-et (2^r)s alakra ahol s páratlan .  Generálunk egy k különböző elemű véletlen listát és ennek minden (Subscript[a, j]) elemére ellenőrizzük az ((Subscript[a, j])^s)≡1  (n), ((Subscript[a, j])^((2^i)s))≡-1  (n)  (i=0,1,...,r-1) kongruenciákat .  Ha valamely (Subscript[a, j]) esetén egyik sem teljesül, akkor az algoritmus kiírja, hogy n összetett és kilép .  Ha egyik (Subscript[a, j]) sem buktatja le n-et, akkor az eljárás megadja n prímségének \(\(valószínűségét\)\(.\)\)

\(RabinMiller[n_, k_] := 
      Module[
{randomlist, val, ind, a, b, 
          bont}, 
listak = {}; 
ind = {}; 
If[OddQ[n], 
          randomlist[m_, j_] := 
            Module[
{A}, 
If[j < m - 1, 
                A = {Random[Integer, {2, m - 1}]}; 
While[\ 
                  Length[A] < j, 
A = 
                    Union[A, {\ 
                        Random[
                          Integer, {2, 
                            m - 1}]\ }]]; 
Return[
                  A], \(Print[j, " nem kisebb,mint ", 
                    m - 1];\)]
]; 
a = 
            randomlist[n, k]; 
bont[l_] := 
            Module[
{s, r, b}, 
s = 
                l - 1; 
r = 0; 
While[
                EvenQ[s], s = s/2; 
                r = r + 1;]; 
b = {r, 
                  s}
]; 
b = 
            bont[n]; 
For[v = 1, 
            v < Length[a] + 1, \(v++\), 
For[i = 0, 
                i < b[\([1]\)], \(i++\), 
\(If[
                    PowerMod[a[\([v]\)], 2\^i*b[\([2]\)], n] == n - 1, 
                    AppendTo[ind, 1], 
                    AppendTo[ind, 0]];\)]
If[
                PowerMod[a[\([v]\)], b[\([2]\)], n] == 1, 
                AppendTo[ind, 1], 
                AppendTo[ind, 0]]; 
AppendTo[listak, ind]; 
            ind = {};]; 
val = 
            N[1 - \((1\/4)\)\^k, 25]; 
If[
            MemberQ[listak, Table[0, {w, 1, b[\([1]\)] + 1}]], 
            Print[n, " összetett"], 
            Print["A(z) ", n, " szám ", 
              val, " valószínűséggel prím"]]
, 
          Print[n, " páros szám. Ha nem 2, akkor összetett"]]
]\)

RabinMiller[100000007, 20]

RabinMiller[
      44792712230380015153004252571676639199064264242458204943933304177375933234124537299443542401921213023812318630140733232379707115581124642830572487340790521257344442028966696868302096598442754894011, 20]

Ennek az algoritmusnak három roppant hasznos tulajdonsága is van. Először is gyors nagyon nagy számokra is, másodszor, kiszűri a Carmichael-számokat, harmadszor pedig ugyanannyi lefutással nagyobb valószínűséget ad az eredményre, mint az előző két teszt.

Összegzés:

A notebookban definiáltuk a prímszámokat és a velük kapcsolatos fontosabb fogalmakat, melyek az elméleti háttér megértéséhez szükségesek voltak. Ezután példákat hoztunk a prímek fontos gyakorlati alkalmazásaira, főleg a kriptográfia terén, és megmutattuk, hogy miért is van szükség prímtesztekre. Az elméleti részt négy prímteszt gyakorlati megvalósítása követte. Mind a négy esetben először az adott teszt elméleti hátterét írtuk le és egy részét bizonyítottuk is, majd ezt követte az algoritmus programozásának magyarázata és végül maga a teszt.

További eredmények

Láttuk, hogy minden tesztnek volt valami hátránya, legtöbbször az, hogy nem garantált tökéletes eredményt egy szám prím voltára csak nagy valószínűségűt. Ismert azonban már olyan, szintén gyors algoritmus, amely teljesen biztos eredményt ad.

Fontos megjegyezni, hogy a fent látott titkosítási módszerek nagy mértékben arra épülnek, hogy nem tudunk nagy számokat gyorsan faktorizálni, azaz prímek szorzatára bontani. Azonban nincs olyan matematikai eredmény, amely azt mutatná, hogy erre nem is létezik algoritmus, sőt egy némiképp hasonló problémára (egész együtthatós polinomok irreducibilis tényezők szorzatára bontása) A. Lenstra, H. Lenstra és Lovász László már találtak gyors megoldást.

Érdekességek: 
    1.Ha valaki kitalálná a prímfaktorizáló algoritmust, akkor a legtöbb titkosítás ezzel használhatatlanná válna. Márpedig, mint ahogy az előbb említettük hasonló problémára már van algoritmus és egyes matematikusok szerint pár évtizeden belül a számok kanonikus alakra hozása is megoldott lesz.
    2.Az alábbi honlapon az igazán nagy prímek vannak csoportosítva rengeteg tulajdonságuk szerint. A teljesség igénye nélkül csak párat említve: Mersenne-prímek, ikerprímek, faktoriális prímek. http://primes.utm.edu/largest.html

Irodalomjegyzék:
                              Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai. Typotex Kiadó, Budapest 2002.
                              Freud Róbert, Gyarmati Edit: Számelmélet. Universitas-Nemzeti Tankönyvkiadó, Budapest 2000.

Budapest 2006.12.10.