Package group: Parametric theory of groups

Information

name	group
version	1.9
description	Parametric theory of groups
author	Joe Leslie-Hurd <joe@gilith.com>
license	MIT
requires	bool group-witness list natural natural-bits natural-fibonacci pair
show	Algebra.Group Data.Bool Data.List Data.Pair Number.Natural

Files

Package tarball group-1.9.tgz
Theory source file group.thy (included in the package tarball)

Defined Constants

Algebra
- Group
  - *
  - -
  - multAdd
  - multSub
  - ElGamal
    - ElGamal.decrypt
    - ElGamal.encrypt

Theorems

⊦ ∀x. x * 0 = 0

⊦ ∀x. x + 0 = x

⊦ ∀n. 0 * n = 0

⊦ ∀x. x * 1 = x

⊦ ∀x. x + ~x = 0

⊦ ∀z x. multAdd z x [] = z

⊦ ∀x. x * 2 = x + x

⊦ ∀x y. x - y = x + ~y

⊦ ∀x y. x + (~x + y) = y

⊦ ∀x y. ~x + (x + y) = y

⊦ ∀x n. x * n = multAdd 0 x (Bits.fromNatural n)

⊦ ∀x n. x * suc n = x + x * n

⊦ ∀x n. x * suc n = x * n + x

⊦ ∀x n. x * n = multSub ⊤ 0 0 x 0 (Fibonacci.encode n)

⊦ ∀x y z. x + (y + z) = y + (x + z)

⊦ ∀z x l. multAdd z x l = z + x * Bits.toNatural l

⊦ ∀x m n. x * (m * n) = x * m * n

⊦ ∀x a b. ElGamal.decrypt x (a, b) = ~(a * x) + b

⊦ ∀x m n. x * (m + n) = x * m + x * n

⊦ ∀g h m k. ElGamal.encrypt g h m k = (g * k, h * k + m)

⊦ ∀g h m k x. h = g * x ⇒ ElGamal.decrypt x (ElGamal.encrypt g h m k) = m

⊦ ∀b n d f p. multSub b n d f p [] = if b then n - d else d - n

⊦ ∀x n y. x + y = y + x ⇒ x * n + y = y + x * n

⊦ ∀x n y. y + x = x + y ⇒ y + x * n = x * n + y

⊦ ∀z x h t.
multAdd z x (h :: t) = multAdd (if h then z + x else z) (x + x) t

⊦ ∀b n d f p h t.
multSub b n d f p (h :: t) =
let s ← p - f in multSub (¬b) d (if h then n - s else n) s f t

⊦ ∀x n d f p l.
    x + n = n + x ∧ x + d = d + x ⇒
    multSub ⊤ n d (x * f) (~(x * p)) l =
    n - d + x * Fibonacci.decode.dest f p l ∧
    multSub ⊥ n d (~(x * f)) (x * p) l =
    d - n + x * Fibonacci.decode.dest f p l

External Type Operators

→
bool
Algebra
- Group
  - group
Data
- List
  - list
- Pair
  - ×
Number
- Natural
  - natural

External Constants

=
select
Algebra
- Group
  - +
  - ~
  - 0
Data
- Bool
  - ∀
  - ∧
  - ⇒
  - ∃
  - ∃!
  - ∨
  - ¬
  - cond
  - ⊥
  - ⊤
- List
  - ::
  - []
- Pair
  - ,
  - fst
  - snd
Number
- Natural
  - *
  - +
  - bit0
  - bit1
  - suc
  - zero
  - Bits
    - Bits.fromNatural
    - Bits.toNatural
  - Fibonacci
    - Fibonacci.decode
      - Fibonacci.decode.dest
    - Fibonacci.encode

Assumptions

⊦ ⊤

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ bit0 0 = 0

⊦ Bits.toNatural [] = 0

⊦ (∃) = λp. p ((select) p)

⊦ ∀t. (∀x. t) ⇔ t

⊦ (∀) = λp. p = λx. ⊤

⊦ ∀t. ⊤ ∧ t ⇔ t

⊦ ∀t. t ∧ t ⇔ t

⊦ ∀x. 0 + x = x

⊦ ∀n. Bits.toNatural (Bits.fromNatural n) = n

⊦ ∀n. Fibonacci.decode (Fibonacci.encode n) = n

⊦ ∀m. m * 0 = 0

⊦ ∀n. 0 + n = n

⊦ ∀x. ~x + x = 0

⊦ ∀n. bit1 n = suc (bit0 n)

⊦ (⇒) = λp q. p ∧ q ⇔ p

⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)

⊦ ∀m. suc m = m + 1

⊦ ∀t₁ t₂. (if ⊥ then t₁ else t₂) = t₂

⊦ ∀t₁ t₂. (if ⊤ then t₁ else t₂) = t₁

⊦ ∀a b. fst (a, b) = a

⊦ ∀a b. snd (a, b) = b

⊦ ∀f p. Fibonacci.decode.dest f p [] = 0

⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))

⊦ ∀l. Fibonacci.decode l = Fibonacci.decode.dest 1 0 l

⊦ ∀x y. x = y ⇔ y = x

⊦ ∀x y. x = y ⇒ y = x

⊦ ∀x y. x + y = y + x

⊦ ∀m n. m * n = n * m

⊦ ∀m n. m + n = n + m

⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤

⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q

⊦ ∀m n. suc m + n = suc (m + n)

⊦ ∀m n. m * suc n = m + m * n

⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r

⊦ ∀x y z. x = y ∧ y = z ⇒ x = z

⊦ ∀x y z. x + y + z = x + (y + z)

⊦ ∀p. (∀x. ∃y. p x y) ⇔ ∃y. ∀x. p x (y x)

⊦ ∀p. p 0 ∧ (∀n. p n ⇒ p (suc n)) ⇒ ∀n. p n

⊦ (∃!) = λp. (∃) p ∧ ∀x y. p x ∧ p y ⇒ x = y

⊦ ∀e f. ∃!fn. fn 0 = e ∧ ∀n. fn (suc n) = f (fn n) n

⊦ ∀p. p [] ∧ (∀h t. p t ⇒ p (h :: t)) ⇒ ∀l. p l

⊦ ∀h t. Bits.toNatural (h :: t) = 2 * Bits.toNatural t + if h then 1 else 0

⊦ ∀b f. ∃fn. fn [] = b ∧ ∀h t. fn (h :: t) = f h t (fn t)

⊦ ∀f p h t.
    Fibonacci.decode.dest f p (h :: t) =
    let s ← f + p in
    let n ← Fibonacci.decode.dest s f t in
    if h then s + n else n