-
Notifications
You must be signed in to change notification settings - Fork 0
/
nfs-example.txt
103 lines (103 loc) · 4 KB
/
nfs-example.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
Attempting to factor 89-bit integer 361913909399305266402579347
Trial division up to 1000 found no factors
Factor target is 89-bit integer 361913909399305266402579347
Firing up the elliptic curve method (ECM)
No more ECM curve point/prime targets, factorization failed
Cranking up the number field sieve (NFS)
NFS configuration = Config {polynomialConfig = PolynomialConfig {polynomialDegree = OptimalPolynomialDegree, polynomialBase = ClosestPolynomialBase, polynomialCoeff = SmallestPolynomialCoeff}, rationalFactorBaseConfig = OptimalFactorBase 3.0, algebraicFactorBaseConfig = OptimalFactorBase 10.0, quadraticCharacterConfig = LinearQuadraticCharacterConfig 20 0.5, extraRankConfig = 5, verboseConfig = False}
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
NFS factorization: 200504042581 * 1805020511010887
Factor target is 38-bit integer 200504042581
Prime: 200504042581
Factor target is 51-bit integer 1805020511010887
Prime: 1805020511010887
361913909399305266402579347
==
200504042581 * 1805020511010887
2818.75user 20.67system 47:27.43elapsed 99%CPU (0avgtext+0avgdata 36544maxresident)k
0inputs+48outputs (0major+3876710minor)pagefaults 0swaps