# 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 Ruby program is an implementation of this coin-flipping algorithm:

#! /usr/bin/ruby

require '~/ruby/math_libraries/number_theory'

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

P_AND_Q_MIN = 10000000000
P_AND_Q_RANGE = 1000000000
p, q = nil, nil

loop do
  p = rand(P_AND_Q_RANGE) + P_AND_Q_MIN
  next if p % 4 != 3
  break if rabin_miller_certain(p)
end

loop do
  q = rand(P_AND_Q_RANGE) + P_AND_Q_MIN
  next if q % 4 != 3
  break if rabin_miller_certain(q) and q != p
end

n = p * q
puts "Alice chooses p = #{p} and q = #{q} and sends Bob pq = #{n}."

x0 = rand(n - 1) + 1
puts "\nBob picks a random number < #{n}, say #{x0}."

a = pow_mod(x0, 2, n)
puts "Bob calculates #{x0}^2 (mod #{n}) = #{a} and sends that number to Alice.\n\n"

a_p = a % p
puts "a_p = a (mod p) = #{a} (mod #{p}) = #{a_p}"
a_q = a % q
puts "a_q = a (mod q) = #{a} (mod #{q}) = #{a_q}"

x_1 = pow_mod(a_p, (p + 1) / 4, p)
puts "\nx_1 = a_p^(p + 1) / 4) = #{x_1} mod(#{p})"

x_2 = pow_mod(a_q, (q + 1) / 4, q)
puts "x_2 = a_q^(q + 1) / 4) = #{x_2} mod(#{q})"

solutions = []

def apply_crt(a_of_a)
  result = nil
  puts "\nUsing Chinese Remainder Theorem to solve:"
  a_of_a.each do |a|
    puts "x = #{a[0]} (mod #{a[1]})"
  end

  begin
    result = crt_1_variable(a_of_a)
    puts "\nx = #{result}"
  rescue RuntimeError => message
    puts message
  end
  result
end

a_of_a = [[x_1, p], [x_2, q]]
solutions << apply_crt(a_of_a)
a_of_a = [[x_1, p], [-x_2, q]]
solutions << apply_crt(a_of_a)
a_of_a = [[-x_1, p], [x_2, q]]
solutions << apply_crt(a_of_a)
a_of_a = [[-x_1, p], [-x_2, q]]
solutions << apply_crt(a_of_a)

puts "\nFour incongruent solutions are #{solutions}."
x_choice = solutions[rand(solutions.length)]
puts "\nAlice randomly chooses x = #{x_choice} and sends that number to Bob."

a_alice = pow_mod(x_choice, 2, n)
puts "\nBob first confirms that Alice's solution satisfies #{x_choice}^2 (mod #{n}) = #{a_alice} = #{a}."
fac_1 = gcd(n, x0 + x_choice)
# fac_2 = gcd(n, x0 + n - x_choice)
puts "Then Bob calculates gcd = gcd(#{n}, #{x0} + #{x_choice}) = #{fac_1}.\n\n"
if fac_1 == 1 or fac_1 == n
  puts "Alice wins because Bob cannot (easily) factor #{n}."
else
  fac_2 = n / fac_1
  puts "Bob wins by returning the factors of #{n} = #{fac_1} * #{fac_2}."
end

# End of Code

# Test Ouput 1 (Alice wins):

# Alice chooses p = 10525607167 and q = 10969572071 and sends Bob pq = 115461406409440632857.

# Bob picks a random number < 115461406409440632857, say 66392732473749671455.
# Bob calculates 66392732473749671455^2 (mod 115461406409440632857) = 59728962320512036916 and sends that number to Alice.

# a_p = a (mod p) = 59728962320512036916 (mod 10525607167) = 9080636939
# a_q = a (mod q) = 59728962320512036916 (mod 10969572071) = 1966551516

# x_1 = a_p^(p + 1) / 4) = 2288945383 mod(10525607167)
# x_2 = a_q^(q + 1) / 4) = 6798599059 mod(10969572071)

# Using Chinese Remainder Theorem to solve:
# x = 2288945383 (mod 10525607167)
# x = 6798599059 (mod 10969572071)

# x = 66392732473749671455

# Using Chinese Remainder Theorem to solve:
# x = 2288945383 (mod 10525607167)
# x = -6798599059 (mod 10969572071)

# x = 106671869176661610989

# Using Chinese Remainder Theorem to solve:
# x = -2288945383 (mod 10525607167)
# x = 6798599059 (mod 10969572071)

# x = 8789537232779021868

# Using Chinese Remainder Theorem to solve:
# x = -2288945383 (mod 10525607167)
# x = -6798599059 (mod 10969572071)

# x = 49068673935690961402

# Four incongruent solutions are [66392732473749671455, 106671869176661610989, 8789537232779021868, 49068673935690961402].

# Alice randomly chooses x = 49068673935690961402 and sends that number to Bob.

# Bob first confirms that Alice's solution satisfies 49068673935690961402^2 (mod 115461406409440632857) = 59728962320512036916 = 59728962320512036916.
# Then Bob calculates gcd = gcd(115461406409440632857, 66392732473749671455 + 49068673935690961402) = 115461406409440632857.

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

# Test Output 2 (Bob wins):

# Alice chooses p = 10992895699 and q = 10939450703 and sends Bob pq = 120256240582431226397.

# Bob picks a random number < 120256240582431226397, say 117879081866275307169.
# Bob calculates 117879081866275307169^2 (mod 120256240582431226397) = 116469475688532673740 and sends that number to Alice.

# a_p = a (mod p) = 116469475688532673740 (mod 10992895699) = 1319400212
# a_q = a (mod q) = 116469475688532673740 (mod 10939450703) = 5147255247

# x_1 = a_p^(p + 1) / 4) = 3281440073 mod(10992895699)
# x_2 = a_q^(q + 1) / 4) = 2598514182 mod(10939450703)

# Using Chinese Remainder Theorem to solve:
# x = 3281440073 (mod 10992895699)
# x = 2598514182 (mod 10939450703)

# x = 117879081866275307169

# Using Chinese Remainder Theorem to solve:
# x = 3281440073 (mod 10992895699)
# x = -2598514182 (mod 10939450703)

# x = 61028244257246182587

# Using Chinese Remainder Theorem to solve:
# x = -3281440073 (mod 10992895699)
# x = 2598514182 (mod 10939450703)

# x = 59227996325185043810

# Using Chinese Remainder Theorem to solve:
# x = -3281440073 (mod 10992895699)
# x = -2598514182 (mod 10939450703)

# x = 2377158716155919228

# Four incongruent solutions are [117879081866275307169, 61028244257246182587, 59227996325185043810, 2377158716155919228].

# Alice randomly chooses x = 59227996325185043810 and sends that number to Bob.

# Bob first confirms that Alice's solution satisfies 59227996325185043810^2 (mod 120256240582431226397) = 116469475688532673740 = 116469475688532673740.
# Then Bob calculates gcd = gcd(120256240582431226397, 117879081866275307169 + 59227996325185043810) = 10992895699.

# Bob wins by returning the factors of 120256240582431226397 = 10992895699 * 10939450703.