728 x 90

, i

Testy pierwszości

Testy pierwszości

 

1. Wstęp

Gdy mamy do czynienia z liczbą będącą iloczynem dwóch czy trzech cyfr, to weryfikacja jej pierwszości nie jest problemem. Jednak gdyby człowiek musiał samodzielnie szukać ewentualnych dzielników dla ogromnych liczb stosowanych w kryptografii, klucz straciłby
ważność przed jego złamaniem.

Na przestrzeni wieków powstał szereg testów pierwszości. Obecnie, częściej niż algorytmy deterministyczne, stosuje się probablistyczne
korzystające z generatora losowych ciągów cyfr. Uogólniając, sprawdzają one, czy dla wylosowanej wartości, spełnione jest określone równanie. Jeśli podczas działania algorytmu nie zostanie znaleziona taka liczba dla zadanej liczby wejściowej, to uznaje się ją za prawdopodobnie pierwszą.

1.1. Aspekt Historyczny

Liczby pierwsze od wieków stanowią poważną zagadkę dla matematyków. W dzisiejszych czasach z aspektu czysto abstrakcyjnego, problem ten przeniósł się do świata rzeczywistego. W XX w. zaczęto używać ich do szyfrowania. Oznaczało to, że poznanie zasady rządzącej liczbami pierwszymi jest szczególie ważne dla współczesnej kryptoanalizy. Spójrzmy jednak w odległe lata.

W starożytnosci tematem tym zajmował się Euklides. Pokazał on, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych. Uczony ten sformułował także bardzo ważne twierdzenie. Co ciekawe, zostało ono udowodnione dopiero przez Gaussa

1.1.1. Twierdzenie Euklidesa o liczbach pierwszych Każdą liczbę naturalną n można jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych.

\begin{align*}
n=a_0 \cdot a_1 \cdot … \cdot a_n
\end{align*}
gdzie: $ \forall 0 \leq i \leq n \exists d : d|a_i$ to $d=a_i \vee d=1$ oraz $a_i > a_{i+1}$

W XVII w. pojawiła się nowe twierdzenie za sprawą Pierre de Fermat’a, udowodnione pózniej przez Eulera i Leibniza.
1.2. Dowód na nieskończenie wiele liczb pierwszych Dowód ten opiera się na pokazaniu rozbieżności sumy odwrotności liczb pierwszych.
\begin{align*}
\sum_{p \in P} \dfrac{1}{p} = \infty
\end{align*}

Załóżmy, że:
\begin{align*}
P(x)&=\sum_{p \in P, p \leq x}\dfrac{1}{p}\\
Q(x)&=\sum_{p \in P, p \leq x}\frac{1}{p-1}
\end{align*}
Ponieważ:
\begin{align*}
&1=(\frac{1}{1}-\frac{1}{2})+(\frac{1}{2}-\frac{1}{3})+ …\\
&P(x)>Q(x)-1\\
&1+\frac{1}{p-1}=\dfrac{1}{1-\frac{1}{p}}=1+\frac{1}{p}+\frac{1}{p^2}+ … \\
&s=\prod_{p \in P, p\leqslant x} (1+\frac{1}{p-1}) \\
&s= \prod_{p \in P, p\leqslant x} (1+\frac{1}{p}+\frac{1}{p^2}+ …) \geqslant \sum_{n=1}^{x}\frac{1}{n} \\
&\frac{1}{p-1}>ln(1+\frac{1}{p-1}) \\
&Q(x)> ln(\prod_{p \in P, p\leqslant  x}(1+\frac{1}{p-1})) = t \\
&t \geqslant ln (\sum_{n=1}^{x}\dfrac{1}{n})>ln(ln(x+1))\rightarrow \infty \\
&P(x)>ln(ln(x+1))-1\rightarrow \infty
\end{align*}

1.3. Małe Twierdzenie Fermata Twierdzenie to zostało sformułowane przez Jana Brożka i stanowi podstawę do testu pierwszosci.

\begin{align*}
a^{p-1}\equiv 1 (mod p)
\end{align*}
gdzie p – liczba pierwsza, oraz $a \in Z$ oznacza to, że $gcd(a,p)=1$

Kolejne lata to odkrycia m.in Mersenne’a. Który wyznaczył wzór na liczby pierwsze nazwane pózniej na cześć jego imieniem.

