Testowanie rozkładu liczby na czynniki ma bardzo dużo przypadków do sprawdzenia. I cóż z tego, że procesory testują miliony przypadków na sekundę. Obliczenia trwają godziny, dni, miesiące.
Zatem należy poszukać takich zależności, które zmniejszą tę krotność.
Jednym z pomysłów było zastosowanie cech podzielności. Znamy podzielność przez 9 (suma cyfr cyfry dziesiętnej dzieli się przez 9), przez 11 (naprzemienna suma cyfr liczby dziesiętnej dzieli się przez 11).
Dla systemów o podstawie p parzystej, ich analogi brzmią następująco:
liczba n przedstawiona w systemie p dzieli się przez p-1, gdy suma jej cyfr dzieli się przez p-1;
liczba n przedstawiona w systemie p dzieli się przez p+1, gdy naprzemienna suma jej cyfr dzieli się przez p+1;
Przykłady liczbowe.
7 ' 595 ' 485 _ p=1088
w systemie o podstawie p ma sumę 'cyfr' 1087, naprzemienną sumę -103. Zatem istnieje dzielnik i jest równy 1088-1 = 1087.
1 ' 3904 ' 3903 _p=10280
ma sumę 'cyfr' 7808, naprzemienną sumę 0, zatem dzielnikiem jest 10281.
Aby znajdować dzielniki, wystarczy rozpatrywać podstawy parzyste(!) 4*m, co już zmniejszy krotność przypadków o połowę.
Uda się wyciągnąć coś jeszcze. Przechodząc po małych podstawach: 4, 8, 16, 20, 24, 30, 36 oznaczmy przez a sumę, zaś przez b sumę naprzemienną. Dla tak małych podstaw dla liczb złożonych okazuje się, że największy wspólny dzielnik d = nwd(p,a) jest równy mniejszej z p, a.
Dla sumy naprzemiennej wystarczy, że ta suma będzie 0, 1 lub -1, aby istniały dzielniki. Dla testowanej liczby pierwszej sumy od razu miały większe wartości.
Iloraz n/p dla takich p jest bardzo bliski liczbom całkowitym. Nie zawsze jest to dzielnik, nawet przy zerowaniu się sumy naprzemiennej.
Kolejna cecha namierzajaca to zmiana znaku sumy naprzemiennej. Towarzyszy rozmienieniu wartości na drobne, co występuje także przy dzielniku.
Przy czym nie możemy wchodzić w minima globalne, lecz lokalne sum naprzemiennych, które dla kolejnych podstaw mogą mieć wartości (4, -49, 3 -> dzielnik, -18, 1, 25, 0)
Czy można zatem zaprząc sumy do poszukiwania dzielnika?
Udaje się dla początkowych wartości namierzyć: w tym kierunku jest dzielnik. Lecz przybliżając się do niego za pomocą konwersji:
a[i]*(2^ip^i) + ... + a[1]*(2p) + a[0] = 2^ia[i]*p^i + ... + 2a[1]*p+a[0]
dla coraz większych p (za każdym razem p się podwaja) mamy coraz większe trudności z utrzymaniem dzielnika 'na celowniku'.
Pojawiające się zerowania lub cechy wspomagające namierzanie dzielnika nie trzymają się jednej wartości, lecz przemieszczają się.
W jednym tescie został namierzony dzielnik dla p=136. Przechodząc do p=272 dzielnik 'zniknął'. Został znowu namierzony dla p=256, przesunięcie 20. Zaś praktycznie dzielnik w tym przypadku był równy 136*8.
Zatem heurystyka niskim kosztem wskazuje: mamy dzielnik. Powinien być bliski takiej to a takiej wartości pomnożonej przez potęgę 2.
Lecz ze znalezieniem należy przeszukiwać brutalnie - chociaż można po wartościach podzielnych przez 4.
Metoda jest hipotezą.
Brak komentarzy:
Prześlij komentarz