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.Navigation;
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.

Delete this entry (admin only).