c# - 为什么这个费马素数测试仪给了我一个例外？

Question

为什么这个费马素数测试仪给了我一个例外？

class PrimeTest
{
    public static bool IsPrime(long n, int iteration = 5)
    {
        Random r = new Random();
        long a = 0;
        long aPow = 0;

        for (int i = 0; i < iteration; i++)
        {
            a = r.Next(1, Convert.ToInt32(n - 1));

            double x = Convert.ToDouble(a);
            double y = Convert.ToDouble(n - 1);
            double p = Math.Pow(x, y);

            aPow = Convert.ToInt64(p);//<==== this line is giving an exception.

            if (1 % n == aPow % n)
            {
                return true;
            }
        }

        return false;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("{0}", PrimeTest.IsPrime(33));
        Console.ReadLine();
    }
}

输出

An unhandled exception of type 'System.OverflowException' occurred in mscorlib.dll

Additional information: Arithmetic operation resulted in an overflow.

标签： c#primes

Answer 1

你a是一个随机数 [1~n-1]，a^(n-1) 可以很容易地大于Int64.Max 例如 a=10 和 10^32 大于 Int64.Max。

        Random r = new Random();
        long a = 0;
        long aPow = 0;

        for( int i = 0; i < iteration; i++ ) {
            a = r.Next( 1, Convert.ToInt32( n - 1 ) );

            // p is 1E32; if a==10
            double p = Math.Pow( Convert.ToDouble( a ), Convert.ToDouble( n - 1 ) );

            // Int64 is 9223372036854775807, which is less than 1E32
            aPow = Convert.ToInt64( p ); //giving exception

            if( 1 % n == aPow % n ) {
                return true;
            }
        }

        return false;