import Random

--Extended GCG algorithm
extd_gcd :: (Int,Int) -> (Int,Int)
extd_gcd (a,b) = 
  if a `mod` b == 0 then (0,1)
  else let
    (x,y) = extd_gcd (b, a `mod` b)
  in
    (y, x-y*(a `div` b))

--Decide if two given numbers are coprime
coprime :: Int -> Int -> Bool
coprime x y = gcd x y == 1

--Coompute the totient : phi(n) = (p-1) * (q-1)
totient :: Int -> Int
totient 1 = 1
totient a = length $ filter (coprime a) [1..a-1]

--A list of 24 large prime numbers to randomly choose p and q from
primes :: [Int]
--primes = [9990510001,9990510011,9990510043,9990510067,9990512687,9990512711,9990512761,9990512767,9990514777,9990514829,9990514837,9990514871,9990515809,9990515831,9990515839,9990515869,9990517783,9990517787,9990517799,9990517807,9990519601,9990519607,9990519629,9990519641]
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89]

--n is the product of p and q
n :: (Int,Int) -> Int
n (a,b) =
  primes!!a * primes!!b

--e is the public key
e :: Int
e = 65537

--d is the private key
d :: Int -> Int -> Int
d fi k = if ((1 + k * fi) `mod` e) == 0 then ((1 + k * fi) `div` e) else d fi k+1

--foo returns two random numbers between 1 and 24 in order to choose p and q from primes list
foo = do
    g <- newStdGen
    let (r1', g1) = random g
    let (r2', _) = random g1
    let r1 = r1' `mod` 24 :: Int
    let r2 = r2' `mod` 24 :: Int
    return (r1, r2)

--The main function of our program
main = do
    (r1, r2) <- foo
    putStrLn $ show r1
    putStrLn $ show r2
    putStrLn $ show $ totient $ n (r1,r2)
    putStrLn (show (d (totient (n (r1,r2))) 1))