# Let's call our parties Alice and Bob and we are going to assume throughout that neither party trusts the other one. (If they did trust each other, one
# of them would simply flip a coin and tell the other one the result!) In our scheme, Bob's job will be to factor a number Alice provides him. If he
# succeeds in factoring the number, he wins the flip, and if not, Alice wins. The math, number theory in this case, involves the Chinese Remainder Theorem
# and a criterion developed by Euler. Neither of these proofs are recent, so presumably this coin-flipping algorithm could have been applied 150 years ago.

# This method, like RSA encryption, relies on the difficulty of factoring large numbers. Non-intuitive as it seems, it is substantially easier to test a
# number to see if it is prime, than it is to find the factors of a composite (non-prime) number. Alice starts the process by generating two odd primes,
# p and q, and sending Bob their product n. Since Bob will win the flip if he can factor n, Alice generates a number that
# she is confident cannot be factored in a reasonable amount of time by computer. Remember, this whole "flipping" process should only take a few minutes at
# most, and almost all of that time is spent exchanging numbers electronically.

# Bob generates a random number less than n, squares that number, takes its n modulus, call it a, and returns a to Alice.
# The random number that Bob used to generate a is its square root, but it is one of 4 square roots of a. Using the Chinese Remainder
# Theorem and Euler's Criterion, Alice can compute the other 3 square roots of a, but, and this is crucial to the operation of the algorithm, she has
# no idea which of the 4 square roots Bob used to generate a.

# Alice randomly selects one of the roots and sends it to Bob. First Bob checks that the number Alice sent is a square root of n and is not bogus.
# Two of those roots, and, of course, not the one Bob started with (which Alice doesn't know), can be used with Euclid's greatest common divisor algorithm to
# factor n. So 50% of the time Bob will be able to factor Alice's original number. If Bob can do the factorization, he sends Alice p and q,
# he wins, and Alice knows it.

# In the event that Bob cannot factor Alice's number, he asks her to forward her choices for p and q to confirm that their product is the
# number she sent him initially and that each is congruent to 3 mod 4 (another requirement on Alice's choice of primes). When everything checks out, Bob
# is convinced that Alice played fair and that she won the "toss".

# The following Python program is an implementation of this coin-flipping algorithm:

#!/usr/local/bin/python3

from random import random, randrange
from fractions import gcd
from number_theory import rabin_miller_certain, pow_mod, crt_1_variable

# Single application of electronic coin-flipping algorithm, pg. 340-1 Rosen, 3rd Edition

P_AND_Q_MIN, P_AND_Q_RANGE = 10000000000, 1000000000

while True:
    p = randrange(P_AND_Q_RANGE) + P_AND_Q_MIN
    if p % 4 != 3:
        continue
    if rabin_miller_certain(p):
        break
while True:
    q = randrange(P_AND_Q_RANGE) + P_AND_Q_MIN
    if q % 4 != 3:
        continue
    if rabin_miller_certain(q) and q != p:
        break

n = p * q
print('Alice chooses p = {0:d} and q = {1:d} and sends Bob pq = {2:d}.'.format(p, q, n))

x0 = randrange(n - 1) + 1
print('\nBob picks a random number < {0:d}, say {1:d}.'.format(n, x0))

a = pow_mod(x0, 2, n)
print('\nBob calculates {0:d}^2 (mod {1:d}) = {2:d} and sends that number to Alice.\n'.format(x0, n, a))

a_p = a % p
print('a_p = a (mod p) = {0:d} (mod {1:d}) = {2:d}'.format(a, p, a_p))
a_q = a % q
print('a_q = a (mod q) = {0:d} (mod {1:d}) = {2:d}'.format(a, q, a_q))

