From 900cbe7e50da8ad0f52844bf789fc1a5e75d0756 Mon Sep 17 00:00:00 2001 From: Jason Gross Date: Mon, 1 Aug 2016 13:46:20 -0700 Subject: Add a lemma about removing division in modular arithmetic After | File Name | Before || Change ---------------------------------------------------------------------------------- 1m42.99s | Total | 1m51.49s || -0m08.50s ---------------------------------------------------------------------------------- 0m32.67s | Specific/GF25519 | 0m40.24s || -0m07.57s 0m15.23s | ModularArithmetic/ModularBaseSystemProofs | 0m15.52s || -0m00.28s 0m11.35s | Experiments/SpecEd25519 | 0m11.36s || -0m00.00s 0m07.03s | Specific/GF1305 | 0m07.39s || -0m00.35s 0m04.05s | ModularArithmetic/Pow2BaseProofs | 0m03.96s || +0m00.08s 0m04.04s | ModularArithmetic/Tutorial | 0m03.72s || +0m00.31s 0m03.75s | BaseSystemProofs | 0m03.70s || +0m00.04s 0m03.13s | ModularArithmetic/ModularBaseSystemOpt | 0m03.77s || -0m00.64s 0m02.70s | Util/ZUtil | 0m02.62s || +0m00.08s 0m01.59s | ModularArithmetic/PrimeFieldTheorems | 0m01.57s || +0m00.02s 0m01.58s | ModularArithmetic/ModularArithmeticTheorems | 0m01.61s || -0m00.03s 0m01.45s | Encoding/PointEncodingPre | 0m01.83s || -0m00.38s 0m01.24s | BaseSystem | 0m01.28s || -0m00.04s 0m01.14s | ModularArithmetic/ExtendedBaseVector | 0m01.18s || -0m00.04s 0m00.98s | Experiments/DerivationsOptionRectLetInEncoding | 0m01.00s || -0m00.02s 0m00.96s | Encoding/ModularWordEncodingPre | 0m00.61s || +0m00.35s 0m00.95s | ModularArithmetic/BarrettReduction/Z | 0m00.93s || +0m00.01s 0m00.87s | ModularArithmetic/ModularBaseSystemField | 0m00.89s || -0m00.02s 0m00.86s | Util/NumTheoryUtil | 0m00.86s || +0m00.00s 0m00.78s | ModularArithmetic/ModularBaseSystemListProofs | 0m00.81s || -0m00.03s 0m00.73s | Experiments/SpecificCurve25519 | 0m00.73s || +0m00.00s 0m00.68s | Encoding/ModularWordEncodingTheorems | 0m00.66s || +0m00.02s 0m00.65s | ModularArithmetic/ExtPow2BaseMulProofs | 0m00.65s || +0m00.00s 0m00.64s | Spec/ModularWordEncoding | 0m00.60s || +0m00.04s 0m00.62s | Testbit | 0m00.63s || -0m00.01s 0m00.60s | ModularArithmetic/ModularBaseSystemList | 0m00.58s || +0m00.02s 0m00.58s | ModularArithmetic/ModularBaseSystem | 0m00.57s || +0m00.01s 0m00.56s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.59s || -0m00.02s 0m00.46s | ModularArithmetic/Pre | 0m00.47s || -0m00.00s 0m00.39s | ModularArithmetic/PseudoMersenneBaseParams | 0m00.40s || -0m00.01s 0m00.38s | ModularArithmetic/Pow2Base | 0m00.39s || -0m00.01s 0m00.35s | Spec/ModularArithmetic | 0m00.37s || -0m00.02s --- src/Util/ZUtil.v | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v index eeb99188b..b7d460fb3 100644 --- a/src/Util/ZUtil.v +++ b/src/Util/ZUtil.v @@ -1227,26 +1227,38 @@ Module Z. Local Instance equiv_modulo_Symmetric : Symmetric equiv_modulo := fun _ _ => @Logic.eq_sym _ _ _. Local Instance equiv_modulo_Transitive : Transitive equiv_modulo := fun _ _ _ => @Logic.eq_trans _ _ _ _. - Lemma mul_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.mul. + Local Instance mul_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.mul. Proof. unfold equiv_modulo, Proper, respectful; auto with zarith. Qed. - Lemma add_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.add. + Local Instance add_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.add. Proof. unfold equiv_modulo, Proper, respectful; auto with zarith. Qed. - Lemma sub_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.sub. + Local Instance sub_mod_Proper : Proper (equiv_modulo ==> equiv_modulo ==> equiv_modulo) Z.sub. Proof. unfold equiv_modulo, Proper, respectful; auto with zarith. Qed. - Lemma opp_mod_Proper : Proper (equiv_modulo ==> equiv_modulo) Z.opp. + Local Instance opp_mod_Proper : Proper (equiv_modulo ==> equiv_modulo) Z.opp. Proof. unfold equiv_modulo, Proper, respectful; auto with zarith. Qed. - Lemma modulo_equiv_modulo_Proper + Local Instance modulo_equiv_modulo_Proper : Proper (equiv_modulo ==> (fun x y => x = N /\ N = y) ==> Logic.eq) Z.modulo. Proof. repeat intro; hnf in *; intuition congruence. Qed. - Lemma eq_to_ProperProxy : ProperProxy (fun x y : Z => x = N /\ N = y) N. + Local Instance eq_to_ProperProxy : ProperProxy (fun x y : Z => x = N /\ N = y) N. Proof. split; reflexivity. Qed. + + Lemma div_to_inv_modulo a x x' : x > 0 -> x * x' mod N = 1 mod N -> (a / x) == ((a - a mod x) * x'). + Proof. + intros H xinv. + replace (a / x) with ((a / x) * 1) by lia. + change (x * x' == 1) in xinv. + rewrite <- xinv. + replace ((a / x) * (x * x')) with ((x * (a / x)) * x') by lia. + rewrite Z.mul_div_eq by assumption. + reflexivity. + Qed. End equiv_modulo. + Hint Rewrite div_to_inv_modulo using lia : zstrip_div. Module EquivModuloInstances (dummy : Nop). (* work around https://coq.inria.fr/bugs/show_bug.cgi?id=4973 *) Existing Instance equiv_modulo_Reflexive. -- cgit v1.2.3