security/nss/lib/freebl/mpi/utils/README

   1 ***** BEGIN LICENSE BLOCK *****
   2 Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3
   4 The contents of this file are subject to the Mozilla Public License Version
   5 1.1 (the "License"); you may not use this file except in compliance with
   6 the License. You may obtain a copy of the License at
   7 http://www.mozilla.org/MPL/
   8
   9 Software distributed under the License is distributed on an "AS IS" basis,
  10 WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11 for the specific language governing rights and limitations under the
  12 License.
  13
  14 The Original Code is the MPI Arbitrary Precision Integer Arithmetic
  15 library.
  16
  17 The Initial Developer of the Original Code is
  18 Michael J. Fromberger <sting@linguist.dartmouth.edu>
  19 Portions created by the Initial Developer are Copyright (C) 1998, 2000
  20 the Initial Developer. All Rights Reserved.
  21
  22 Contributor(s):
  23
  24 Alternatively, the contents of this file may be used under the terms of
  25 either the GNU General Public License Version 2 or later (the "GPL"), or
  26 the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27 in which case the provisions of the GPL or the LGPL are applicable instead
  28 of those above. If you wish to allow use of your version of this file only
  29 under the terms of either the GPL or the LGPL, and not to allow others to
  30 use your version of this file under the terms of the MPL, indicate your
  31 decision by deleting the provisions above and replace them with the notice
  32 and other provisions required by the GPL or the LGPL. If you do not delete
  33 the provisions above, a recipient may use your version of this file under
  34 the terms of any one of the MPL, the GPL or the LGPL.
  35
  36 ***** END LICENSE BLOCK *****
  37
  38 Additional MPI utilities
  39 ------------------------
  40
  41 The files 'mpprime.h' and 'mpprime.c' define some useful extensions to
  42 the MPI library for dealing with prime numbers (in particular, testing
  43 for divisbility, and the Rabin-Miller probabilistic primality test).
  44
  45 The files 'mplogic.h' and 'mplogic.c' define extensions to the MPI
  46 library for doing bitwise logical operations and shifting.
  47
  48 This document assumes you have read the help file for the MPI library
  49 and understand its conventions.
  50
  51 Divisibility (mpprime.h)
  52 ------------
  53
  54 To test a number for divisibility by another number:
  55
  56 mpp_divis(a, b)         - test if b|a
  57 mpp_divis_d(a, d)       - test if d|a
  58
  59 Each of these functions returns MP_YES if its initial argument is
  60 divisible by its second, or MP_NO if it is not.  Other errors may be
  61 returned as appropriate (such as MP_RANGE if you try to test for
  62 divisibility by zero).
  63
  64 Randomness (mpprime.h)
  65 ----------
  66
  67 To generate random data:
  68
  69 mpp_random(a)           - fill a with random data
  70 mpp_random_size(a, p)   - fill a with p digits of random data
  71
  72 The mpp_random_size() function increases the precision of a to at
  73 least p, then fills all those digits randomly.  The mp_random()
  74 function fills a to its current precision (as determined by the number
  75 of significant digits, USED(a))
  76
  77 Note that these functions simply use the C library's rand() function
  78 to fill a with random digits up to its precision.  This should be
  79 adequate for primality testing, but should not be used for
  80 cryptographic applications where truly random values are required for
  81 security.
  82
  83 You should call srand() in your driver program in order to seed the
  84 random generator; this function doesn't call it.
  85
  86 Primality Testing (mpprime.h)
  87 -----------------
  88
  89 mpp_divis_vector(a, v, s, w)   - is a divisible by any of the s values
  90                                  in v, and if so, w = which.
  91 mpp_divis_primes(a, np)   - is a divisible by any of the first np primes?
  92 mpp_fermat(a, w)          - is a pseudoprime with respect to witness w?
  93 mpp_pprime(a, nt)         - run nt iterations of Rabin-Miller on a.
  94
  95 The mpp_divis_vector() function tests a for divisibility by each
  96 member of an array of digits.  The array is v, the size of that array
  97 is s.  Returns MP_YES if a is divisible, and stores the index of the
  98 offending digit in w.  Returns MP_NO if a is not divisible by any of
  99 the digits in the array.
 100
 101 A small table of primes is compiled into the library (typically the
 102 first 128 primes, although you can change this by editing the file
 103 'primes.c' before you build).  The global variable prime_tab_size
 104 contains the number of primes in the table, and the values themselves
 105 are in the array prime_tab[], which is an array of mp_digit.
 106
 107 The mpp_divis_primes() function is basically just a wrapper around
 108 mpp_divis_vector() that uses prime_tab[] as the test vector.  The np
 109 parameter is a pointer to an mp_digit -- on input, it should specify
 110 the number of primes to be tested against.  If a is divisible by any
 111 of the primes, MP_YES is returned and np is given the prime value that
 112 divided a (you can use this if you're factoring, for example).
 113 Otherwise, MP_NO is returned and np is untouched.
 114
 115 The function mpp_fermat() performs Fermat's test, using w as a
 116 witness.  This test basically relies on the fact that if a is prime,
 117 and w is relatively prime to a, then:
 118
 119         w^a = w (mod a)
 120
 121 That is,
 122
 123         w^(a - 1) = 1 (mod a)
 124
 125 The function returns MP_YES if the test passes, MP_NO if it fails.  If
 126 w is relatively prime to a, and the test fails, a is definitely
 127 composite.  If w is relatively prime to a and the test passes, then a
 128 is either prime, or w is a false witness (the probability of this
 129 happening depends on the choice of w and of a ... consult a number
 130 theory textbook for more information about this).
 131
 132 Note:  If (w, a) != 1, the output of this test is meaningless.
 133 ----
 134
 135 The function mpp_pprime() performs the Rabin-Miller probabilistic
 136 primality test for nt rounds.  If all the tests pass, MP_YES is
 137 returned, and a is probably prime.  The probability that an answer of
 138 MP_YES is incorrect is no greater than 1 in 4^nt, and in fact is
 139 usually much less than that (this is a pessimistic estimate).  If any
 140 test fails, MP_NO is returned, and a is definitely composite.
 141
 142 Bruce Schneier recommends at least 5 iterations of this test for most
 143 cryptographic applications; Knuth suggests that 25 are reasonable.
 144 Run it as many times as you feel are necessary.
 145
 146 See the programs 'makeprime.c' and 'isprime.c' for reasonable examples
 147 of how to use these functions for primality testing.
 148
 149
 150 Bitwise Logic (mplogic.c)
 151 -------------
 152
 153 The four commonest logical operations are implemented as:
 154
 155 mpl_not(a, b)           - Compute bitwise (one's) complement, b = ~a
 156
 157 mpl_and(a, b, c)        - Compute bitwise AND, c = a & b
 158
 159 mpl_or(a, b, c)         - Compute bitwise OR, c = a | b
 160
 161 mpl_xor(a, b, c)        - Compute bitwise XOR, c = a ^ b
 162
 163 Left and right shifts are available as well.  These take a number to
 164 shift, a destination, and a shift amount.  The shift amount must be a
 165 digit value between 0 and DIGIT_BIT inclusive; if it is not, MP_RANGE
 166 will be returned and the shift will not happen.
 167
 168 mpl_rsh(a, b, d)        - Compute logical right shift, b = a >> d
 169
 170 mpl_lsh(a, b, d)        - Compute logical left shift, b = a << d
 171
 172 Since these are logical shifts, they fill with zeroes (the library
 173 uses a signed magnitude representation, so there are no sign bits to
 174 extend anyway).
 175
 176
 177 Command-line Utilities
 178 ----------------------
 179
 180 A handful of interesting command-line utilities are provided.  These
 181 are:
 182
 183 lap.c           - Find the order of a mod m.  Usage is 'lap <a> <m>'.
 184                   This uses a dumb algorithm, so don't use it for
 185                   a really big modulus.
 186
 187 invmod.c        - Find the inverse of a mod m, if it exists.  Usage
 188                   is 'invmod <a> <m>'
 189
 190 sieve.c         - A simple bitmap-based implementation of the Sieve
 191                   of Eratosthenes.  Used to generate the table of
 192                   primes in primes.c.  Usage is 'sieve <nbits>'
 193
 194 prng.c          - Uses the routines in bbs_rand.{h,c} to generate
 195                   one or more 32-bit pseudo-random integers.  This
 196                   is mainly an example, not intended for use in a
 197                   cryptographic application (the system time is
 198                   the only source of entropy used)
 199
 200 dec2hex.c       - Convert decimal to hexadecimal
 201
 202 hex2dec.c       - Convert hexadecimal to decimal
 203
 204 basecvt.c       - General radix conversion tool (supports 2-64)
 205
 206 isprime.c       - Probabilistically test an integer for primality
 207                   using the Rabin-Miller pseudoprime test combined
 208                   with division by small primes.
 209
 210 primegen.c      - Generate primes at random.
 211
 212 exptmod.c       - Perform modular exponentiation
 213
 214 ptab.pl         - A Perl script to munge the output of the sieve
 215                   program into a compilable C structure.
 216
 217
 218 Other Files
 219 -----------
 220
 221 PRIMES          - Some randomly generated numbers which are prime with
 222                   extremely high probability.
 223
 224 README          - You're reading me already.
 225
 226
 227 About the Author
 228 ----------------
 229
 230 This software was written by Michael J. Fromberger.  You can contact
 231 the author as follows:
 232
 233 E-mail:   <sting@linguist.dartmouth.edu>
 234
 235 Postal:   8000 Cummings Hall, Thayer School of Engineering
 236           Dartmouth College, Hanover, New Hampshire, USA
 237
 238 PGP key:  http://linguist.dartmouth.edu/~sting/keys/mjf.html
 239           9736 188B 5AFA 23D6 D6AA  BE0D 5856 4525 289D 9907
 240
 241 Last updated:  $Id: README,v 1.3 2005/02/02 22:28:23 gerv%gerv.net Exp $