https://github.com/EasyCrypt/easycrypt
Raw File
Tip revision: 9db28d59d65422c4ba10a109a3dc53d190f7d806 authored by Pierre-Yves Strub on 27 January 2020, 13:46:58 UTC
script for testing EasyCrypt on various external devs
Tip revision: 9db28d5
ZModP.eca
(* --------------------------------------------------------------------
 * Copyright (c) - 2012--2016 - IMDEA Software Institute
 * Copyright (c) - 2012--2018 - Inria
 * Copyright (c) - 2012--2018 - Ecole Polytechnique
 *
 * Distributed under the terms of the CeCILL-B-V1 license
 * -------------------------------------------------------------------- *)

(* -------------------------------------------------------------------- *)
require import Int IntDiv.
require (*--*) Subtype Ring.

(* -------------------------------------------------------------------- *)
(* This abstract theory provides the construction of the ring Z/pZ.     *)
(* -------------------------------------------------------------------- *)
const p : { int | 2 <= p } as le2_p.

(* -------------------------------------------------------------------- *)
type zmod.

clone Subtype as Sub with
  type T <- int, type sT <- zmod,
  pred P (x : int) <- 0 <= x < p.

(* -------------------------------------------------------------------- *)
op inzmod (z : int)  = Sub.insubd (z %% p).
op asint  (z : zmod) = Sub.val z.

lemma inzmodK (z : int): asint (inzmod z) = z %% p.
proof. smt ml=1. qed.

lemma asint_inj: injective asint by apply/Sub.val_inj.

(* -------------------------------------------------------------------- *)
abbrev zmodcgr (z1 z2 : int) = z1 %% p = z2 %% p.

(* -------------------------------------------------------------------- *)
lemma eq_inzmod (z1 z2 : int) : zmodcgr z1 z2 <=> inzmod z1 = inzmod z2.
proof. split.
+ by move=> h; apply/asint_inj; rewrite !inzmodK.
+ by move/(congr1 asint); rewrite !inzmodK.
qed.

(* -------------------------------------------------------------------- *)
op zero      = inzmod 0.
op one       = inzmod 1.
op [ - ] x   = inzmod (- asint x).
op ( + ) x y = inzmod (asint x + asint y).
op ( * ) x y = inzmod (asint x * asint y).

op unit x = exists y, y * x = one.
op inv  x = choiceb (fun y => y * x = one) x.

(* -------------------------------------------------------------------- *)
lemma zeroE: asint Self.zero = 0.
proof. by rewrite /zero inzmodK mod0z. qed.

lemma oneE: asint Self.one = 1.
proof. by rewrite /one inzmodK modz_small; smt. qed.

lemma oppE (x : zmod): asint (-x) = (- (asint x)) %% p.
proof. by rewrite /[-] /inzmod /asint /= Sub.insubdK; smt. qed.

lemma addE (x y : zmod): asint (x + y) = (asint x + asint y) %% p.
proof. by rewrite /(+) /inzmod /asint /= Sub.insubdK; smt. qed.

lemma mulE (x y : zmod): asint (x * y) = (asint x * asint y) %% p.
proof. rewrite /( * ) /inzmod /asint /= Sub.insubdK; smt. qed.

(* -------------------------------------------------------------------- *)
theory ZModule.
lemma addrA (x y z : zmod): x + (y + z) = (x + y) + z.
proof. by apply/asint_inj; rewrite !addE modzDml modzDmr addzA. qed.

lemma addrC (x y : zmod): x + y = y + x.
proof. by apply/asint_inj; rewrite !addE addzC. qed.

lemma add0r (x : zmod): Self.zero + x = x.
proof. by apply/asint_inj; rewrite !(addE, zeroE) add0z smt. qed.

lemma addNr (x : zmod): (-x) + x = Self.zero.
proof.
apply/asint_inj; rewrite !(zeroE, addE, oppE).
by rewrite modzDml addNz.
qed.
end ZModule.

(* -------------------------------------------------------------------- *)
theory ComRing.
lemma oner_neq0 : Self.one <> Self.zero by smt.