Wzór 1.3 – Liczby Merssen’a
\begin{align*}
2^p – 1
\end{align*}
Największą oficjalnie znaną liczbę pierwszą odkryto w 2016 roku w ramach projektu GIMPS i jest nią $2^{74207281}-1$ tzn, że ma 22 338 618 cyfr.
Swój wkład w rozwój tej dziedziny wnieśli także polacy. Pochodzący z lwowskiej szkoły matematycznej Stanisław Ulam odkrył pewną zależność. W czasopiśmie Scientific American opublikował on tzw. Spiralę Ulama, przedstawioną na poniższych grafikach.
1.3.1. Spirala Ulama Rozpoczynając od liczby 1, znajdują sie na niej wszystkie liczby naturalne w postaci spirali. Przy wystarczająco dużej złożoności tablicy na niektórych przekątnych liczby pierwsze pojawiają się znacznie częściej, fakt ten jednak nie został jeszcze wytłumaczony.

1.3.2. Spirala Ulama z różnych perspektyw

2. Hipoteza Riemanna Jeden z tzw. problemów milenijnych. Sformułowana w 1859 roku przez Bernharda Riemanna. Mówi ona ,że wszystkie tzw. nietrywialne zera (nierzeczywiste) funkcji dzeta mają część rzeczywistą równą $\dfrac{1}{2}$
2.0.1. Wzór 1.3 – Funkcja Dzeta \begin{align*}
\zeta (s)=\sum_{n=1, n \in P}^{\infty}\frac{1}{n^s}
\end{align*}

Nieprzypadkowość liczb pierwszych, chciał udowodnić także niemiecki matematyk Euler obliczając wartość poniższego działania.
\begin{align*}
\dfrac{2^2}{2^-1}\cdot \dfrac{3^2}{3^-1}\cdot \dfrac{5^2}{5^-1} \cdot…=\prod_{n \in P}\frac{n^2}{n^2 – 1} = \pi^2/6
\end{align*}

Jednocześnie pokazując związek świata rzeczywistego i liczb.

2.1. Twierdzenie Dirachleta Jeśli $gcd(a,n)=1$ to istnieje nieskończenie wiele liczb pierwszych kongruentnych z a modulo n.

2.2. Przybliżona wartość n-tej liczby pierwszej \begin{align*}
n ln(n)< p_n < n(ln(n)+ln(ln(n))
\end{align*}
gdzie: $p_n$ – liczba pierwsza i $n\geq 6$

2.3. Liczba liczb pierwszych w przedziale [2,x] Wzór określa liczbę liczb pierwszych w przedziale [2,x], które są kongruentne z a modulo n gdzie $\gcd(a,n)=1$. Wtedy:
\begin{align*}
\pi (x,a,n)~\frac{x}{\phi(n)ln(n)}
\end{align*}

Natomiast liczba liczb pierwszych w przedziale [2,x] jest równa asymptotycznie:

\begin{align*}
\dfrac{x}{ln(x)}
\end{align*}

2.4. Aspekt Kryptologiczny Wiele współczesnych kryptosystemów opiera się na liczbach pierwszych. A ich bezpieczeństwo na problemie faktoryzacji. Najpopularniejsze z nich to RSA, protokół uzgodniania klucz Diffiego-Hellmana. Liczby pierwsze pozwalają na stworzenie często wykorzystywanych wielomianów stopnia $m$ nad ciałem $Z_p$ oraz $F_{p^m}$ do stworzenia ciała $F_{p^m}$

3. Testy Pierwszości 3.1. Test Solovaya-Strassena Test ten ma charakter historyczny, ponieważ został on wyparty przez test Rabina Millera. Algorytm opiera się na symbolu Jacobiego.

3.1.1. Kryterium Eulera Niech $n \in P$ wtedy $a^{n-1/2}\equiv \left( \frac{a}{n} \right) (mod n) $ dla $\forall a \in Z: \gcd(a,n)=1$
Jeśli liczba nie spełnia tego kryterium, liczba $n$ jest świadkiem złożoności Eulera.

Jeśli $n$ jest liczbą nieparzystą to najwyżej $\phi (n) /2 $, spośród wszystkich liczb $1\leqslant a\leqslant n-1$ to fałszywi świadkowie Eulera dla liczby $n$

3.1.2. Pseudokod Dane Wejściowe: Liczba $n \in N $
Dane Wyjściowe: Odpowiedz na pytanie czy liczba jest złożona?

Algorytm:
1.Dla i od 1 do wybranego t wykonaj:
1.1 Wylosuj $a \in $
1.2 Oblicz $r=a^{()n-1)/2}(mod n)$
1.3 Jeśli $r \neq 1$ oraz $r \neq n-1 $ Zwróć: ZŁOŻONA
1.4 Oblicz symbol Jacobiego $s=\left( \frac{a}{n} \right)$
1.5 Jeśli $s\neq s (mod n)$ Zwróć: ZŁOŻONA
2. Zwróć: PSEUDOPIERWSZA

