c# - 将数字分解为 2 个质数余因子

Question

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 )

有没有适合这种情况的素数算法？

Answer 1

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