Pozwoliłem sobie na przegląd reszt z dzielenia przez kolejne liczby naturalne.
Wybrałem liczbę, dzieliłem ją przez liczby poczynając od pierwiastka do coraz mniejszych wartości.
Skupiłem się na poszukiwaniach lokalnie najmniejszych wartości, tzn. takich, że dzieląc kolejno przez q+1, q, q-1, wartość reszty n%q jest mniejsza od sąsiednich.
Jeśli liczba n = (ap+b)p+c (p jest podstawą systemu między pierwiastkiem sześciennym i kwadratowym z n), to wyznaczone przez q lokalne minima układają się dosyć specyficznie.
Weźmy przedział dla stałego a. Wtedy dla wartości bliskich iloczynom a oraz kwadratowi pewnej liczby oraz (a+1) oraz kwadratowi innej liczby lokalne minima są bardzo rzadkie.
Równie rzadko, chociaż częściej występują one dla liczb n o wartościach bliskich t = (ap + p/2)p+c, czyli dokładnie w połowie przedziału, w którym iloraz n/p^2 ma stałą część całkowitą.
Dalej, kiedy znajdę resztę lokalnie najmniejszą, oraz nie jestem zbyt blisko krawędzi (lub środka) przedziału o stałym a, łatwo wyznaczę konwersję, którą należy zastosować, by dostać się do najbliższej lokalnie najmniejszej reszty. Trafiam dokładnie w ten dzielnik lub w sąsiednią wartość.
Dla wartości p większych niż t przekształcenie jest postaci b/q, oraz jeśli od q odejmę b/q znów mam wartość reszty lokalnie najmniejszą.
Dla wartości q mniejszych niż t przekształcenie jest postaci (q+c)/(q-b). Wtedy b jest większe niż połowa q, dlatego dzielę przez coraz miejszą wartość, zmniejszając podstawę q o tę wartość trafię blisko kolejnej lokalnie minimalnej wartości.
Przekształcenia te nie działają przy krawędziach lub na środku. Jest to spowodowane zbyt małymi różnicami między kolejnymi resztami. Różnica między resztami dla p, p-1 oraz między resztami p-1, p-2 różni się o dokładnie 2a. Przy krawędziach (b bliskie 0 lub b bliskie p) jest to tak mała wartość, że można zastosować wzór na wyraz szeregu arytmetycznego i uzyskamy dobre przybliżenie. Po trafieniu w lokalnie najmniejsze minimum ilorazy b/q wolno maleją do 3 pozwalajac pominąć mnóstwo wartości p, dla których dzielniki są większe. W okolicy połowy przedziału, czyli blisko t, mamy skoki, jest coś w rodzaju bifurkacji, oraz widać układające się monotonicznie ciągi, ale co druga reszta. Możemy je traktować oddzielnie, np. licząc tylko dla wartości p nieparzystych. Przy przekraczaniu t następuje skok. Od tego momentu ciąg co drugiej reszty powoli zaczyna się zachowywać coraz mniej przewidywalnie, aż wreszcie lokalne minimum pojawia się co trzecia reszta. Od tego momentu można przyjąć drugie przekształcenie (q+c)/(q-b), które powoli rośnie wskazując kolejne lokalnie minimalne reszty, wreszcie dojdziemy blisko krawędzi, gdzie iloraz jest duży, ale i tak bywa za mały dla sprawdzenia monotoniczności reszt.
Dla większych a obszar w środku staje się coraz bardziej przewidywalny, tak że można cały czas korzystać ze podanych przekształceń uważając tylko, kiedy b urośnie powyżej połowy podstawy p.
W ten sposób dla liczby 2^(101) pomijam nawet miliony przypadków dzielenia przez wartości, dla których reszta z dzielenia będzie dodatnia.
Zaś dzielniki, zwłaszcza te najbardziej poszukiwane (RSA) układają się najbardziej gęsto w okolicach niezbyt bliskich t (b bliskie połowie systemu), ale zarazem bardzo daleko od granic (b małe albo niewiele mniejsze niż podstawa systemu), przy którach a jest równe 1, 2, 3, i tak do 9. Zwłaszcza na obszarze wartości nieco mniejszych niż t (b większe niż połowa podstawy systemu).
Najmniejsze wartości lokalnie najmniejszych reszt występują, gdy b jest małe. Reszty te są mniejsze nie tylko od p, ale i od b. Drugim takim obszarem są bardzo duże b, bliskie podstawy systemu. Wtedy lokalnie najmniejsze reszty też są mniejsze niż (p-b). Oraz sporadycznie gdzie indziej.
Dodatkowo zauważyłem, że w badanym przypadku, którym była liczba złożona, minima lokalne sąsiadujące z dzielnikiem (w którym reszta jest oczywiście 0) miały wartość większą niż połowa podstawy systemu p.
Można to wykorzystać. Wiadomo, gdzie szanse na znalezienie dzielnika są znikome, zwłaszcza po przebadaniu dzieleń przez kilka podejrzanych wartości.
Brak komentarzy:
Prześlij komentarz