liczby nie musza być blisko pierwiastka
i
a<b i b w pryzbliżeniu nie przekracza a +10pierwiastków z a
się wyklucza :)
Jeśli masz dwie liczby które są blisko siebie (a u ciebie wymuszasz ze nie mogą się różnić o więcej niż jakieś 10+sqrt(a), czyli różnią się na nie więcej niż połowie dolnych bitów) to muszą być blisko (czyli różnić się znów w tym przypadku jedynie na dolnej połowie bitów) pierwiastka z iloczynu. To jest matematyka na poziomie szkoły podstawowej.
Weźmy twój przykład:
x = 1234567890123456789012345678900987654321098765432187897213984701293487102398471092384710293487109233 *1234567890123456789012345678900987654321098765432170129348710239847109238471029348710923389787398321
gmpy2.isqrt(x)
mpz(1234567890123456789012345678900987654321098765432179013281347470570298170434750220547816841637253776L)
Jak nie trudno zauważyć, dostaliśmy liczbę która ma wszystkie górne bity takie same jak "wspólna" część twoich wejściowych liczb. Generalnie pierwiastek będzie mniej więcej w połowie między twoimi czynnikami p i q.
Czy ten algorytm w sekundę rozłoży np. Ten przykĺad który dałem
Rozłoży rzędy wielkości szybciej i to nawet biorąc pod uwagę ze to wieśniacka implementacja w pythonie. Na moim laptopie średnia z miliona uruchomień to 5.87 mikrosekundy. W sekundę można by to uruchomić 200 tysięcy razy.
Jeszcze raz: jestem pewien ze twój algorytm polega na tej samej zasadzie, nawet jeśli liczysz to w bardziej nieudolny sposób. Jasno wskazują na to ograniczenia które nakładasz na różnicę między czynnikami.
Dobra a teraz zniszczę twoje marzenia o fortunie :D Widać dość jasno, ze twoje założenie a<b i b w pryzbliżeniu nie przekracza a +10pierwiastków z a oznacza, że pierwiastek z n pozwala nam odzyskać połowę górnych bitów p oraz q (bo są takie same). Czyli innymi słowy twoja metoda (vel metoda Fermata) pozwala na faktoryzacje jeśli znamy aż połowę bitów p oraz q. To jest dość mocne założenie. Pokaże ci teraz metodę (wspominałem o niej wyżej), która potrafi dokonać faktoryzacji znając połowę bitów (górnych lub dolnych, bez różnicy) tylko jednego z czynników i nie nakłada żadnych (!) ograniczeń na drugi czynnik, ani na różnicę między czynnikami. Siłą rzeczy jest znacznie mocniejsza niż to o czym dotąd pisaliśmy:
bits = 512
hidden = 215
# dwa losowe dowolne prime
p = random_prime(2^bits-1, false, 2^(bits-1))
q = random_prime(2^bits-1, false, 2^(bits-1))
# dla pewnosci pokazujemy ze roznia sie praktycznie na wszystkich bitach!
print((p-q).nbits())
# bierzemy sobie p>q, to bez roznicy ale trzeba by pozniej liczyc 2 razy w zaleznosci od przypadku
if q > p:
tmp = p
p = q
q = tmp
# kasujemy dolne hidden bitow z liczby p
p_approx = (p >> hidden) << (hidden)
print('p', hex(p))
print('p_approx', hex(p_approx))
print('q', hex(q))
N = p*q
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x + p_approx
d = f.small_roots(X=2^hidden, beta=0.5)[0]
print('recovered', hex(int(p_approx + d)))
(zeby dostać więcej hidden bitów trzeba by troche podkręcic parametry i liczyłoby sie dłużej, ale górna granica to właśnie połowa bitów, o ile znamy przynajmniej połowę, algorytm się policzy w czasie wielomianowym)