Is this the correct implementation of Fermat's Primality Test?

[user366312]

Homework Statement

I need to implement Fermat's primality tester in Python. I don't know Python very well. So, I am implementing it in C#. If I succeed, I will convet it to Python.

Relevant Equations

https://en.wikipedia.org/wiki/Fermat_primality_test

[CODE lang="csharp" title="Fermat's Primality Tester" highlight="17"]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();
}
}[/CODE]

[CODE title="Output"]An unhandled exception of type 'System.OverflowException' occurred in mscorlib.dll

Additional information: Arithmetic operation resulted in an overflow.[/CODE]

I have two questions:

1. Is this implementation correct? If not, why?
2. How to get rid of this overflow exception?

 

[Mark44]

Homework Statement:: I need to implement Fermat's primality tester in Python. I don't know Python very well. So, I am implementing it in C#. If I succeed, I will convet it to Python.
Relevant Equations:: https://en.wikipedia.org/wiki/Fermat_primality_test

[CODE lang="csharp" title="Fermat's Primality Tester's Primality Tester" highlight="17"]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();
}
}[/CODE]

[CODE title="Output"]An unhandled exception of type 'System.OverflowException' occurred in mscorlib.dll

Additional information: Arithmetic operation resulted in an overflow.[/CODE]

I have two questions:

1. Is this implementation correct? If not, why?
2. How to get rid of this overflow exception?

1. Is the implementation correct? No. As noted in the wiki article, this primality test is probabilistic. It will determine that a number is composite, or that it probably is prime. In your code, you have declared a Random object, but you never use it. Since you want to determine that 33 is prime or not, your code should loop through the numbers in the range 2 through 31.
2. You can't avoid the overflow exception as long as you are limited to using the Int64 type for your numbers. In running your program, in the first iteration, it attempts to convert a number that is about $8.34 \times 10^{40}$, which is larger than $2^{123}$. This is way too large to fit into 64 bits -- the largest unsigned 64-bit integer is $2^{64} - 1$.
You can however, use a different type, the BigInteger struct (https://docs.microsoft.com/en-us/dotnet/api/system.numerics.biginteger?view=netframework-4.8), which allows you to work with arbitrarily large integer values, similar to what Python offers. The BigInteger struct also provides a set of methods for arithmetic, including a method called ModPow (https://docs.microsoft.com/en-us/dotnet/api/system.numerics.biginteger.modpow?view=netframework-4.8) that would be useful for what you're trying to do.

 

[user366312]

In your code, you have declared a Random object, but you never use it.

That is not true. I used that. see closely kindly.

 

[sysprog]

That is not true. I used that. see closely kindly.

I looked and saw it defined but not used; can you please tell us on what line you called or used your 'Random' object?

 

[user366312]

I looked and saw it defined but not used; can you please tell us on what line you called or used your 'Random' object?

see line#11.

 

[sysprog]

I looked and saw it defined but not used; can you please tell us on what line you called or used your 'Random' object?

see line#11.

It looks to me to be the case that line 11:a = r.Next(1, Convert.ToInt32(n - 1)); [/size]is inside the 'Random' object and does not call it --

 

[user366312]

It looks to me to be the case that line 11:a = r.Next(1, Convert.ToInt32(n - 1)); is inside the 'Random' object and does not call it --

lol

 

[Mark44]

It looks to me to be the case that line 11:a = r.Next(1, Convert.ToInt32(n - 1)); is inside the 'Random' object and does not call it --

No, the Random object r is being used here. The Next() method is one of three overloaded methods on the Random class. The variable a is being set to a random integer between 1 and 32 here.

It's easy to overlook variables with single-letter names. I didn't pick up on the fact that the Random object was being used, and it appears that you (@sysprog) missed it as well.

My other comment about the size limitations on 64-bit integers is still applicable, though.

 

[sysprog]

You're right, @Mark44 and @user366312; I missed that.