3.2. Test Fermata Test ten opiera się na wspominanym wcześniej Małym Twierdzeniu Fermata. Algorytm polega na znalezieniu tzw. świadków złożoności czyli takiego $a \in $, że $a^{n-1}\neq 1 (mod n)$. Warto pamiętać, że nie znalezienie świadka złożoności nie oznacza, że liczba jest pierwsza, nazywamy ją pseudopierwszą ponieważ test jest probablistyczny.
3.1.2. Pseudokod Dane Wejściowe: Liczba $n \in N $
Dane Wyjściowe: Odpowiedz na pytanie czy liczba jest złożona?

Algorytm:
1.Dla i od 1 do wybranego t wykonaj:
1.1 Wylosuj $a \in $
1.2 Oblicz $r=a^{n-1}(mod n)$
1.3 Jeśli $r \neq 1$ Zwróć: ZŁOŻONA
2. Zwróć: PSEUDOPIERWSZA

Niestety test Fermata ma pewna wadę. Istnieją liczby złożone, które test wykazuje jako iczby pseudopierwsze, są to liczby Carmichaela.

3.2.1. Definicja-Liczba Carmichaela Jest to liczba złożona $n \in Z$, taka, że $a^{n-1}\equiv1 (mod n)$,dla wszystkich liczb $a \in Z$ takich, że $\gcd(a,n)=1$. Ponadto liczba ta jest wolna od czynników kwadratowych tzn. że nie dzieli się przez kwadrat, żadnej liczby pierwszej. Ponadto każda liczba Carmicheala jest iloczynem co najmniej trzech liczb pierwszych. Najmniejszą taką liczbą jest $561=3 \cdot 11 \cdot 17$. Istnieje nieskończenie wiele liczb Carmicheala, jednak ich występowanie jest stosunkowo rzadkie. Istnieje tylko $105 212 na 10^{15}$ liczb.

3.3. Test Rabina Millera Test silnej pseudolosowości jest najczęściej stosowanym testem pierwszości. Algorytm korzysta z następującego faktu. Jeśli liczb $n \in P$ oraz $n-1=2^e r$ oraz $x \in Z$ takie, że $gcd(x,n)=1$. Wtedy albo $a^k \equiv 1(mod n)$ albo $x^{2^e k}\equiv -1 (mod n)$. Przy założeniu poprawności Hipotezy Riemanna test ten jest deterministyczny.
3.3.1. Dowód Ponieważ $x^{n-1} -1 = x^{2^e k}-1$ , a $n-1=2^{e}k$ oraz $x^{n-1}-1\equiv 0$ wtedy:
$x^{2^{j}k}-1=(x^{2^{e-1}k})^2 -1$

$= ((x^{2^{e-1}k}) -1)((x^{2^{e-1}k}) +1)$

$=…= (x^k -1)(x^k+1)(x^{2k}+1)(x^{4k}+1)…(x^{2^{e-1}k}+1)\equiv 0 mod n$
Stąd:
\begin{align*}
x^k\equiv 1 mod n \vee x^{2^i k}\equiv -1 mod n
\end{align*}

3.1.2. Pseudokod Dane Wejściowe: Liczba $a \in N $
Dane Wyjściowe: Odpowiedz na pytanie czy liczba jest złożona?

