3 obserwujących
32 notki
13k odsłon
134 odsłony

TAJEMNICA LICZB (4)

Wykop Skomentuj2

MM&AlK

Liczby Mersenne’a jak już wspominaliśmy mają postać Mn = 2n – 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| 2p – 1 – 1.

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

Dp – 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

2mb  + 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|Nn – 1, gdzie n jest liczbą naturalną nieparzystą.

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

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

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

p|Nn + 1 stąd: p|(2 – 1)n + 1. Np. 

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

Ciekawe są własności liczby 3… 

1. Każda liczba naturalna nieparzysta postaci N = 2n + 1, gdzie n jest liczbą nieparzystą n = 2k + 1, (k liczba naturalna), dzieli się przez 3. Jest więc:   3|22k + 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 = 23m + 1 = (2m + 1)  x  [2m(2m – 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 pn + 1, gdzie n jest liczbą nieparzystą.

3|pn +  1.

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

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

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

3t|2n + 1

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

t = 1;   n = 31 = 3 stąd: 3|23 + 1

t = 2;   n = 32 = 9 stąd 9|29 + 1

t = 3 ;  n = 33 = 27 stąd 27|227 + 1

t = 4;  n = 34 = 81 stąd 81|281 + 1

t = 5;  n = 35 = 243 stąd 243|2243 + 1

t = 6;  n = 36 = 729 stąd 729|2729 + 1

t = 7;  n = 37 = 2187 stąd 2187|22187 + 1

t = 8;  n = 38 = 6561 stąd 6561|26561 + 1

t = 9;  n = 39 = 19683 stąd 19683|219683 + 1

t = 10;  n = 310 = 59049 stąd 59049|259049 + 1

           n = 3t stąd 3t|23t + 1

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

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

to 3|2n +  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 2p w zapisie dwójkowym, to liczba jeden z ciągiem p zer, liczba 2p – 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 2nb  + 1. Przy tego typu kluczach publicznych należy zwracać szczególną uwagę na generatory liczb losowych – ale nie tylko…


Wykop Skomentuj2
Ciekawi nas Twoje zdanie! Napisz notkę Zgłoś nadużycie

Więcej na ten temat

Salon24 news

Co o tym sądzisz?

Inne tematy w dziale Technologie