bnintern.doc

包含哈希,对称以及非对称的经典算法 包含经典事例

bnInit_?? function.

If only one word size is in use, you may link in the file bninit??.c,
which provides a trivial bnInit function.  If multiple word sizes are
in use, you must provide the appropriate bnInit function.  See
bn8086.c as an example.

For maximum portability, you may just compile and link in the files
lbn00.c, bn00.c and bninit00.c, which determine, using the preprocessor
at compile time, the best word size to use.  (The logic is actually
located in the file bnsize00.h, so that the three .c files cannot get out
of sync.)

The bignum buffers are allocated using the memory management routines in
lbnmem.c.  These are word-size independent; they expect byte counts and
expect the system malloc() to return suitably aligned buffers.  The
main reason for this wrapper layer is to support any customized allocators
that the user might want to provide.

* Other bn*.c files

bnprint.c is a simple routine for printing a bignum in hex.  It is
provided in a separate file so that its calls to stdio can be eliminated
from the link process if the capability is not needed.

bntest??.c is a very useful regression test if you're implementing
assembly primitives.  If it doesn't complain, you've probably
got it right.  It also does timing tests so you can see the effects
of any changes.

* Other files

sieve.c contains some primitives which use the bignum library to perform
sieving (trial division) of ranges of numbers looking for candidate primes.
This involves two steps: using a sieve of Eratosthenes to generate the
primes up to 65536, and using that to do trial division on a range of
numbers following a larger input number.  Note that this is designed
for large numbers, greater than 65536, since there is no check to see
if the input is one of the small primes; if it is divisible, it is assumed
composite.

prime.c uses sieve.c to generate primes.  It uses sieve.c to eliminate
numbers with trivial divisors, then does strong pseudoprimality tests
with some small bases.  (Actually, the first test, to the base 2, is
optimized a bit to be faster when it fails, which is the common case,
but 1/8 of the time it's not a strong pseudoprimality test, so an extra,
strong, test is done in that case.)

It prints progress indicators as it searches.  The algorithm
searches a range of numbers starting at a given prime, but it does
so in a "shuffled" order, inspired by algorithm M from Knuth.  (The
random number generator to use for this is passed in; if no function
is given, the numbers are searched in sequential order and the
returns value will be the next prime >= the input value.)

germain.c operates similarly, but generates Sophie Germain primes;
that is, primes p such that (p-1)/2 is also prime.  It lacks the
shuffling feature - searching is always sequential.

jacobi.c computes the Jacobi symbol between a small integer and a BigNum.
It's currently only ever used in germain.c.

* Sources

Obviously, a key source of information was Knuth, Volume 2,
particularly on division algorithms.

The greatest inspiration, however, was Arjen Lenstra's LIP
(Large Integer Package), distributed with the RSA-129 effort.
While very difficult to read (there is no internal documentation on
sometimes very subtle algorithms), it showed me many useful tricks,
notably the windowed exponentiation algorithm that saves so many
multiplies.  If you need a more general-purpose large-integer package,
with only a minor speed penalty, the LIP package is almost certainly
the best available.  It implements a great range of efficient
algorithms.

The second most important source was Torbjorn Granlund's gmp
(GNU multi-precision) library.  A number of C coding tricks were
adapted from there.  I'd like to thank Torbjorn for some useful
discussions and letting me see his development work on GMP 2.0.

Antoon Bosselaers, Rene' Govaerts and Joos Vandewalle, in their CRYPTO
'93 paper, "Comparison of three modular reduction functions", brought
Montgomery reduction to my attention, for which I am grateful.

Burt Kaliski's article in the September 1993 Dr. Dobb's Journal,
"The Z80180 and Big-number Arithmetic" pointed out the advantages (and
terminology) of product scanning to me, although the limited
experiments I've done have shown no improvement from trying it in C.

Hans Reisel's book, "Prime Numbers and Computer Methods for Factorization"
was of great help in designing the prime testing, although some of
the code in the book, notably the Jacobi function in Appendix 3,
is an impressive example of why GOTO should be considered harmful.
Papers by R. G. E. Pinch and others in Mathematics of Computation were
also very useful.

Keith Geddes, Stephen Czapor and George Labahn's book "Algorithms
for Computer Algebra", although it's mostly about polynomials,
has some useful multi-precision math examples.

Philip Zimmermann's mpi (multi-precision integer) library suggested
storing the numbers in native byte order to facilitate assembly
subroutines, although the core modular multiplication algorithms are
so confusing that I still don't understand them.  His boasting about
the speed of his library (albeit in 1986, before any of the above were
available for study) also inspired me to particular effort to soundly
beat it.  It also provoked a strong reaction from me against fixed
buffer sizes, and complaints about its implementation from Paul Leyland
(interface) and Robert Silverman (prime searching) contributed usefully
to the design of this current library.

I'd like to credit all of the above, plus the Berkeley MP package, with
giving me difficulty finding a short, unique distinguishing prefix for
my library's functions.  (I have just, sigh, discovered that Eric Young
is using the same prefix for *his* library, although with the
bn_function_name convention as opposed to the bnFunctionName one.)

I'd like to thank the original implementor of Unix "dc" and "factor"
for providing useful tools for verifying the correct operation of
my library.

* Future

- Obviously, assembly-language subroutines for more platforms would
  always be nice.
- There's a special case in the division for a two-word denominator
  which should be completed.
- When the quotient of a division is big enough, compute an inverse of
  the high word of the denominator and use multiplication by that
  to do the divide.
- A more efficient GCD algorithm would be nice to have.
- More efficient modular inversion is possible.  Do it.
- Extend modular inversion to deal with non-relatively-prime
  inputs.  Produce y = inv(x,m) with y * x == gcd(x,m) mod m.
- Try some product scanning in assembly.
- Karatsuba's multiplication and squaring speedups would be nice.
- I *don't* think that FFT-based algorithms are worth implementing yet,
  but it's worth a little bit of study to make sure.
- More general support for numbers in Montgomery form, so they can
  be used by more than the bowels of lbnExpMod.
- Provide an lbnExpMod optimized for small arguments > 2, using
  conventional (or even Barrett) reduction of the multiplies, and
  Montgomery reduction of the squarings.
- Adding a Lucas-based prime test would be a real coup, although it's
  hard to give rational reasons why it's necessary.  I have a number of
  ideas on this already.  Find out if norm-1 (which is faster to
  compute) suffices.
- Split up the source code more to support linking with smaller subsets
  of the library.