Number Field Sieve

nfs-example.txt

Attempting to factor n = 361913909399305266402579347
Working in Z[w] where w is a complex root of f and f(m) = n
  where f(x) = x^4 + 1412261 * x^2 + 260933 * x - 880918
  and m = 4361655
Verified that f(x) is irreducible in Z[x]
Rational factor base contains 869 prime integers:
  2
  3
  5
  [... 863 omitted primes ...]
  6719
  6733
  6737
Algebraic factor base contains 2477 first degree prime ideals:
  (r,p) such that f(r) = 0 (mod p)
  (0,2)
  (2,3)
  (6,13)
  [... 2471 omitted prime ideals ...]
  (10524,22469)
  (417,22483)
  (17289,22483)
Searching for 1+869+2477+44+5 = 3396 smooth elements of Z[w]:
  a + bw |-> (a + bm, (-b)^degree(f) * f(a/(-b)))
  w |-> (4361655, -880918)
  1 + w |-> (4361656, 270411)
  -5 + 4w |-> (17446615, 422888577)
  [... 3390 omitted smooth elements ...]
  3575 + 4833w |-> (21079882190, -164327268318503894003)
  7976 + 433w |-> (1888604591, 16648736743084759906)
  4423 + 3987w |-> (17389922908, 143436554997002445127)
Derivative of f is f'(x) = 4 * x^3 + 2824522 * x + 260933
Generated 44 quadratic characters nonzero for f' and all smooth elements:
  (3425,22511)
  (10017,22511)
  (10244,22511)
  [... 38 omitted quadratic characters ...]
  (8221,22861)
  (9692,22861)
  (8591,22877)
Gaussian elimination resulted in 222 square products
Considering square product of 1190 elements of Z[w]:
  1 + w
  -12 + 5w
  1 + 19w
  [... 1184 omitted elements ...]
  -8195 + 192w
  -4311 + 4094w
  7976 + 433w
Rational square root modulo n is 72138865944910295627077969
Reducing modulo prime 10957
  totally splits f(x) as (x - 2228)(x - 3211)(x - 7519)(x - 8956)
  and algebraic square root is [3080,1150,4311,2751]
Lifted algebraic square root modulo 10957^804 has same square modulo n
Algebraic square root modulo n is 72138865944910295627077969
Greatest common divisor of n and sum of square roots is 1 (bad luck)
Considering square product of 1199 elements of Z[w]:
  w
  -5 + 4w
  11 + 3w
  [... 1193 omitted elements ...]
  -8195 + 192w
  -3395 + 5001w
  -8314 + 83w
Rational square root modulo n is 265216352534150276214654367
Reducing modulo prime 17851
  totally splits f(x) as (x - 1259)(x - 4949)(x - 13824)(x - 15670)
  and algebraic square root is [3565,8211,5051,6218]
Lifted algebraic square root modulo 17851^773 has same square modulo n
Algebraic square root modulo n is 96697556865154990187924980
Greatest common divisor of n and sum of square roots is n (bad luck)
Considering square product of 1205 elements of Z[w]:
  1 + w
  11 + 3w
  -12 + 5w
  [... 1199 omitted elements ...]
  -7238 + 1143w
  -8291 + 97w
  7976 + 433w
Rational square root modulo n is 350099632065833449943714007
Reducing modulo prime 16823
  totally splits f(x) as (x - 3622)(x - 6145)(x - 10050)(x - 13829)
  and algebraic square root is [4872,6405,6018,5831]
Lifted algebraic square root modulo 16823^778 has same square modulo n
Algebraic square root modulo n is 45996710851587876523107545
Greatest common divisor of n and sum of square roots is 200504042581
Factorization: 200504042581 * 1805020511010887