bn.doc

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

* The BigNum multi-precision integer math library

This is a multi-precision math library designed to be very portable,
reasonably clean and easy to use, have very liberal bounds on the sizes
of numbers that can be represented, but above all to perform extremely
fast modular exponentiation.  It has some limitations, such as
representing positive numbers only, and supporting only odd moduli,
which simplify it without impairing this ability.

A second speed goal which has had considerable effort applied to it is
prime number generation.

Finally, while there is probably a long way to go in this direction,
some effort has gone into commenting the code a lot more than seems to
be fashionable among mathematicians.

It is written in C, and should compile on any platform with an ANSI C
compiler and 16 and 32-bit unsigned data types, but various primitives
can be replaced with assembly versions in a great variety of ways for
greater speedup.  See "bnintern.doc" for a description.

In case you're wondering, yes C++ would produce a much nicer syntax
for working with these numbers, but there are a lot of compilers out
there that actually implement ANSI C, and get it almost right.  I have
a few kludges to deal with some that get little things wrong, but
overall it's not too difficult to write code that I can be sure
will work on lots of machines.  And porting it to a K&R C compiler,
if it ever becomes necessary, shouldn't be all *that* difficult.

The C++ compiler world is a less friendly place.  First of all, C++
compilers are still not as common as C compilers, so that hurts
portability right there, and I don't need the extra power to write my
code.  C++ compilers all seem to have important bugs, and different
bugs for each compiler.  First I have to learn all the foibles of a
whole lot of C++ compilers, and then I have write code that uses only
the features that work in all of them.  This is a language not a whole
heck of a lot bigger than C.

(The fact that it drives me *batty* the way that C++ drags *everything*
into the same name space is also a contributing factor.  I *like*
writing "struct" (or "class") before structure names.  I *like* putting
"this->" in front of member references.  It makes it clear to me, when
reading a single line of code, roughly what is being affected by it and
where I can find the relevant source code to find out more.  I've seen
people develop complicated naming conventions to make all this clear,
but the conventions are still very much in flux.)

Anyway...

The main public interface is contained in the file bn.h.  This is
mostly a bunch of pointers to functions which start out uninitialized.
The bnInit() function sets this up.  It must be called before any other
routine in the library.

All of the public routines have names of the bnFunction variety.
Some internal routines are lbnFunction, but you should never have to
worry about those unless you're hacking with the code.

The code uses the assert() macro a lot internally.  If you do something
you're not supposed to, you'll generally notice because an assert()
will fail.  The library does not have special error codes for division
by zero or the like - it assert fails instead.  Just don't do that.

A BigNum is represented by a struct BigNum, which really doesn't
need to be understood, but it often makes me feel better to understand
what's going on, so here it is:

#> struct BigNum {
#>	void *ptr;
#>	unsigned size;	/* Note: in (variable-sized) words */
#>	unsigned allocated;
#> };

The pointer points to the least-significant end of an array of words which
hold the number.  The array contains "allocated" words, but only "size"
of them are actually meaningful.  The others may have any value.
This is all of limited use because the size of a word is not specified.
In fact, it can change at run time - if you run on an 8086 one day and an
80386 the next, you may find the word size different.

* Initialization

The first function you have to call is this:
#> void bnInit(void);
This sets up the library for use.  It is idempotent, so you can call it
multiple times if you like.  The only thing it does right now is set
up the function pointers to the rest of the library.  If you crash
a program and the debugger tells you that it's trying to execute at
address 0, you forgot to call bnInit.

The user of the library is responsible for allocating and freeing the struct
BigNum.  All the library functions take pointers to them.  The first thing
you need to do is initialize all the fields to empty, a zero-valued BigNum.
This is done with the function bnBegin:
#> void bnBegin(struct BigNum *bn);

When you're done with a BigNum, call bnEnd to deallocate the data storage
in preparation for deallocating the structure:
#> void bnEnd(struct BigNum *bn);

This resets the number to the 0 state.  You can actually start using the
number right away again, or call bnEnd again, so if you're really
memory-conscious you might want to use this to free a large
number you're done with this way before going on to use the buffer
for smaller things.

A simple assignment can be done with bnCopy.  
#> int bnCopy(struct BigNum *dest, struct BigNum const *src);

This sets dest = src, and returns an error code.  Most functions in the
library do this, and return 0 on success and -1 if they were unable to
allocate needed memory.  If you're lazy and sure you'll never run out
of memory, you can avoid checking this, but it's better to be
paranoid.  If a function returns -1, the what has happened to the
destination values is undefined.  They're usually unmodified, and
they're always still valid BigNum numbers, but their values might be
strange.

In general, anywhere that follows, unless otherwise documented, assume
that an "int" return value is 0 for success or -1 for error.

A trivial little function which is sometimes handy, and quite cheap to
execute (it just swaps the pointers) is:
#> void bnSwap(struct BigNum *a, struct BigNum *b);

* Input and output

For now, the library only works with numbers in binary form - there's
no way to get decimal numbers into or out of it.  But it's pretty
flexible on how it does that.

The first function just sets a BigNum to have a small value.
"small" is defined as less than 2^16, the minimum word size supported
by the library.  This is still useful for a lot of work.
#> int bnSetQ(struct BigNum *dest, unsigned src);

This returns the usual -1 error if it couldn't allocate memory.

There's also a function to determine the size of a BigNum, in bits.
The size is the number of bits required to represent the number,
0 if the number is 0, and floor(log2(src)) + 1 otherwise.  E.g. 1 is
the only 1-bit number, 2 and 3 are 2-bit numbers, etc.
#> unsigned bnBits(struct BigNum const *src);