x_1 = pow_mod(a_p, (p + 1) // 4, p)
print('\nx_1 = a_p^(p + 1) / 4) = {0:d} mod({1:d})'.format(x_1, p))
x_2 = pow_mod(a_q, (q + 1) // 4, q)
print('x_2 = a_q^(q + 1) / 4) = {0:d} mod({1:d})'.format(x_2, q))

def apply_crt(t_of_t):
    print('\nUsing Chinese Remainder Theorem to solve:')
    for a_t in t_of_t:
        print('x = {0:d} (mod {1:d})'.format(a_t[0], a_t[1]))
    try:
        result = crt_1_variable(t_of_t)
        print('\nx =', result)
    except DataError as e:
        print('\nDataError exception occurred:', e.value)
    
    return result

solutions = []

t_of_t = ((x_1, p), (x_2, q))
solutions.append(apply_crt(t_of_t))
t_of_t = ((x_1, p), (-x_2, q))
solutions.append(apply_crt(t_of_t))
t_of_t = ((-x_1, p), (x_2, q))
solutions.append(apply_crt(t_of_t))
t_of_t = ((-x_1, p), (-x_2, q))
solutions.append(apply_crt(t_of_t))

print('\nFour incongruent solutions are:', solutions, '.')
x_choice = solutions[randrange(len(solutions))]
print('\nAlice randomly chooses x =', x_choice, 'and sends that number to Bob.')
a_alice = pow_mod(x_choice, 2, n)
print('Bob first confirms that Alice\'s solution satisfies {0:d}^2 (mod {1:d}) = {2:d} = {3:d}.'.format(x_choice, n, a_alice, a))
fac_1 = gcd(n, x0 + x_choice)
print('Then Bob calculates gcd = gcd({0:d}, {1:d} + {2:d}) = {3:d}.\n\n'.format(n, x0, x_choice, fac_1))
if fac_1 == 1 or fac_1 == n:
    print('Alice wins because Bob cannot (easily) factor', n, '.')
else:
    fac_2 = n // fac_1
    print('Bob wins by returning the factors of', n, '=', fac_1, '*', fac_2, '.')

# End of Code

# Test Ouput 1 (Alice wins):

# Alice chooses p = 10625745343 and q = 10414902359 and sends Bob pq = 110666100238943964137.

# Bob picks a random number < 110666100238943964137, say 2930932775883526600.

# Bob calculates 2930932775883526600^2 (mod 110666100238943964137) = 90834303625468593944 and sends that number to Alice.

# a_p = a (mod p) = 90834303625468593944 (mod 10625745343) = 10572239851
# a_q = a (mod q) = 90834303625468593944 (mod 10414902359) = 2654235935

# x_1 = a_p^(p + 1) / 4) = 9328987522 mod(10625745343)
# x_2 = a_q^(q + 1) / 4) = 9238476508 mod(10414902359)

# Using Chinese Remainder Theorem to solve:
# x = 9328987522 (mod 10625745343)
# x = 9238476508 (mod 10414902359)

# x = 101112873596480924924

# Using Chinese Remainder Theorem to solve:
# x = 9328987522 (mod 10625745343)
# x = -9238476508 (mod 10414902359)

# x = 2930932775883526600

# Using Chinese Remainder Theorem to solve:
# x = -9328987522 (mod 10625745343)
# x = 9238476508 (mod 10414902359)

# x = 107735167463060437537

# Using Chinese Remainder Theorem to solve:
# x = -9328987522 (mod 10625745343)
# x = -9238476508 (mod 10414902359)

# x = 9553226642463039213

# Four incongruent solutions are: [101112873596480924924, 2930932775883526600, 107735167463060437537, 9553226642463039213] .

# Alice randomly chooses x = 2930932775883526600 and sends that number to Bob.
# Bob first confirms that Alice's solution satisfies 2930932775883526600^2 (mod 110666100238943964137) = 90834303625468593944 = 90834303625468593944.
# Then Bob calculates gcd = gcd(110666100238943964137, 2930932775883526600 + 2930932775883526600) = 1.

# Alice wins because Bob cannot (easily) factor 110666100238943964137 .

# Test Output 2 (Bob wins):

# Alice chooses p = 10307037959 and q = 10677961963 and sends Bob pq = 110058159277399153517.

# Bob picks a random number < 110058159277399153517, say 67651847318516044956.

# Bob calculates 67651847318516044956^2 (mod 110058159277399153517) = 3566685500757706995 and sends that number to Alice.

# a_p = a (mod p) = 3566685500757706995 (mod 10307037959) = 920088490
# a_q = a (mod q) = 3566685500757706995 (mod 10677961963) = 3346726104

# x_1 = a_p^(p + 1) / 4) = 2583504146 mod(10307037959)
# x_2 = a_q^(q + 1) / 4) = 324182031 mod(10677961963)

# Using Chinese Remainder Theorem to solve:
# x = 2583504146 (mod 10307037959)
# x = 324182031 (mod 10677961963)

# x = 48693017205594935493

# Using Chinese Remainder Theorem to solve:
# x = 2583504146 (mod 10307037959)
# x = -324182031 (mod 10677961963)

# x = 67651847318516044956

# Using Chinese Remainder Theorem to solve:
# x = -2583504146 (mod 10307037959)
# x = 324182031 (mod 10677961963)

# x = 42406311958883108561

# Using Chinese Remainder Theorem to solve:
# x = -2583504146 (mod 10307037959)
# x = -324182031 (mod 10677961963)

# x = 61365142071804218024

# Four incongruent solutions are: [48693017205594935493, 67651847318516044956, 42406311958883108561, 61365142071804218024] .

# Alice randomly chooses x = 48693017205594935493 and sends that number to Bob.
# Bob first confirms that Alice's solution satisfies 48693017205594935493^2 (mod 110058159277399153517) = 3566685500757706995 = 3566685500757706995.
# Then Bob calculates gcd = gcd(110058159277399153517, 67651847318516044956 + 48693017205594935493) = 10677961963.

# Bob wins by returning the factors of 110058159277399153517 = 10677961963 * 10307037959 .