More ZUtil

After    | File Name                                       | Before   || Change
----------------------------------------------------------------------------------
1m43.10s | Total                                           | 1m50.46s || -0m07.35s
----------------------------------------------------------------------------------
0m04.08s | ModularArithmetic/Pow2BaseProofs                | 0m05.41s || -0m01.33s
0m03.75s | ModularArithmetic/Tutorial                      | 0m05.07s || -0m01.32s
0m32.60s | Specific/GF25519                                | 0m32.45s || +0m00.14s
0m15.63s | ModularArithmetic/ModularBaseSystemProofs       | 0m15.48s || +0m00.15s
0m11.48s | Experiments/SpecEd25519                         | 0m11.72s || -0m00.24s
0m07.10s | Specific/GF1305                                 | 0m07.15s || -0m00.05s
0m03.81s | BaseSystemProofs                                | 0m04.18s || -0m00.36s
0m03.21s | ModularArithmetic/ModularBaseSystemOpt          | 0m03.15s || +0m00.06s
0m02.82s | Util/ZUtil                                      | 0m02.86s || -0m00.04s
0m01.66s | ModularArithmetic/PrimeFieldTheorems            | 0m01.68s || -0m00.02s
0m01.53s | ModularArithmetic/ModularArithmeticTheorems     | 0m01.73s || -0m00.19s
0m01.51s | Encoding/PointEncodingPre                       | 0m01.73s || -0m00.21s
0m01.16s | BaseSystem                                      | 0m01.66s || -0m00.50s
0m01.08s | ModularArithmetic/ExtendedBaseVector            | 0m01.18s || -0m00.09s
0m00.95s | ModularArithmetic/BarrettReduction/Z            | 0m01.08s || -0m00.13s
0m00.94s | Experiments/DerivationsOptionRectLetInEncoding  | 0m01.43s || -0m00.49s
0m00.87s | ModularArithmetic/ModularBaseSystemField        | 0m00.89s || -0m00.02s
0m00.84s | Util/NumTheoryUtil                              | 0m01.34s || -0m00.50s
0m00.80s | ModularArithmetic/ModularBaseSystemListProofs   | 0m00.89s || -0m00.08s
0m00.74s | Encoding/ModularWordEncodingTheorems            | 0m00.78s || -0m00.04s
0m00.69s | Experiments/SpecificCurve25519                  | 0m00.69s || +0m00.00s
0m00.65s | Encoding/ModularWordEncodingPre                 | 0m00.84s || -0m00.18s
0m00.64s | ModularArithmetic/ExtPow2BaseMulProofs          | 0m00.96s || -0m00.31s
0m00.63s | Testbit                                         | 0m00.90s || -0m00.27s
0m00.61s | ModularArithmetic/ModularBaseSystemList         | 0m00.95s || -0m00.34s
0m00.58s | Spec/ModularWordEncoding                        | 0m00.84s || -0m00.26s
0m00.57s | ModularArithmetic/ModularBaseSystem             | 0m00.62s || -0m00.05s
0m00.55s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.89s || -0m00.34s
0m00.49s | ModularArithmetic/Pre                           | 0m00.49s || +0m00.00s
0m00.41s | ModularArithmetic/PseudoMersenneBaseParams      | 0m00.49s || -0m00.08s
0m00.39s | ModularArithmetic/Pow2Base                      | 0m00.45s || -0m00.06s
0m00.34s | Spec/ModularArithmetic                          | 0m00.48s || -0m00.13s

1 files changed, 27 insertions, 1 deletions

diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v
index b7547f150..06d703bb7 100644
--- a/src/Util/ZUtil.v
+++ b/src/Util/ZUtil.v
@@ -24,7 +24,7 @@ Hint Resolve (fun a b H => proj1 (Z.mod_pos_bound a b H)) (fun a b H => proj2 (Z
     which can reasonably be said to "simplify" the goal, should go in
     this database. *)
 Create HintDb zsimplify discriminated.
-Hint Rewrite Z.div_1_r Z.mul_1_r Z.mul_1_l Z.sub_diag Z.mul_0_r Z.mul_0_l Z.add_0_l Z.add_0_r Z.opp_involutive Z.sub_0_r Z_mod_same_full Z.sub_simpl_r Z.sub_simpl_l Z.add_opp_diag_r Z.add_opp_diag_l Zmod_0_l Z.add_simpl_r Z.add_simpl_l Z.opp_0 : zsimplify.
+Hint Rewrite Z.div_1_r Z.mul_1_r Z.mul_1_l Z.sub_diag Z.mul_0_r Z.mul_0_l Z.add_0_l Z.add_0_r Z.opp_involutive Z.sub_0_r Z_mod_same_full Z.sub_simpl_r Z.sub_simpl_l Z.add_opp_diag_r Z.add_opp_diag_l Zmod_0_l Z.add_simpl_r Z.add_simpl_l Z.opp_0 Zmod_0_r : zsimplify.
 Hint Rewrite Z.div_mul Z.div_1_l Z.div_same Z.mod_same Z.div_small Z.mod_small Z.div_add Z.div_add_l Z.mod_add Z.div_0_l Z.mod_mod using lia : zsimplify.
 Hint Rewrite <- Z.opp_eq_mul_m1 : zsimplify.
 
@@ -1170,6 +1170,13 @@ Module Z.
   Proof. reflexivity. Qed.
   Hint Rewrite minus_minus_one : zsimplify.
 
+  Lemma div_add_exact x y d : d <> 0 -> x mod d = 0 -> (x + y) / d = x / d + y / d.
+  Proof.
+    intros; rewrite (Z_div_exact_full_2 x d) at 1 by assumption.
+    rewrite Z.div_add_l' by assumption; lia.
+  Qed.
+  Hint Rewrite div_add_exact using lia : zsimplify.
+
   Lemma mul_mod_l a b n : n <> 0 -> (a * b) mod n = ((a mod n) * b) mod n.
   Proof.
     intros; rewrite (Z.mul_mod a b), (Z.mul_mod (a mod n) b) by lia.
@@ -1241,6 +1248,25 @@ Module Z.
   Proof. intros; symmetry; apply Zminus_mod_idemp_r; assumption. Qed.
   Hint Rewrite sub_mod_r_push using solve [ NoZMod | lia ] : push_Zmod.
 
+  Lemma sub_mod_mod_0 x d : (x - x mod d) mod d = 0.
+  Proof.
+    destruct (Z_zerop d); subst; autorewrite with push_Zmod zsimplify; reflexivity.
+  Qed.
+  Hint Resolve sub_mod_mod_0 : zarith.
+  Hint Rewrite sub_mod_mod_0 : zsimplify.
+
+  Lemma div_sub_mod_cond x y d
+    : d <> 0
+      -> (x - y) / d
+         = x / d + ((x mod d - y) / d).
+  Proof. clear.
+         intro.
+         replace (x - y) with ((x - x mod d) + (x mod d - y)) by lia.
+         rewrite div_add_exact by auto with zarith.
+         rewrite <- Z.div_sub_mod_exact by lia; lia.
+  Qed.
+  Hint Resolve div_sub_mod_cond : zarith.
+
   Lemma simplify_twice_sub_sub x y : 2 * x - (x - y) = x + y.
   Proof. lia. Qed.
   Hint Rewrite simplify_twice_sub_sub : zsimplify.