## Fast Fourier Transform

fft [a] = a

fft l@(a:rest) =

let n = length l

omega = e**(2*pi*i/n)

evens = everyother l

odds = everyother rest

evenfft = fft evens

oddfft = fft odds

y m = evenfft !! m + omega * oddfft !! m

z m = evenfft !! m - omega * oddfft !! m

in

concat

(map y [0..n/2])

(map z [0..n/2])

## Private-Key Cryptosystems

#### Function s often known, but requires a special value, a key

###### Currying fun!

mycrypt message = encrypt key message

mycrypt = encrypt key

## Or, in Code

#### A writes to B, or decodes from B:

module A (Apublic) where

import B

codeForB message = Bpublic Asecret message

#### And vice versa, B to A:

module B (Bpublic) where

import A

codeForA message = Apublic Bsecret message

## RSA in Code

encode n e msg = mod (msg^e) n

toAfromB n b a msg =

let rsa = encode n in

rsa b (rsa a msg)

#### And in use....

let p = 17

q = 19

n = p * q

phi = (p-1) * (q-1) -- 16 * 18 = 288

e = 23

d = 263 in

encode n e msg

## Efficient Modular Powers

#### Mod "inside" or "outside"

-- O(n), but bounded by n

encode' n 0 msg = 1

encode' n 1 msg = mod msg n

encode' n e msg = mod ((mod (msg * msg) n) *

(encode' n (e-1) msg)) n

#### Log-n

encode'' n 0 msg = 1

encode'' n 1 msg = mod msg n

encode'' n e msg =

let bits = bitsrep e

modexp a n d b' =

if d then mod (d * d * a) n

else mod (d * d) n

in foldr1 (modexp msg n 1) bitsrep