diff options
author | Jason Gross <jagro@google.com> | 2016-08-23 15:27:40 -0700 |
---|---|---|
committer | Jason Gross <jagro@google.com> | 2016-08-23 15:36:06 -0700 |
commit | c7b73992a35fac09251cd045cff38871ecd7e772 (patch) | |
tree | d20b609c3a154da1c8ee29d506a8499c3ff3f6ba | |
parent | 42c031911c49c7c4d740a031abaa398974dd46ab (diff) |
More ZUtil
After | File Name | Before || Change
----------------------------------------------------------------------------------
3m12.82s | Total | 3m41.60s || -0m28.77s
----------------------------------------------------------------------------------
0m45.19s | ModularArithmetic/Pow2BaseProofs | 0m56.43s || -0m11.24s
0m11.84s | Util/ZUtil | 0m14.96s || -0m03.12s
0m18.96s | ModularArithmetic/ModularBaseSystemProofs | 0m20.98s || -0m02.01s
0m13.99s | Experiments/SpecEd25519 | 0m16.65s || -0m02.65s
0m11.97s | ModularArithmetic/Montgomery/ZProofs | 0m13.49s || -0m01.51s
0m05.06s | ModularArithmetic/Tutorial | 0m06.06s || -0m01.00s
0m13.89s | Specific/GF25519 | 0m14.28s || -0m00.38s
0m10.57s | Testbit | 0m10.65s || -0m00.08s
0m10.11s | Specific/GF1305 | 0m10.76s || -0m00.65s
0m05.77s | ModularArithmetic/BarrettReduction/ZHandbook | 0m06.03s || -0m00.26s
0m05.58s | BaseSystemProofs | 0m06.05s || -0m00.46s
0m04.54s | ModularArithmetic/BarrettReduction/ZGeneralized | 0m05.03s || -0m00.49s
0m04.28s | ModularArithmetic/ModularArithmeticTheorems | 0m04.36s || -0m00.08s
0m03.70s | Experiments/SpecificCurve25519 | 0m03.37s || +0m00.33s
0m03.17s | ModularArithmetic/BarrettReduction/ZBounded | 0m02.80s || +0m00.37s
0m02.35s | ModularArithmetic/ModularBaseSystemOpt | 0m02.61s || -0m00.25s
0m01.82s | BaseSystem | 0m01.93s || -0m00.10s
0m01.67s | Encoding/PointEncodingPre | 0m02.45s || -0m00.78s
0m01.64s | ModularArithmetic/BarrettReduction/Z | 0m02.41s || -0m00.77s
0m01.47s | ModularArithmetic/ExtendedBaseVector | 0m01.85s || -0m00.38s
0m01.28s | Util/NumTheoryUtil | 0m01.43s || -0m00.14s
0m01.26s | ModularArithmetic/Montgomery/ZBounded | 0m01.37s || -0m00.11s
0m01.19s | ModularArithmetic/ModularBaseSystemListProofs | 0m01.18s || +0m00.01s
0m01.17s | ModularArithmetic/PrimeFieldTheorems | 0m01.35s || -0m00.18s
0m01.05s | ModularArithmetic/ModularBaseSystemField | 0m01.38s || -0m00.32s
0m00.99s | Experiments/DerivationsOptionRectLetInEncoding | 0m01.27s || -0m00.28s
0m00.82s | ModularArithmetic/ModularBaseSystem | 0m00.79s || +0m00.02s
0m00.80s | ModularArithmetic/ModularBaseSystemList | 0m00.99s || -0m00.18s
0m00.79s | ModularArithmetic/ExtPow2BaseMulProofs | 0m00.84s || -0m00.04s
0m00.74s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.78s || -0m00.04s
0m00.71s | Encoding/ModularWordEncodingTheorems | 0m01.11s || -0m00.40s
0m00.71s | ModularArithmetic/Pre | 0m00.80s || -0m00.09s
0m00.68s | Encoding/ModularWordEncodingPre | 0m00.94s || -0m00.25s
0m00.62s | Spec/ModularWordEncoding | 0m00.90s || -0m00.28s
0m00.55s | Spec/ModularArithmetic | 0m00.60s || -0m00.04s
0m00.51s | ModularArithmetic/ZBounded | 0m00.74s || -0m00.23s
0m00.51s | ModularArithmetic/Pow2Base | 0m00.70s || -0m00.18s
0m00.46s | ModularArithmetic/PseudoMersenneBaseParams | 0m00.65s || -0m00.19s
0m00.42s | ModularArithmetic/Montgomery/Z | 0m00.63s || -0m00.21s
-rw-r--r-- | src/Util/ZUtil.v | 16 |
1 files changed, 16 insertions, 0 deletions
diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v index 56ba8dd7a..5c13c319d 100644 --- a/src/Util/ZUtil.v +++ b/src/Util/ZUtil.v @@ -1639,6 +1639,22 @@ Module Z. Proof. intros; rewrite (mod_small_n 1) by lia; lia. Qed. Hint Rewrite mod_small_1 using zutil_arith : zsimplify. + Lemma div_between_if n a b : 0 <= n -> b <> 0 -> n * b <= a < (2 + n) * b -> (a / b = if (1 + n) * b <=? a then 1 + n else n)%Z. + Proof. + intros. + break_match; ltb_to_lt; + apply div_between; lia. + Qed. + + Lemma mod_small_n_if n a b : 0 <= n -> b <> 0 -> n * b <= a < (2 + n) * b -> a mod b = a - (if (1 + n) * b <=? a then (1 + n) else n) * b. + Proof. intros; erewrite Zmod_eq_full, div_between_if by eassumption; autorewrite with zsimplify_const. reflexivity. Qed. + + Lemma div_between_0_if a b : b <> 0 -> 0 <= a < 2 * b -> a / b = if b <=? a then 1 else 0. + Proof. intros; rewrite (div_between_if 0) by lia; autorewrite with zsimplify_const; reflexivity. Qed. + + Lemma mod_small_0_if a b : b <> 0 -> 0 <= a < 2 * b -> a mod b = a - if b <=? a then b else 0. + Proof. intros; rewrite (mod_small_n_if 0) by lia; autorewrite with zsimplify_const. break_match; lia. Qed. + Lemma mul_mod_distr_r_full a b c : (a * c) mod (b * c) = (a mod b * c). Proof. destruct (Z_zerop b); [ | destruct (Z_zerop c) ]; subst; |