因为p,q的位数太小了,导致了yafu很容易的分解出了p,q
但是即便p,q的计算结果n非常的大,如果生成的p,q的差值过小也会导致被爆破
费马分解原理
n = p * q ---> p,q都是大素数,奇数
所以存在 a,b 有这样的关系
a = (p + q)/2
b = (p - q)/2
n = a^2 - b^2
所以只需要枚举大于n的完全平方数,即可成功分解n
当然这里出现的原因是因为p,q之间的差值过小
导致b = (p - q)/2值较小,就可以快速分解n
Pollard_rho分解原理
通过某种方法获得a,b
计算 p = gcd(a-b,n)
直到p不为1,或者a,b出现循环为止,然后再判断p是否为n
如果 p = n,那么返回的n是一个质数,否则返回的p是n的一个因子
紧接着递归计算 Pollard(p) 和 Pollard(n/p),这样就可以计算n的所有质因子
这里我们只需要了解到分解n的原理和条件就行了
这几种方法在yafu中已经可以轻松实现