文章 - 相邻素数

Problem: 相邻素数

[[toc]]

思路

此题解题的关键在于求出p，q，n又过于大且所分解出的两个素数相差不是很大，通过取n开方后的不精确偏移值来穷是否为完全平方数，举出正确的p，q

EXP

import libnum, gmpy2

def factor(n):


a = gmpy2.iroot(n, 2)[0]

while True:

    num = pow(a, 2) - n

    if gmpy2.is_square(num):

        b = gmpy2.iroot(num, 2)[0]
        p = a + b
        q = a - b
        return p, q

    a += 1

n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
p, q = factor(n)
i = (p - 1) * (q - 1)
d = pow(e, -1, i)
m = pow(c, d, n)
print(libnum.n2s(int(m)).decode())

总结

通过找到偏移后n的开方值，推出p和q