W poprzednim poście wspomniałem o pomyśle równoczesnego badania dwu dzielników s*t, s<t, w którym s i t tworzą ciągi arytmetyczne o przyroście |2|. Sposób nie unika mnożeń lub dzieleń, lecz obecne są przez stosunkowo małe wartości. Dodatkowo wartości te łatwo jest szacować.
Wygodnie jest nie pamiętać liczb n, lecz ich trójki [a,p,b]: n = a*p+b.
Jest to na dwu poziomach, jeden przy podstawie p, obliczanej przez dodanie zmniejszającej się o 8 wartości w. Drugi poziom dotyczy iloczynu a*w, rozpisanego trójką a*w = [c,t,d].
Wartość b zapisujemy analogiczną trójką b = [e,t,f]. Przy przekształcaniu odejmujemy b-a*w = [e-c,t,f-d] starając się, by wartość f-d była dodatnia. W razie potrzeby dodajemy s*t zmniejszając a. Wartość e-c dla sprawdzanego zakresu jest zawsze dodatnia. Podobnie można zrobić z wartością s.
Pamiętamy stare wartości (to te z primami).
Zaczynamy od s=3, t będącą nieparzystą wartością nieco mniejszą niż pierwiastek kwadratowy z rozkładanej liczby n, przyjmujemy w = 2*t-10;
Przy sprawdzaniu kolejnych dwu dzielników postępujemy następująco:
w = w'-8;
p = p'+w = (s'+2)*(t'-2) = s*t;
a*w = [ct, t, dt] = [cs, s, ds]
b' - a*w + s*t*x = [e, t', f] - [ct, t, dt] + s*t*x = [e-ct+s*x, t, 2*e+f-dt]
Rozwiązujemy nierówność liniową e-ct+s*x>0 zmiennej x szukając najmniejszego możliwego x. Od pewnego momentu jest x=1 lub x=0.
Jeśli 2*e+f-dt= 0, mamy dzielnik t.
Podobnie można zrobić z kandydatem na dzielnik s, uwzględniając znaleziony x. Tym razem:
b'-a*w + s*t*x = [e, s', f] - [cs, s, ds] + s*t*x = [e-cs+t*x, s, f-2*e-ds]
Jednak ostatnia wartość f-2*e-ds bywa na tyle mała, że trzeba dodać kilka s, aby uczynić ją nieujemną. Krotność dodanych s zmniejsza (e-cs+t*x).
Po tych przekształceniach zmniejszamy a = a'-x
Przykład numeryczny.
Wartość w = 2164, p' = s'*t' = 955*2035, 'obliczamy' p = p'+w = (s'+2)*(t'-2):
n = [a, p, b] =
4 * 1 943 425 + [570, 2035, 403] = 4 * 1 943 425 + [1215, 955, 28]
Sprawdzamy kandydatów t=2033, s=957:
w = 2164-8 = 2156,
a*w = [4, 2033, 492] = [9, 957, 11]
nowe b = [ct, t, dt] = 570*2035+403 - 4*2033-482 + 2033*957x =
(570-4+957x)*2033 + (1140+403-492)
w tym przypadku mamy x=0, bo 570-4>0
b = 566*2033+1051 = [566, 2033, 1051], 1051<>0, t=2033 nie jest dzielnikiem
dla s:
b = 1215*955+28 - 9*957-11 + 957*2033*0 = 1206*957-2413 = 1206*957+458 = [1206, 957, 458]
s też nie jest dzielnikiem
wartości a nie zmniejszamy, bo x=0.
Następna para s*t = 959*2033 ma a*w = 4*2156 = [4, 2031, 468] = [8, 959, 920]
Przekształcamy dopóki s stanie się większe niż t albo trzeci element trójki będzie zerem.
Wydaje mi się, że obliczanie s w analogiczny sposób jak t jest bezcelowe, lepiej podzielić znaną wartość b = ct*t+dt przez s resztami modulo.
Jak już wspomniałem poprzednio, dla małych s 'a*w' są gigantyczne, ale dla nich x jest duże. Zatem w maleje, a maleje, wkrótce zaczynamy coraz rzadziej dodawać s*t, tylko przy zmianie a.