If bnBits(src) <= 16, you can get the whole number with this function.
If it's larger, you get the low k bits, where k is at least 16.
(This doesn't bother masking if it's easy to return more, but you
shouldn't rely on it.)  Even that is useful for many things, like
deciding if a number is even or odd.
#> unsigned bnLSWord(struct BigNum const *src);

For larger numbers, the format used by the library is an array of
unsigned 8-bit bytes.  These bytes may be in big-endian or little-endian
order, and it's possible to examine or change just part of a number.
The functions are:
#> void bnExtractBigBytes(struct BigNum const *bn, unsigned char *dest,
#> 	unsigned lsbyte, unsigned len);
#> int bnInsertBigBytes(struct BigNum *bn, unsigned char const *src,
#> 	unsigned lsbyte, unsigned len);
#> void bnExtractLittleBytes(struct BigNum const *bn, unsigned char *dest,
#> 	unsigned lsbyte, unsigned len);
#> int bnInsertLittleBytes(struct BigNum *bn, unsigned char const *src,
#> 	unsigned lsbyte, unsigned len);

These move bytes between the BigNum and the buffer of 8-bit bytes.  The
Insert functions can allocate memory, so return an error code.  The
Extract functions always succeed.

The buffer is encoded in base 256, with either the most significant
byte (the Big functions) or the least significant byte (the Little
functions) coming first.  "len" is the length of the buffer, so the
buffer always encodes a value between 0 and 256^len.  (That's
"to the power of", not "xor".)

"lsbyte" gives the offset into the BigNum which is being worked with.
This is usually zero, but you can, for example, read out a large
BigNum in 32-byte chunks, using a len of 32 and an lsbyte of 0, 32,
64, 96, etc.

After these complete, the number encoded in the buffer will be
equal to (bn / 256^lsbyte) % 256^len.  The only difference between
Insert and Extract is which is changed to match the other.

* Simple math

#> int bnAdd(struct BigNum *dest, struct BigNum const *src);
#> int bnAddQ(struct BigNum *dest, unsigned src);

These add dest += src.  In the Q form, src must be < 65536.  In either
case, the functions can fail and return -1, as usual.

#> int bnSub(struct BigNum *dest, struct BigNum const *src);
#> int bnSubQ(struct BigNum *dest, unsigned src);

These subtract dest -= src.  If this would make the result negative,
dest is set to (src-dest) and a value of 1 is returned, so you can
keep track of a separate sign if you need to.  Otherwise, they return
0 on success and -1 if they were unable to allocate needed memory.

To make your life simpler if you are error checking, these are guaranteed
not to allocate memory unnecessarily.  So if you know that the addition
or subtraction you're doing won't produce a result larger than the
input, and won't underflow either (like subtracting 1 from an odd
number or adding 1 to an even number), you can skip checking the
error code.

#> extern int (*bnCmp)(struct BigNum const *a, struct BigNum const *b);
This returns the sign (-1, 0 or +1) of a-b.  Another way of saying
this is that a <=> b is the same as bnCmp(a, b) <=> 0,
where "<=>" stands for any of <, <=, =, !=, >= or >.

#> int bnSquare(struct BigNum *dest, struct BigNum const *src);

This computes dest = src^2, returning an error if it ran out of memory.
If you care about performance tuning, this slows down when dest and
src are the same BigNum, since it needs to allocate a temporary buffer
to do the work in.  It does work, however.

#> int bnMul(struct BigNum *dest, struct BigNum const *a,
#>	struct BigNum const *b);
#> int bnMulQ(struct BigNum *dest, struct BigNum const *a, unsigned b);

These compute dest = a * b, and work in the same way as bnSquare.
(Including the comment about preferring if dest is not the same as any of
the inputs.)  bnSquare is faster if a and b are the same.

#> int bnDivMod(struct BigNum *q, struct BigNum *r,
#>	struct BigNum const *n, struct BigNum const *d);

This computes division with remainder, q = n/d and r = n%d.  Don't
pass in a zero d; it will blow up.  In general, all of the values
must be different (it will blow up if you try), but r and n may be the
same.

RE-ENTRANCY NOTE: This temporarily modifies the BigNum "d" internally,
although it restores it before returning.  If you're doing something
multi-threaded, you can't share the d value between threads, even though
it says "const".  That's a safe assumption elsewhere, but this is an
exception.

That note also means that it's not safe to let n be the same as d,
although that's such a stupid way to set q to 1 and r to 0 that
I don't think it's worth worrying about.  (I hope you understand that
this doesn't mean that n and d can't have the same numerical value,
just that they can't both point to the same struct BigNum.)

#> int bnMod(struct BigNum *dest, struct BigNum const *src,
#> 	struct BigNum const *d);

This works just the same as the above, but doesn't bother you with the
quotient.  (No, there's no function that doesn't bother you with the
remainder.)  Again, dest and src may be the same (it's actually
more efficient if they are), but d may not be the same as either.

#> unsigned int bnModQ(struct BigNum const *src, unsigned d);

This also computes src % d, but does so for small (up to 65535,
the usual limit on "Q" functions) values of d.  It returns the
remainder.

* Advanced math

#> int bnLShift(struct BigNum *dest, unsigned amt);
#> void bnRShift(struct BigNum *dest, unsigned amt);

These shift the given bignum left or right by "amt" bit positions.
Left shifts multiply by 2^amt, and may have to allocate memory