728 x 90

, , i

Analiza testów pierwszosci

Analiza testów pierwszosci

Liczby pierwsze Koło Naukowe Kryptologii i Cyberbezpieczeństwa WAT

Szczególne podziękowania dla dr Lucjana Kowalskiego za pomoc przy artykule

1 Wstęp

W artykule “Testy pierwszości” zajeliśmy się opisaniem problemu poszukiwania liczb pierwszych oraz ich wykorzystaniem. Dowiedzieliśmy się, że są one szeroko stosowane we współczesnej kryptologii. Większość współczesnych kryptosystemów opiera się na problemie faktoryzacji jest nim np. najpopularniejszy szyfr RSA, który stanowi podstawę bezpieczenstwa w internecie. Kryptografia asymetryczna dzięki swojej prostocie, a przede wszystkim skuteczności, stała się nieodłącznym elementem dzisiejszego świata. Jednak wraz ze wzrostem mocy obliczeniowej komputerów klasycznych, oraz widmem pojawienia się komputerów kwantowych poszukujemy nowych rozwiązań. Algorytmami postkwantowymi zajmiemy się w innym czasie, dziś poruszymy temat długości klucza. Z roku na rok ludzie coraz bardziej obawiają się o swoje zasoby, coraz ważniejsza staje sie informacja. Zniszczenie lub przechwycenie zasobów elektronicznych może mieć poważne konsekwencje w świecie rzeczywistym. Dlatego w nowoczesnych szyfrach zmienia się długość klucza na coraz to większą. Np. dla AES jest to 4096 bitów, a jeszcze niedawno było to 256. W kryptosystemach opartych na problemie faktoryzacji szukamy coraz to nowych liczb pierwszych. Nowe projekty poszukiwania takie jak GIMPS oczywiście pozwalają na coraz skuteczniejszą analizę liczb, jednak najważaniejsze są algorytmy. W poprzednim artykule bliżej przyjżeliśmy się testowi Rabina – Millera oraz Fermata. Dziś zajmiemy się testem probablistycznym Solovaya-Strassena oraz testem deterministycznym AKS. Nastepnie porównamy ich działania. Aby przypomnieć sobie o jakiej skali problemu mówimy, największą znaną liczba pierwszą jest M74207281 i ma postać $2^{74 207 281} – 1$. A deterministyczne sprawdzenie jej pierwości trwało 31 dni. Dlatego używamy tutaj testów probablistycznych.

2 Liczby Pierwsze

W poprzednim artykule pokazaliśmy czym sa liczby pierwsze, dziś przedstawimy dokładniej dwa testy oraz dowody na nieskończoność liczb pierwszych. Warto przypomnieć na poczatek czym są te liczby. Jest to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.

Nie znamy wzoru na liczby pierwsze jednak za sprawą badań Marina Mersenne’a, Poznaliśmy wzór określający największe dzisiejsze liczby pierwsze. Mają one postać $2^{n-1}$. Warunkiem koniecznym aby liczba Mersena była pierwsza jest aby wykładnik $n$ był liczbą pierwszą.

Z poprzedniego artykułu wiemy, że liczb pierwszych jest nieskończenie wiele, spójrzmy teraz na inne bardzo ciekawe dowody.

2.1 Dowody, że liczb pierwszych jest nieskończenie wiele

2.1.1 

Zakładamy, że jest skończenie wiele liczb pierwszych:

$$p_1,p_2,..,p_n$$
Rozpatrujemy liczbę $s=p_1\cdot p_2 \cdot… \cdot p_n + 1$.
Liczba ta powinna być złożona, ponieważ jest większa od rozpatrywanych liczb pierwszych. \newline
Niech $p_i$ będzie dzielnikiem liczby $s$, liczba $p_i$ jest też dzielnikiem liczby $s-1$. Zatem $p_i$ będzie też dzielnikiem liczby $s-(s-1)=1$, co prowadzi do sprzeczności.

Wniosek:

Jeżeli $P$ jest zbiorem liczb pierwszych i $P$ jest zbiorem skończonym, to iloczyn liczb należących do tego zbioru powiększony o 1 jest liczbą pierwszą nienależącą do $P$, albo jest liczbą złożoną, której rozkład na czynniki pierwsze zawiera liczby spoza zbioru $P$.

2.1.2 Dowód Eulera

Euler udowodnił, że szereg odwrotności liczb pierwszych jest rozbieżny($p_n$ – n-ta liczba pierwsza)
$$\sum_{n}^{} \frac{1}{p_n}$$
Gdyby liczb pierwszych było skończenie wiele, to taki szereg miałby sumę skończoną.

2.1.3 Twierdzenie Czebyszewa o liczbach pierwszych:

Dla każdej liczby naturalnej $n > 1$
istnieje liczba pierwsza $p$ taka, że $n < p < 2n$.
Zatem liczby pierwsze mogą być dowolnie duże.

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)$

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)$

Stąd:

$x^k\equiv 1 mod n \vee x^{2^i k}\equiv -1 mod n$

Pseudokod

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

1.Przedstaw n-1 w postaci $2^e k$
2.Dla i od 1 do wybranego t wykonaj:
2.1 Wylosuj $a \in <2;n-2>$
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

4 Test Solovaya-Strassena

Jest to probablistyczny test oparty na badaniach Robert M. Solovay’a i Volkera Strassen’a. Test ten określa, czy dana liczba jest złożona, czy pseudopierwsza. Złożoność czasowa algorymu to $O(klog^3n)$. Prawdopodobieństwo błędu to $2^{-k}$. Jeśłi założymy, że k jest odpowiednio duże np. 100, to prawdopodobieństwo błędu jest nikłe. \newpage

