Commit | Line | Data |
---|---|---|
7de4d3fe MW |
1 | .\" -*-nroff-*- |
2 | .\" | |
3 | .\" Describe the primality certificate generator and checker | |
4 | .\" | |
5 | .\" (c) 2016 Straylight/Edgeware | |
6 | .\" | |
7 | . | |
8 | .\"----- Licensing notice --------------------------------------------------- | |
9 | .\" | |
10 | .\" This file is part of the Python interface to Catacomb. | |
11 | .\" | |
12 | .\" Catacomb/Python is free software; you can redistribute it and/or modify | |
13 | .\" it under the terms of the GNU General Public License as published by | |
14 | .\" the Free Software Foundation; either version 2 of the License, or | |
15 | .\" (at your option) any later version. | |
16 | .\" | |
17 | .\" Catacomb/Python is distributed in the hope that it will be useful, | |
18 | .\" but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | .\" GNU General Public License for more details. | |
21 | .\" | |
22 | .\" You should have received a copy of the GNU General Public License | |
23 | .\" along with Catacomb/Python; if not, write to the Free Software Foundation, | |
24 | .\" Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
25 | . | |
26 | .ie t \{\ | |
27 | . if \n(.g \{\ | |
28 | . fam P | |
29 | . \} | |
30 | . ds o \(bu | |
31 | . ds ss \s7\v'-4p' | |
32 | . ds se \v'4p'\s0 | |
33 | . ds us \s7\v'2p' | |
34 | . ds ue \v'-2p'\s0 | |
35 | . ds *e \(*e | |
36 | . ds mo \(mo | |
37 | . ds sr \(sr | |
38 | . ds cu \(cu | |
39 | . ds ca \(ca | |
40 | . ds iy \(if | |
41 | . ds == \(== | |
42 | . ds .. \&.\h'2p'.\h'2p'.\& | |
43 | . ds /= \h'(\w'\*(=='-\w'/')/2'/\h'-(\w'\*(=='+\w'/')/2'\*(== | |
44 | .\} | |
45 | .el \{\ | |
46 | . ds o o | |
47 | . ds ss ^ | |
48 | . ds se | |
49 | . ds us _ | |
50 | . ds ue | |
51 | . ds *e \fIepsilon\fP | |
52 | . ds mo in | |
53 | . ds sr sqrt | |
54 | . ds cu union | |
55 | . ds ca isect | |
56 | . ds iy infty | |
57 | . ds == == | |
58 | . ds .. \&...\& | |
59 | . ds /= /== | |
60 | .\} | |
61 | .de hP | |
62 | .IP | |
63 | \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c | |
64 | .. | |
65 | . | |
66 | .TH pock 1 "28 May 2017" "Straylight/Edgeware" "Catacomb cryptographic library" | |
67 | .SH NAME | |
68 | pock \- generate and verify primality certificates | |
69 | . | |
70 | .\"-------------------------------------------------------------------------- | |
71 | .SH SYNOPSIS | |
72 | . | |
73 | .B pock | |
74 | .RB [ \-qv ] | |
75 | .I command | |
76 | .IR [ arguments ...] | |
77 | .PP | |
78 | Subcommands: | |
79 | .RS | |
80 | .br | |
81 | .B gen | |
82 | .I nbits | |
83 | .br | |
84 | .B ll | |
85 | .I nbits | |
86 | .I nsubbits | |
87 | .br | |
88 | .B check | |
89 | .RI [ file ] | |
90 | .RE | |
91 | . | |
92 | .\"-------------------------------------------------------------------------- | |
93 | .SH DESCRIPTION | |
94 | . | |
95 | Many cryptographic protocols make use of large prime numbers. | |
96 | The usual way of determining primality in such circumstances | |
97 | is due to Rabin and Miller. | |
98 | Given a candidate | |
99 | .I n | |
100 | and a | |
101 | .I witness | |
102 | 2 \(<= | |
103 | .I a | |
104 | < | |
105 | .IR n , | |
106 | the test answers either `composite' or `unknown'. | |
107 | If | |
108 | .I n | |
109 | is prime then the test answers `unknown' for every witness | |
110 | .IR a ; | |
111 | if | |
112 | .I n | |
113 | is in fact composite | |
114 | then the test answers `composite' | |
115 | for at least three quarters of the possible witnesses. | |
116 | If | |
117 | .I n | |
118 | is a composite, | |
119 | then the witnesses | |
120 | .I a | |
121 | for which the test reports `unknown' | |
122 | are called | |
123 | .IR liars . | |
124 | .PP | |
125 | Naively, then, | |
126 | to reduce the probability of falsely accepting a composite | |
127 | below some bound \*(*e, | |
128 | one must perform | |
129 | \-(log\*(us2\*(ue \*(*e)/2 | |
130 | iterations of the test, | |
131 | with independent, uniformly distributed witnesses. | |
132 | This is especially slow when high security levels are wanted, | |
133 | both because tests take longer on larger candidate numbers, | |
134 | and because one must do more tests | |
135 | to reach the necessary higher confidence level. | |
136 | .PP | |
137 | The above is a worst-case bound: | |
138 | very few composite numbers | |
139 | .I n | |
140 | have anywhere near | |
141 | .IR n /4 | |
142 | liars. | |
143 | In situations such as RSA key generation, | |
144 | the user generating the prime number is the only one | |
145 | who must be convinced of the number's primality, | |
146 | and they have valuable additional knowledge: | |
147 | specifically that the candidate has been chosen at random | |
148 | according to some suitable probability distribution. | |
149 | In this case, one needs many fewer iterations, | |
150 | and the number of iterations needed | |
151 | .I decreases | |
152 | with the size of the candidate being tested. | |
153 | .PP | |
154 | But in cases where many users must share some large prime parameter, | |
155 | each of them must test the proposed prime separately, | |
156 | and often they must pessimistically assume | |
157 | that the number was chosen maliciously, | |
158 | and the worst-case | |
159 | .IR n /4 | |
13c5ef39 | 160 | bound is the best one can do using the Rabin\(enMiller test. |
7de4d3fe MW |
161 | For large candidates, |
162 | this is inconveniently slow. | |
163 | (Also, many implementations incorrectly use | |
164 | a number of iterations suitable for randomly chosen primes | |
165 | for testing candidates of unknown provenance.) | |
166 | .PP | |
13c5ef39 MW |
167 | There |
168 | .I are | |
169 | stronger probabilistic tests. | |
170 | A combination of Rabin\(enMiller and | |
171 | Grantham's Frobenius test | |
172 | is known as the | |
173 | Baillie\(enPSW test | |
174 | (after Baillie, Pomerance, Selfridge, and Wagstaff); | |
175 | there are | |
176 | .I no | |
177 | known composites which pass this test, | |
178 | nor is it known how to construct any. | |
179 | On the other hand, it's been conjectured that | |
180 | infinitely many Baillie\(enPSW pseudoprimes exist. | |
181 | While it may be reasonable to assume | |
182 | the strength of the Baillie\(enPSW test, | |
183 | it must be borne in mind that this | |
184 | .I does | |
185 | constitute a security assumption. | |
186 | .PP | |
187 | By contrast,the | |
7de4d3fe MW |
188 | .B pock |
189 | program will generate prime numbers | |
190 | of sizes suitable for use in cryptography, | |
191 | along with a | |
192 | .I certificate of primality | |
193 | which can be independently verified fairly efficiently. | |
194 | Specifically, verifying a proof takes a little longer | |
195 | than a single iteration of the Rabin\(enMiller probabilistic test. | |
196 | It can also verify such certificates. | |
197 | .PP | |
198 | Note that the primes selected by | |
199 | .B pock | |
200 | are a long way from uniformly distributed. | |
201 | Indeed, they have somewhat unusual structure, | |
202 | but it seems unlikely that this structure | |
203 | renders them unsuitable for e.g., discrete-logarithm cryptography. | |
204 | . | |
205 | .SS "Command line" | |
206 | The following options are recognized. | |
207 | .TP | |
208 | .B "\-h, \-\-help" | |
209 | Write help text to standard output and exit with status 0. | |
210 | .TP | |
211 | .B "\-q, \-\-quiet" | |
212 | Be less verbose during prime generation or certificate verification. | |
213 | .TP | |
214 | .B "\-v, \-\-verbose" | |
215 | Be more verbose during prime generation or certificate verification. | |
216 | .TP | |
217 | .BI "\-s, \-\-sievebits " b | |
218 | When generating certificates, | |
219 | require that the verifier can check numbers smaller than | |
220 | .RI 2\*(ss b \*(se | |
221 | without assistance. | |
222 | Larger values lead to sightly shorter proofs, | |
223 | but spend more time at startup constructing a sieve; | |
224 | smaller values lead to somewhat longer proofs, | |
225 | but spend less time constructing the sieve. | |
226 | The default is 32, | |
227 | which seems to work well in practice. | |
228 | . | |
229 | .SS "gen" | |
230 | The | |
231 | .B gen | |
232 | command generates a prime | |
233 | .I p | |
234 | which is | |
235 | .I nbits | |
236 | long (i.e., | |
237 | .RI 2\*(ss nbits \-1\*(se | |
238 | < | |
239 | .I p | |
240 | < | |
241 | .RI 2\*(ss nbits \*(se, | |
242 | and writes a certificate to standard output. | |
243 | By default, mysterious runes are written to standard error | |
244 | to keep the user amused and informed about the operation's progress; | |
245 | the | |
246 | .B \-q | |
247 | option suppresses the runes; | |
248 | the | |
249 | .B \-v | |
250 | option produces more detailed runes. | |
251 | . | |
252 | .SS "ll" | |
253 | The | |
254 | .B ll | |
255 | command generates a Lim\(enLee prime | |
256 | .I p | |
257 | = | |
258 | 2 | |
259 | .IR q \*(us0\*(ue | |
260 | .IR q \*(us1\*(ue | |
261 | \*(.. | |
262 | .IR q \*(us k \*(ue | |
263 | + | |
264 | 1 | |
265 | which is | |
266 | .I nbits | |
267 | long (i.e., | |
268 | .RI 2\*(ss nbits \-1\*(se | |
269 | < | |
270 | .I p | |
271 | < | |
272 | .RI 2\*(ss nbits \*(se, | |
273 | such that each | |
274 | .IR q \*(us i \*(ue | |
275 | is an | |
276 | .IR nsubbits -bit | |
277 | prime, for | |
278 | 0 \(<= | |
279 | .I i | |
280 | < | |
281 | .IR k , | |
282 | and | |
283 | .IR q \*(us k \*(ue | |
284 | is an | |
285 | .IR nsubbits -bit | |
286 | prime, | |
287 | and writes a certificate to standard output. | |
288 | By default, mysterious runes are written to standard error | |
289 | to keep the user amused and informed about the operation's progress; | |
290 | the | |
291 | .B \-q | |
292 | option suppresses the runes; | |
293 | the | |
294 | .B \-v | |
295 | option produces more detailed runes. | |
296 | . | |
297 | .SS "check" | |
298 | The | |
299 | .B check | |
300 | command reads a primality certificate from the named | |
301 | .I file | |
302 | or from standard input, | |
303 | and checks it. | |
304 | By default, | |
305 | each | |
306 | .B check | |
307 | line in the certificate causes a line | |
308 | .IP | |
309 | .B ;; | |
310 | .I label | |
311 | .B = | |
312 | .I n | |
313 | .BI [ b ] | |
314 | .PP | |
315 | to be printed to standard output, | |
316 | listing the prime's | |
317 | .IR label , | |
318 | value | |
319 | .IR n , | |
320 | and length | |
321 | .I b | |
322 | in bits; | |
323 | this behaviour is inhibited by the | |
324 | .B \-q | |
325 | option. | |
326 | . | |
327 | .SS Runes | |
328 | The following mysterious runes are printed during prime searches. | |
329 | This information is provided for diagnostic purposes | |
330 | and to satisfy idle curiosity: | |
331 | later versions may print different runes, | |
332 | or use the same rune characters to mean different things. | |
333 | .TP | |
334 | .B ! | |
335 | Started to generate a large prime. | |
336 | The next step is to generate a number of smaller primes. | |
337 | Usually, this will only need to be done once. | |
338 | .TP | |
339 | .B . | |
340 | Candidate failed a Fermat test. | |
341 | .TP | |
342 | .B * | |
343 | Candidate passed a Fermat test. | |
344 | This is usually the last rune for a prime search. | |
345 | .TP | |
346 | .B @ | |
347 | A candidate generator failed to generate the necessary subgroup. | |
348 | This is unusual. | |
349 | .TP | |
350 | .B < | |
351 | For Lim\(enLee primes, | |
352 | discarding the large prime | |
353 | because it produces results which are too small. | |
354 | .TP | |
355 | .B > | |
356 | For Lim\(enLee primes, | |
357 | discarding the large prime | |
358 | because it produces results which are too large. | |
359 | .TP | |
360 | .B [ | |
361 | Starting a subsidiary prime search. | |
362 | .TP | |
363 | .B ] | |
364 | Finished a subsidiary prime search. | |
365 | . | |
366 | .\"-------------------------------------------------------------------------- | |
367 | .SH CERTIFICATE FORMAT | |
368 | . | |
369 | A certificate consists of a number of lines. | |
370 | Blank lines, | |
371 | and lines beginning with a | |
372 | .RB ` ; ', | |
373 | are ignored. | |
374 | Other lines are as follows. | |
375 | .TP | |
376 | .BI "sievebits " b | |
377 | Declares that the verifier is expected to be able to check | |
378 | primes smaller than | |
379 | .RI 2\*(ss b \*(se | |
380 | for primality for itself. | |
381 | A | |
382 | .B sievebits | |
383 | line must appear before the first | |
384 | .B small | |
385 | line. | |
386 | .TP | |
387 | .BI "small " label " = " p | |
388 | Asserts that | |
389 | .I p | |
390 | is a small prime, | |
391 | and associates it with the | |
392 | .IR label . | |
393 | It is an error if the label has been assigned by a previous line. | |
394 | It is required that | |
395 | 1 < | |
396 | .I p | |
397 | < | |
398 | .RI 2\*(ss b \*(se | |
399 | and that | |
400 | .I p | |
401 | is prime. | |
402 | Such small primes constitute the leaves of a proof tree. | |
403 | .TP | |
404 | .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]" | |
405 | Asserts that a number | |
406 | .I n | |
407 | (defined below) is prime by Pocklington's criterion, | |
408 | and associates it with the | |
409 | .IR label . | |
410 | It is an error if the label has been assigned by a previous line. | |
411 | .RS | |
412 | .PP | |
413 | The strings | |
414 | .IR i , | |
415 | .IR j , | |
416 | \*(.. | |
417 | must be labels assigned by earlier lines. | |
418 | For each such label | |
419 | .IR i , | |
420 | let | |
421 | .IR q \*(us i \*(ue | |
422 | be the associated prime. | |
423 | Let | |
424 | .I Q | |
425 | = | |
426 | .IR q \*(us i \*(ue | |
427 | .IR q \*(us j \*(ue | |
428 | \*(.. | |
429 | be the product of these primes. | |
430 | Let | |
431 | .I n | |
432 | = | |
433 | .RI 2 QR | |
434 | + | |
435 | 1. | |
436 | It is required that: | |
437 | .hP 1. | |
438 | The | |
439 | .IR q \*(us i \*(ue | |
440 | are distinct. | |
441 | .hP 2. | |
442 | .IR Q \*(ss2\*(se | |
443 | \(>= | |
444 | .IR n . | |
445 | .hP 3. | |
446 | .IR a \*(ss n \-1\*(se | |
447 | \*(== | |
448 | 1 | |
449 | (mod | |
450 | .IR n ). | |
451 | .hP 4. | |
452 | .RI gcd( a \*(ss( n \-1)/ q \*(se | |
453 | \- | |
454 | 1, | |
455 | .IR n ) | |
456 | = | |
457 | 1 | |
458 | for each prime | |
459 | .IR q | |
460 | dividing | |
461 | .IR Q . | |
462 | .PP | |
463 | To see why this works, let | |
464 | .I p | |
465 | be the smallest prime factor of | |
466 | .IR n . | |
467 | From | |
468 | .B 3 | |
469 | we see that | |
470 | the order of | |
471 | .I a | |
472 | in | |
473 | .RB ( Z /\fIp Z )\*(ss\(**\*(se | |
474 | divides | |
7db83a89 | 475 | .I n |
7de4d3fe MW |
476 | \- |
477 | 1. | |
478 | Consider some prime | |
479 | .I q | |
480 | dividing | |
481 | .I Q | |
482 | and let | |
483 | .I t | |
484 | = | |
485 | .IR a \*(ss( n \-1)/ q \*(se; | |
486 | then | |
487 | .I t | |
488 | has order dividing | |
489 | .IR q . | |
490 | From | |
491 | .BR 4 , | |
492 | we have | |
69afd8a9 | 493 | .I t |
7de4d3fe MW |
494 | \*(/= |
495 | 1 | |
496 | (mod | |
497 | .IR p ), | |
498 | and hence | |
499 | .I t | |
500 | has order precisely | |
501 | .I q | |
502 | in | |
503 | .RB ( Z /\fIp Z )\*(ss\(**\*(se. | |
504 | This implies that | |
505 | .I q | |
506 | divides | |
507 | .I p | |
508 | \- | |
509 | 1. | |
510 | Since this holds for each prime | |
511 | .I q | |
512 | dividing | |
513 | .IR Q , | |
514 | and, | |
515 | from | |
516 | .BR 1 , | |
5ddddeff | 517 | these primes are distinct, |
7de4d3fe MW |
518 | we deduce that |
519 | .I Q | |
520 | divides | |
521 | .I p | |
522 | \- | |
523 | 1 | |
524 | and hence that | |
525 | .I p | |
526 | > | |
527 | .IR Q . | |
528 | Let | |
529 | .IR p \(fm | |
530 | be any prime factor of | |
531 | .IR n / p . | |
532 | Then | |
533 | .IR p \(fm | |
534 | \(>= | |
535 | .I p | |
536 | > | |
537 | .I Q | |
538 | so, | |
539 | from | |
540 | .BR 2 , | |
541 | .IR pp \(fm | |
542 | > | |
543 | .IR Q \*(ss2\*(se | |
544 | \(>= | |
545 | .IR n ; | |
546 | but | |
547 | .IR pp \(fm | |
548 | divides | |
549 | .I n | |
550 | so this is a contradiction. | |
551 | We must conclude that | |
552 | .IR p \(fm | |
553 | does not exist, | |
554 | and | |
555 | .I n | |
556 | must be prime. | |
557 | .RE | |
558 | .TP | |
559 | .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]" | |
560 | Asserts that the number | |
561 | .I n | |
562 | is prime by Goldwasser and Kilian's ECPP method, | |
563 | and associates it with the | |
564 | .IR label . | |
565 | It is an error if the label has been assigned by a previous line. | |
566 | .RS | |
567 | .PP | |
568 | The strings | |
569 | .IR i , | |
570 | .IR j , | |
571 | \*.. | |
572 | must be labels assigned by earlier lines. | |
573 | For each such label | |
574 | .IR i , | |
575 | let | |
576 | .IR q \*(us i \*(ue | |
577 | be the associated prime. | |
578 | Let | |
579 | .I Q | |
580 | = | |
581 | .IR q \*(us i \*(ue | |
582 | .IR q \*(us j \*(ue | |
583 | \*(.. | |
584 | be the product of these primes. | |
585 | Define | |
586 | .I E\*(usn\*(ue | |
587 | = { | |
588 | .RI ( x ", " y ) | |
589 | \*(mo | |
590 | .RB ( Z /\fIn Z )\*(ss2\*(se | |
591 | | | |
592 | .IR y \*(ss2\*(se | |
593 | = | |
594 | .IR x \*(ss3\*(se | |
595 | + | |
596 | .I Ax | |
597 | + | |
598 | .I B | |
599 | } | |
600 | \*(cu | |
601 | { \*(iy }; | |
602 | if | |
603 | .I n | |
604 | is prime and the curve is not singular | |
605 | then this is the elliptic curve over | |
606 | .RI GF( n ) | |
607 | with short-Weierstrass coefficients | |
608 | .I A | |
609 | and | |
610 | .IR B . | |
611 | Let | |
612 | .I R | |
613 | = | |
614 | .RI ( x , | |
615 | .IR y ). | |
616 | It is required that: | |
617 | .hP 1. | |
618 | .I g | |
619 | = | |
620 | .RI gcd(4 a \*(ss3\*(se | |
621 | + | |
622 | .RI 27 b \*(ss2\*(se, | |
623 | .IR n ) | |
624 | = 1. | |
625 | .hP 2. | |
626 | .I R | |
627 | \*(mo | |
628 | .IR E\*(usn\*(ue ; | |
629 | i.e., | |
630 | .IR y \*(ss2\*(se | |
631 | \*(== | |
632 | .IR x \*(ss3\*(se | |
633 | + | |
634 | .I Ax | |
635 | + | |
636 | .I B | |
637 | (mod | |
638 | .IR n ). | |
639 | .hP 3. The | |
640 | .I q\*(usi\*(ue | |
641 | are distinct. | |
642 | .hP 4. | |
643 | .IR QR , | |
644 | the elliptic-curve scalar product of the point | |
645 | .I R | |
646 | by the integer | |
647 | .IR Q , | |
648 | calculated as if | |
649 | .I E | |
650 | is a true elliptic curve, | |
651 | is the point at infinity. | |
652 | .hP 5. | |
653 | .RI ( Q / q ) R | |
654 | is finite for each prime | |
655 | .I q | |
656 | dividing | |
657 | .IR Q . | |
658 | .hP 6. | |
659 | .I Q | |
660 | > | |
661 | .RI ( n \*(ss1/4\*(se | |
662 | + 1)\*(ss2\*(se. | |
663 | .PP | |
664 | To see why this test works, let | |
665 | .I p | |
666 | be the smallest prime factor of | |
667 | .IR n , | |
668 | and let | |
669 | .I E\*(usp\*(ue | |
670 | = { | |
671 | .RI ( x ", " y ) | |
672 | \*(mo | |
673 | .RI GF( p )\*(ss2\*(se | |
674 | | | |
675 | .IR y \*(ss2\*(se | |
676 | = | |
677 | .IR x \*(ss3\*(se | |
678 | + | |
679 | .I Ax | |
680 | + | |
681 | .I B | |
682 | } | |
683 | \*(cu | |
684 | { \*(iy }. | |
685 | From | |
686 | .BR 1 , | |
687 | .I g | |
688 | = 1, | |
689 | .I E\*(usp\*(ue | |
690 | is an elliptic curve. | |
691 | (If 1 < | |
692 | .I g | |
693 | < | |
694 | .I n | |
695 | then | |
696 | .I g | |
697 | is a proper factor of | |
698 | .I n | |
699 | and | |
700 | .I n | |
701 | is certainly not prime; | |
702 | if | |
703 | .I g | |
704 | = | |
705 | .I n | |
706 | then the curve will be singular and the test fails.) | |
707 | From | |
708 | .BR 2 , | |
709 | .I R | |
710 | is a point on | |
711 | .IR E\*(usp\*(ue . | |
712 | From | |
713 | .BR 4 , | |
714 | .I R | |
715 | has | |
716 | .IR Q -torsion | |
717 | in | |
718 | .IR E\*(usp\*(ue . | |
719 | Consider some prime | |
720 | .I q | |
721 | dividing | |
722 | .I Q | |
723 | and let | |
724 | .I T | |
725 | = | |
726 | .RI ( Q/q ) R ; | |
727 | then | |
728 | .I T | |
729 | has torsion dividing | |
730 | .IR q . | |
731 | From | |
732 | .BR 5 , | |
733 | .RI ( Q/q ) R | |
734 | \(!= 0, | |
735 | and hence | |
736 | .I T | |
737 | has order precisely | |
738 | .I q | |
739 | in | |
740 | .IR E\*(usp\*(ue . | |
741 | This implies that | |
742 | .I q | |
743 | divides | |
744 | .RI # E\*(usp\*(ue . | |
745 | Since this holds for each prime | |
746 | .I q | |
747 | dividing | |
748 | .IR Q , | |
749 | and, from | |
750 | .BR 3 , | |
751 | the | |
752 | .I q | |
753 | are distinct, | |
754 | we deduce that | |
755 | .I Q | |
756 | divides | |
757 | .RI # E\*(usp\*(ue | |
758 | and hence that | |
759 | .RI # E\*(usp\*(ue | |
760 | \(>= | |
761 | .IR Q . | |
762 | Hasse's theorem tells us that | |
763 | .RI | p | |
764 | + 1 \- | |
765 | .RI # E\*(usp\*(ue | | |
766 | \(<= | |
767 | .RI 2\*(sr p , | |
79033570 MW |
768 | so, in particular, |
769 | .RI # E\*(usp\*(ue | |
770 | \- | |
771 | .I p | |
772 | \- 1 | |
773 | \(<= | |
774 | .RI 2\*(sr p , | |
7de4d3fe MW |
775 | whence |
776 | .I p | |
777 | + 1 + | |
778 | .RI 2\*(sr p | |
779 | = | |
780 | .RI (\*(sr p | |
781 | + 1)\*(ss2\*(se | |
782 | \(>= | |
783 | .RI # E\*(usp\*(ue | |
784 | \(>= | |
785 | .IR Q | |
786 | > | |
787 | .RI ( n \*(ss1/4\*(se | |
788 | + 1)\*(ss2\*(se | |
789 | (from | |
790 | .BR 6 ); | |
791 | so | |
792 | .IR p\*(ss2\*(se | |
793 | > | |
794 | .IR n . | |
795 | Let | |
796 | .IR p \(fm | |
797 | be any prime factor of | |
798 | .IR n / p . | |
799 | Then | |
800 | .IR p \(fm | |
801 | \(>= | |
802 | .I p | |
803 | and | |
804 | .IR pp \(fm | |
805 | \(>= | |
806 | .IR p \*(ss2\*(se | |
807 | > | |
808 | .IR n ; | |
809 | but | |
810 | .IR pp \(fm | |
811 | divides | |
812 | .I n | |
813 | so this is a contradiction. | |
814 | We must conclude that | |
815 | .IR p \(fm | |
816 | does not exist, | |
817 | and | |
818 | .I n | |
819 | must be prime. | |
820 | .PP | |
821 | Note that | |
822 | .B pock | |
823 | currently cannot generate proofs which use | |
824 | .BR ecpp , | |
825 | though it will verify them. | |
826 | .RE | |
827 | .TP | |
828 | .BI "check " label ", " b ", " p | |
829 | Verify that the prime associated with the | |
830 | .I label | |
831 | is equal to | |
832 | .I p | |
833 | and that it is | |
834 | .I b | |
835 | bits long; | |
836 | i.e., that | |
837 | .RI 2\*(ss b \-1\*(se | |
838 | \(<= | |
839 | .I p | |
840 | < | |
841 | .RI 2\*(ss b \*(se. | |
842 | Unless | |
843 | inhibited by | |
844 | .BR \-q , | |
845 | the label and value are printed to stdout during verification. | |
846 | . | |
847 | .\"-------------------------------------------------------------------------- | |
848 | .SH "SEE ALSO" | |
849 | .BR key (1). | |
850 | .SH AUTHOR | |
851 | Mark Wooding, <mdw@distorted.org.uk> | |
852 | . | |
853 | .\"----- That's all, folks -------------------------------------------------- |