Faktoryzacja liczb nieparzystych wymaga kandydatów nieparzystych. Wydaje się, że poszukiwanie dzielników dla podstaw systemów niedziesiątkowych będących liczbami parzystymi jest głupotą. A jednak!
Konwersje przy podstawach parzystych mogą aproksymować iloraz q/d gdzie q*d jest dużą liczbą na tyle skutecznie, że liczbość operacji spada do logarytmu z liczby.
Sam proces ma trzy fazy:
- oszacowanie długości dzielników
(p-x)(p+y) przechodzi w (p+x)(p+y) po konwersji, gdzie p jest potęgą 2, zaś x i y nieujemnymi odległościami dzielników od podstawy systemu
- znalezienie części całkowitej q/d, gdzie q*d = N są dzielnikami liczby rozkładanej N; płynnie przechodzi w następną fazę:
- dopasowanie reszty z dzielenia, w którym usiłuję zapisać dzielnik q>d w systemie o podstawie d. Docelowo mam uzyskać postać liczby trójcyfrowej
a b b-a _ p
lub
a b a+b _ p
Teraz wystarcza cecha podzielności i mam dzielnik np. p+1 oraz a(p+1)+b.
Działa dla dowolnego z dzielników, i zawsze znajdzie co najmniej jeden: n*1.
Ta ostatnia część jest bardzo szybka, wartości a i b mają skłonności do rozjeżdżania się, lecz potrafią się znowu zbiec. Stosuję konwersje p=p +- 2^k przy malejącym k, co aproksymuje dzielnik.
Nie wiem jeszcze dokładnie, jakie formuły zadać algorytmowi. Patrząc na oko, najpierw odległość liczby trójcyfrowej
a b c _p
c-b powinna być jak najmniejsza, a potem starać sie utrzymywać c bliskie b stosując konwersje o malejące potęgi 2. Ale nie na siłę, raczej widełkami ograniczającymi zakresy badanych wartości.W ostateczności, jest to przebieg wykładniczy względem log n, czyli liniowy.
Stosując te konwersje, znajduję dzielniki liczby 2^(101)-1, i to w około 51 krokach, jak sprawdziłem. Choć przyznaję, długość dzielników oraz niektóre bity skrajne znam z innych badanych algorytmów - służyły mi za punkt odniesienia.
Jeśli nie trafi się w odpowiedni przedział, wartości sugerowane przez heurystykę zawierają długi ciąg zer lub jedynek.
Podejście, w ktorym usiłuję uzyskać na pozycji jedności narastające potęgi 2 nie działa w ogólności. Dla ustawionych bitów dzielnika wydaje się działać, zera psują. Zatem przegląd zupełny, wykładniczy.
Istnieje jednak możliwość przycięcia tego rozrostu, co jest opisane w innym poście Faktoryzacja liczbami parzystymi z 6 kwietnia 2019 roku
