Demo entry 1076395

Project 1

   

Submitted by anonymous on Jan 15, 2015 at 07:54
Language: C#. Code size: 2.5 kB.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void solve_Click(object sender, EventArgs e)
        {
            BigInteger inputValue = BigInteger.Parse(input.Text);
            var k = 20;
            Random rand = new System.Random();
            Boolean hasFailed = false;
            for (int i = 0; i < k; i++)
            {
                BigInteger random_number = 0;
                while (true)
                {
                    random_number = 0;
                    for (int j = 0; j < Math.Ceiling((BigInteger.Log(inputValue, 2) + 1) / 32) / 2; j++)
                    {
                        random_number = (random_number << 32) + rand.Next();
                    }
                    Console.WriteLine("I am generating random numbers " + random_number.ToString());
                    random_number = random_number % inputValue;
                    if (random_number > 0 && random_number < inputValue)
                    {
                        break;
                    }

                }
                if (myModExp(random_number, inputValue - 1, inputValue) == 1)
                {
                    
                }
                else
                {
                    hasFailed = true;
                }
            }
            if (!hasFailed)
            {
                output.Text = "yes with probability " + (1 - (Math.Pow(.5, k)));
            }
            else 
            {
                output.Text = "no";
            }
        }

        private BigInteger myModExp(BigInteger random, BigInteger exponent, BigInteger input)
        {
            Console.WriteLine("running myModExp");
            if (exponent == 0)
            {
                return 1;
            }

            var z = myModExp(random, exponent / 2, input);

            if (exponent.IsEven)
            {
                return (z * z) % input;
            }
            else
            {
                return (random * (z * z) % input);
            }
        }
    }
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).