lemma mulrA (x y z : zmod): x * (y * z) = (x * y) * z.
proof. by apply/asint_inj; rewrite !mulE modzMml modzMmr mulzA. qed.

lemma mulrC (x y : zmod): x * y = y * x.
proof. by apply/asint_inj; rewrite !mulE mulzC. qed.

lemma mul1r (x : zmod): Self.one * x = x.
proof. by apply/asint_inj; rewrite !(mulE, oneE) mul1z smt. qed.

lemma mulrDl (x y z : zmod): (x + y) * z = (x * z) + (y * z).
proof.
apply/asint_inj; rewrite !(addE, mulE).
by rewrite !(modzMml, modzMmr, modzDml, modzDmr) mulzDl.
qed.

lemma mulVr x : unit x => (inv x) * x = one.
proof. by move/choicebP=> /(_ x). qed.

lemma unitP x y : y * x = one => unit x.
proof. by move=> eq; exists y. qed.

lemma unitout x : ! unit x => inv x = x.
proof.
move=> Nux; rewrite choiceb_dfl //= => y; apply/negP.
by move=> h; apply/Nux; exists y.
qed.
end ComRing.

(* -------------------------------------------------------------------- *)
clone Ring.ComRing as ZModpRing with
  type t     <- zmod,
  op   zeror <- Self.zero,
  op   oner  <- Self.one,
  op   ( + ) <- Self.( + ),
  op   [ - ] <- Self.([-]),
  op   ( * ) <- Self.( * ),
  op   invr  <- inv,
  pred unit  <- Self.unit
  proof *.

realize addrA.     proof. by apply/ZModule.addrA. qed.
realize addrC.     proof. by apply/ZModule.addrC. qed.
realize add0r.     proof. by apply/ZModule.add0r. qed.
realize addNr.     proof. by apply/ZModule.addNr. qed.
realize mulrA.     proof. by apply/ComRing.mulrA. qed.
realize mulrC.     proof. by apply/ComRing.mulrC. qed.
realize mul1r.     proof. by apply/ComRing.mul1r. qed.
realize mulrDl.    proof. by apply/ComRing.mulrDl. qed.
realize oner_neq0. proof. by apply/ComRing.oner_neq0. qed.
realize mulVr.     proof. by apply/ComRing.mulVr. qed.
realize unitP.     proof. by apply/ComRing.unitP. qed.
realize unitout.   proof. by apply/ComRing.unitout. qed.

(* -------------------------------------------------------------------- *)
instance ring with zmod
  op rzero = Self.zero
  op rone  = Self.one
  op add   = Self.( + )
  op mul   = Self.( * )
  op opp   = Self.([-])

  proof oner_neq0 by apply/ZModpRing.oner_neq0
  proof addr0     by apply/ZModpRing.addr0
  proof addrA     by apply/ZModpRing.addrA
  proof addrC     by apply/ZModpRing.addrC
  proof addrN     by apply/ZModpRing.addrN
  proof mulr1     by apply/ZModpRing.mulr1
  proof mulrA     by apply/ZModpRing.mulrA
  proof mulrC     by apply/ZModpRing.mulrC
  proof mulrDl    by apply/ZModpRing.mulrDl.

(* -------------------------------------------------------------------- *)
lemma inzmodD (a b : int):
  inzmod (a + b) = inzmod a + inzmod b.
proof. by apply/asint_inj; rewrite addE !inzmodK modzDmr modzDml. qed.

lemma inzmodM (a b : int):
  inzmod (a * b) = inzmod a * inzmod b.
proof. by apply/asint_inj; rewrite mulE !inzmodK modzMmr modzMml. qed.

lemma inzmodN (n : int):
  inzmod (- n) = -(inzmod n).
proof. by apply/asint_inj; rewrite oppE !inzmodK modzNm. qed.

lemma inzmodB (a b : int):
  inzmod (a - b) = (inzmod a) + (- (inzmod b)).
proof. by rewrite inzmodD inzmodN. qed.
back to top