assig6.hs

{-# LANGUAGE BangPatterns #-}

import Numeric

modexp !x !e !m = go x e 1
    where mod' = flip mod m
          go _ 0 !z = mod' z
          go !x !e !z = go (mod' x^2) q (if r == 0 then z else (mod' (x*z)))
                where (q,r) = quotRem e 2

exgcd _ 0 = (1,0)
exgcd !a !b = (t, s - q*t)
    where (!q,!r) = quotRem a b
          (!s,!t) = exgcd b r

modInv a n = flip mod n . fst $ exgcd a n

intsqrt n = go 0 n
    where go !lo !hi
            | lo == hi   = hi
            | mid^2 >= n = go lo mid
            | otherwise  = go (mid+1) hi
                where mid = (lo + hi) `div` 2

solve1 = solve2
solve2 n = head . filter (\(x,y) -> x*y == n) . map f $ [a0..]
    where a0 = intsqrt n
          f a = (a-x, a+x)
            where x = intsqrt $ a^2 - n

solve3 n = ((a-x) `div` 6, (a+x) `div` 4)
    where a = intsqrt $ 24*n
          x = intsqrt $ 4*((a^2 `div` 4) - 6*n)

solve4 cyph (p,q) e n = toHex $ modexp cyph d n
    where d = modInv e phi
          phi = (p-1) * (q-1)
          toHex n = showHex n ""

main = do
    print $ fst . solve1 $ a
    print $ fst . solve2 $ b
    print $ fst . solve3 $ c
    print $ solve4 d (solve1 a) 65537 a

a = 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
b = 648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877
c = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
d = 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540