Długo nie zaglądałem na niektóre strony matematyczne. Kiedy spróbowałem tam dotrzeć, nie były mi proponowane w DuckDuckGo (odpowiednik google z interfejsem łatwo modyfikowanym na ciemny). Wyrzuciło mnie z tej bańki generowanej jako proponowane podpowiedzi przeglądarek.
Potrzebowałem wpisać wiecej informacji, że strona była na Poznańskim Portalu Matematycznym uniwersytetu, by ponownie ją znaleźć.
A jest tam wyprowadzony bardzo ciekawy test pierwszości liczb związany z systemem Fibonaciego i dziesiątkowym. Pozwolę sobie go tu powtórzyć:
Ciąg Fibonacciego jako test pierwszości
Jeśi p jest liczbą, obliczamy p-tę liczbę Fibonacciego jako F_{p}. Liczba złożona p nie spełnia poniższych warunków:
Jeśli p ma resztę plus minus 1 modulo 5, F_{p} przystaje do 1 oraz F_{p+1} przystaje do 1 modulo p, to jest możliwe, że liczba p jest pierwsza;
jeśli p ma resztę plus minus 2 modulo 5, F_{p}+1 przystaje do 0 modulo p oraz p dzieli F_{p+1}, to jest możliwe, że p jest pierwsza.
Wynika to z implikacji:
jeśli liczba p jest pierwsza, to spełniony jest zawsze jeden z trzech warunków:
p jest piątką p=5;
p jest dzielnikiem F_{p-1} oraz F_{p}-1;
p jest dzielnikiem F_{p}+1 oraz F_{p+1}
Przypominam z logiki - odwracanie kolejności w implikacji nie zawsze jest prawdziwe. Warunki te zależą od cyfry jedności systemu dziesiątkowego. Niestety, liczby F_{p} są gigantyczne dla większych p... Można je jednak stosunkowo łatwo wyznaczyć, gdyż liczby Fibonacciego wyznacza się jako modułowe iloczyny macierzy. Na wspomnianej stronie są szczegóły.
By wejść bliżej do bańki z fachowymi rezultatami, zajrzałem na stronę wielomianowego deteministycznego testu pierwszości AKS
aks [dot] bluhost [dot] pl
przejrzałem i nieco mnie zaskoczył opis implementacji. Nie chodzi o to, że algorytm nazywa się wielomianowym, ale tam występuje znajdowanie rzędu elementu w grupie multiplikatywnej. Zaś odwrócenia niektórych sit mają dokładnie tę samą liczność operacji, bo poszukują najmniejszego rzędu, ale w analogicznej grupie addytywnej. Dlaczego zatem dociera do mnie informacja, że 'nie ma wielomianowego algorytmu rozkładu liczb na czynniki'? W literaturze podaje się ich złożoność jako zależną od bardzo dużej stałej, właśnie rzędu czynnika. A dokładnie to samo występuje przy wyznaczaniu stałej r w teście pierwszości AKS. Czyli jak dla mnie: wyznaczam odległość od czynnika niby niezależnie od rozkładanej liczby, a potem wykorzystuję go, by dowieść, że jest najmniejszy. Zapominam dokonanych obliczeń, by dowieść czegoś słabszego. A finalnie mam ogólną złożoność lepszą niż dla złożoność fragmentu wewnętrznego. Coś mi tu nie gra.
Wnioskuję, że te sita przegrywają z testem pierwszości, gdy mam bardzo duże wartości. A przekształcenia, które stosuję właśnie w tym obszarze są ignorowane, bo trudno jest zauważyć niesamowitą kompresję im towarzyszącą. Doświadczenia z małych wartości przenoszone są poza swój zakres występowania. Tak jak prawo Hooka, które działa tylko w stosunkowo wąskim zakresie, ktoś usiłuje stosować dla wszystkich przypadków.
Dodatkowo zauważam jeszcze jedną własność przyspieszajacą obliczenia w tych przedziałach, gdzie mój zapis korzysta z iloczynu dwu liczb dwucyfrowych, w których cyfry 'jedności' są znacznie większe niż 'cyfry dziesiątek'. Nie muszę obliczać za każdym razem tego iloczynu, bo mogę korzystać z wartości wyznaczonej iterację wcześniej, wtedy mnożenie dużych ;jedności' jest zastępowane stałym iloczynem znacznie mniejszych 'dziesiątek' oraz kombinacją liniową, która przedziałami maleje ze wzrostem podstawy systemów.
