RSA中对模数n分解的方法

1、暴力算法

家人们，但凡数值大一点包算不出来的，有着超级简单的脚本思路，但是等pycharm运行出结果的时间都够睡一觉了！

2、费马分解

原理是将模数n分解成平方差的格式，适用于分解俩个因子接近的奇数（不是奇数就把他变成奇数呗！）
$$
n = a^2 - b^2 = (a+b)(a-b)
$$
具体步骤如下：

  1. 找到一个整数 a，使 a^2^ 接近 n 并且 a^2^≥n。
  2. 计算 b^2^=a^2^−n.
  3. 检查 b^2^ 是否是一个完全平方数。如果是，那么 n 的因子为 (a+b)和 (a−b)。
  4. 如果 b^2^ 不是一个完全平方数，增加 a 的值并重复步骤 2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math

def is_square(n):
    """检查一个数是否为完全平方数"""
    root = int(math.isqrt(n))
    return root * root == n

def fermat_factor(n):
    """费马分解法"""
    a = math.isqrt(n)
    b2 = a * a - n
    while not is_square(b2):
        a += 1
        b2 = a * a - n
    b = int(math.isqrt(b2))
    return a - b, a + b

3、在线工具分解

https://factordb.com/

这个网站还是比较靠谱的了，可以比较快的分解出因数

4、factorint函数分解

1
2
from sympy import factorint
factorint("需要的模数")