Telegram Authentication 的要求之一正在将给定数字分解为 2 个素数余因子。特别是P*Q = N, where N < 2^63
我们怎样才能找到较小的素余因子,例如 P < square_root(N)
我的建议:
1) 预先计算从 3 到 2^31.5
的素数, 然后测试是否 N mod P = 0
2) 找到一个算法来测试素数(但我们仍然要测试 N mod P =0
)
有没有适合这种情况的素数算法?
最佳答案
Pollard 的 Rho 算法 [VB.Net]
查找 P
非常快,在哪里P*Q = N
, 对于 N < 2^63
Dim rnd As New System.Random
Function PollardRho(n As BigInteger) As BigInteger
If n Mod 2 = 0 Then Return 2
Dim x As BigInteger = rnd.Next(1, 1000)
Dim c As BigInteger = rnd.Next(1, 1000)
Dim g As BigInteger = 1
Dim y = x
While g = 1
x = ((x * x) Mod n + c) Mod n
y = ((y * y) Mod n + c) Mod n
y = ((y * y) Mod n + c) Mod n
g = gcd(BigInteger.Abs(x - y), n)
End While
Return g
End Function
Function gcd(a As BigInteger, b As BigInteger) As BigInteger
Dim r As BigInteger
While b <> 0
r = a Mod b
a = b
b = r
End While
Return a
End Function
Richard Brent 的算法 [VB.Net] 这甚至更快。
Function Brent(n As BigInteger) As BigInteger
If n Mod 2 = 0 Then Return 2
Dim y As BigInteger = rnd.Next(1, 1000)
Dim c As BigInteger = rnd.Next(1, 1000)
Dim m As BigInteger = rnd.Next(1, 1000)
Dim g As BigInteger = 1
Dim r As BigInteger = 1
Dim q As BigInteger = 1
Dim x As BigInteger = 0
Dim ys As BigInteger = 0
While g = 1
x = y
For i = 1 To r
y = ((y * y) Mod n + c) Mod n
Next
Dim k = New BigInteger(0)
While (k < r And g = 1)
ys = y
For i = 1 To BigInteger.Min(m, r - k)
y = ((y * y) Mod n + c) Mod n
q = q * (BigInteger.Abs(x - y)) Mod n
Next
g = gcd(q, n)
k = k + m
End While
r = r * 2
End While
If g = n Then
While True
ys = ((ys * ys) Mod n + c) Mod n
g = gcd(BigInteger.Abs(x - ys), n)
If g > 1 Then
Exit While
End If
End While
End If
Return g
End Function
关于c# - 将数字分解为 2 个质数余因子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31953836/