Wymieniłem sposób dzielenia w faktoryzacji metodą kolejnych dzieleń.
Zastosowałem dzielenie, a które naprowadziły mnie systemy niedziesiątkowe.
Dla bardzo dużych liczb n, długości 2i lub 2i-1, dzielę n na dwie paczki o długościach nie przekraczających i:
n = a ## b = a*10^i+b
Cecha podzielności przez odpowiednio duże liczby jest postaci:
"liczba n jest podzielna przez p=10^(i+1)-r wtedy i tylko wtedy gdy wartość a*r+b jest podzielna przez p";
istnieje też podobna cecha, gdy p=10^i+r, cecha lepiej działa, gdy r nie jest większe niż 2*10^(i-1):
"liczba n jest podzielna przez p=10^i+r wtedy i tylko wtedy, gdy wyrażenie -a*r+b jest podzielne przez p".
Co się wtedy dzieje dla bardzo dużych liczb, typu RSA?
Otóż w zależności od przedziału p \in (10^i/(k+1) , 10^i/k) cecha podzielności może zmniejszyć wartości biorące udział w obliczeniach. Mianowicie przyrost r można zastąpić wartością 10^i % r, co powoduje zmniejszenie czynnika, czasem bardzo duże.
Przyjmujemy p nieparzyste. Jeśli p>5*10^(i-1), to cecha pozwala liczyć wyrażenie ar+b, zaś dla liczby p-2 już tylko a(r+2)+b. Oznacza to, że w tym przedziale nie trzeba wykonywać iloczynu a*(r+2), tylko do poprzedniego dodać 2a.
Gdy p \in (0,(3)*10^i , 0,5*10^i ), dla porachowania wartości w (p-2) należy do wcześniejszego iloczynu dodać 4a. I tak dalej, każde kolejne zmniejszenie poniżej 10^i/k powoduje konieczość dokładania 2k*a.
Dodatkowo, możemy jeszcze liczyć kongruencje modulo p iloczynów.
Nie trzeba także sprawdzać wartości 10^i/k. Pojawia się ona automatycznie, kiedy wartości r przekroczą p.
Dla tych największych wartości nie warto stosować drugiej z cech (suma naprzemienna) ze względu na pogorszenie sytuacji obniżającej wykładnik potęgi. Wtedy warto używać działań modulo dla iloczynów, choć można wygenerować też równanie kwadratowe, którego wartość jest dodawana.
Jednak, nie znalazłszy dzielnika dla tych największych wartości, można kontynuować, stosujac cechę podzielności w innym obszarze:
n = a ## b ## c = a*10^(2j)+b*10^j+c
"liczba n jest podzielna przez p = 10^(j+1)+r, r = (10^(j+1) % p) wtedy i tylko wtedy gdy (ar+b)r+c jest podzielne przez p"
"liczba n jest podzielna przez p = 10^j+r, r<10^j wtedy i tylko wtedy gdy -(-ar+b)r+c jest podzielne przez p"
To nie jest już tak wygodne jak wcześniejszy przypadek, ale nadal prosty.
Modyfikacja ta pozwala upraszczać od 1% do 90% przypadków (związane z wartością liczby n) w najgorszym obliczeniowo obszarze. Dodatkowe wykorzystanie podziału liczby n na trzy części pozwala sprawdzić około 90-99% przypadków.
Przykład numeryczny: n = 8934053 = 893*10^4 + 4053,
podzielność przez p=2501: r = 10^4 % 2501 = 2497
reszta n%p = (893*2497+4053)%p = (2233874)%p = (1430+1552)%p = 481
kolejne dodanie 6+2497 > 2500, następuje zmiana wielokrotności dodawanych a
podzielność przez p=2499: r = 10^4 % 2499 = 4
reszta n%p = (893*4+4053)%p = 7625%2499 = 128
podzielność przez p=2497: r = 10^4 % 2497 = 12 (1/4 k: dodać 2*4a=8a)
reszta n%p = (893*12+4053)%p = 2284 = (8*893+7625)%2497
podzielność przez 1001: r = 10^4 % 1001 = 991
reszta (893*991+4053)%1001, ale także
-(-8+934)+53 = -873 = 128 (1001)
Brak komentarzy:
Prześlij komentarz