millerrabin.vb

    Dim gen As New Random
    Function IsPrime(value As BigInteger, Optional witness As Integer = 10) As Boolean
        If value <= 1 Then
            Return False
        End If
        Dim d As BigInteger = value - 1
        Dim s As Integer = 0
        While d Mod 2 = 0
            d /= 2
            s += 1
        End While
        Dim bytes As [Byte]() = New Byte(value.ToByteArray().LongLength - 1) {}
        Dim a As BigInteger
        For i As Integer = 0 To witness - 1
            Do
                gen.NextBytes(bytes)
                a = New BigInteger(bytes)

            Loop While a < 2 OrElse a >= value - 2
            Dim x As BigInteger = BigInteger.ModPow(a, d, value)
            If x = 1 OrElse x = value - 1 Then
                Continue For
            End If
            For r As Integer = 1 To s - 1
                x = BigInteger.ModPow(x, 2, value)
                If x = 1 Then
                    Return False
                End If
                If x = value - 1 Then
                    Exit For
                End If
            Next
            If x <> value - 1 Then
                Return False
            End If
        Next
        Return True
    End Function