49 proof - |
49 proof - |
50 from `0 < z` have modth: "x mod z \<ge> 0" by simp |
50 from `0 < z` have modth: "x mod z \<ge> 0" by simp |
51 have "(x div z) * z \<le> (x div z) * z" by simp |
51 have "(x div z) * z \<le> (x div z) * z" by simp |
52 then have "(x div z) * z \<le> (x div z) * z + x mod z" using modth by arith |
52 then have "(x div z) * z \<le> (x div z) * z + x mod z" using modth by arith |
53 also have "\<dots> = x" |
53 also have "\<dots> = x" |
54 by (auto simp add: zmod_zdiv_equality [symmetric] zmult_ac) |
54 by (auto simp add: zmod_zdiv_equality [symmetric] mult_ac) |
55 also note `x < y * z` |
55 also note `x < y * z` |
56 finally show ?thesis |
56 finally show ?thesis |
57 apply (auto simp add: mult_less_cancel_right) |
57 apply (auto simp add: mult_less_cancel_right) |
58 using assms apply arith |
58 using assms apply arith |
59 done |
59 done |
113 apply (auto simp add: int_distrib) |
113 apply (auto simp add: int_distrib) |
114 done |
114 done |
115 |
115 |
116 lemma zcong_zmult_prop2: "[a = b](mod m) ==> |
116 lemma zcong_zmult_prop2: "[a = b](mod m) ==> |
117 ([c = d * a](mod m) = [c = d * b] (mod m))" |
117 ([c = d * a](mod m) = [c = d * b] (mod m))" |
118 by (auto simp add: zmult_ac zcong_zmult_prop1) |
118 by (auto simp add: mult_ac zcong_zmult_prop1) |
119 |
119 |
120 lemma zcong_zmult_prop3: "[| zprime p; ~[x = 0] (mod p); |
120 lemma zcong_zmult_prop3: "[| zprime p; ~[x = 0] (mod p); |
121 ~[y = 0] (mod p) |] ==> ~[x * y = 0] (mod p)" |
121 ~[y = 0] (mod p) |] ==> ~[x * y = 0] (mod p)" |
122 apply (auto simp add: zcong_def) |
122 apply (auto simp add: zcong_def) |
123 apply (drule zprime_zdvd_zmult_better, auto) |
123 apply (drule zprime_zdvd_zmult_better, auto) |
124 done |
124 done |
125 |
125 |
126 lemma zcong_less_eq: "[| 0 < x; 0 < y; 0 < m; [x = y] (mod m); |
126 lemma zcong_less_eq: "[| 0 < x; 0 < y; 0 < m; [x = y] (mod m); |
127 x < m; y < m |] ==> x = y" |
127 x < m; y < m |] ==> x = y" |
128 by (metis zcong_not zcong_sym zless_linear) |
128 by (metis zcong_not zcong_sym less_linear) |
129 |
129 |
130 lemma zcong_neg_1_impl_ne_1: |
130 lemma zcong_neg_1_impl_ne_1: |
131 assumes "2 < p" and "[x = -1] (mod p)" |
131 assumes "2 < p" and "[x = -1] (mod p)" |
132 shows "~([x = 1] (mod p))" |
132 shows "~([x = 1] (mod p))" |
133 proof |
133 proof |
196 finally (zcong_trans) show "[x * x ^ nat (p - 2) = 1] (mod p)" . |
196 finally (zcong_trans) show "[x * x ^ nat (p - 2) = 1] (mod p)" . |
197 qed |
197 qed |
198 |
198 |
199 lemma MultInv_prop2a: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==> |
199 lemma MultInv_prop2a: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==> |
200 [(MultInv p x) * x = 1] (mod p)" |
200 [(MultInv p x) * x = 1] (mod p)" |
201 by (auto simp add: MultInv_prop2 zmult_ac) |
201 by (auto simp add: MultInv_prop2 mult_ac) |
202 |
202 |
203 lemma aux_1: "2 < p ==> ((nat p) - 2) = (nat (p - 2))" |
203 lemma aux_1: "2 < p ==> ((nat p) - 2) = (nat (p - 2))" |
204 by (simp add: nat_diff_distrib) |
204 by (simp add: nat_diff_distrib) |
205 |
205 |
206 lemma aux_2: "2 < p ==> 0 < nat (p - 2)" |
206 lemma aux_2: "2 < p ==> 0 < nat (p - 2)" |
225 [(x * (MultInv p x) * (MultInv p (MultInv p x))) = x] (mod p)" |
225 [(x * (MultInv p x) * (MultInv p (MultInv p x))) = x] (mod p)" |
226 apply (frule MultInv_prop3, auto) |
226 apply (frule MultInv_prop3, auto) |
227 apply (insert MultInv_prop2 [of p "MultInv p x"], auto) |
227 apply (insert MultInv_prop2 [of p "MultInv p x"], auto) |
228 apply (drule MultInv_prop2, auto) |
228 apply (drule MultInv_prop2, auto) |
229 apply (drule_tac k = x in zcong_scalar2, auto) |
229 apply (drule_tac k = x in zcong_scalar2, auto) |
230 apply (auto simp add: zmult_ac) |
230 apply (auto simp add: mult_ac) |
231 done |
231 done |
232 |
232 |
233 lemma MultInv_prop4: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==> |
233 lemma MultInv_prop4: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==> |
234 [(MultInv p (MultInv p x)) = x] (mod p)" |
234 [(MultInv p (MultInv p x)) = x] (mod p)" |
235 apply (frule aux__1, auto) |
235 apply (frule aux__1, auto) |
242 [x = y] (mod p)" |
242 [x = y] (mod p)" |
243 apply (drule_tac a = "MultInv p x" and b = "MultInv p y" and |
243 apply (drule_tac a = "MultInv p x" and b = "MultInv p y" and |
244 m = p and k = x in zcong_scalar) |
244 m = p and k = x in zcong_scalar) |
245 apply (insert MultInv_prop2 [of p x], simp) |
245 apply (insert MultInv_prop2 [of p x], simp) |
246 apply (auto simp only: zcong_sym [of "MultInv p x * x"]) |
246 apply (auto simp only: zcong_sym [of "MultInv p x * x"]) |
247 apply (auto simp add: zmult_ac) |
247 apply (auto simp add: mult_ac) |
248 apply (drule zcong_trans, auto) |
248 apply (drule zcong_trans, auto) |
249 apply (drule_tac a = "x * MultInv p y" and k = y in zcong_scalar, auto) |
249 apply (drule_tac a = "x * MultInv p y" and k = y in zcong_scalar, auto) |
250 apply (insert MultInv_prop2a [of p y], auto simp add: zmult_ac) |
250 apply (insert MultInv_prop2a [of p y], auto simp add: mult_ac) |
251 apply (insert zcong_zmult_prop2 [of "y * MultInv p y" 1 p y x]) |
251 apply (insert zcong_zmult_prop2 [of "y * MultInv p y" 1 p y x]) |
252 apply (auto simp add: zcong_sym) |
252 apply (auto simp add: zcong_sym) |
253 done |
253 done |
254 |
254 |
255 lemma MultInv_zcong_prop1: "[| 2 < p; [j = k] (mod p) |] ==> |
255 lemma MultInv_zcong_prop1: "[| 2 < p; [j = k] (mod p) |] ==> |
262 |
262 |
263 lemma aux___2: "[|2 < p; zprime p; ~([k = 0](mod p)); |
263 lemma aux___2: "[|2 < p; zprime p; ~([k = 0](mod p)); |
264 [j * k = a * MultInv p k * k] (mod p) |] ==> [j * k = a] (mod p)" |
264 [j * k = a * MultInv p k * k] (mod p) |] ==> [j * k = a] (mod p)" |
265 apply (insert MultInv_prop2a [of p k] zcong_zmult_prop2 |
265 apply (insert MultInv_prop2a [of p k] zcong_zmult_prop2 |
266 [of "MultInv p k * k" 1 p "j * k" a]) |
266 [of "MultInv p k * k" 1 p "j * k" a]) |
267 apply (auto simp add: zmult_ac) |
267 apply (auto simp add: mult_ac) |
268 done |
268 done |
269 |
269 |
270 lemma aux___3: "[j * k = a] (mod p) ==> [(MultInv p j) * j * k = |
270 lemma aux___3: "[j * k = a] (mod p) ==> [(MultInv p j) * j * k = |
271 (MultInv p j) * a] (mod p)" |
271 (MultInv p j) * a] (mod p)" |
272 by (auto simp add: zmult_assoc zcong_scalar2) |
272 by (auto simp add: mult_assoc zcong_scalar2) |
273 |
273 |
274 lemma aux___4: "[|2 < p; zprime p; ~([j = 0](mod p)); |
274 lemma aux___4: "[|2 < p; zprime p; ~([j = 0](mod p)); |
275 [(MultInv p j) * j * k = (MultInv p j) * a] (mod p) |] |
275 [(MultInv p j) * j * k = (MultInv p j) * a] (mod p) |] |
276 ==> [k = a * (MultInv p j)] (mod p)" |
276 ==> [k = a * (MultInv p j)] (mod p)" |
277 apply (insert MultInv_prop2a [of p j] zcong_zmult_prop1 |
277 apply (insert MultInv_prop2a [of p j] zcong_zmult_prop1 |
278 [of "MultInv p j * j" 1 p "MultInv p j * a" k]) |
278 [of "MultInv p j * j" 1 p "MultInv p j * a" k]) |
279 apply (auto simp add: zmult_ac zcong_sym) |
279 apply (auto simp add: mult_ac zcong_sym) |
280 done |
280 done |
281 |
281 |
282 lemma MultInv_zcong_prop2: "[| 2 < p; zprime p; ~([k = 0](mod p)); |
282 lemma MultInv_zcong_prop2: "[| 2 < p; zprime p; ~([k = 0](mod p)); |
283 ~([j = 0](mod p)); [j = a * MultInv p k] (mod p) |] ==> |
283 ~([j = 0](mod p)); [j = a * MultInv p k] (mod p) |] ==> |
284 [k = a * MultInv p j] (mod p)" |
284 [k = a * MultInv p j] (mod p)" |