Skip to content

Instantly share code, notes, and snippets.

@dfyz
Last active Jan 21, 2022
Embed
What would you like to do?
diff --git a/factorizer_qs.py b/factorizer_qs.py
index 1368283..e326743 100644
--- a/factorizer_qs.py
+++ b/factorizer_qs.py
@@ -70,7 +70,7 @@ class QuadraticSieve(Factorizer):
x = int(x)
candidate = (x+chunk_start)*(x+chunk_start) - N
factorization = _is_smooth(candidate)
- if factorization is not None: candidates_out[candidate] = factorization
+ if factorization is not None: candidates_out[x+chunk_start] = factorization.to_dict()
return candidates_out
candidates = dict() # dict of {x: x^2 - N} s.t. x^2-N is smooth
@@ -86,7 +86,7 @@ class QuadraticSieve(Factorizer):
candidates = OrderedDict([(c, candidates[c]) for c in sample(list(candidates), len(primes)+1)])
exponent_vectors = []
for c in candidates:
- factorization = candidates[c].to_dict()
+ factorization = candidates[c]
exponent_vectors.append([factorization[p] % 2 for p in primes ])
# Inspired by https://github.com/mikolajsawicki/quadratic-sieve/blob/main/quadratic_sieve/fast_gauss.py
# Also referred to https://www.cs.umd.edu/~gasarch/TOPICS/factoring/fastgauss.pdf
@@ -134,11 +134,26 @@ class QuadraticSieve(Factorizer):
x = prod(x_s)
y = _sqrt_prod(y_s).prod()
d = gcd(x-y, N)
- if d != 1:
- return d
+ if d != 1 and d != N:
+ return d, N//d
else:
- print("d == 1, trying again...")
+ print("Found a trivial factorization, trying again...")
-N = 8754660968220887821
-# N = 1413409093
-x_s, y_s = QuadraticSieve(N).factor()
+Ns = [
+ # The original N used in the code
+ 8754660968220887821,
+
+ # A bunch of extra Ns obtained with random_prime(2^32) * random_prime(2^32) in Sage
+ 2288734926177412733,
+ 5904209312552100917,
+ 504130586996406611,
+ 2994875707959333043,
+]
+
+results = []
+for N in Ns:
+ results.append(QuadraticSieve(N).factor())
+
+for N, (x, y) in zip(Ns, results):
+ assert x * y == N
+ print(f'{N} = {x} * {y}')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment