-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
FermatPrimeChecker.cs
45 lines (38 loc) · 1.48 KB
/
FermatPrimeChecker.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using System;
using System.Numerics;
namespace Algorithms.Other;
/// <summary>
/// Fermat's prime tester https://en.wikipedia.org/wiki/Fermat_primality_test.
/// </summary>
public static class FermatPrimeChecker
{
/// <summary>
/// Checks if input number is a probable prime.
/// </summary>
/// <param name="numberToTest">Input number.</param>
/// <param name="timesToCheck">Number of times to check.</param>
/// <returns>True if is a prime; False otherwise.</returns>
public static bool IsPrime(int numberToTest, int timesToCheck)
{
// You have to use BigInteger for two reasons:
// 1. The pow operation between two int numbers usually overflows an int
// 2. The pow and modular operation is very optimized
var numberToTestBigInteger = new BigInteger(numberToTest);
var exponentBigInteger = new BigInteger(numberToTest - 1);
// Create a random number generator using the current time as seed
var r = new Random(default(DateTime).Millisecond);
var iterator = 1;
var prime = true;
while (iterator < timesToCheck && prime)
{
var randomNumber = r.Next(1, numberToTest);
var randomNumberBigInteger = new BigInteger(randomNumber);
if (BigInteger.ModPow(randomNumberBigInteger, exponentBigInteger, numberToTestBigInteger) != 1)
{
prime = false;
}
iterator++;
}
return prime;
}
}