Mnożenie liczb mających w systemie binarnym same jedynki daje pośrednio (przed użyciem przeniesień między cyframi) bardzo specyficzną strukturę - piramidę, np. 3*7 = [1 2 2 1] _2.
Długość piramidy jest o 1 mniejsza niż długość (liczność bitów) większego z dzielników, największa wartość piramidy to liczność bitów krótszego dzielnika. Zatem mogąc utworzyć z liczby taką piramidę - wartość w nawiasie powtarza się:
1 (2) 1,
1 2 (3) 2 1,
1 2 3 (4) 3 2 1, itd.
łatwo dopasujemy dzielnik.
Istnieje jeszcze jedna własność, gdy w dzielniku p dokładnie jeden z bitów jest wyzerowany, np. 2^k, liczba N = p*q, to przez dodanie t = q*2^k uzyskamy piramidę o znanym rozkładzie. Korzystając wtedy z
N+q*2^k = q*(p + 2^k) = (2^r-1) * (2^s-1)
uzyskujemy, że dodawana wartość jest wielokrotnością dzielnika N. Zatem dopełniając N do piramidy, oraz licząc największy wspólny dzielnik gcd(t,N), uzyskamy niezwykle szybko rozkład N.
Uzupełnianie do piramidy odbywa się następująco: przechodzimy po bitach N wyłączając skrajne najmniej i najbardziej znaczące cyfry. Jeśli jest tam 0, wstawiamy 2, jeśli 1 zostawiamy. Uzyskana podwojona wartość binarna jest tą, która jest iloczynem 3*(2^n-1) o postaci 1 (2) 1.
By uzyskać kolejny poziom, dodajemy po prostu wartość (2^(n-2*k)-1)*2^k dla odpowiedniego k przy długości nieparzystej podstawy piramidy. Dla długości parzystej modyfikacja jest niewielka. Zasada - w kolejnym składniku usuwamy obie skrajne jedynki i mnożymy przez 2.
I tak mając 25 = [1 1 0 0 1], aby uzyskać piramidę, należy dodać [1 2 2]*2 = 20, wspólny dzielnik gcd(25, 20) = 5 jest dzielnikiem.
Ten sposób działa dla 7, 13, 11, 5, 31 i innych, zawodzi przy 19, która ma dwa bity wyzerowane w zapisie.
Brak komentarzy:
Prześlij komentarz