# Demo entry 1076741

Primality Tester

Submitted by anonymous on Jan 16, 2015 at 16:23
Language: C#. Code size: 3.8 kB.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Shapes;

namespace WpfApplication2
{
/// <summary>
/// Interaction logic for MainWindow.xaml
/// </summary>
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
}

private void button1_Click(object sender, RoutedEventArgs e)
{
System.Numerics.BigInteger p;
p = System.Numerics.BigInteger.Parse(textBox1.Text);

//k is the iteratation count for the IsPrime method
//which implements fermat's theorem
int k = 20;

if (IsPrime(p, k))
textBox2.Text = "yes with probability (1/2)^" + k;
else
textBox2.Text = "no";

}

//implements fermat's theorem where
//  -p is the big integer we look to evaluate
//  -k is the iterative count
private Boolean IsPrime(System.Numerics.BigInteger p, int k)
{
for (int i = 0; i < k; i++)
{
System.Numerics.BigInteger a = GetBigRandom(p);

if (modexp(a, p - 1, p) != 1)
return false;
}
return true;
}

//method for modular exponentiation where
//  -x is the random integer generated within the range of 1 to p-1
//  -y is the currently evaluated number-1
//  -N is the curretnly evaluated number
private System.Numerics.BigInteger modexp(System.Numerics.BigInteger x,
System.Numerics.BigInteger y,
System.Numerics.BigInteger N)
{
if (y == 0)
return 1;

System.Numerics.BigInteger z = modexp(x, y / 2, N);

if ((y % 2) == 0)
return (z * z) % N;
else
return x * (z * z) % N;
}

//retrieves a random number in the range of 1-(p-1) where
//  -p is the currently evaluated number
private System.Numerics.BigInteger GetBigRandom(System.Numerics.BigInteger p)
{
Random random = new Random();

//calculation for the number of bits needed to represent p
int length = (int) System.Numerics.BigInteger.Log(p, 2) +1;

System.Numerics.BigInteger big_random_value = 0;

bool hasValidRandom = false;

while (!hasValidRandom)
{
//generate 32 bit random chunks until we can cover the
//entire range 1-(p-1)
for (int i = 0; i < length / 32; i++)
big_random_value = (big_random_value << 32) + random.Next();

//if the number is small enough for integer value, generate
//within integer range using p as an upper bound
if (big_random_value == 0)
big_random_value = random.Next(2, (int)p);

//if the generated number is in the appropriate range, exit
//the while loop, otherwise continue iterating
if (big_random_value > 0 && big_random_value < p)
hasValidRandom = true;
}

//Console.Write(big_random_value);
return big_random_value;
}
}
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.