# Arup Guha
# 11/5/2020
# Miller Rabin Primality Test

'''
Edited by Seth Jones for CIS 3362 Homework #5 Solution (question 8)
'''

import random
import math

# Returns (base**exp) % mod, efficiently.
def fastmodexpo(base,exp,mod):

    # Base case.
    if exp == 0:
        return 1

    # Speed up here with even exponent.
    if exp%2 == 0:
        tmp = fastmodexpo(base,exp//2,mod)
        return (tmp*tmp)%mod

    # Odd case, must just do the regular ways.
    return (base*fastmodexpo(base,exp-1,mod))%mod

# Returns the gcd of a and b.
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)

def millerrabin(n):

    # Choose random base for Miller Rabin.
    a = random.randint(2,n-2)

    # Set up our base exponent.
    baseexp = n-1
    k = 0

    # Divide out 2 as many times as possible from n-1.
    while baseexp%2 == 0:
        baseexp = baseexp//2
        k += 1

    # Calculate first exponentiation.
    curValue = pow(a, baseexp, n)

    # Here we say it's probably prime.
    if curValue == 1:
        return True

    for i in range(k):

        # Must happen for all primes, and more rarely for composites.
        if curValue == n-1:
            return True

        # We just square it to get to the next number in the sequence.
        else:
            curValue = (curValue*curValue)%n

    # If we get here, it must be composite.
    return False

def isprobablyprime(n, numTimes):

    # Run Miller Rabin numTimes times.
    for i in range(numTimes):

        # If it ever fails, immediately return that the number is definitely
        # composite.
        tmp = millerrabin(n)
        if not tmp:
            return False

    # If we get here, it's probably prime.
    return True

# Simple test I can check with primes online.
def testmillerrabin():

    for i in range(1000000000,1000001000):
        if isprobablyprime(i, 50):
            print(i)

'''
Added code for the test
'''

counts = []
lns = []
for i in range(4):
    counts.append(0)

for i in range(100000):
    rand = random.randint(pow(10,15),pow(10,16))
    if(isprobablyprime(rand,50)):
        counts[0] += 1
    rand = random.randint(pow(10,50),pow(10,51))
    if(isprobablyprime(rand,50)):
        counts[1] += 1
    rand = random.randint(pow(10,100),pow(10,101))
    if(isprobablyprime(rand,50)):
        counts[2] += 1
    rand = random.randint(pow(10,300),pow(10,301))
    if(isprobablyprime(rand,50)):
        counts[3] += 1


for count in counts:
    print(count/100000)

print(1/math.log(pow(10,15)))
print(1/math.log(pow(10,50)))
print(1/math.log(pow(10,100)))
print(1/math.log(pow(10,300)))
