|
|
The quadratic sieve
def qs_basic(N,differences,y):
X = [Integer(a^2-N) for a in range(sqrt(N)+1,sqrt(N)+differences)]
P = list(primes(2,y))
F = easyfactorizations(P,X)
M = matrix(GF(2),len(F),len(P),lambda i,j:P[j] in F[i][0])
for K in M.left_kernel().basis():
x = product([sqrt(f[2]+N) for f,k in zip(F,K) if k==1])
y = sqrt(product([f[2] for f,k in zip(F,K) if k==1]))
return [gcd(N,x - y),gcd(N,x + y)]
return [1,N]
# example:
print qs_basic(275801,1000,20)
# output: [389, 709]
Larger example:
time print qs_basic(314159265358979323,500000,1000)
Version:
This is version 2012.12.28 of the qs.html web page.
|