diff options
| author |  Jason Gross <jagro@google.com> | 2016-07-29 13:18:14 -0700 |
|---|---|---|
| committer | Jason Gross <jagro@google.com> | 2016-07-29 13:22:30 -0700 |
| commit | 2d866442e53479bb0525797b8155562f31aab5bc (patch) | |
| tree | bca468cc10899235aafed2e9c8e03347aa819dcd /src | |
| parent | 74e7e2bb0b2414ea598b76a88c4a4550e2b3e554 (diff) | |
Add a zutil lemma
After | File Name | Before || Change
----------------------------------------------------------------------------------
1m46.53s | Total | 1m48.84s || -0m02.31s
----------------------------------------------------------------------------------
0m33.03s | Specific/GF25519 | 0m33.12s || -0m00.08s
0m15.63s | ModularArithmetic/ModularBaseSystemProofs | 0m16.43s || -0m00.79s
0m11.57s | Experiments/SpecEd25519 | 0m12.01s || -0m00.43s
0m07.55s | Specific/GF1305 | 0m07.16s || +0m00.38s
0m04.55s | ModularArithmetic/Pow2BaseProofs | 0m04.60s || -0m00.04s
0m03.98s | BaseSystemProofs | 0m04.02s || -0m00.03s
0m03.88s | ModularArithmetic/Tutorial | 0m04.02s || -0m00.13s
0m03.19s | ModularArithmetic/ModularBaseSystemOpt | 0m03.21s || -0m00.02s
0m02.46s | Util/ZUtil | 0m02.38s || +0m00.08s
0m01.73s | Encoding/PointEncodingPre | 0m02.02s || -0m00.29s
0m01.63s | BaseSystem | 0m01.40s || +0m00.23s
0m01.62s | ModularArithmetic/PrimeFieldTheorems | 0m01.66s || -0m00.03s
0m01.57s | ModularArithmetic/ModularArithmeticTheorems | 0m01.58s || -0m00.01s
0m01.42s | Experiments/DerivationsOptionRectLetInEncoding | 0m01.29s || +0m00.12s
0m01.31s | Util/NumTheoryUtil | 0m01.33s || -0m00.02s
0m01.20s | ModularArithmetic/ExtendedBaseVector | 0m01.16s || +0m00.04s
0m00.94s | ModularArithmetic/BarrettReduction/Z | 0m01.39s || -0m00.44s
0m00.94s | Testbit | 0m00.93s || +0m00.00s
0m00.92s | ModularArithmetic/ModularBaseSystemField | 0m00.88s || +0m00.04s
0m00.82s | ModularArithmetic/ModularBaseSystemListProofs | 0m00.81s || +0m00.00s
0m00.74s | Experiments/SpecificCurve25519 | 0m00.71s || +0m00.03s
0m00.67s | Encoding/ModularWordEncodingTheorems | 0m01.01s || -0m00.34s
0m00.62s | Encoding/ModularWordEncodingPre | 0m00.62s || +0m00.00s
0m00.61s | Spec/ModularWordEncoding | 0m00.62s || -0m00.01s
0m00.60s | ModularArithmetic/ExtPow2BaseMulProofs | 0m00.65s || -0m00.05s
0m00.60s | ModularArithmetic/ModularBaseSystemList | 0m00.59s || +0m00.01s
0m00.58s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.67s || -0m00.09s
0m00.57s | ModularArithmetic/ModularBaseSystem | 0m00.70s || -0m00.13s
0m00.45s | ModularArithmetic/Pre | 0m00.68s || -0m00.23s
0m00.44s | ModularArithmetic/Pow2Base | 0m00.43s || +0m00.01s
0m00.39s | ModularArithmetic/PseudoMersenneBaseParams | 0m00.43s || -0m00.03s
0m00.33s | Spec/ModularArithmetic | 0m00.34s || -0m00.01s
Diffstat (limited to 'src')
| -rw-r--r-- | src/Util/ZUtil.v | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v index 045ada019..8177444a5 100644 --- a/src/Util/ZUtil.v +++ b/src/Util/ZUtil.v @@ -1132,6 +1132,14 @@ Module Z. Qed. Hint Resolve f_equal_sub_mod : zarith. + Lemma div_sub_mod_exact a b : b <> 0 -> a / b = (a - a mod b) / b. + Proof. + intro. + rewrite (Z.div_mod a b) at 2 by lia. + autorewrite with zsimplify. + reflexivity. + Qed. + Section equiv_modulo. Context (N : Z). Definition equiv_modulo x y := x mod N = y mod N. |