Algorytm
1.Przedstaw n-1 w postaci $2^e k$
2.Dla i od 1 do wybranego t wykonaj:
2.1 Wylosuj $a \in $
2.2 Oblicz $y\equiv a^k mod n$
2.3 Jeśli $y\neq1 oraz y\neq n-1 $ to:
2.3.1 $j:=1$
2.3.2 Dopóki $j\leqslant e-1$ oraz $y \neq n-1$ to:
2.3.2.1 Oblicz $y:=y^2 mod n$
2.3.2.2 Jeśli $y=1$ to Zwróć: ZŁOŻONA
2.3.2.3 $j:=j+1$
2.3.3 Jeśli $y \neq n-1$ Zwróć: ZŁOŻONA
3. Zwróć: PSEUDOPIERWSZA

3.4. Test Lucasa-Lehmera dla liczb Mersenn’a Test ten jest deterministyczny, w przeciwieństwie do poprzednich. Algorytm sprawdza czy liczba Mersenne’a jest pierwsza.

Dane Wejściowe: Liczba Mersenne’a $n=2^s -1$
Dane Wyjściowe: Odpowiedz na pytanie czy liczba jest złożona?

Algorytm
1. Wykonaj próbne dzielenie między 2 i $\lfloor \sqrt{s}\rfloor$
2. $u:=4$
3. Dla k od 1 do s-2:
3.1 Oblicz $u:=(u^2)-1$ mod n
4. Jeśli $u=0$ to zwróć: PIERWSZA w przeciwnym przypadku ZŁOŻONA

4. Bibliografia

Kryptografia Stosowana A.Menezes, P. Oorschot, S.Vanstone

 

Źródła obrazów: wikipedia.pl, Imathination.org, pinterest.com, grafika główna https://pixabay.com/

 

2 comments

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

2 Comments

  • Mateusz
    17 października 2017, 23:29

    Bardzo fajny tekst. Tylko ten dowód faktu, że liczb pierwszych jest nieskończenie wiele…zabijacie muchę armatą (poza tym z niektórych przejść warto by było się wytłumaczyć). A co do testów statystycznych, wiadomo coś o ich mocach? Jeżeli nie ma na ten temat teorii, to przynajmniej warto zrobić pewne symulacje, żeby mieć świadomość jaka jest skuteczność przedstawionych metod. W razie czego służę pomocą;)

    REPLY
  • Krzysztof
    16 listopada 2017, 10:30

    Jest jeszcze inny sposób analizy liczb pierwszych pokazany poniżej. Pozwala na większy zakres analizy liczb pierwszych np. w Excelu.

    Sito Małgorzaty opisane pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhhzzvgOxdib8Y_rW

    Sub sito()

    Dim j, i As Long
    Dim a, b As Long
    Dim t As Boolean
    Dim f As Boolean
    Dim x_max As Long
    Dim x As Long
    Dim yp As Long

    Dim pk As Integer
    Dim pky As Integer
    Dim pk_max As Integer
    Dim pk_min As Integer

    Range("B:Z").ClearContents
    ‘ilo栤anych w kadej kolumnie
    x_max = Range("A1").Text
    ‘ilo栫olumn – warto栭ax 25
    pk_max = Range("A2").Text

    ‘ zaczynamy od 2 kolumny
    pk = 2
    pky = 2
    pk_min = 2
    pk_max = pk_max + 1
    t = True

    ‘ warto栰ocztkowa dla iteracji
    yp = 1
    i = 0

    Do
    i = i + 1
    ‘ warto栰ocztkowa x dla danej iteracji i
    x = yp
    ‘ wyliczenie wartosci a i b
    a = 1 + 2 * i
    If t Then
    b = 4 * i + 3
    Else
    b = 4 * i + 1
    End If
    ‘ ustawienie kolejnoci a czy b – t dla iteracji i , f dla poditeracji
    f = t
    If Cells(i, pk).Value <> 1 Then
    If f Then
    x = x + b
    yp = x + a
    Else
    x = x + a
    yp = x + b
    End If
    ‘zaznaczenie elementla danej iteracji
    For j = pk_min To pk_max
    Do While x < x_max
    Cells(x, j) = 1
    If f Then
    x = x + a
    Else
    x = x + b
    End If
    f = Not (f)
    Loop
    x = x – x_max + 1
    Next j
    Else
    yp = yp + a + b
    End If
    If Not (yp < x_max) Then
    yp = yp – x_max + 1
    pky = pky + 1
    End If
    pk_min = pky
    t = Not (t)
    Loop Until (pky > pk_max)

    End Sub

    REPLY

Inne artykuły