module type Params =
  sig
    val n : int
  end

module type MakeField = functor (P : Params) ->
  sig
    type t
    val n : int
    val q : int
    val irr : int
    val zero : t
    val one : t
    val (+) : t -> t -> t
    val (-) : t -> t -> t
    val minus : t -> t
    val ( * ) : t -> t -> t
    val inv : t -> t
    val ( / ) : t -> t -> t
    val pow : t -> int -> t
    val print : t -> unit
    val print_irr : unit -> unit
  end

module Make : MakeField = functor (P : Params) ->
  struct
    type t = Zero | Pow of int
    let n = P.n
    let q = 1 lsl n
    let irr = find_irr P.n
    let zero = Zero
    let one = Pow 0
    let add_table = make_table q n irr
    let rev_add_table = reverse_table q add_table
    let (+) a b =
        match a,b with
        | Zero,_ -> b
        | _,Zero -> a
        | (Pow x),(Pow y) ->
            let res = add_table.(x) lxor add_table.(y) in
            if res = 0 then Zero else Pow rev_add_table.(res-1)
    let (-) = (+)
    let minus (x:t) = x
    let ( * ) a b =
        match a,b with
        | Zero,_ -> Zero
        | _,Zero -> Zero
        | (Pow x),(Pow y) -> let c = ((x+y) mod (q-1)) in Pow c
    let inv = function
        | Zero -> raise (Invalid_argument "inv")
        | Pow 0 -> Pow 0
        | Pow a -> Pow (q - 1 - a)
    let ( / ) a b = a * (inv b)
    let pow p = function 0 -> one | n -> fast_exp ( * ) p n
    let print_irr () = print irr
    let print = function Zero -> Printf "0\n" | Pow a -> print add_table.(a)
  end