25 stycznia 2022

Herystyki przyspieszające rozkład liczby w przeglądzie zupełnym

 Mimo aktualnych trudności (remont + wykluczenie) nabieram doświadczenia oglądając przebieg sita, które w jednej iteracji początkowej nie sprawdza statystycznie ułamka liczby pierwszej (liczba pierwsza pojawia się dopiero po pokonaniu dystansu do kolejnej), lecz na iterację napotykam kilka liczb pierwszych, z których część często nie jestem w stanie od razu rozpoznać (iloczyn kilku zbyt dużych liczb pierwszych nie jest odróżnialny od liczby pierwszej). To się zmienia, gdy daną liczbę pierwszą spotkam ponownie. 

Ale przebieg sita nasuwa mi przyspieszacze: np. istnieje przedział, w którym można przeskakiwać część iteracji (budowa liczby [1,b,c]_p, gdzie (p-1) jest bliskie (1+b+c) sugeruje kolejną podejrzaną o dzielnik pozycję przez przesunięcie o iloraz p/(b-1) ). W ten sposób sprawdzałem wręcz pierwszość liczb rzędu pięciu milionów, gdy największą wychwytywaną w danej iteracji była liczba rzędu 3-4 milionów (kwadrat dystansu zbliżał się do 2000). 

Teraz zmodyfikowałem wyrażenie sita, co jeszcze przyspieszyło obliczenia. Przesunąłem się na zakres nieco ponad pierwiastek kwadratowy z liczby rozkładanej

N = [a, b] _ p, a bliskie sqrt N

gdzie a*p+b = N, a maleje o 1 do połowy swej początkowej wartości, p rośnie (na ogół też o 1), b tworzy wykres piłokształtny przedziałami rosnący. Sito Eraostenesa stosuję do cyfry 'dziesiątek' a, ignorując złożoność jej dzielników (dystans będący licznikiem iteracji i tak wskaże pośrednio dzielniki). 


A teraz kolejna herurystyka, która zapowiada się interesująco. Najpierw przebieg teoretyczny: 

Bierzemy iloczyn dwu liczb nieparzystych b*d, który jest bliski liczby rozkładanej N: 

b*d - N + r = 0,  b >= d

Wartość d zapisuję we wszystkich dostępnych kolejnych systemach liczbowych o cyfrze 'dziesiątek' 1: d = [1,e]_(2*p). Sprawdzam czy  (2*p+1) dzieli r+(e-1)*b. 

Przejście na sąsiedni system: e-=2; p+=2; dla podzielności wystarczy zmodyfikować wartość o stałą 2b. Największe możliwe e to połowa (d-1)/2, gdyż z założenia b i d są nieparzyste. 

Jeśli mamy podzielność, 2*p+1 jest dzielnikiem, drugi uzyskamy w bardziej skomplikowany sposób, z sumy b oraz równomiernie rozlokowanej na pozycje wartości r+(e-1)*b. Po to nam była potrzebna podzielność!


Dlaczego to działa? 

Konwersje są niezmiennicze względem wartości liczbowych. Jeśli jeden czynnik traktujemy jako stały (b), a drugi d podlega konwersjom, mamy do czynienia z wyrażeniem [1*b, e*b] _ (2*p). Tu uwzględniana jest nieparzystość bardzo dużego b oraz fakt, że d zostało dobrane jako większe niż szukany dzielnik. Każdą liczbę można sprowadzić do postaci [1, e]_p wykorzystując wielokrotnie zwiększanie systemu o 1 oraz jego podwajanie. Nie wiemy jak to zrobić bez konkretnych wartości, dlatego potrzebujemy przeglądu. 

Liczba [1, 1]_ (2*p) jest podzielna przez 2*p+1, bo jest to inny zapis 1*(2*p)+1. Zabieramy nadmiar z pozycji jedności (tu (e-1)*b) oraz w sumie z r sprawdzamy, czy uda się to rozprowadzić na wszystkich pozycjach.  

Kiedy r nie jest ujemne, lecz dodatnie, znaleziona podzielność w przypadku testowym znalazła się tuż poza 'poprawnym' zapisem pozycyjnym liczby. Przy ujemnym podobnie. Ale i odległość między dzielnikami była spora.  


Przykład liczbowy, dla liczb pierwszych i niektórych złożonych nie znajdujemy podzielności: 

253 = 17 * 15 - 2

Zapisujemy 15 = [1, 7]_8 = [1, 5]_10 = [1, 3]_12 = [1, 1]_14 . 

Sprawdzamy kolejno odpowienie podzielności:
-2+(7-1)*17 = 100 = 9*(8+1)+1,
-2+(5-1)*17 = 100-34 = 66 = 6*(10+1)+0 dzielnik 11
-2+(3-1)*17 = 66-34 = 32 = 2*(12+1)+6
-2+(1-1)*17 = -2 = 0*(14+1)-2

Liczba złożona o dzielniku 11, drugim jest 17+66/11 = 23. 


259 = 17 * 15 + 4 = 17 * 17  - 30

Po rozpisaniu (jak wyżej) w pierwszej wersji potrzebowalibyśmy [1, 9]_6 do znalezienia dzielnika 7, gdyż dopiero 8*17+4 jest wielokrotnością 7. A to nie jest poprawna liczba. W drugiej wersji 17*17-30 podobnie [1,9]_8.

4 komentarze:

kazik1007 pisze...

Dzień Dobry, widzę, że pan dalej się zajmuję faktoryzacją. Ja ostatnio wziąłem pod uwagę algorytm fermata.

kazik1007 pisze...

Biorąc jeden składnik z obliczeń wyszło mi:
4x² + 4x + 1 ///kwadraty

4x² + 8x + 3
4x² + 12x + 5
4x² + 16x + 7 
4x² + 20x + 9
4x² + 24x + 11
4x² + 28x + 13
4x² + 32x + 15 

4x²+4xy+2y-1 //wzór ogólny

Dla x=1 6y+3 ///6y+4n^2-1
Dla x=2 10y+15 ///10y+4n^2-1
Dla x=3 14y+35 ///14y+4n^2-1
Dla x=4 18y+63 ///18y+4n^2-1

Dla y=1 4x^2+4x+1
Dla y=2 4x^2+8x+3
Dla y=3 4x^2+12x+5

kazik1007 pisze...

Dalej z tego jeśli, (n-x^2) jest podzielne przez 2x+1 dla dodatniego x, to 2x+1 jest dzielnikiem 2 (n - x^2), z wyjątkami, bo niektóre złożone mają trochę inny format, ale i tak znając x mamy rozwiązanie.

jaNusz pisze...

Chwilowo nie publikuję nowych osiągnięć - za duże ryzyko wykorzystania w cyberwojnie. Skupiłem się na kolejnej własnosci, że liczba zawirajaca tylko na pozycjach cyfr wielokrotności a jest podzielna przez a.
Sito z ostatniego postu pozwala mi łatwo proponowaź pary kluczy prywatnych na potrzeby RSA.
A tak przy okazji, rozłożyłem metodą chałupniczą liczbę 90 bitową, której oba dzielniki były rzędu bilionów,