More ZUtil

After    | File Name                                       | Before   || Change
----------------------------------------------------------------------------------
1m44.88s | Total                                           | 1m48.07s || -0m03.19s
----------------------------------------------------------------------------------
0m03.72s | ModularArithmetic/Tutorial                      | 0m04.76s || -0m01.03s
0m33.03s | Specific/GF25519                                | 0m32.64s || +0m00.39s
0m15.51s | ModularArithmetic/ModularBaseSystemProofs       | 0m15.54s || -0m00.02s
0m11.59s | Experiments/SpecEd25519                         | 0m11.98s || -0m00.39s
0m07.22s | Specific/GF1305                                 | 0m07.14s || +0m00.08s
0m04.58s | ModularArithmetic/Pow2BaseProofs                | 0m04.75s || -0m00.16s
0m04.14s | BaseSystemProofs                                | 0m04.01s || +0m00.12s
0m03.19s | ModularArithmetic/ModularBaseSystemOpt          | 0m03.80s || -0m00.60s
0m02.96s | Util/ZUtil                                      | 0m02.85s || +0m00.10s
0m01.64s | ModularArithmetic/ModularArithmeticTheorems     | 0m01.62s || +0m00.01s
0m01.62s | ModularArithmetic/PrimeFieldTheorems            | 0m01.60s || +0m00.02s
0m01.48s | Encoding/PointEncodingPre                       | 0m01.96s || -0m00.48s
0m01.22s | BaseSystem                                      | 0m01.18s || +0m00.04s
0m01.11s | ModularArithmetic/ExtendedBaseVector            | 0m01.32s || -0m00.20s
0m00.99s | ModularArithmetic/BarrettReduction/Z            | 0m00.97s || +0m00.02s
0m00.95s | Experiments/DerivationsOptionRectLetInEncoding  | 0m01.00s || -0m00.05s
0m00.88s | Util/NumTheoryUtil                              | 0m00.88s || +0m00.00s
0m00.86s | ModularArithmetic/ModularBaseSystemField        | 0m00.84s || +0m00.02s
0m00.85s | ModularArithmetic/ModularBaseSystemListProofs   | 0m00.92s || -0m00.07s
0m00.72s | Experiments/SpecificCurve25519                  | 0m00.69s || +0m00.03s
0m00.70s | Encoding/ModularWordEncodingTheorems            | 0m00.73s || -0m00.03s
0m00.63s | ModularArithmetic/ExtPow2BaseMulProofs          | 0m00.90s || -0m00.27s
0m00.62s | Testbit                                         | 0m00.72s || -0m00.09s
0m00.61s | Encoding/ModularWordEncodingPre                 | 0m00.59s || +0m00.02s
0m00.60s | Spec/ModularWordEncoding                        | 0m00.60s || +0m00.00s
0m00.60s | ModularArithmetic/ModularBaseSystemList         | 0m00.70s || -0m00.09s
0m00.58s | ModularArithmetic/ModularBaseSystem             | 0m00.78s || -0m00.20s
0m00.55s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.81s || -0m00.26s
0m00.53s | ModularArithmetic/Pre                           | 0m00.59s || -0m00.05s
0m00.44s | ModularArithmetic/PseudoMersenneBaseParams      | 0m00.38s || +0m00.06s
0m00.41s | ModularArithmetic/Pow2Base                      | 0m00.45s || -0m00.04s
0m00.36s | Spec/ModularArithmetic                          | 0m00.38s || -0m00.02s

1 files changed, 19 insertions, 1 deletions

diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v
index 06d703bb7..5005cc32f 100644
--- a/src/Util/ZUtil.v
+++ b/src/Util/ZUtil.v
@@ -17,7 +17,7 @@ Hint Extern 1 => lia : lia.
 Hint Extern 1 => lra : lra.
 Hint Extern 1 => nia : nia.
 Hint Extern 1 => omega : omega.
-Hint Resolve Z.log2_nonneg Z.div_small Z.mod_small Z.pow_neg_r Z.pow_0_l Z.pow_pos_nonneg Z.lt_le_incl Z.pow_nonzero Z.div_le_upper_bound Z_div_exact_full_2 Z.div_same Z.div_lt_upper_bound Z.div_le_lower_bound : zarith.
+Hint Resolve Z.log2_nonneg Z.div_small Z.mod_small Z.pow_neg_r Z.pow_0_l Z.pow_pos_nonneg Z.lt_le_incl Z.pow_nonzero Z.div_le_upper_bound Z_div_exact_full_2 Z.div_same Z.div_lt_upper_bound Z.div_le_lower_bound Zplus_minus : zarith.
 Hint Resolve (fun a b H => proj1 (Z.mod_pos_bound a b H)) (fun a b H => proj2 (Z.mod_pos_bound a b H)) : zarith.
 
 (** Only hints that are always safe to apply (i.e., reversible), and
@@ -1051,6 +1051,24 @@ Module Z.
 
   Hint Rewrite Z.div_mul_skip Z.div_mul_skip' using lia : zsimplify.
 
+  Lemma div_mul_skip_pow base e0 e1 x y : 0 < x -> 0 < y -> 0 < base -> 0 <= e1 <= e0 -> x * base^e0 / y / base^e1 = x * base^(e0 - e1) / y.
+  Proof.
+    intros.
+    assert (0 < base^e1) by auto with zarith.
+    replace (base^e0) with (base^(e0 - e1) * base^e1) by (autorewrite with pull_Zpow zsimplify; reflexivity).
+    rewrite !Z.mul_assoc.
+    autorewrite with zsimplify; lia.
+  Qed.
+  Hint Rewrite div_mul_skip_pow using lia : zsimplify.
+
+  Lemma div_mul_skip_pow' base e0 e1 x y : 0 < x -> 0 < y -> 0 < base -> 0 <= e1 <= e0 -> base^e0 * x / y / base^e1 = base^(e0 - e1) * x / y.
+  Proof.
+    intros.
+    rewrite (Z.mul_comm (base^e0) x), div_mul_skip_pow by lia.
+    auto using f_equal2 with lia.
+  Qed.
+  Hint Rewrite div_mul_skip_pow' using lia : zsimplify.
+
   Lemma mod_eq_le_to_eq a b : 0 < a <= b -> a mod b = 0 -> a = b.
   Proof.
     intros H H'.