MM&AlK
W poprzedniej notce wspominaliśmy, że najtrudniejsze do rozłożenia na czynniki są liczby postaci
A = 2a + 1. Szczególne znaczenie mają w tym przypadku liczby pierwsze Sophie Germain. Liczby Sophie Germain to liczby pierwsze posiadające w swej strukturze liczbę pierwszą, a więc liczby mające postać:
p = 2pn + 1, gdzie p, pn są liczbami pierwszymi.
Jeżeli liczby pierwsze są postaci:
p1 = 2
a + 1,
p2 = 2
b + 1, gdzie
a,
b są liczbami złożonymi
i (
a,
b) ≠ 1, to iloczyn takich liczb pierwszych jest znaczne łatwiej rozłożyć na czynniki.
Jest bowiem bardzo często tak, że liczby
a,
b tworzące strukturę liczb pierwszych
p1 i
p2 mają wspólny dzielnik. Związane jest to z faktem, że co trzecia liczba w zbiorze liczb naturalnych dzieli się przez liczby będące wielokrotnością innych liczb pierwszych lub ich potęg. Tak więc istnieje wiele liczb pierwszych, w których liczby
a,
b posiadają wspólny dzielnik będący wielokrotnością liczby pierwszej lub będący potęgą liczby pierwszej (3, 5, 7, 11, ...) np.
7 = 2 x 3 + 1, 13 = 2 x 6 + 1, 31 = 2 x 15 + 1, 37 = 2 x 18 + 1, …
19 = 2 x 32 + 1, 109 = 4 x 33 + 1, 487 = 2 x 35 + 1, …
21 = 2 x 10 + 1, 31 = 2 x 15 + 1, 41 = 2 x 20 + 1, 61 = 2 x 30 + 1, ...
251 = 2 x 53 + 1, 501 = 4 x 56 + 1, ...
29 = 2 x 14 + 1, 71 = 2 x 35 + 1, 113 = 2 x 56 + 1, ... 1 373 = 4 x 73 + 1, ...
23 = 2 x 11 + 1, 67 = 2 x 33 + 1, 89 = 2 x 44 + 1, 199 = 2 x 99 + 1, ...
2 663 = 12 x 113 + 1, ...
53 = 2 x 26 + 1, 79 = 2 x 39 + 1, 131 = 2 x 65 + 1, 157 = 2 x 78 + 1, ...
Problem rozkładu liczb naturalnych na dwa czynniki, to problem od początków kształtowania się teorii liczb. P. Fermat podał następujący sposób znajdowania dla każdej liczby naturalnej nieparzystej n najmniejszej liczby naturalnej a, takiej iż a jest dzielnikiem n , n = ab i a ≥ b. Wyznaczamy największą liczbę naturalną r, taką iż r2 < n i przyjmujemy d = n – r2. Do – d dodajemy kolejno liczby 2r + 1, 2r + 3, 2r + 5, 2r + 7, …, 2r + 2k – 1, aż otrzymamy kwadrat liczby całkowitej nieujemnej q2; wówczas a = k + r + q będzie najmniejszą liczbą naturalną a taką, iż a będzie dzielnikiem n, n = ab i a ≥ b (W. Sierpiński, Teoria liczb cz. II str. 341). Metoda Fermata, znajdowania dwu czynników liczby naturalnej złożonej, wykorzystywana jest w metodzie sita kwadratowego stosowanej w kryptologii. Metoda Fermata jest ściśle związana z funkcją kwadratową…
Przyjrzyjmy się czynnikom liczby nieparzystej złożonej N...
N = A × B = A(A + 2k), gdzie k jest liczbą naturalną, B > A.
Jest zatem: A
2 + 2kA – N = 0.
Rozwiązujemy równanie kwadratowe względem A. Jest więc:
∆ = 4k2 + 4N = 4(k2 + N) = 4d; ∆1/2 = 2(k2 + N)1/2 = 2d1/2;
Pierwiastek z delty musi być liczbą naturalną... Traktując
k chwilowo jak liczbę zmienną, szukamy takiej liczby
k, dla której pierwiastek z delty jest liczbą naturalną… Pierwiastek równania czyli liczba A wynosi:
A = (∆1/2 – 2k)/2 = (k2 + N)1/2 – k = d1/2 – k.
Wobec B = A + 2k otrzymujemy: B = (k
2 + N)
1/2 + k = d
1/2 + k.
Jest zatem: N = A × B = (d
1/2 – k)(d
1/2 + k) = d – k
2 = (k
2 + N) – k
2 = N.
Rozwiązaniem jest: B = d
1/2 + k, A = d
1/2 – k.
Inne ciekawe przekształcenie…
Po dodaniu obustronnie liczby k2 do równania N = A × B = A(A + 2k), gdzie k jest liczbą naturalną,
B > A, otrzymujemy:
N + k2 = A2 + 2Ak + k2; stąd: N + k2 = (A + k)2; N + k2 = d2.
Tak więc szukamy takiej liczby k
x dla której pierwiastek z liczby N + k
x2 jest liczba naturalną:
(N + kx2)1/2 = d.
Pewną odmianą metody Fermata i funkcji kwadratowej jest metoda wynikająca z hipotezy Goldbacha mówiącej, że każda liczba parzysta jest sumą dwóch liczb pierwszych. Jest wówczas:
2n = p1 + p2, gdzie p1 = (n + m), p2 = (n – m).
Dla iloczynu liczb mamy: N = p
1 x p
2 = (n + m)(n – m) = n
2 – m
2; stąd: n
2 – N = m
2. Traktując
n jak zmienną, szukamy takiej liczby
nx dla której pierwiastek z różnicy n
x2– N jest liczbą naturalną m. Jest wówczas:
(nx2 – N)1/2 = m. Ostatecznie znajdujemy: p1 = (nx + m), p2 = (nx – m).
Bardzo ciekawie wygląda jeszcze inne przekształcenie:
N = A × B stąd: (N – A)/A = B – 1.
Jeżeli liczby pierwsze p
1, p
2 w swej strukturze mają wspólny dzielnik: p
1 = 2ad + 1 ; p
2 = 2bd + 1, gdzie a,b d, to liczby naturalne, wówczas otrzymujemy: (N – p
1)/(2dp
1) = b.
Przykład:
Dana jest liczba N = 10 362 031 rozłożyć liczbę N na dwa czynniki. Poszukujemy wspólnego dzielnika d.
W tym celu od Liczby N odejmujemy 1 i szukamy potęg liczb pierwszych przez która dzieli się liczba (N – 1). Liczba (N – 1) ma dzielniki: 2, 3, 5,
73, 19, 53. Nas interesuje liczba 7
3 = d. Przyjmujemy:
p
1 = 2 x
73a
x + 1. Jest więc: [10 362 031 – (2 x
73a
x + 1)]/[ 2 x
73 x (2 x
73a
x + 1)] = b. Przyjmując za a
x kolejne liczby naturalne szukamy takiej wartości a
x, dla której b jest liczbą naturalną. Możemy takie działania wykonać na arkuszu kalkulacyjnym lub napisać programik komputerowy. Bardzo szybko znajdziemy rozwiązanie, bowiem dla
ax = 2 otrzymujemy:
10 362 031 – (2 x
73 x
2 + 1)]/[ 2 x
73 x (2 x
73 x
2 + 1)] = 11.
Zatem liczby pierwsze p1, p2 to:
p1 = 4 x 73 + 1 = 1373; p2 = 2 x 73 x 11 + 1 = 7547.
W notkach Szyfry (1), (2), (3) pokazaliśmy jak głęboko sięga ingerencja programistów i urzędów certyfikujących w kształt kluczy publicznych. Czynnik ludzki w procesie szyfrowania oraz firmy certyfikujące, to najsłabsze ogniwo… To dlatego rząd USA zabronił stosowania, w administracji państwowej, algorytmu RSA.
(w oparciu o ebook Zabawy z Pitagorasem, Fermatem i Goldbachem)
