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 | |
160 | bound is the best one can do. | |
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 | |
167 | The | |
168 | .B pock | |
169 | program will generate prime numbers | |
170 | of sizes suitable for use in cryptography, | |
171 | along with a | |
172 | .I certificate of primality | |
173 | which can be independently verified fairly efficiently. | |
174 | Specifically, verifying a proof takes a little longer | |
175 | than a single iteration of the Rabin\(enMiller probabilistic test. | |
176 | It can also verify such certificates. | |
177 | .PP | |
178 | Note that the primes selected by | |
179 | .B pock | |
180 | are a long way from uniformly distributed. | |
181 | Indeed, they have somewhat unusual structure, | |
182 | but it seems unlikely that this structure | |
183 | renders them unsuitable for e.g., discrete-logarithm cryptography. | |
184 | . | |
185 | .SS "Command line" | |
186 | The following options are recognized. | |
187 | .TP | |
188 | .B "\-h, \-\-help" | |
189 | Write help text to standard output and exit with status 0. | |
190 | .TP | |
191 | .B "\-q, \-\-quiet" | |
192 | Be less verbose during prime generation or certificate verification. | |
193 | .TP | |
194 | .B "\-v, \-\-verbose" | |
195 | Be more verbose during prime generation or certificate verification. | |
196 | .TP | |
197 | .BI "\-s, \-\-sievebits " b | |
198 | When generating certificates, | |
199 | require that the verifier can check numbers smaller than | |
200 | .RI 2\*(ss b \*(se | |
201 | without assistance. | |
202 | Larger values lead to sightly shorter proofs, | |
203 | but spend more time at startup constructing a sieve; | |
204 | smaller values lead to somewhat longer proofs, | |
205 | but spend less time constructing the sieve. | |
206 | The default is 32, | |
207 | which seems to work well in practice. | |
208 | . | |
209 | .SS "gen" | |
210 | The | |
211 | .B gen | |
212 | command generates a prime | |
213 | .I p | |
214 | which is | |
215 | .I nbits | |
216 | long (i.e., | |
217 | .RI 2\*(ss nbits \-1\*(se | |
218 | < | |
219 | .I p | |
220 | < | |
221 | .RI 2\*(ss nbits \*(se, | |
222 | and writes a certificate to standard output. | |
223 | By default, mysterious runes are written to standard error | |
224 | to keep the user amused and informed about the operation's progress; | |
225 | the | |
226 | .B \-q | |
227 | option suppresses the runes; | |
228 | the | |
229 | .B \-v | |
230 | option produces more detailed runes. | |
231 | . | |
232 | .SS "ll" | |
233 | The | |
234 | .B ll | |
235 | command generates a Lim\(enLee prime | |
236 | .I p | |
237 | = | |
238 | 2 | |
239 | .IR q \*(us0\*(ue | |
240 | .IR q \*(us1\*(ue | |
241 | \*(.. | |
242 | .IR q \*(us k \*(ue | |
243 | + | |
244 | 1 | |
245 | which is | |
246 | .I nbits | |
247 | long (i.e., | |
248 | .RI 2\*(ss nbits \-1\*(se | |
249 | < | |
250 | .I p | |
251 | < | |
252 | .RI 2\*(ss nbits \*(se, | |
253 | such that each | |
254 | .IR q \*(us i \*(ue | |
255 | is an | |
256 | .IR nsubbits -bit | |
257 | prime, for | |
258 | 0 \(<= | |
259 | .I i | |
260 | < | |
261 | .IR k , | |
262 | and | |
263 | .IR q \*(us k \*(ue | |
264 | is an | |
265 | .IR nsubbits -bit | |
266 | prime, | |
267 | and writes a certificate to standard output. | |
268 | By default, mysterious runes are written to standard error | |
269 | to keep the user amused and informed about the operation's progress; | |
270 | the | |
271 | .B \-q | |
272 | option suppresses the runes; | |
273 | the | |
274 | .B \-v | |
275 | option produces more detailed runes. | |
276 | . | |
277 | .SS "check" | |
278 | The | |
279 | .B check | |
280 | command reads a primality certificate from the named | |
281 | .I file | |
282 | or from standard input, | |
283 | and checks it. | |
284 | By default, | |
285 | each | |
286 | .B check | |
287 | line in the certificate causes a line | |
288 | .IP | |
289 | .B ;; | |
290 | .I label | |
291 | .B = | |
292 | .I n | |
293 | .BI [ b ] | |
294 | .PP | |
295 | to be printed to standard output, | |
296 | listing the prime's | |
297 | .IR label , | |
298 | value | |
299 | .IR n , | |
300 | and length | |
301 | .I b | |
302 | in bits; | |
303 | this behaviour is inhibited by the | |
304 | .B \-q | |
305 | option. | |
306 | . | |
307 | .SS Runes | |
308 | The following mysterious runes are printed during prime searches. | |
309 | This information is provided for diagnostic purposes | |
310 | and to satisfy idle curiosity: | |
311 | later versions may print different runes, | |
312 | or use the same rune characters to mean different things. | |
313 | .TP | |
314 | .B ! | |
315 | Started to generate a large prime. | |
316 | The next step is to generate a number of smaller primes. | |
317 | Usually, this will only need to be done once. | |
318 | .TP | |
319 | .B . | |
320 | Candidate failed a Fermat test. | |
321 | .TP | |
322 | .B * | |
323 | Candidate passed a Fermat test. | |
324 | This is usually the last rune for a prime search. | |
325 | .TP | |
326 | .B @ | |
327 | A candidate generator failed to generate the necessary subgroup. | |
328 | This is unusual. | |
329 | .TP | |
330 | .B < | |
331 | For Lim\(enLee primes, | |
332 | discarding the large prime | |
333 | because it produces results which are too small. | |
334 | .TP | |
335 | .B > | |
336 | For Lim\(enLee primes, | |
337 | discarding the large prime | |
338 | because it produces results which are too large. | |
339 | .TP | |
340 | .B [ | |
341 | Starting a subsidiary prime search. | |
342 | .TP | |
343 | .B ] | |
344 | Finished a subsidiary prime search. | |
345 | . | |
346 | .\"-------------------------------------------------------------------------- | |
347 | .SH CERTIFICATE FORMAT | |
348 | . | |
349 | A certificate consists of a number of lines. | |
350 | Blank lines, | |
351 | and lines beginning with a | |
352 | .RB ` ; ', | |
353 | are ignored. | |
354 | Other lines are as follows. | |
355 | .TP | |
356 | .BI "sievebits " b | |
357 | Declares that the verifier is expected to be able to check | |
358 | primes smaller than | |
359 | .RI 2\*(ss b \*(se | |
360 | for primality for itself. | |
361 | A | |
362 | .B sievebits | |
363 | line must appear before the first | |
364 | .B small | |
365 | line. | |
366 | .TP | |
367 | .BI "small " label " = " p | |
368 | Asserts that | |
369 | .I p | |
370 | is a small prime, | |
371 | and associates it with the | |
372 | .IR label . | |
373 | It is an error if the label has been assigned by a previous line. | |
374 | It is required that | |
375 | 1 < | |
376 | .I p | |
377 | < | |
378 | .RI 2\*(ss b \*(se | |
379 | and that | |
380 | .I p | |
381 | is prime. | |
382 | Such small primes constitute the leaves of a proof tree. | |
383 | .TP | |
384 | .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]" | |
385 | Asserts that a number | |
386 | .I n | |
387 | (defined below) is prime by Pocklington's criterion, | |
388 | and associates it with the | |
389 | .IR label . | |
390 | It is an error if the label has been assigned by a previous line. | |
391 | .RS | |
392 | .PP | |
393 | The strings | |
394 | .IR i , | |
395 | .IR j , | |
396 | \*(.. | |
397 | must be labels assigned by earlier lines. | |
398 | For each such label | |
399 | .IR i , | |
400 | let | |
401 | .IR q \*(us i \*(ue | |
402 | be the associated prime. | |
403 | Let | |
404 | .I Q | |
405 | = | |
406 | .IR q \*(us i \*(ue | |
407 | .IR q \*(us j \*(ue | |
408 | \*(.. | |
409 | be the product of these primes. | |
410 | Let | |
411 | .I n | |
412 | = | |
413 | .RI 2 QR | |
414 | + | |
415 | 1. | |
416 | It is required that: | |
417 | .hP 1. | |
418 | The | |
419 | .IR q \*(us i \*(ue | |
420 | are distinct. | |
421 | .hP 2. | |
422 | .IR Q \*(ss2\*(se | |
423 | \(>= | |
424 | .IR n . | |
425 | .hP 3. | |
426 | .IR a \*(ss n \-1\*(se | |
427 | \*(== | |
428 | 1 | |
429 | (mod | |
430 | .IR n ). | |
431 | .hP 4. | |
432 | .RI gcd( a \*(ss( n \-1)/ q \*(se | |
433 | \- | |
434 | 1, | |
435 | .IR n ) | |
436 | = | |
437 | 1 | |
438 | for each prime | |
439 | .IR q | |
440 | dividing | |
441 | .IR Q . | |
442 | .PP | |
443 | To see why this works, let | |
444 | .I p | |
445 | be the smallest prime factor of | |
446 | .IR n . | |
447 | From | |
448 | .B 3 | |
449 | we see that | |
450 | the order of | |
451 | .I a | |
452 | in | |
453 | .RB ( Z /\fIp Z )\*(ss\(**\*(se | |
454 | divides | |
455 | .I p | |
456 | \- | |
457 | 1. | |
458 | Consider some prime | |
459 | .I q | |
460 | dividing | |
461 | .I Q | |
462 | and let | |
463 | .I t | |
464 | = | |
465 | .IR a \*(ss( n \-1)/ q \*(se; | |
466 | then | |
467 | .I t | |
468 | has order dividing | |
469 | .IR q . | |
470 | From | |
471 | .BR 4 , | |
472 | we have | |
473 | .IR t \*(ss q \*(se | |
474 | \*(/= | |
475 | 1 | |
476 | (mod | |
477 | .IR p ), | |
478 | and hence | |
479 | .I t | |
480 | has order precisely | |
481 | .I q | |
482 | in | |
483 | .RB ( Z /\fIp Z )\*(ss\(**\*(se. | |
484 | This implies that | |
485 | .I q | |
486 | divides | |
487 | .I p | |
488 | \- | |
489 | 1. | |
490 | Since this holds for each prime | |
491 | .I q | |
492 | dividing | |
493 | .IR Q , | |
494 | and, | |
495 | from | |
496 | .BR 1 , | |
497 | the | |
498 | .I q | |
499 | are distinct, | |
500 | we deduce that | |
501 | .I Q | |
502 | divides | |
503 | .I p | |
504 | \- | |
505 | 1 | |
506 | and hence that | |
507 | .I p | |
508 | > | |
509 | .IR Q . | |
510 | Let | |
511 | .IR p \(fm | |
512 | be any prime factor of | |
513 | .IR n / p . | |
514 | Then | |
515 | .IR p \(fm | |
516 | \(>= | |
517 | .I p | |
518 | > | |
519 | .I Q | |
520 | so, | |
521 | from | |
522 | .BR 2 , | |
523 | .IR pp \(fm | |
524 | > | |
525 | .IR Q \*(ss2\*(se | |
526 | \(>= | |
527 | .IR n ; | |
528 | but | |
529 | .IR pp \(fm | |
530 | divides | |
531 | .I n | |
532 | so this is a contradiction. | |
533 | We must conclude that | |
534 | .IR p \(fm | |
535 | does not exist, | |
536 | and | |
537 | .I n | |
538 | must be prime. | |
539 | .RE | |
540 | .TP | |
541 | .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]" | |
542 | Asserts that the number | |
543 | .I n | |
544 | is prime by Goldwasser and Kilian's ECPP method, | |
545 | and associates it with the | |
546 | .IR label . | |
547 | It is an error if the label has been assigned by a previous line. | |
548 | .RS | |
549 | .PP | |
550 | The strings | |
551 | .IR i , | |
552 | .IR j , | |
553 | \*.. | |
554 | must be labels assigned by earlier lines. | |
555 | For each such label | |
556 | .IR i , | |
557 | let | |
558 | .IR q \*(us i \*(ue | |
559 | be the associated prime. | |
560 | Let | |
561 | .I Q | |
562 | = | |
563 | .IR q \*(us i \*(ue | |
564 | .IR q \*(us j \*(ue | |
565 | \*(.. | |
566 | be the product of these primes. | |
567 | Define | |
568 | .I E\*(usn\*(ue | |
569 | = { | |
570 | .RI ( x ", " y ) | |
571 | \*(mo | |
572 | .RB ( Z /\fIn Z )\*(ss2\*(se | |
573 | | | |
574 | .IR y \*(ss2\*(se | |
575 | = | |
576 | .IR x \*(ss3\*(se | |
577 | + | |
578 | .I Ax | |
579 | + | |
580 | .I B | |
581 | } | |
582 | \*(cu | |
583 | { \*(iy }; | |
584 | if | |
585 | .I n | |
586 | is prime and the curve is not singular | |
587 | then this is the elliptic curve over | |
588 | .RI GF( n ) | |
589 | with short-Weierstrass coefficients | |
590 | .I A | |
591 | and | |
592 | .IR B . | |
593 | Let | |
594 | .I R | |
595 | = | |
596 | .RI ( x , | |
597 | .IR y ). | |
598 | It is required that: | |
599 | .hP 1. | |
600 | .I g | |
601 | = | |
602 | .RI gcd(4 a \*(ss3\*(se | |
603 | + | |
604 | .RI 27 b \*(ss2\*(se, | |
605 | .IR n ) | |
606 | = 1. | |
607 | .hP 2. | |
608 | .I R | |
609 | \*(mo | |
610 | .IR E\*(usn\*(ue ; | |
611 | i.e., | |
612 | .IR y \*(ss2\*(se | |
613 | \*(== | |
614 | .IR x \*(ss3\*(se | |
615 | + | |
616 | .I Ax | |
617 | + | |
618 | .I B | |
619 | (mod | |
620 | .IR n ). | |
621 | .hP 3. The | |
622 | .I q\*(usi\*(ue | |
623 | are distinct. | |
624 | .hP 4. | |
625 | .IR QR , | |
626 | the elliptic-curve scalar product of the point | |
627 | .I R | |
628 | by the integer | |
629 | .IR Q , | |
630 | calculated as if | |
631 | .I E | |
632 | is a true elliptic curve, | |
633 | is the point at infinity. | |
634 | .hP 5. | |
635 | .RI ( Q / q ) R | |
636 | is finite for each prime | |
637 | .I q | |
638 | dividing | |
639 | .IR Q . | |
640 | .hP 6. | |
641 | .I Q | |
642 | > | |
643 | .RI ( n \*(ss1/4\*(se | |
644 | + 1)\*(ss2\*(se. | |
645 | .PP | |
646 | To see why this test works, let | |
647 | .I p | |
648 | be the smallest prime factor of | |
649 | .IR n , | |
650 | and let | |
651 | .I E\*(usp\*(ue | |
652 | = { | |
653 | .RI ( x ", " y ) | |
654 | \*(mo | |
655 | .RI GF( p )\*(ss2\*(se | |
656 | | | |
657 | .IR y \*(ss2\*(se | |
658 | = | |
659 | .IR x \*(ss3\*(se | |
660 | + | |
661 | .I Ax | |
662 | + | |
663 | .I B | |
664 | } | |
665 | \*(cu | |
666 | { \*(iy }. | |
667 | From | |
668 | .BR 1 , | |
669 | .I g | |
670 | = 1, | |
671 | .I E\*(usp\*(ue | |
672 | is an elliptic curve. | |
673 | (If 1 < | |
674 | .I g | |
675 | < | |
676 | .I n | |
677 | then | |
678 | .I g | |
679 | is a proper factor of | |
680 | .I n | |
681 | and | |
682 | .I n | |
683 | is certainly not prime; | |
684 | if | |
685 | .I g | |
686 | = | |
687 | .I n | |
688 | then the curve will be singular and the test fails.) | |
689 | From | |
690 | .BR 2 , | |
691 | .I R | |
692 | is a point on | |
693 | .IR E\*(usp\*(ue . | |
694 | From | |
695 | .BR 4 , | |
696 | .I R | |
697 | has | |
698 | .IR Q -torsion | |
699 | in | |
700 | .IR E\*(usp\*(ue . | |
701 | Consider some prime | |
702 | .I q | |
703 | dividing | |
704 | .I Q | |
705 | and let | |
706 | .I T | |
707 | = | |
708 | .RI ( Q/q ) R ; | |
709 | then | |
710 | .I T | |
711 | has torsion dividing | |
712 | .IR q . | |
713 | From | |
714 | .BR 5 , | |
715 | .RI ( Q/q ) R | |
716 | \(!= 0, | |
717 | and hence | |
718 | .I T | |
719 | has order precisely | |
720 | .I q | |
721 | in | |
722 | .IR E\*(usp\*(ue . | |
723 | This implies that | |
724 | .I q | |
725 | divides | |
726 | .RI # E\*(usp\*(ue . | |
727 | Since this holds for each prime | |
728 | .I q | |
729 | dividing | |
730 | .IR Q , | |
731 | and, from | |
732 | .BR 3 , | |
733 | the | |
734 | .I q | |
735 | are distinct, | |
736 | we deduce that | |
737 | .I Q | |
738 | divides | |
739 | .RI # E\*(usp\*(ue | |
740 | and hence that | |
741 | .RI # E\*(usp\*(ue | |
742 | \(>= | |
743 | .IR Q . | |
744 | Hasse's theorem tells us that | |
745 | .RI | p | |
746 | + 1 \- | |
747 | .RI # E\*(usp\*(ue | | |
748 | \(<= | |
749 | .RI 2\*(sr p , | |
750 | whence | |
751 | .I p | |
752 | + 1 + | |
753 | .RI 2\*(sr p | |
754 | = | |
755 | .RI (\*(sr p | |
756 | + 1)\*(ss2\*(se | |
757 | \(>= | |
758 | .RI # E\*(usp\*(ue | |
759 | \(>= | |
760 | .IR Q | |
761 | > | |
762 | .RI ( n \*(ss1/4\*(se | |
763 | + 1)\*(ss2\*(se | |
764 | (from | |
765 | .BR 6 ); | |
766 | so | |
767 | .IR p\*(ss2\*(se | |
768 | > | |
769 | .IR n . | |
770 | Let | |
771 | .IR p \(fm | |
772 | be any prime factor of | |
773 | .IR n / p . | |
774 | Then | |
775 | .IR p \(fm | |
776 | \(>= | |
777 | .I p | |
778 | and | |
779 | .IR pp \(fm | |
780 | \(>= | |
781 | .IR p \*(ss2\*(se | |
782 | > | |
783 | .IR n ; | |
784 | but | |
785 | .IR pp \(fm | |
786 | divides | |
787 | .I n | |
788 | so this is a contradiction. | |
789 | We must conclude that | |
790 | .IR p \(fm | |
791 | does not exist, | |
792 | and | |
793 | .I n | |
794 | must be prime. | |
795 | .PP | |
796 | Note that | |
797 | .B pock | |
798 | currently cannot generate proofs which use | |
799 | .BR ecpp , | |
800 | though it will verify them. | |
801 | .RE | |
802 | .TP | |
803 | .BI "check " label ", " b ", " p | |
804 | Verify that the prime associated with the | |
805 | .I label | |
806 | is equal to | |
807 | .I p | |
808 | and that it is | |
809 | .I b | |
810 | bits long; | |
811 | i.e., that | |
812 | .RI 2\*(ss b \-1\*(se | |
813 | \(<= | |
814 | .I p | |
815 | < | |
816 | .RI 2\*(ss b \*(se. | |
817 | Unless | |
818 | inhibited by | |
819 | .BR \-q , | |
820 | the label and value are printed to stdout during verification. | |
821 | . | |
822 | .\"-------------------------------------------------------------------------- | |
823 | .SH "SEE ALSO" | |
824 | .BR key (1). | |
825 | .SH AUTHOR | |
826 | Mark Wooding, <mdw@distorted.org.uk> | |
827 | . | |
828 | .\"----- That's all, folks -------------------------------------------------- |