TAJEMNICA LICZB (4)

MM&AlK

Liczby Mersenne’a jak już wspominaliśmy mają postać M_n = 2ⁿ – 1, gdzie n >1 jest liczbą naturalną. Jeżeli liczba Mersenne’a jest liczbą pierwszą, to jej wskaźnik potęgowy musi być liczbą pierwszą. Tak więc liczby pierwsze Mersenne’a są ściśle związane z małym twierdzeniem Fermata i wnioskiem z tego twierdzenia mówiącym, że dla liczb pierwszych nieparzystych p mamy:

p| 2^{p – 1} – 1.

Małe twierdzenie Fermata mówiące, że jeżeli liczba całkowita D jest niepodzielna przez liczbę pierwszą p, to

D^{p – 1} ≡ (mod p)

stanowi jeden z podstawowych fundamentów algorytmów szyfrujących RSA…

Dla potrzeb kryptografii niezbędne są duże liczby pierwsze. Duże liczmy Mersenne’a znajduje się wykorzystując test pierwszości Lucasa-Lehmer'a. Test pierwszości Milera-Rabina służy do znajdowania dużych liczb pierwszych postaci

2^mb  + 1, gdzie liczby naturalne b, m są liczbami nieparzystymi.

Kryptografia, to zajęcie dla fachowców… Wracam zatem do ciekawych własności liczb pierwszych…

1. Jeżeli liczba N – 1 = p, to liczba p|Nⁿ – 1, gdzie n jest liczbą naturalną nieparzystą.

Jest więc: p|(p  + 1)ⁿ – 1. Liczba p jest dzielnikiem liczby (p  + 1)ⁿ – 1. Np.

3|4ⁿ – 1,   5|6ⁿ – 1,   7|8ⁿ – 1,   11|12ⁿ – 1,   13|14ⁿ – 1,   17|18ⁿ – 1…

2. Jeżeli liczba N + 1 = 2p, gdzie p jest liczbą pierwszą p > 3, natomiast n jest liczbą naturalną nieparzystą, to liczba p jest dzielnikiem liczby (2p – 1)ⁿ + 1.

p|Nⁿ + 1 stąd: p|(2p  – 1)ⁿ + 1. Np. 

5|9ⁿ + 1,   7|13ⁿ + 1,    11|21ⁿ + 1,    13|25ⁿ + 1,    17|33ⁿ + 1,    19|37ⁿ + 1, …

Ciekawe są własności liczby 3… 

1. Każda liczba naturalna nieparzysta postaci N = 2ⁿ + 1, gdzie n jest liczbą nieparzystą n = 2k + 1, (k liczba naturalna), dzieli się przez 3. Jest więc:   3|2^{2k + 1} + 1 

Dowód jest bardzo prosty ale trochę „figlarny”…

2. Jeżeli wykładnik potęgowy n jest wielokrotnością liczby 3, a więc: n = 3m, wówczas: 

N = 2^3m + 1 = (2^m + 1)  x  [2^m(2^m – 1) + 1].

Ten przykład pokazałem już wcześniej przy prezentacji rozkładu dużej liczby na czynniki pierwsze.

3. Jeżeli liczba pierwsza p przy dzieleniu przez liczbę 3 daje resztę 2, to liczba 3 jest dzielnikiem liczby pⁿ + 1, gdzie n jest liczbą nieparzystą.

3|pⁿ +  1.

Są to liczby pierwsze takie jak: 5,11,17,23,29,41,47,…

3|5ⁿ + 1,   3|11ⁿ + 1,  3|17ⁿ + 1,   3|23ⁿ + 1,   3|29ⁿ + 1,  3|41ⁿ + 1,   3|47ⁿ + 1, ….

4. Jeżeli n = 3^tk, gdzie k jest liczbą naturalną nieparzystą, wówczas liczba N = 2ⁿ  + 1  dzieli się przez 3^t.

3^t|2ⁿ + 1

Ciekawie to wygląda, gdy k  = 1 stąd n = 3^t np. przyjmując kolejno t  = 1,2,3,4,5,6,7,8,… otrzymujemy: 

t = 1;   n = 3¹ = 3 stąd: 3|2³ + 1

t = 2;   n = 3² = 9 stąd 9|2⁹ + 1

t = 3 ;  n = 3³ = 27 stąd 27|2²⁷ + 1

t = 4;  n = 3⁴ = 81 stąd 81|2⁸¹ + 1

t = 5;  n = 3⁵ = 243 stąd 243|2²⁴³ + 1

t = 6;  n = 3⁶ = 729 stąd 729|2⁷²⁹ + 1

t = 7;  n = 3⁷ = 2187 stąd 2187|2²¹⁸⁷ + 1

t = 8;  n = 3⁸ = 6561 stąd 6561|2⁶⁵⁶¹ + 1

t = 9;  n = 3⁹ = 19683 stąd 19683|2¹⁹⁶⁸³ + 1

t = 10;  n = 3¹⁰ = 59049 stąd 59049|2⁵⁹⁰⁴⁹ + 1

           n = 3^t stąd 3^t|₂3^t + 1

Również dla liczb postaci 2ⁿb  + 1 gdzie n, b są liczbami nieparzystymi możemy szukać dzielników np.

Jeżeli liczba b jest liczbą postaci b = 6k  + 7, gdzie k = 0,1,2,3,4,5,6,7,8…

to 3|2ⁿb  +  1…

Tak więc liczba b nie może przyjmować wartości: 7,13,19,25,31,37,43,...

Moja rada dla kryptografów… Dla kluczy publicznych, będących iloczynem dwu liczb pierwszych, nie należy stosować liczb Mersenne’a. Stosowanie takich liczb przyspiesza procesy szyfrowania (liczba 2^p w zapisie dwójkowym, to liczba jeden z ciągiem p zer, liczba 2^p – 1, to ciąg jedynek) ale klucz publiczny jest podatny na złamanie bez względu na długość klucza (nie ma znaczenia czy klucz ma dwieście, siedemset, tysiąc, czy też więcej cyfr...).

Trudniejsze do złamania są klucze publiczne utworzone przez iloczyny liczb pierwszych postaci 2ⁿb  + 1. Przy tego typu kluczach publicznych należy zwracać szczególną uwagę na generatory liczb losowych – ale nie tylko…