生成私要一般需要分解大数n为两个大素数p,q
生成私钥需要计算 （p-1）*（q-1）
对于一些特定的大数是无须分解的。
现说明如下：
假设n满足如下：条件就无须分解。
设 n^(1/2)+1 为 x。
如果能找到合适一个数 y 且
x+y=q x-y=p
且（x-1）^2 < n
如果数据满足上述条件则:无须分解此大数
可以看出: (q-1)*(p-1) = n - 2*x + 1
我们看出计算 n的平方根应该比较简单.
但我们是否发现,没有分解大数,怎么知道是否满足上述条件.
其实我们可以先假设n满足条件,然后计算出私钥 d,
然后用他加密一段明文,然后用共钥看能否解开就可以了,如果解不开
则肯定不满足上述条件,这时再分解大数n也不迟.
插入表情