Pseudokod

Dane Wejściowe: Liczba $n \in N $
Dane Wyjściowe: Odpowiedz na pytanie – Czy liczba jest złożona?

1.Dla i od 1 do wybranego t wykonaj:
1.1 Wylosuj $a \in <2;n-2>$
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

4.1 Symbol Jacobiego

Symbol Jacobiego jest uogólnieniem symoblu Legendre’a – $(\frac{a}{n})$ – dla przypadku, kiedy $n$ jest liczbą nieparzystą niekoniecznie pierwszą.

Własności symbolu Jacobiego:

1 .$(\frac{1}{n}) = 1$
2. $(\frac{a}{n}) = (\frac{a(modn)}{n})$
3. $(\frac{ab}{n}) = (\frac{a}{n})(\frac{b}{n})$
4. $(\frac{a}{mn}) = (\frac{a}{m})(\frac{a}{n})$
5. $(\frac{-1}{n}) = {(-1)}^{(n-1)/2}$
6. $(\frac{2}{n}) = {-1}^{({n}^{2}-1)/8}$
Uogólnienie prawa wzajemności reszt kwadratowych:

7. $(\frac{m}{n}) =(\frac{n}{m}){(-1)}^{(m-1)(n-1)/4}$
Symbol Jacobiego dla liczby nieparzystej złożonej, której rozkład na czynniki pierwsze wygląda następująco:
$n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdot\cdot\cdot{p_n}^{\alpha_n}$, możemy przedstawić jako:
$(\frac{a}{n})={(\frac{a}{p_1})}^{\alpha_1}{(\frac{a}{p_2})}^{\alpha_2}\cdot\cdot\cdot{(\frac{a}{p_n})}^{\alpha_n}$

Tak jak dla symobolu Legendre’a:

  • Jeżeli $(\frac{a}{n}) = -1$, to $a$ jest nieresztą kwadratową modulo $n$.
  • Jeżeli $(\frac{a}{n}) = 0$, to $a$ i $n$ nie są względnie pierwsze.

W odróżnieniu do symbolu Legendre’a:
Jeżeli $(\frac{a}{n}) = 1$, to $a$ może(ale nie musi) być resztą kwadratową modulo $n$.
Jeżeli natomiast $a$ jest resztą kwadratową modulo $n$, to $(\frac{a}{n}) = 1$.

5 Algorytm AKS

AKS jest to deterministyczny test pierwszości zaprezentowany przez trzech hinduskich matematyków Manindra Agrawal, Neeraj Kayal i Nitin Saxena. Jest to pierwszy taki test czyli test dający jednoznaczną odpowiedż czy n jest pierwsza. Opiera się on na równości, która jest prawdziwa gdy n należy do zbioru liczb pierwszych $(x-a)^n=(x^n-a)(modn)$. Aby zmniejszyć złożonosc testu przekształacamy naszą rónowśc do postaci : $(x-a)^n=(x^n-a)(modn,x^r-1)$

Pseudokod

Dane Wejściowe: Liczba $n \in N $
Dane Wyjściowe: n- pierwsza albo n – złożona

1.1 Jeżeli $n=a^b$ Zwróć: ZŁOŻONA
2 Dla r=2 do $r<n$ wykonaj:
2.1 Jeżeli r dzieli n Zwróć: ZŁOŻONA
2.2 Jeżeli r jest pierwsza wykonaj:
2.2.1 Dla i=1 do $i=4log(n)^2$
2.2.2 Jeżeli $n^i(mod r)=1$ przerwij
2.3 r=r+1
3. Jeżeli r=n Zwróć: PIERWSZA
4. Dla a=1 do $2rlog(n)$ wykonaj:
4.1 Dla $x \in Zn[x]$ jeżeli $(x+a)^n(mod (x^r-1))\neq x^{n(modr)}+a$ Zwróć: ZŁOŻONA
5. Zwróć: PIERWSZA

6 Analiza wyników

Powyższy wykres przedstawia dokładność testu SS, przy czym wartości oznaczone pomarańczową krzywą są wygenerowane dla prawdopodobieństwa 0,5, zaś niebieską 0,14. Można zauważyć znaczącą różnicę poprawności między nimi – im mniejsze prawdopodobieństwo poprawności, tym, oczywiście, mniejsza jest sama poprawność.

Tym razem przyjrzyjmy się wykresowi z czasem wykonywania algorytmu AKS. W odróżnieniu od Rabina Millera widać wyraźną zależność między czasem, a wielkością sprawdzanej liczby – w miarę zwiększania wartości badanej zmiennej zwiększa się również czas algorytmu.

Spójrzmy na czas wykonywania testu Rabina Millera dla liczb z zakresu od 1 do 95400. Nie widać zależności między czasem wykonywania, a wielkością liczb, można więc uznać, że czas wykonywania jest przypadkowy.


Powyższe wykresy przedstawiają procentową dokładność algorytmu Rabina Millera z liczbą obrotów kolejno 2, 7 i 50. Można zauważyć, że poprawność między dwoma, a siedmioma obrotami zwiększyła się, ale między 7 a 50 jest już porównywalna.

 

Źródło: Obraz wyróżniający: freeimages.com 

Wykresy oraz pseudokody opracowanie własne

Leave a Comment

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

Cancel reply

Inne artykuły