bn.doc

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

(and thus fail).  Right shifts divide by 2^amt, throwing away the
remainder, and can never fail.

#> unsigned bnMakeOdd(struct BigNum *n);

This right shifts the input number as many places as possible without
throwing anything away, and returns the number of bits shifted.
If you see "let n = s * 2^t, where s is odd" in an algorithm,
this is the function to call.  It modifies n in place to produce s
and returns t.

This returns 0 if you pass it 0.

#> int bnExpMod(struct BigNum *result, struct BigNum const *n,
#> 	struct BigNum const *exp, struct BigNum const *mod);

Ah, now we get to the heart of the library - probably the most heavily
optimized function in it.  This computes result = n^exp, modulo "mod".
result may be the same as n, but not the same as exp or mod.  For large
exponents and moduli, it can try to allocate quite a bit of working
storage, although it will manage to finish its work (just slower)
if some of those allocations fail.  (Not all, though - the first few
are essential.)

"mod" must be odd.  It will blow up if not.  Also, n must be less than
mod.  If you're not sure if it is, use bnMod first.  The return value
is always between 0 and mod-1.

#> int bnTwoExpMod(struct BigNum *result, struct BigNum const *exp,
#>	struct BigNum const *mod);

This computes result = 2^exp, modulo "mod".  It's faster than the general
bnExpMod function, although that function checks to see if n = 2 and calls
this one internally, so you don't need to check yourself if you're not
sure.  The main reason to mention this is that if you're doing something
like a pseudoprimality test, using a base of 2 first can save some time.

#> int bnDoubleExpMod(struct BigNum *result,
#> 	struct BigNum const *n1, struct BigNum const *e1,
#> 	struct BigNum const *n2, struct BigNum const *e2,
#> 	struct BigNum const *mod);

This computes dest = n1^e1 * n2^e2, modulo "mod".  It does it quite
a bit faster than doing two separate bnExpMod operations; in fact,
it's not that much more expensive than one.  "result" may be the
same BigNum as n1 or n2, but it may not be the same as the exponents
or the modulus.  All of the other caveats about bnExpMod apply.

#> int bnGcd(struct BigNum *dest, struct BigNum const *a,
#>	struct BigNum const *b);

This returns dest = gcd(a,b).  dest may be the same as either input.

/* dest = src^-1, modulo "mod".  dest may be the same as src. */
#> int bnInv(struct BigNum *dest, struct BigNum const *src,
#>	struct BigNum const *mod);

This requires that gcd(src, mod) = 1, and returns dest = src^-1, modulo
"mod".  That is, 0 < dest < mod and dest*src = 1, modulo "mod".
dest and src may be the same, but mod must be different.

This will probably get extended at some point to find dest such that
dest * src = gcd(src, mod), modulo "mod", but that isn't implemented
yet.

* Auxiliary functions

These functions have very limited usefulness, and might even get removed,
but for now they're there in the unusual case where you might want them.

#> int bnPrealloc(struct BigNum *bn, unsigned bits);

This preallocates space in bn to make sure that it can hold "bits" bits.
If the overflow characteristics of various algorithms get documented
better, this might allow even more error-checking to be avoided, but
for now it's only to reduce memory fragmentation.

#> void bnNorm(struct BigNum *bn);

This decreases the "size" field of the given bignum until it has no leading
zero words in its internal representation.  Given that almost everything
in the library does the equivalent of this on input and output, the utility
of this function is a bit dubious.  It's kind of a legacy.

* Extra libraries

There are a number of utilities built on top of the basic library.
They are built on top of the interfaces just described, and can be used
if you like.

* jacobi.h

#> int bnJacobiQ(unsigned p, struct BigNum const *bn);

This returns the Jacobi symbol J(p,bn), where p is a small number.
The Jacobi symbol is always -1, 0, or +1.  You'll note that p may
only be positive, even though the Jacobi symbol is defined for
negative p.  If you want to worry about negative p, do it yourself.
J(-p,bn) = (bnLSWord(bn) & 2 ? -1 : +1) * bnJacobiQ(p, bn).

A function to compute the Jacobi symbol for large p would be nice.

* prime.h

#> int primeGen(struct BigNum *bn, unsigned (*rand)(unsigned),
#> 	int (*f)(void *arg, int c), void *arg, unsigned exponent, ...);

This finds the next prime p >= bn, and sets bn to equal it.
Well, sort of.

It always leaves bn at least as large as when it started (unless it
runs out of memory and returns -1), and if you pass a 0 for the rand
function, it will be the next prime >= bn.

Except:
- It doesn't bother coping with small primes.  If it's divisible by any
prime up to 65521, it's considered non-prime.  Even if the quotient is 0.
If you pass in "1", expecting to get "2" back, you'll get 65537.  Maybe
it would be nice to fix that.
- It actually only does a few strong pseudoprimality tests to fixed
bases to determine if the candidate number is prime.  For random input,
this is fine; the chance of error is so infinitesimal that it is
absolutely not worth worrying about.  But if you give it numbers carefully
chosen to be strong pseudoprimes, it will think they're primes and not
complain.  For example, 341550071728321 = 10670053 * 32010157 will
pass the primality test quite handily.  So will
68528663395046912244223605902738356719751082784386681071.
- If you supply a rand() function, which returns 0 <= rand(n) < n
(n never gets very large - currently, at most 256), this shuffles the
candidates before testing and accepting one.  If you want a "random"
prime, this produces a more uniformly distributed prime, while
retaining all of the speed advantages of a sequential search from a
random starting point, which would otherwise produce a bias towards
primes which were not closely preceded by other primes.  So, for
example, the second of a pair of twin primes would be very unlikely to
be chosen.  rand() doesn't totally flatten the distribution, but it
comes very close.

