Przez ostatnie tygodnie przygotowywałem ślad przebiegu dwu algorytmów faktoryzacji w języku angielskim. Ponieważ nie widzę, aby ten blog przyjmował załączniki tekstowe, wyciąłem nieco tekstu jako rysunki.
Faktoryzowana jest liczba
169,747,007
= 19*1087*8219
.
Narzędzia konwersji:
Użyte algorytmy:
Pierwszy z przykładowych algorytmów znajduje dzielnik następująco:
Po przekroczeniu pierwiastka sześciennego, coraz więcej przekształceń upraszcza się do postaci jak podana:
W drugim z algorytmów startujemy od postaci kwadratu z liczby. Konwersje między systemami są tak proste, że zapisuję kolejne postaci jedną pod drugiej, prawdzając od czasu do czasu małe dzielniki. Początek algorytmu wygląda następujaco:
Po znalezieniu dzielnika19 następuje porządne zamieszanie, gdyż współczynniki a, b, c, p, s i t muszą być przeliczone, lecz nie zmienia to wartości q.
Zaś zakończenie algorytmu wygląda następująco:
W ostatnim kroku s=219, gdyż przy zwiększaniu wartości s reszta z dzielenia 1099 przez 5 jest coraz mniejsza. Miły szczegół upraszczający rachunki.
Brak komentarzy:
Prześlij komentarz