Fermat Primality Tester
Brandon Blatter
CS 312
View this report in your browser
Let's be honest. PDFs were not meant for displaying code, and code was not meant to be displayed in PDFs. Please view this report in your browser so it's easy to read.
Code
MainWindow.cs
using System;
using Gtk;
public partial class MainWindow
{
public MainWindow() : base(Gtk.WindowType.Toplevel)
{
Build();
}
protected void OnDeleteEvent(object sender, DeleteEventArgs a)
{
Application.Quit();
a.RetVal = true;
}
protected void ButtonWasClicked(object sender, EventArgs e)
{
this.outputEntry.Text = primality.MainClass.IsPrime(this.inputEntry.Text, this.kValueEntry.Text);
}
}
Program.cs
using System;
using Gtk;
using System.Numerics;
using System.Collections.Generic;
namespace primality
{
class MainClass
{
public static void Main(string[] args)
{
Application.Init();
MainWindow win = new MainWindow();
win.Show();
Application.Run();
}
public static BigInteger ModExp(BigInteger currentBase, BigInteger exponent, BigInteger modulus)
{
// return 1 if the exponent is 0
if(exponent == 0) return 1;
// bit shift the exponent by 1 to simulate floor division by 2
// bit shifting is O(n)
BigInteger halfExp = exponent >> 1;
// recurs n times for big O of O(n)
// use a BigInteger to store this result so we can handle big primes
BigInteger z = ModExp(currentBase, halfExp, modulus);
// modulus is O(n^2)
// if exponent is even
if(exponent % 2 == 0) return (z * z) % modulus;
// if exponent is odd
return (currentBase * ((z * z) % modulus)) % modulus;
}
public static String IsPrime(String primeCandidateString, String kValueString)
{
// warn users if they're using ridiculous k values
if (kValueString.Length > 6)
return "If you perform that calculation you'll be here for a loooooong time.";
// warn users if they're missing data
if(primeCandidateString == "" || kValueString == "")
return "Please enter values for input and K-value";
// convert strings to big integers
BigInteger primeCandidate = BigInteger.Parse(primeCandidateString);
BigInteger kValue = BigInteger.Parse(kValueString);
if (primeCandidate <= kValue + 1) return "Please enter a bigger prime candidate value or a smaller k value.";
// seed a new Random object
Random rand = new Random();
BigInteger currentBase = 0;
List<BigInteger> usedBases = new List<BigInteger>();
usedBases.Add(currentBase);
// set current unsureness to 1
decimal unsureness = 1;
// repeat n times where n = kValue, which multiplies the big O by k
for(BigInteger i = 0; i < kValue; i++)
{
// generate a random number
// cannot be already used
while(usedBases.Contains(currentBase)) {
// should be at least 2 because 0 and 1 will always be congruent to 1
// should be less than the prime candidate number
// cap it at 2^30 so we can generate integers for big prime candidates
currentBase = rand.Next(2, (int)(primeCandidate % 1073741824));
}
usedBases.Add(currentBase);
// if congruent to 1 (mod N) return definitely prime
if(ModExp(currentBase, primeCandidate - 1, primeCandidate) == 1) unsureness *= (decimal).5;
// else multiply unsureness by 1/2
else return primeCandidate + " is definitely composite.";
}
// calculate sureness that the prime candidate is prime
decimal sureness = (decimal)1 - unsureness;
return "There is a " + sureness + " probability that " + primeCandidate + " is prime.";
}
}
}
Time and Space Complexity
Time Complexity
The only time complexity we're concerned with is in the ModExp function. The for loop in the IsPrime function has a running time of O(1) because kValue is a constant unrelated to the size of the prime number candidate.
In ModExp, the largest big O caused every time the function is called occurs when the function multiplies
// if exponent is even
if(exponent % 2 == 0) return (z * z) % modulus;
// if exponent is odd
return (currentBase * ((z * z) % modulus)) % modulus;
This multiplies the function's complexity by O(n2).
Additional complexity occurs as a result of recursion.
BigInteger halfExp = (int)(exponent / 2);
BigInteger z = ModExp(currentBase, halfExp, modulus);
The function recurs O(n) times, where n is the length of the exponent in bits. Because the exponent's length in bits is reduced by 1 each time the function recurs, the big O is O(n).
The final big O is the product of these complexities, as the O(n2) function is executed O(n) times. The result is O (n2 • n) or O(n3).
Space Complexity
Everything in this program has a space complexity of O(1) besides the stack used in the modular exponentiation function when it recurs. This is because in the rest of the program no data is stored besides that in single variables (no arrays, heaps, maps, matrices, etc. are used).
The stack in the modular exponentiation function will grow by one entry each time the function recurs, which we already know to occur O(n) times, where n is the length of the exponent in bits. Therefore the space complexity of the entire program is O(n).
Probability of Correctness
To calculate the probability of correctness, I first set a base variable called unsureness to 1. I then multiply unsureness by .5 each time a randomly generated number successfully passes the Fermat test. After the loop is completed, I subtract unsureness from 1 to get a final probability of correctness.
In a worst case scenario, a composite number has a .5 probability of failing the Fermat test. Each time a prime candidate number passes the Fermat test, we can be .5 times as sure that it is a prime number.