The "f" function is called periodically during the progress of the
search (which can take a while) with the supplied argument (for private
context) and a character c, which sort of tells you what it's doing.
c is either '.' or '*' (if it's found something and is confirming that
it's really prime) or '/' (if it's having a really hard time finding
something).  Also, if f returns < 0, primeGen immediately returns that
value.  This can form the basis for a user interface which can show some
life occasionally and abort the computation if desired.

If you just print these characters to the screen, don't forget to
fflush() after printing them.

Finally, "exponent, ..." is a zero-terminated list of small numbers
which must not divide p-1 when the function returns.  If the numbers
are chosen to be the prime factors of n, then gcd(n, p-1) will be
1, so the map f(x) -> x^n is invertible modulo p.

#> int primeGenStrong(struct BigNum *bn, struct BigNum const *step,
#>	int (*f)(void *arg, int c), void *arg);

This is similar, but searches in steps of "step", rather than 1, from the
given starting value.  The starting value must be odd and the step
size must be even!  If you start with bn == 1 (mod step), and step
is 2*q, where q is a large prime, then this generates "strong" primes,
p-1 having a large prime factor q.  There are other uses, too.

#ifdef __cplusplus
}
#endif

* germain.h

#> int germainPrimeGen(struct BigNum *bn, int (*f)(void *arg, int c),
#>	void *arg);

This increases bn until it is a Sophie Germain prime, that is, a number p
such that p and (p-1)/2 are both prime.  These numbers are rarer than
ordinary primes and the search takes correspondingly longer.

It omits the randomization portion of primeGen, and the exponent list,
since the factors of bn-1 are known already.  The f function for
progress is the same, but it is also sometimes passed a '+' or '-'
character when it's found a (p-1)/2 that's prime.  This is just to lend
some interest to an otherwise very boring row of dots.  Finding large
primes with this function, even though it's pretty optimized, takes a
*while*, and otherwise once the screen filled with dots (one every few
seconds) it would be hard to keep track of the scroll.

It varies a lot, depending on luck of the starting value and the speed
of your machine, but if your starting number is over 1024 bits, plan on
over an hour of run time, and if it's over 2048 bits, plan on a day.
At 4096 bits, start thinking about a week.

Past that, supporting checkpoint/restart is a good idea.  Every time
the progress function gets a '/' is probably a good interval, and when
it happens have f return a distinct error value like -2.  When
germainPrimeGen returns with that value, save the value in bn to a file
somewhere and call it again with the same bn to continue searching.

* sieve.h

This is the sieving code that the other prime-finding functions call
to do trial division.  You might use it if you are doing some magic
prime-finding of your own.  A sieve is an array of bits, stored
little-endian in an array of bytes (i.e. the lsb of byte 0 is bit 0).
Sieves are indexed with the "unsigned" data type, so should not, for
portability, be larger than 65536/8 = 8192 bytes long.

A 1 bit is considered "in" the sieve, it has passed all the sieving.
A 0 bit has been removed by some step.

The functions are:

#> void sieveSingle(unsigned char *array, unsigned size, unsigned start,
#>	unsigned step);

This (efficiently) clears the bits at positions start, start+step,
start+2*step, etc. in the sieve given by array and size.  This is the
elementary sieve-building step.  Start with a sieve of all 1s, and
apply this as required.

#> unsigned sieveSearch(unsigned char const *array, unsigned size,
#>	unsigned start);

This returns the next bit position *greater than* start which is set
in the indicated sieve, or 0 on failure.  NOTE that this means that
you have to look at the bit at position 0 (array[0] & 1) by yourself
if you want to pay attention to it, because there's no way to tell
sieveSearch to start searching at 0 - it starts at start+1.

#> int sieveBuild(unsigned char *array, unsigned size, struct BigNum const *bn,
#>	unsigned step, unsigned dbl);

This initializes a sieve where, if bit i is set, then bn+step*i is not
divisible by any small primes.  (Small is from 2 through 65521, the
largest prime less that 65536.)  If "dbl" is > 0, then bits are also
cleared if 2*(bn+step*i)+1 is divisible.  If dbl > 1, then
4*(bn+step*i)+3 is also checked, and so on.  This feature is used when
generating Sohpie Germain primes.

Usually, you use a step of 2.

#> int sieveBuildBig(unsigned char *array, unsigned size,
#>	struct BigNum const *bn, struct BigNum const *step, unsigned dbl);

This is just the same, but accepts a BigNum step size, and is correspondingly
slower.

* bnprint.h

#> int bnPrint(FILE *f, char const *prefix, struct BigNum const *bn,
#>	char const *suffix);

This prints a nicely-formatted BigNum in hexadecimal form to the given
FILE *.  The "prefix" is printed before it, as a prompt, and the
"suffix" is printed afterwards.  The BigNum itself is printed in
64-character lines, broken with a trailing backslash if necessary.
Continuation lines are indented by the length of the prefix.

E.g. a 2^512-1, printed with the call bnPrint(stdout, "a = (", bn, ")\n")
would result in:

a = (FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
     FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)

Hex digits are printed in upper case to facilitate cutting and pasting into
the Unix "dc" utility.