prime 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  1. .TH PRIME 2
  2. .SH NAME
  3. genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest \- prime number generation
  4. .SH SYNOPSIS
  5. .B #include <u.h>
  6. .br
  7. .B #include <libc.h>
  8. .br
  9. .B #include <mp.h>
  10. .br
  11. .B #include <libsec.h>
  12. .PP
  13. .B
  14. int smallprimetest(mpint *p)
  15. .PP
  16. .B
  17. int probably_prime(mpint *p, int nrep)
  18. .PP
  19. .B
  20. void genprime(mpint *p, int n, int nrep)
  21. .PP
  22. .B
  23. void gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
  24. .PP
  25. .B
  26. void genstrongprime(mpint *p, int n, int nrep)
  27. .PP
  28. .B
  29. void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
  30. .SH DESCRIPTION
  31. .PP
  32. Public key algorithms abound in prime numbers. The following routines
  33. generate primes or test numbers for primality.
  34. .PP
  35. .I Smallprimetest
  36. checks for divisibility by the first 10000 primes. It returns 0
  37. if
  38. .I p
  39. is not divisible by the primes and \-1 if it is.
  40. .PP
  41. .I Probably_prime
  42. uses the Miller-Rabin test to test
  43. .IR p .
  44. It returns non-zero if
  45. .I P
  46. is probably prime. The probability of it not being prime is
  47. 1/4**\fInrep\fR.
  48. .PP
  49. .I Genprime
  50. generates a random
  51. .I n
  52. bit prime. Since it uses the Miller-Rabin test,
  53. .I nrep
  54. is the repetition count passed to
  55. .IR probably_prime .
  56. .I Gensafegprime
  57. generates an
  58. .IR n -bit
  59. prime
  60. .I p
  61. and a generator
  62. .I alpha
  63. of the multiplicative group of integers mod \fIp\fR;
  64. there is a prime \fIq\fR such that \fIp-1=2*q\fR.
  65. .I Genstrongprime
  66. generates a prime,
  67. .IR p ,
  68. with the following properties:
  69. .IP \-
  70. (\fIp\fR-1)/2 is prime. Therefore
  71. .IR p -1
  72. has a large prime factor,
  73. .IR p '.
  74. .IP \-
  75. .IR p '-1
  76. has a large prime factor
  77. .IP \-
  78. .IR p +1
  79. has a large prime factor
  80. .PP
  81. .I DSAprimes
  82. generates two primes,
  83. .I q
  84. and
  85. .IR p,
  86. using the NIST recommended algorithm for DSA primes.
  87. .I q
  88. divides
  89. .IR p -1.
  90. The random seed used is also returned, so that skeptics
  91. can later confirm the computation. Be patient; this is a
  92. slow algorithm.
  93. .SH SOURCE
  94. .B /sys/src/libsec
  95. .SH SEE ALSO
  96. .IR aes (2)
  97. .IR blowfish (2),
  98. .IR des (2),
  99. .IR elgamal (2),
  100. .IR rsa (2),