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

1 files changed, 18 insertions, 6 deletions

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.