bnintern.doc

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

* The organization of the BigNum Library

As mentioned in bn.doc, the library should compile on anything with an
ANSI C compiler and 16 and 32-bit data types.  (Non-power-of-2 word
lengths probably wouldn't be *too* hard, but the matter is likely to
remain academic.)  However, assembly subroutines can be added in a
great variety of ways to speed up computations.

It's even possible to vary the word length dynamically at run time.
Currently, 80x86 and 680x0 assembly primitives have been written in 16
and 32-bit forms, as not all members of these families support 32x32->64
bit multiply.  In future, 32/64 bit routines may be nice for the MIPS
and PowerPC processors.  (The SPARC has a 64-bit extension, but it still
only produces a maximum 64-bit multiply result.  The MIPS, PowerPC and
Alpha give access to 128 bits of product.)

The way that this works is that the file bn.c declares a big pile of
function pointers, and the first bnInit() call figures out which set
of functions to point these to.  The functions are named so that
it is possible to link several sets into the same executable without
collisions.

The library can store numbers in big-endian or little-endian word order,
although the order of bytes within a word is always the platform native
order.  As long as you're using the pure C version, you can compile
independent of the native byte ordering, but the flexibility is available
in case assembly primitives are easier to write one way or the other.
(In the absence of other considerations, little-endian is somewhat more
efficient, and is the default.  This is controlled by BN_XXX_ENDIAN.)

In fact, it would be possible to change the word order at run time,
except that there is no naming convention to support linking in
functions that differ only in endianness.  (Which is because the
point of doing so is unclear.)

The core of the library is in the files lbn??.c and bn??.c, where "??"
is 16, 32, or 64.  The 32 and 64-bit files are generated from the 16-bit
version by a simple textual substitution.  The 16-bit files are generally
considered the master source, and the others generated from it with sed.

Usually, only one set of these files is used on any given platform,
but if you want multiple word sizes, you include one for each supported
word size.  The files bninit??.c define a bnInit function for a given
word size, which calls bnInit_??() internally.  Only one of these may
be included at a time, and multiple word sizes are handled by a more
complex bnInit function such as the ones in bn8086.c and bn68000.c,
which determine the word size of the processor they're running on and
call the appropriate bnInit_??() function.

The file lbn.h uses <limits.h> to find the platform's available data
types.  The types are defined both as macros (BNWORD32) and as typedefs
(bnword32) which aren't used anywhere but can come in very handy when
using a debugger (which doesn't know about macros).  Any of these may
be overridden either on the compiler command line (cc -DBN_BIG_ENDIAN
-DBNWORD32="unsigned long"), or from an extra include file BNINCLUDE
defined on the command line.  (cc -DBNINCLUDE=lbnmagic.h)  This is the
preferred way to specify assembly primitives.

So, for example, to build a 68020 version of the library, compile the
32-bit library with -DBNINCLUDE=lbn68020.h, and compile and link in
lbn68020.c (which is actually an assembly source file, if you look).

Both 16- and 32-bit 80x86 code is included in lbn8086.h and .asm.  That
code uses 16-bit large-model addressing.  lbn80386.h and .asm use 32-bit
flat-model addressing.

Three particularly heavily used macros defined by lbn.h are BIG(x),
LITTLE(y) and BIGLITTLE(x,y).  These expand to x (or nothing) on
a big-endian system, and y (or nothing) on a little-endian system.
These are used to conditionalize the rest of the code without taking
up entire lines to say "#ifdef BN_BIG_ENDIAN", "#else" and "#endif".

* The lbn??.c files

The lbn?? file contains the low-level bignum functions.  These universally
expect their numbers to be passed to them in (buffer, length) form and
do not attempt to extend the buffers.  (In some cases, they do allocate
temporary buffers.)  The buffer pointer points to the least-significant
end of the buffer.  If the machine uses big-endian word ordering, that
is a pointer to the end of the buffer.  This is motivated by considering
pointers to point to the boundaries between words (or bytes).  If you
consider a pointer to point to a word rather than between words, the
pointer in the big-endian case points to the first word past the end of the
buffer.

All of the primitives have names of the form  lbnAddN_16, where the
_16 is the word size.  All are surrounded by "#ifndef lbnAddN_16".
If you #define lbnAddN_16 previously (either on the command like or
in the BNINCLUDE file), the C code will neither define *nor declare* the
corresponding function.  The declaration must be suppressed in case you
declare it in a magic way with special calling attributes or define it as
a macro.

If you wish to write an assembly primitive, lbnMulAdd1_??, which
multiplies N words by 1 word and adds the result to N words, returning
the carry word, is by FAR the most important function - almost all of
the time spent performing a modular exponentiation is spent in this
function.  lbnMulSub1_??, which does the same but subtracts the product
and returns a word of borrow, is used heavily in the division routine
and thus by GCD and modular inverse computation.

These two functions are the only functions which *require* some sort
of double-word data type, so if you define them in assembly language,
the ?? may be the widest word your C compiler supports; otherwise, you
must limit your implementation to half of the maximum word size.  Other
functions will, however, use a double-word data type if available.

Actually, there are some even simpler primitives which you can provide
to allow double-width multiplication: mul??_ppmm, mul??_ppmma and
mul??_ppmmaa These are expected to be defined as macros (all arguments
are always side-effect-free lvalues), and must return two words of result
of the computation m1*m2 + a1 + a2.  It is best to define all three,
although any that are not defined will be generated from the others in
the obvious way.  GCC's inline assembler can be used to define these.
(The names are borrowed from the GNU MP package.)

There is also lbnMulN1_??, which stores the result rather than adding or
subtracting it, but it is less critical.  If it is not provided, but
lbnMulAdd1_?? is, it will be implemented in terms of lbnMulAdd1_?? in the
obvious way.

lbnDiv21_??, which divides two words by one word and returns a quotient
and remainder, is greatly sped up by a double-word data type, macro
definition, or assembly implementation, but has a version which will run
without one.  If your platform has a double/single divide with remainder,
it would help to define this, and it's quite simple.

lbnModQ_?? (return a multi-precision number reduced modulo a "quick"
(< 65536) modulus is used heavily by prime generation for trial division,
but is otherwise little used.

Other primitives may be implemented depending on the expected usage mix.
It is generally not worth implementing lbnAddN_?? and lbnSubN_?? unless
you want to start learning to write assembly primitives on something
simple; they just aren't used very much.  (Of course, if you do, you'll
probably get some improvements, in both speed and object code size, so
it's worth keeping them in, once written.)

* The bn??.c files

While the lbn??.c files deal in words, the bn??.c files provide the
public interface to the library and deal in bignum structures.  These
contain a buffer pointer, an allocated length, and a used length.
The lengths are specified in words, but as long as the user doesn't go
prying into such innards, all of the different word-size libraries
provide the same interface; they may be exchanged at link time, or even
at run time.

The bn.c file defines a large collection of function pointers and one
function, bnInit.  bnInit is responsible for setting the function pointers
to point to the appropriate bn??.c functions.  Each bn??.c file
provides a bnInit_?? function which sets itself up; it is the job
of bnInit to figure out which word size to use and call the appropriate