diff options
author | 2017-06-26 00:34:03 -0400 | |
---|---|---|
committer | 2017-06-26 10:02:10 -0400 | |
commit | 689bd71a2a5afd5ce652ff123252f163f5047b74 (patch) | |
tree | b0743697e6daacd38ff9e45274910d880306b04d /src/Specific/NISTP256 | |
parent | b259663f37d8cf05ad247c1fe3232b08f6e09e8b (diff) |
Add nonzero synthesis
Diffstat (limited to 'src/Specific/NISTP256')
3 files changed, 150 insertions, 1 deletions
diff --git a/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_Nonzero.v b/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_Nonzero.v new file mode 100644 index 000000000..5f0d15b18 --- /dev/null +++ b/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_Nonzero.v @@ -0,0 +1,114 @@ +Require Import Coq.ZArith.ZArith. +Require Import Coq.Lists.List. +Local Open Scope Z_scope. + +Require Import Crypto.Arithmetic.Core. +Require Import Crypto.Util.FixedWordSizes. +Require Import Crypto.Arithmetic.MontgomeryReduction.WordByWord.Definition. +Require Import Crypto.Arithmetic.Core. Import B. +Require Import Crypto.Specific.NISTP256.AMD64.MontgomeryP256. +Require Import Crypto.Arithmetic.PrimeFieldTheorems. +Require Import Crypto.Util.Tuple Crypto.Util.Sigma Crypto.Util.Sigma.MapProjections Crypto.Util.Sigma.Lift Crypto.Util.Notations Crypto.Util.ZRange Crypto.Util.BoundedWord. +Require Import Crypto.Util.Tactics.Head. +Require Import Crypto.Util.Tactics.MoveLetIn. +Require Import Crypto.Util.Tactics.DestructHead. +Require Import Crypto.Util.ZUtil.Tactics.LtbToLt. +Import ListNotations. + +Require Import Crypto.Specific.IntegrationTestTemporaryMiscCommon. + +Require Import Crypto.Compilers.Z.Bounds.Pipeline. + +Section BoundedField25p5. + Local Coercion Z.of_nat : nat >-> Z. + + Let bound1 : zrange + := Eval compute in + {| lower := 0 ; upper := r-1 |}. + Let bounds : Tuple.tuple zrange sz + := Eval compute in + Tuple.repeat bound1 sz. + + Let lgbitwidth := Eval compute in (Z.to_nat (Z.log2_up (Z.log2_up r))). + Let bitwidth := Eval compute in (2^lgbitwidth)%nat. + Let feZ : Type := tuple Z sz. + Let feW : Type := tuple (wordT lgbitwidth) sz. + Let feBW : Type := BoundedWord sz bitwidth bounds. + Let eval : feBW -> Z := + fun x => Saturated.eval (Z.pos r) (BoundedWordToZ _ _ _ x). + Let feBW_small : Type := { v : feBW | eval v < Saturated.eval (n:=sz) (Z.pos r) p256 }. + Let feBW_of_feBW_small : feBW_small -> feBW := @proj1_sig _ _. + Local Coercion feBW_of_feBW_small : feBW_small >-> feBW. + Let phi : feBW -> F m := + fun x => montgomery_to_F (eval x). + + (* TODO : change this to field once field isomorphism happens *) + Definition nonzero + : { nonzero : feBW_small -> BoundedWord 1 bitwidth bound1 + | forall A, (BoundedWordToZ _ _ _ (nonzero A) =? 0) = (if Decidable.dec (phi A = F.of_Z m 0) then true else false) }. + Proof. + lazymatch goal with + | [ |- { f | forall a, (?R (?phi (f a)) ?v) = @?rhs a } ] + => apply lift1_sig with (P:=fun a f => R (phi f) v = rhs a) + end. + intros a. + cbv [feBW_of_feBW_small]. + eexists_sig_etransitivity. all:cbv [phi eval]. + refine (_ : (if Decidable.dec (_ = 0) then true else false) = _). + lazymatch goal with + | [ |- (if Decidable.dec ?x then _ else _) = (if Decidable.dec ?y then _ else _) ] + => cut (x <-> y); + [ destruct (Decidable.dec x), (Decidable.dec y); try reflexivity; intros [? ?]; + generalize dependent x; generalize dependent y; solve [ intuition congruence ] + | ] + end. + etransitivity; [ | eapply (proj2_sig nonzero) ]; + [ | solve [ try (hnf; rewrite <- (is_bounded_by_None_repeat_In_iff_lt _ _ _)); destruct_head' feBW_small; destruct_head' feBW; try assumption ].. ]. + reflexivity. + let decP := lazymatch goal with |- { c | _ = if Decidable.dec (?decP = 0) then _ else _ } => decP end in + apply (@proj2_sig_map _ (fun c => BoundedWordToZ 1 _ _ c = decP) _). + { intros a' H'; rewrite H'. + let H := fresh in + lazymatch goal with |- context[Decidable.dec ?x] => destruct (Decidable.dec x) as [H|H]; try rewrite H end. + { reflexivity. } + { let H := fresh in + lazymatch goal with |- context[?x =? 0] => destruct (x =? 0) eqn:? end; + try reflexivity. + Z.ltb_to_lt; congruence. } } + eexists_sig_etransitivity. + set (nonzeroZ := proj1_sig nonzero). + context_to_dlet_in_rhs nonzeroZ; cbv [nonzeroZ]. + cbv beta iota delta [nonzero nonzero' proj1_sig Saturated.T lift1_sig fst snd runtime_lor runtime_add runtime_and runtime_mul runtime_opp runtime_shr]. + reflexivity. + sig_dlet_in_rhs_to_context. + match goal with + | [ H : feBW_small |- _ ] => destruct H as [? _] + end. + (* jgross start here! *) + Set Ltac Profiling. + (* Set Ltac Profiling. + Print Ltac ReflectiveTactics.solve_side_conditions. + Ltac ReflectiveTactics.solve_side_conditions ::= idtac. + Time refine_reflectively128_with_uint8_with anf. (* Finished transaction in 212.693 secs (212.576u,0.184s) (successful) *) + { Time ReflectiveTactics.do_reify. } + { Time UnifyAbstractReflexivity.unify_abstract_vm_compute_rhs_reflexivity. } + { Time UnifyAbstractReflexivity.unify_abstract_vm_compute_rhs_reflexivity. } + { Time UnifyAbstractReflexivity.unify_abstract_vm_compute_rhs_reflexivity. } + { Require Import CNotations. + Time UnifyAbstractReflexivity.unify_abstract_vm_compute_rhs_reflexivity. } + { Time UnifyAbstractReflexivity.unify_abstract_vm_compute_rhs_reflexivity. } + { Time UnifyAbstractReflexivity.unify_abstract_rhs_reflexivity. } + { Time ReflectiveTactics.unify_abstract_renamify_rhs_reflexivity. } + { Time SubstLet.subst_let; clear; abstract vm_cast_no_check eq_refl. } + { Time SubstLet.subst_let; clear; vm_compute; reflexivity. } + { Time UnifyAbstractReflexivity.unify_abstract_compute_rhs_reflexivity. } + { Time ReflectiveTactics.unify_abstract_cbv_interp_rhs_reflexivity. } + { Time abstract ReflectiveTactics.handle_bounds_from_hyps. } + { Time ReflectiveTactics.handle_boundedness_side_condition. } *) + Time refine_reflectively_with_uint8_with anf. (* Finished transaction in 212.693 secs (212.576u,0.184s) (successful) *) + Show Ltac Profile. + Time Defined. (* Finished transaction in 21.291 secs (21.231u,0.032s) (successful) *) + +Time End BoundedField25p5. (* Finished transaction in 14.666 secs (14.556u,0.111s) (successful) *) + +Print Assumptions nonzero. diff --git a/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_NonzeroDisplay.v b/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_NonzeroDisplay.v new file mode 100644 index 000000000..c56e9a92d --- /dev/null +++ b/src/Specific/NISTP256/AMD64/IntegrationTestMontgomeryP256_NonzeroDisplay.v @@ -0,0 +1,4 @@ +Require Import Crypto.Specific.NISTP256.AMD64.IntegrationTestMontgomeryP256_Nonzero. +Require Import Crypto.Specific.IntegrationTestDisplayCommon. + +Check display nonzero. diff --git a/src/Specific/NISTP256/AMD64/MontgomeryP256.v b/src/Specific/NISTP256/AMD64/MontgomeryP256.v index cd933f0b7..865004dd6 100644 --- a/src/Specific/NISTP256/AMD64/MontgomeryP256.v +++ b/src/Specific/NISTP256/AMD64/MontgomeryP256.v @@ -162,6 +162,17 @@ Proof. reflexivity. Defined. +Definition nonzero' : { f:Tuple.tuple Z sz -> Z + | forall (A : Tuple.tuple Z sz), + f A = + (nonzero (R_numlimbs:=sz) A) + }. +Proof. + eapply (lift1_sig (fun A c => c = _)); eexists. + cbv -[runtime_lor Let_In]. + reflexivity. +Defined. + Import ModularArithmetic. (*Definition mulmod_256 : { f:Tuple.tuple Z sz -> Tuple.tuple Z sz -> Tuple.tuple Z sz @@ -290,5 +301,25 @@ Proof. ). Defined. -Local Definition for_assumptions := (mulmod_256, add, sub, opp). +Axiom proof_admitted : False. +Definition nonzero : { f:Tuple.tuple Z sz -> Z + | let eval := Saturated.eval (Z.pos r) in + forall (A : Tuple.tuple Z sz) (_ : Saturated.small (Z.pos r) A), + (eval A < eval p256 + -> f A = 0 <-> (montgomery_to_F (eval A) = F.of_Z m 0))%Z }. +Proof. + exists (proj1_sig nonzero'). + abstract ( + intros eval A H **; rewrite (proj2_sig nonzero'), eval_nonzero by eassumption; + subst eval; + unfold montgomery_to_F, Saturated.uweight in *; rewrite <- ?ModularArithmeticTheorems.F.of_Z_mul; + rewrite <- ModularArithmeticTheorems.F.eq_of_Z_iff, m_p256; + let H := fresh in + split; intro H; + [ rewrite H; autorewrite with zsimplify_const; reflexivity + | repeat match goal with H : _ |- _ => revert H end; case proof_admitted ] + ). +Defined. + +Local Definition for_assumptions := (mulmod_256, add, sub, opp, nonzero). Print Assumptions for_assumptions. |