Pierwszość liczby jest funkcją, która zwraca wartość: 'argument jest / nie jest liczbą pierwszą.
Wydaje się idiotyczne, by sprawdzać pierwszość liczby za pomocą, wydawałoby się znacznie gorszego przypadku logarytmów dyskretnych. Przecież do liczenia logarytmów dyskretnych wymagana jest znajomość faktoryzacji liczby, aby obliczenia były prostsze. Nawet przy metodzie liczenia logarytmów dyskretnych publikowanych na tym blogu.
Lecz konstrukcja tworzenia podgrafu nie jest związana ze znajomością liczb pierwszych, i właśnie ta konstrukcja potrafi wskazać dzielniki. Sprawdziłem to między innymi dla liczb będących iloczynami małych liczb pierwszych typu 11*7.
Post może być nieco zagmatwany. Jeszcze nie znam sposobu przedstawienia tematu w sposób 'dla ludzi', zwłaszcza fragmentu eliminowania liczb pierwszych nie będących dzielnikami.
Mamy liczbę n, której dzielniki chcemy znaleźć.
Przygotujmy dwie tablice pomocnicze, w jednej trzymamy liczby pierwsze i niektóre złożone {2, 3, 5, 7, 11, 13, 17, 19, ... }.
Do drugiej będziemy odkładać liczby pierwsze, które na pewno nie są dzielnikami n.
Dobierzmy ziarno a, będzie to pierwsza wartość pierwszej z tablic, np. a=2.
Tworzymy ciąg skończony (m_1, ..., m_i)
m_k = a^k (mod n), k>0
w którym m_i jest jedną z trzech wartości: 0, 1 lub a, zaś i jest pierwszą napotkaną pozycją z jedną z tych wartości. Z małego twierdzenia Fermata i<n.
Licząc wartości m_k, od razu możemy modyfikować tablice pomocnicze: m_k jest liczbą złożoną, wtedy powinniśmy je zfaktoryzować. Ewentualnie sprawdzić podzielność przez a oraz liczby pierwsze występujące w drugiej z tablic. Jeśli wśród dzielników m_k nie ma a, przenosimy je do drugiej tablicy pomocniczej. Z pierwszej tablicy kasujemy a i wszystkie jego wielokrotności.
Dzieląc m_k przez liczby pierwsze drugiej tablicy możemy natrafić na kolejną liczbę pierwszą, ta na pewno nie jest dzielnikiem. Robimy z nią tak samo jak z a. Przenosimy ją do drugiej tablicy usuwając jej wielokrotnosci z pierwszej. Czasem się zdarza, że m_k jest złożona i nie widzimy jej dzielnika. Wtedy czeka na inne m_j takie, że nwd(m_k, m_j) jest pierwsza i robimy znów to samo co przy a.
Jest to najgorszy fragment, który należy dopracować. Przy czym przeliczenia pomocnicze wystarczy robić tylko przy spełnionym warunku m_{k-1}*a>m_k.
Odczyt wyniku, gdy już wyznaczymy długość ciągu i. Mamy przypadki:
m_i = 0 oznacza, że a było dzielnikiem, zaś n jest potęgą a (a jest pierwsza);
m_i = a oraz dla każdego k=1..i a| m_k. Wtedy a jest dzielnikiem n
wreszcie m_i = 1 oraz i= n-1 lub i = (n-1)/2 oznacza, że n jest liczbą pierwszą.
W pozostałych przypadkach reszta z dzielenia n przez i jest związana z dzielnikiem. Czasem jest to dzielnik, jak w przypadku 91, gdyż długość ciągu dla a=2 jest i=12 oraz 91 = 7*12+7. W tym przypadku mamy nawet gotowy rozkład.
Dla n=81 a=2 uzyskujemy ciąg zawierajacy 54 elementy, do drugiej tablicy zostały przeniesione liczby pierwsze oprócz 3, zatem 3 jest dzielnikiem, zaś 81-54 = 27.
Dla n=77 a=2 ciąg ma 31 elementów, w którym wśród m_k pojawiają się 2, 25, 9, 29 i inne liczby pierwsze inne niż 7 czy 11. Mamy 77 = 2*31+15, oraz suma długości pozostałych ciągów generowanych przez a=7 oraz a=11 sumuje się do 15. Przykładowo ciąg wyznaczony przez a=11 ma postać [11, 44, 22, 11].
Jeśli mamy dzielnik, to długość ciągu go wyznaczająca bywa drugim z dzielników. Tu dla n=77 długość ciągu wyznaczonego przez 7 jest 11.
Policzmy konkretny przykład n=91,
a=2
k m_k dzielniki do odstawienia
1 2
2 4
3 8
4 16
5 32
6 64
7 37 2, 37
8 74
9 57 złożona 57=3*19, nie widać dzielników, mogą się jeszcze pojawić
10 23 23
11 46
12 1 wyznaczone i=k = 12
szacujemy n/i otrzymując 91 = 7*12 + 7, zauważamy rozkład 91 = 7*13.
Bez zauważenia, stosujemy kolejne ziarno a=3, domyślamy się, że dzielnik jest nie większy od uzyskanej reszty 7.
