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

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

        //Uses Fermats Little Thm
        private void solve_Click(object sender, EventArgs e)
        {
            long N = Convert.ToInt64(input.Text);
            long k = Convert.ToInt64(k_value.Text);
            Random random = new Random();
            for (int i = 1; i <= k && i <= (N-1); i++) //Run k tests, max N-1 since the set of numbers to test a^(N-1) must be between 1 and N-1
            {
                int random = rdm.Next(1, (int)N); //Random.Next is O(1) according to docs
                if (Modexp(random, N - 1, N) != 1)
                {
                    output.Text = "Nope, it's not prime";
                    return;
                }
            }

            output.Text = "Yes! It's prime with probability " + ((long)1 - ((long)1 / Math.Pow(2, k)));
        }

        //This is O(n^3). You have at most O(n) levels of recursion and the multiplication in the recursion is O(n^2)
        private long Modexp(int x, long e, long N)
        {
            if (e == 0)
                return 1;
            long z = Modexp(x, e/2, N); //Note: C# integer division automatically floors
            if (e % 2 == 0) return (z * z) % N;
            else return (x * ((z * z) % N)) % N;
        }
    }
}