CTF RSA 高精度整数开根 解一元二次方程

做BJDCTF第二届出的RSA题目,需要解高精度整数的一元二次方程,参考着网上写了个Python脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def HPSqrt(a,b): #高精度开整数根,a为开几次根,b为要开根的数
    l=0
    r=1
    while(r**a<=b):
        l=r
        r=r*2  
    while(l+1<r):  
        mid=(l+r)//2
        if (mid**a<=b): l=mid
        else: r=mid
    if (l**a<=b): return l
    else: return r

def HPSolve12(a,b,c): #高精度解整数一元二次方程,解RSA用
    key=HPSqrt(2,b*b-4*a*c)
    return ((-b+key)//2//a,(-b-key)//2//a)

a=1
b=-2
c=1
print(HPSolve12(a,b,c)) #将方程整理成ax^2+bx+c=0的形式代入即可

参考资料:高精度Python开根 https://www.luogu.com.cn/blog/wjy666/solution-p2293

发表评论

电子邮件地址不会被公开。 必填项已用*标注