Przedstawiony tu algorytm postępowania opiera się na ciągach Dirichleta. Jednakże pewne elementy wynikają z mojej własnej metody, którą nazwałem rzeszotem. Ponieważ nie wszystkie kroki będę uzasadniał szczegółowo, to dla rozwiania ewentualnych niejasności – dodatkowych wyjaśnień należy szukać przy opisie całej metody, bowiem poniższe – stanowi jedynie jej wyrywek, przeznaczony dla konkretnych zastosowań.. .
Autor
Szybkie znajdywanie liczb pierwszych,
dużych, oraz bardzo dużych
metodą izolowanych ścieżek rzeszota
Dla tych, którzy szukają gotowego narzędzia, do pobrania jest ð excelowski arkusz, realizujący metodę izolowanych ścieżek w bardzo uproszczonej implementacji. Za jego pomocą można błyskawicznie otrzymać każdą liczbę pierwszą – od małych, do wielocyfrowych. Jednak w oferowanym tu, prymitywnym wydaniu – jako arkusz kalkulacyjny – wielkość otrzymywanych liczb jest ograniczona długością (precyzją) używanych przez Excel zmiennych.
Dla otrzymywania liczb znacznie większych można pobrać program ð program „tutor” autorstwa Marcina Krzyżanowskiego. Program ma kilka opcji, pozwalających wyszukiwać liczby pierwsze na kilka sposobów, różnymi metodami, następnie są one sprawdzane skróconym algorytmem (Millera Rabina), odrzucającym większość liczb złożonych.
Można się też posłużyć programem Mathematica, korzystając z pracy, kodu, oraz “recenzji” Rzeszota, wykonanych przez ð Takamurę. Niestety, już niedostępna! Recenzja nie była zbyt pochlebna...
I – Wprowadzenie: ciągi arytmetyczne Dirichleta
W 1837 roku Dirichlet podał analityczny dowód hipotezy postawionej w roku 1788 przez znanego matematyka francuskiego A. M. Legendre'a;
TWIERDZENIE. Jeżeli d ≥ 2 i a ≠ 0 są względnie pierwszymi liczbami całkowitymi, to ciąg arytmetyczny:
a, a + d, a + 2d, a + 3d, ... zawiera nieskończenie wiele liczb pierwszych.
WA * B
Najprostszym takim ciągiem posługujemy się dość często:
Wzór 1 : an= 1+n*2 - przedstawia ciąg liczb nieparzystych. Jeśli jednak byśmy chcieli w podobny sposób zapisać ciąg liczb niepodzielnych przez 3, to musimy zauważyć, iż mamy już do czynienie z dwiema możliwymi kongruencjami, a więc musimy obserwować dwa, różne ciągi:
Wzór 1,1a: 3bn= 2+n*3 oraz Wzór 1,1b: 3bn= 1+n*3
Lecz powyższych wzorów używać nie będziemy, bowiem dla dalszych naszych potrzeb wygodniej będzie posługiwać się ciągami następującymi:
Wzór 2.2: 5bn= 5+n*(2*3) oraz 7bn= 7+n*(2*3) - Wzór 2.1
- które generują liczby niepodzielne zarówno przez 2, jak i przez 3.
Możliwość 1-sza: zamiast posługiwać się przedstawioną poniżej, metodą izolowanych ścieżek, można pójść na skróty, i do któregoś z powyższych ciągów wstawić po prostu dostatecznie duże n, po czym sprawdzać, czy otrzymana liczna – jest L. pierwszą. Jednak izolowanie daje nam znacznie wyższe prawdopodobieństwo trafienia (choć, niestety, nie sięga ono 100% – bowiem część wskazań – to liczby złożone).
II – Elementy składowe metody – nazewnictwo.
Spójrzmy ponownie na Wzór 2.2: 5bn= 5+n*(2*3) - na potrzeby odpowiedniego opisu użytkowego, głównym elementom składowym metody nadamy specyficzne nazwy:
Iloczyn, zamknięty powyżej w nawiasie nazywać będziemy dominiką. Zawiera on liczby pierwsze, odpowiedzialne za generowanie następnych, kolejnych wyrazów danego ciągu. Natomiast konkretną wartość przyjętą dla n, określać będziemy tu jako faktor.
Odźwierna. Występujący na pierwszym miejscu każdego takiego wyrażenia czynnik stały (w powyższych wzorach 2,2 oraz 2,1 są to, odpowiednio, liczby: 5, oraz 7) nazwałem odźwierną, jako że właśnie owa wartość „wprowadza” pozostałe L. pierwsze każdego ciągu…
II – „Wybieranie” faktora.
Podstawowym parametrem w przedstawionym algorytmie będzie wielkość faktora n, i manipulując ową wielkością będziemy mogli otrzymywać różne wartości końcowe: dowolną liczbę pierwszą. Ze specyfiki rzeszota wynika, iż wielkość n (faktora), będąca liczbą naturalną, ma się zawierać w przedziale jednostronnie domkniętym < 1 ; odźwierna). Bez powiązania z celem, dla którego użytkownik poszukiwać będzie dużych liczb pierwszych – trudno z góry określić, jakie byłyby preferencje przy rozwijaniu kolejnych szeregów. Dlatego, na użytek prezentowanych przykładów przyjmujemy, że zamiast losować kolejne faktory (czynność narzucająca się, gdybyśmy np. chcieli, przez izolowanie, otrzymać liczbę mającą stanowić podstawę klucza kryptograficznego), będziemy tu, dla „wylosowania” faktora, zastępczo używać każdorazowo mnożnika 2/3 (razy aktualna odźwierną) – oraz zaokrąglać wynik zawsze w górę. Jednak w dalszym opisie będzie mowa o „wybieraniu faktora” – bez wnikania w kryteria takiego „wyboru”, bowiem są już one wobec przedstawianej metody – czymś zewnętrznym.
III – Postępowanie.
Dwie, najmniejsze liczby pierwsze to 2 i 3 – umieszczamy je w równaniu wyjściowym:
b = 3 + n * (1*2) = 7 - gdy za n wstawiliśmy („wylosowaną”) liczbę 2...
Kolejne kroki: A) wybieramy faktor B) wstawiamy do równania, i obliczamy wynik
7bn= 7 + 5 *(2*3) = 37 C) otrzymany wynik stanowi teraz kolejną, nową odźwierną, natomiast odźwierną dotychczasową (w tym przypadku: liczbę 7) – włączamy w skład dominiki: 37bn= 37 + 25 *(2*3*7) = 1087 - następnie kroki A, B, C, powtarzamy tak długo, aż otrzymamy jako wynik liczbę, której wielkość nas zadowala. W zasadzie powyższy opis wyczerpuje całość metody. Kto już chwycił zasadę – może na tym poprzestać. To co poniżej – to już tylko komentarze...
Odpowiednie równanie można też przedstawić następująco:
b n= odźwierna n + faktor * (dominika n ) zaś w następnym kroku będziemy mieli odwołanie rekurencyjne:
bn+1= b n + faktor 2 * (dominika n * odźwierna n ) gdzie jakiś-tam faktor wybieramy ponownie (dowolnie). Zauważmy, że:
dominika n+1 = (dominika n * odźwierna n ) zaś w jeszcze następnym będzie, oczywiście:
odźwierna n+2 = bn+1 etc. Jeśli zapamiętamy jedynie ową prostą formułę rekurencyjną, oraz wypiszemy sobie jej wyjściowe równanie, podstawiając za dominikę oraz odźwierną dwie, najmniejsze liczby pierwsze:
iteruj bk= 3 + n * (1*2) = odźwierna k+1 - oraz nie zapomnimy, że faktor n < odźwierna n to niemal tak, jakbyśmy zapamiętali wszystkie liczby pierwsze! - niestety, z pewną domieszką liczb złoconych...
Poniżej, dla zobrazowania szybkości wzrostu – kolejne, tak uzyskane równania:
[ ilość cyfr / generacja ]
[ 7 / 4] bn= 1087 + 725 *(2*3*7*37) = 1 127 737
[13 / 5] bn= 1 127 737 + 751 825 *(2*3*7*37*1087) = 1 269 982 414 087
[25 / 6] bn= 1269982414087 + 846654942725*(2*3*7*37*1087*1127737) =
1 612 853 184 802 073 623 277 437
[48 / 7] bn= 1612853184802073623277437+1075235456534715748851625*
(2*3*7*37*1087*1127737*1269982414087) = 2,6012953957231194094458903140684e+48
Jak widać, w tym ostatnim, z tu przedstawionych kroków, uzyskaliśmy liczbę 48-mio cyfrową (w zapisie dziesiętnym). Należy zauważyć, iż nastąpiło to już w siódmym kroku (czyli: otrzymana liczba powinna być określana jako 7-mej generacji, wskazuje na to 7 liczb tworzących odźwierną). Oczywiście szybkość owego przyrostu zależy od tego, jakie obieramy (każdorazowo!) faktory, jednak dla powyższych przykładów posłużyliśmy się dość umiarkowanym, stałym mnożnikiem 2/3-cie, przy którym każdy kolejny krok powodował bardzo duży wzrost długości otrzymywanej liczby: niemalże podwojenie ilości cyfr. Przy mnożniku bliższym jedności ( stu %-tom odźwiernej ) – wzrost byłby jeszcze szybszy, co można łatwo sprawdzić posługując się dostępnym do ściągnięcia arkuszem kalkulacyjnym w Excelu. Największe przerosty osiągniemy wpisując w komórkę J9 wartość 100 (jednostką są w niej %-ty), natomiast kolumnę L wypełniając wartościami ( -1). Jako pouczające ćwiczenie warto też zobaczyć w nim, jak zmienia się odpowiednia szybkość, kiedy faktor jest najmniejszy (proszę wpisać w kolumnę N same +jedynki).
IV – Otrzymane wartości.
Otrzymane liczby, niestety – nie zawsze są liczbami pierwszymi, jednak odsetek powinien być wysoki. Niezbyt duża (praktycznie: niemal znikoma!) złożoność obliczeniowa powyżej przedstawionej metody – pozwala jednak tak znacząco zwiększyć szybkość znajdywania wielocyfrowych liczb pierwszych (hm, dokładniej: kandydatek), iż dodatkowa konieczność ich weryfikacji – nie wydaje się być zaskakująca. Szczególnie, gdy porównać ją z powszechnie stosowanym obecnie wstępnym typowaniem liczb „po omacku” – czyli całkowicie losowym. Warto jednak zauważyć, iż dzięki użyciu „rzeszota” - omijamy też pewną część liczb pseudopierwszych, w tym najgorsze – Carmichaela, czyli „L. doskonałe pseudopierwsze”... Zobacz ð krótkie omówienie tego tematu.
Do tego, aby sprawdzić, czy otrzymane liczby są pierwsze – jest w sieci wiele różnych metod. W arkuszu umieściłem tablicę liczb pierwszych (do 100 003) i sprawdzana jest prosta podzielność przez nie... Uwaga: przed użyciem, ową tablicę trzeba rozbudować (opis jest w arkuszu).
Jeśli „prime test” wykaże, iż otrzymana liczba pierwszą nie jest – wówczas do faktora dodajemy, lub też odejmujemy kolejne jedynki (uwaga: nie ma żadnej potrzeby dodawać / odejmować więcej niż 1 na raz!), i testujemy następne, tak otrzymane wartości, pamiętając jednak o tym, iż faktor powinien być zawsze mniejszy od aktualnej odźwiernej. Ewentualnie możemy się cofnąć o jeden (lub, jeśli mamy taki kaprys – więcej niż jeden) krok algorytmu, i wówczas zmieniając faktor - wybrać całą, nową gałąź badanych liczb...
V – Uzupełnieniem metody...
... pomocnym do niektórych zastosowań, będzie algorytm (c)raszujący, stanowiący formułę odwrotną, i pozwalający szybko znaleźć dominikę, i odźwierną, oraz ew. odpowiednie współczynniki tworzące (wartości faktora dla kolejnych generacji) w metodzie izolowania - dla każdej liczby pierwszej. Przykładowym jego zastosowaniem może być sprawdzanie, czy pewna liczba – leży na jakichś gałęziach (c)rasz–drzewa, co pozwolić może na szybkie wykluczenie niektórych liczb silnie pseudopierwszych (stwierdzenie, iż są złożone). Oczywiście ma to sens jedynie w stosunku do liczb znalezionych innymi, niż pochodzące od rzeszota metodami – gdyż wszystkie liczby wygenerowane np. przez izolowanie - zawsze dadzą identyczny wynik, bez względu na to, czy będą pierwsze, czy też złocone...
Kontakt: R.B. Szulc
.