26 marca 2014

Faktoryzacja metodą kolejnych dzieleń z cechami podzielności

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)


14 marca 2014

Spacerkiem koło dzielników

Rozwijałem pomysł odwrócenia iloczynu
N = q1*q2
gdzie wszystkie wartości są traktowane schematem Hornera. Oznacza to dla wartości zapisanych trzycyfrowo
q1=(a2*p1+a1)*p0+a0,
dla dowolnych liczb p1, p2 i ciągach współczynników (a), (b) zapis:
N = ((a2*p1+a1)*p0+a0) * ((b2*p1+b1)*p0+b0) =
(( a2*b2*p1*p0 + p0*(a2*b1+a1*b2) + (a2*b0+a0*b2) )*p1 +
(a1*b1*p0 + (a1*b0+a0*b1) )*p0 + a0*b0 =
n*p1*p0 + w[a1,b1]*p0 + a0*b0

Jeśliby udało się jednoznacznie dopasowywać kolejne współczynniki ciągów 'cyfr' a, b, mamy do czynienia z algorytmem działającym na coraz mniejszych wartościach, w którym wyszukiwanie zostałoby przerzucone na znajdywanie odpowiednich par (a,b) stanowiących kolejne wyrazy.

Owszem, wielomian w[a,b] pojawiający się we wzorze jest łatwo wyznaczany, współczynniki znajdujemy z równań kongruencyjnych, których liczność zależy od wartości współczynnika danego poziomu p. Jest jednak duży kłopot z jednoznacznością.
Można temu częściowo zaradzić, biorąc za p niewielką liczbę pierwszą. Wtedy mamy do rozwiązania p-1 kongruencji, z których jedna jest sprzeczna, jak to pisałem w poprzednim poście.
Nauczyłem się także wskazywać, które z par (a,b) nie warto badać przy szukaniu dzielników. Zatem ciągi (a), (b) powinny z pomocą (p) skonwertować się na dzielniki. A wtedy pojawia się pułapka.

Oto heurystyka, która pozwala przybliżać orbity dzielników zapisanych jako a*P+A,
gdzie P jest iloczynem wartosci p0*p1*p2*..., A jest liczbą uzyskaną z obciętego ciągu (a0, a1, ..., am) wzorem A=a0+p0*(a1+p1*(...(am)...)).
Inicjujemy n=(N-1):2, A=1, B=1, P=2, w[0,0]=1. 

Dane są: liczba n, wielomian w[a,b] = abP+aA+bB o współczynnikach P, A i B
Wybieramy liczbę pierwszą p, dbając, by p nie dzieliło n.
Dzielimy z resztą n = p*q+r, 0<r<p.
Szukamy rozwiązań równania kongruencyjnego  jako par liczb (a,b)
w[a,b] = r (mod p)
po prostu wstawiając kolejno a=0, ..., a=p-1. Uzyskamy wartość b.
Tworzymy równanie  zmiennych C=A, D=B
q = (A+aP)*C+(B+bP)*D
które traktujemy modulo min(A,B) uzyskując równanie rekurencyjne jednej zmiennej. Jeżeli rozwiązanie tego równania istnieje i jest (w kolejności) mniejsze niż p, równe 0, wielokrotnością p, w takim razie mamy dużą szansę, że para (a,b) stanowi lepsze przybliżenie dzielników.
Modyfikujemy w kolejności: A=A+aP, B=B+bP, P=p*P, n = (n-w[a,b]):p

Powtarzamy tak długo, dopóki n jest dodatnie.
Wartość n=0 oznacza, że udało nam się dokładnie wyznaczyć ciągi współczynników dzielników, czyli A, B są dzielnikami N.

A oto pułapka. Może się zdarzyć, że któryś ze współczynników A+aP, B=bP jest dzielnikiem oraz n>0, wtedy algorytm się nie zatrzymuje, lecz szuka dalej.

Przykład numeryczny, 8934053
n = (8934053-1):2 = 4467026
p = 3, w[a,b] = 2ab+a+b
rozwiązaniem równania w[a,b]=2 są pary (2,0), (0,2), zaś (1,1) daje równanie sprzeczne. Przyjmujemy a=(2,0) dzieki równaniu (n-2):3 = 5A+B
nowy wielomian w[a,b] = 6ab+a+5b
Dalej p=5, równanie dla a=4 jest 4b+4=3 (5)
Podaję w[a,b] oraz p
w[a,b] = 30ab+7a+29b, p=7, rozwiązanie (0,1) z D=4
w[a,b] = 210ab+37a+29b, p=3, rozwiązanie (0,2) z C=21=7*3
w[a,b] = 1470ab+457a+29b, p=7, rozwiązanie (0,6) z D=7
i tu następuje ominięcie, gdyż właściwym rozwiązaniem jest (6,1), wtedy współczynnik przy D jest dzielnikiem 1087 liczby 8934053 oraz następne n jest równe n=0.
Biorąc liczbę pierwszą większą od 11, też uzyskamy rozkład na dzielniki po tych sześciu iteracjach. A=8219, B=1087.