import random

def extendedEuclidean(x, N):
    A, B = N, x
    U, V = 0, 1
    while True:
        q = A//B
        temp1, temp2 = B, A + (-q * B)
        A, B = temp1, temp2
        temp1, temp2 = V, U + (-q * V)
        U, V = temp1, temp2
        if B == 0:
            break
    d, u = A, U
    v = (d - x * u) // N
    return (u, v, d)

print(extendedEuclidean(10,13))

# Zadanie 1
def generateRandomInteger(n, k):
    try:
        assert k > 0, "You need at least one bit to write an integer"
        assert n > 0, "Cannot divide by 0"
        if k == 1:
            minValue = 0
            maxValue = 1
        else:
            assert 2**(k-1) < n, "No numbers to choose from"
            minValue = 2**(k-1)
            maxValue = (2**k)-1
        generator = random.SystemRandom()
        while True:
            randomNumber = generator.randint(minValue, maxValue)
            if randomNumber < n:
                break
        print(randomNumber)
    except AssertionError as error:
        print("Error: {}".format(error))
        main()

# Zadanie 2
def inverseValueInPhi(n, b):
    value = 0
    found = False
    for i in range(1, n):
        value = (i * b) % n
        if value == 1:
            if extendedEuclidean(n, value)[2] == 1:
                found = True
                value = i
                break
    if found:
        print("Result: {}".format(value))
    else:
        print("Result: No inverse number exists")

# Zadanie 3
def exponentialSquaring(n, k, b):
    temp = 1
    while (k > 0):
        if (k % 2 != 0):
            temp = (temp * b) % n
        b = (b * b) % n
        k = k // 2
    return(temp % n)

# Zadanie 4
def quadricResidue(p, b):
    try:
        assert p > 2, "p must be higher than 2"
        if exponentialSquaring(p, (p-1)/2, b) == 1:
            return True
        else:
            return False
    except AssertionError as error:
        print("Error: {}".format(error))
        main()

# Zadanie 5
def squareRoot(p, b):
    try:
        assert p % 4 == 3, "p mod 4 != 3"
        assert quadricResidue(p, b), "b is not a quadric residue in p"
        print("{}" . format(p))
        for i in range(0, p):
            a = exponentialSquaring(p, (p+1)//4, i)
            print("%d %d %d" % (i, a, b, ))
            if a == b:
                return("Result: {}".format(i))
        return False
    except AssertionError as error:
        print("Error: {}".format(error))
        main()

# Zadanie 6
def primalityTest(n):
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    generator = random.SystemRandom()
    counter = generator.randint(n//2, n)
    while(counter != 0):
        b = generator.randint(2, n-2)
        if exponentialSquaring(n, n-1, b) != 1:
            return False
        counter = counter - 1
    return True

# User interface
def main():
    while True:
        print("""
              Choose function:
              Type "1 n k" for generateRandomInteger(n,k)
              Type "2 n b" for inverseValueInPhi(n, b)
              Type "3 n k b" for exponentialSquaring(n, k, b)
              Type "4 p b" for quadricResidue(p, b)
              Type "5 p b" for squareRoot(p,b)
              Type "6 n" for primalityTest(n)
              Type "exit" to end program's execution
              """)
        userInput = input("Choose desired action: ")
        if userInput == "exit":
                exit()
        userInput = list(map(int, userInput.split(" ")))
        if userInput[0] == 1:
            for i in range(0, int(input("How many times to run the function?: "))):
                  generateRandomInteger(userInput[1], userInput[2])
        elif userInput[0] == 2:
            inverseValueInPhi(userInput[1], userInput[2])
        elif userInput[0] == 3:
            print("Result: {}".format(exponentialSquaring(userInput[1], userInput[2], userInput[3])))
        elif userInput[0] == 4:
            print("Result: {}".format(quadricResidue(userInput[1], userInput[2])))
        elif userInput[0] == 5:
            print(squareRoot(userInput[1], userInput[2]))
        elif userInput[0] == 6:
            print("Result: {}".format(primalityTest(userInput[1])))
        else:
            print("Error: Wrong instruction. Try again")

if __name__ == "__main__":
    main()