forked from truongkma/ctf-tools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
fermat_factor.py
37 lines (32 loc) · 2.48 KB
/
fermat_factor.py
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
def fermat_factor(n, n1, n2):
a = gmpy.sqrt(n) + 1
b = a * a - n
bsq = gmpy.sqrt(b)
while bsq * bsq != b or a + bsq == n1 or a + bsq == n2:
a += 1
b = a * a - n
bsq = gmpy.sqrt(b)
return a + bsq
N1 = 102343019429239678743451757102284566204106655684289193110570833127319552999565297607608589023212457484551234247136939807851775127106740105823090723431092749501624749145144636275125802946199286944290667744865263111568280070596928513452821442436056684204771050138983157389631201771249685577604662960327032225835763438342414703615365972841937606577068873311259645834416901672201478160212630493162338805146860777841879927540043527038315751014591621647783040070592654991293875737836324169206791927375526333675198340894875801684850915156650902515108599610274775146783267282887271203906521597483404982127340111993948782314001700630128664211438390423057011422024904330208788487388512957478720223427408818094408046406663479295817364649694665910473125160506122215790880901295234515422706593753906351829139770019936223
N2 = 102343019429239678743451757102284566204106655684289193110570833127319552999565297607608589023212457484551234247136939807851775127106740105823090723431092749501624749145144636275125802946199286944290667744865263111568280070596928513452821442436056684204771050138983157389631201771249685577604662960327032225835763438342414703615365972841937606577068873311259645834416901672201478160212630493162338805148891983157191441281286437933635170222049354852045978252944579198451122629301443128735187002334029347561904260996895503094759169980628538095264800519820061337074502573029802344519371901798193181453367724481849891695522140373228522094765893527782956477714048871040581885680284497836909184741177716034659720839328742940592415983836829182516657934474250414409369296521132907323749135673115788133168383864582483
N = N1 * N2
a = fermat_factor(N, N1, N2)
p1 = gcd(N1, a)
q1 = N1 / p1
# import gmpy2
# N = gmpy2.mpz(
# 0xE8953849F11E932E9127AF35E1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051F8EB7D0556E09FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAD55)
# gmpy2.get_context().precision = 2048
# a = int(gmpy2.sqrt(N))
# a2 = a * a
# b2 = gmpy2.sub(a2, N)
# while not(gmpy2.is_square(b2)):
# a = a + 1
# b2 = a * a - N
# b2 = gmpy2.mpz(b2)
# gmpy2.get_context().precision = 2048
# b = int(gmpy2.sqrt(b2))
# p = a + b
# q = a - b
# print p
# print q