Dotychczas moje algorytmy przekształcały rozkładaną liczbę. Aby podliniowo faktoryzować, należy skorzystać z właściwości dzielników. Można je uzyskiwać nawet nie znając tych dzielników. Zainteresowych odsyłam, by zapisać kolejne cyfry liczby w innych systemach, oraz sposób odwrócenia kolejności dwu ostatnich podstaw, co już daje nieco informacji o dzielnikach...
Pomocą może być także funkcja wskazująca rozmieszczenie liczb pierwszych, bliźniaczych, czworaczych, opublikowana już na tym blogu. Rozszerzenie nie musi być o kolejną liczbę pierwszą, lecz o dowolną liczbę pierwszą.
Liczba jest pierwsza, gdy wspomniana funkcja przyjmuje wartość 1 dla każdego rozszerzenia mniejszego niż dana liczba. Pojawiającą się drobną nieoznaczoność przy nie kolejnych liczbach pierwszych można łatwo namierzyć, np. dla k=6 i rozszerzaniu o liczbę p będzie sugerowana własność pierwszości dodatkowo tylko dla p oraz 5*p, gdy nie uwzględniamy liczby pierwszej 5. Dla p pierwszej wartość funkcji tych miejsc ulega modyfikacji z 1 do p. Funkcja z liczby ma wartość a>1, gdy liczba ta jest podzielna przez a.
A kiedy weźmiemy za mało danych, do gry wchodzi chińskie twierdzenie o resztach, dzięki któremu obszar poszukiwań dzielników drastycznie się kurczy.
Wystarczy funkcja dla p \in {2, 3, 5, 7}, a znajdziemy rozkład 7387, mając reszty modulo: 6, 30=6*5, 42=6*7. Te same dane (już bez chińskiego twierdzenia o resztach) wystarczyły na wykazanie pierwszości 127. I tylko warto przyjmować rozkład liczb ujemnych, np. testując -5 = (-1)*5 lub -5 = 1*(-5), by dopasować iloczyny reszt dzielników. Unikamy w ten sposób testowania wielu wartości.
Nie chcę podawać tu szczegółów - to jest za szybkie na obecne zabezpieczenia cyberbezpieczeństwa. Przy rozkładzie 7387 użyte tylko cztery liczby pierwsze spośród 23 kandydatów już wskazały rozkład... Wystarczyło uzgodnić 30*a+r1 = 42*b+r2, gdzie a, b małe liczby; r1, r2 pozycje funkcji, w której r1*r2 przystaje do wyznaczonej reszty, np. -5 = 37-42 = r1*r2 - 42. Reszta będąca liczbą pierwszą to nie jest przypadek...
Brak komentarzy:
Prześlij komentarz