aboutsummaryrefslogtreecommitdiff
path: root/src/ModularArithmetic
diff options
context:
space:
mode:
authorGravatar jadep <jade.philipoom@gmail.com>2016-08-28 16:28:19 -0400
committerGravatar jadep <jade.philipoom@gmail.com>2016-08-31 10:03:57 -0400
commit9ffba573db9c809f53ed422e9cc4e4fab69693b9 (patch)
tree97e12e58814f27b1e071e2a55b20b75b1b66756d /src/ModularArithmetic
parentae07ed5c7f6e39cc4d8375f5607e8ae7b8a84eaf (diff)
Parameterized square roots for primes that are 5 mod 8 over any computation of sqrt (-1)
Diffstat (limited to 'src/ModularArithmetic')
-rw-r--r--src/ModularArithmetic/PrimeFieldTheorems.v10
1 files changed, 5 insertions, 5 deletions
diff --git a/src/ModularArithmetic/PrimeFieldTheorems.v b/src/ModularArithmetic/PrimeFieldTheorems.v
index f5a02ce27..bd2000df8 100644
--- a/src/ModularArithmetic/PrimeFieldTheorems.v
+++ b/src/ModularArithmetic/PrimeFieldTheorems.v
@@ -147,16 +147,16 @@ Module F.
Section SquareRootsPrime5Mod8.
Context {q:Z} {prime_q: prime q} {q_5mod8 : q mod 8 = 5}.
- (* This is always true, but easier to check by computation than to prove *)
- Context (sqrt_minus1_valid : ((F.of_Z q 2 ^ Z.to_N (q / 4)) ^ 2 = F.opp 1)%F).
Local Open Scope F_scope.
Add Field _field3 : (field_theory q)
(morphism (F.ring_morph q),
constants [F.is_constant],
div (F.morph_div_theory q),
power_tac (F.power_theory q) [F.is_pow_constant]).
-
- Let sqrt_minus1 := F.of_Z q 2 ^ Z.to_N (q / 4).
+
+ (* Any nonsquare element raised to (q-1)/4 (real implementations use 2 ^ ((q-1)/4) )
+ would work for sqrt_minus1 *)
+ Context (sqrt_minus1 : F q) (sqrt_minus1_valid : sqrt_minus1 * sqrt_minus1 = F.opp 1).
Lemma two_lt_q_5mod8 : 2 < q.
Proof.
@@ -210,7 +210,7 @@ Module F.
Proof.
intros.
transitivity (F.opp 1 * (x * x)); [ | field].
- subst_let; rewrite <-sqrt_minus1_valid.
+ rewrite <-sqrt_minus1_valid.
field.
Qed.