qs_patch.patch

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}')