RSA 工业级素数
Industrial-Grade Primes in RSA
刘卓
1 为何使用素数
为了保证 RSA 使用过程中的安全性,p, q 的选择必须为素数。如果采用两个合数相乘,那么乘积依
然为合数,两把密匙并不唯一,则加密-解密的逆运算将不成立。即解密可能出现多解。
2 因式分解方法
2.1 试除法
给定一个合数 n(这里 n 是一个待分解的正整数),试除法是用小于等于
√
n 的每个素数去试除待分
解的正整数 n。如果找到一个数能够将 n 整除除尽,则这个数就是待分解整数 n 的因子。时间复杂度为
O
(2
logN/2
)。
def is_prime(a):
if a == 1:
return False
for i in range(2, int(a**0.5)+1):
if a % i == 0:
return False
return True
a = ’67280421310721 ’
b = is_prime(int(a))
print(b)
2.2 普通数域筛选法
普通数域筛选法 (General Number Field Sieve) 是已知效率最高的分解整数的算法。分解一个整数
n,需要
exp
3
64
9
+ o(1)
(ln n)
1
3
(ln ln n)
2
3
= L
n
1
3
,
3
64
9
步才能实现。所以时间负责度是 O
exp
64
9
n
1
3
(log n)
2
3
.
1