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.
Brak komentarzy:
Prześlij komentarz