home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / BN.H < prev    next >
C/C++ Source or Header  |  1996-05-24  |  7KB  |  186 lines

  1. /*
  2.  * bn.h - the interface to the bignum routines.
  3.  * All functions which return ints can potentially allocate memory
  4.  * and return -1 if they are unable to. All "const" arguments
  5.  * are unmodified.
  6.  *
  7.  * This is not particularly asymmetric, as some operations are of the
  8.  * form a = b @ c, while others do a @= b.  In general, outputs may not
  9.  * point to the same struct BigNums as inputs, except as specified
  10.  * below.  This relationship is referred to as "being the same as".
  11.  * This is not numerical equivalence.
  12.  *
  13.  * The "Q" operations take "unsigned" inputs.  Higher values of the
  14.  * extra input may work on some implementations, but 65535 is the
  15.  * highest portable value.  Just because UNSIGNED_MAX is larger than
  16.  * that, or you know that the word size of the library is larger than that,
  17.  * that, does *not* mean it's allowed.
  18.  */
  19. #ifndef BN_H
  20. #define BN_H
  21.  
  22. struct BigNum {
  23.     void *ptr;
  24.     unsigned size;    /* Note: in (variable-sized) words */
  25.     unsigned allocated;
  26. };
  27.  
  28. #ifdef __cplusplus
  29. extern "C" {
  30. #endif
  31.  
  32. /* Functions */
  33.  
  34. /* bnInit *must* be called before any other bignum library function */
  35. void bnInit(void);
  36.  
  37. /*
  38.  * This initializes an empty struct BigNum to a zero value.
  39.  * Do not use this on a BigNum which has had a value stored in it!
  40.  */
  41. void bnBegin(struct BigNum *bn);
  42.  
  43. /* Swap two BigNums.  Cheap. */
  44. void bnSwap(struct BigNum *a, struct BigNum *b);
  45.  
  46. /* Reset an initialized bigNum to empty, pending deallocation. */
  47. extern void (*bnEnd)(struct BigNum *bn);
  48.  
  49. /*
  50.  * If you know you'll need space in the number soon, you can use this function
  51.  * to ensure that there is room for at least "bits" bits.  Optional.
  52.  * Returns <0 on out of memory, but the value is unaffected.
  53.  */
  54. extern int (*bnPrealloc)(struct BigNum *bn, unsigned bits);
  55.  
  56. /* Hopefully obvious.  dest = src.   dest may be the same as src. */
  57. extern int (*bnCopy)(struct BigNum *dest, struct BigNum const *src);
  58.  
  59. /*
  60.  * Mostly done automatically, but this removes leading zero words from
  61.  * the internal representation of the BigNum.  Use is unclear.
  62.  */
  63. extern void (*bnNorm)(struct BigNum *bn);
  64.  
  65. /*
  66.  * Move bytes between the given buffer and the given BigNum encoded in
  67.  * base 256.  I.e. after either of these, the buffer will be equal to
  68.  * (bn / 256^lsbyte) % 256^len.  The difference is which is altered to
  69.  * match the other!
  70.  */
  71. extern void (*bnExtractBigBytes)(struct BigNum const *bn,
  72.     unsigned char *dest, unsigned lsbyte, unsigned len);
  73. extern int (*bnInsertBigBytes)(struct BigNum *bn, unsigned char const *src,
  74.     unsigned lsbyte, unsigned len);
  75.  
  76. /* The same, but the buffer is little-endian. */
  77. extern void (*bnExtractLittleBytes)(struct BigNum const *bn,
  78.     unsigned char *dest, unsigned lsbyte, unsigned len);
  79. extern int (*bnInsertLittleBytes)(struct BigNum *bn, unsigned char const *src,
  80.     unsigned lsbyte, unsigned len);
  81.  
  82. /* Return the least-significant bits (at least 16) of the BigNum */
  83. extern unsigned (*bnLSWord)(struct BigNum const *src);
  84.  
  85. /*
  86.  * Return the number of significant bits in the BigNum.
  87.  * 0 or 1+floor(log2(src))
  88.  */
  89. extern unsigned (*bnBits)(struct BigNum const *src);
  90.  
  91. /*
  92.  * dest += src.  dest and src may be the same.  Guaranteed not to
  93.  * allocate memory unnecessarily, so if you're sure bnBits(dest)
  94.  * won't change, you don't need to check the return value.
  95.  */
  96. extern int (*bnAdd)(struct BigNum *dest, struct BigNum const *src);
  97.  
  98. /*
  99.  * dest -= src.  dest and src may be the same, but bnSetQ(dest, 0) is faster.
  100.  * if dest < src, returns +1 and sets dest = src-dest.
  101.  */
  102. extern int (*bnSub)(struct BigNum *dest, struct BigNum const *src);
  103.  
  104. /* Return sign (-1, 0, +1) of a-b.  a <=> b --> bnCmpQ(a, b) <=> 0 */
  105. extern int (*bnCmpQ)(struct BigNum const *a, unsigned b);
  106.  
  107. /* dest = src, where 0 <= src < 2^16. */
  108. extern int (*bnSetQ)(struct BigNum *dest, unsigned src);
  109.  
  110. /* dest += src, where 0 <= src < 2^16 */
  111. extern int (*bnAddQ)(struct BigNum *dest, unsigned src);
  112.  
  113. /* dest -= src, where 0 <= src < 2^16 */
  114. extern int (*bnSubQ)(struct BigNum *dest, unsigned src);
  115.  
  116. /* Return sign (-1, 0, +1) of a-b.  a <=> b --> bnCmp(a, b) <=> 0 */
  117. extern int (*bnCmp)(struct BigNum const *a, struct BigNum const *b);
  118.  
  119. /* dest = src^2.  dest may be the same as src, but it costs time. */
  120. extern int (*bnSquare)(struct BigNum *dest, struct BigNum const *src);
  121.  
  122. /* dest = a * b.  dest may be the same as a or b, but it costs time. */
  123. extern int (*bnMul)(struct BigNum *dest, struct BigNum const *a,
  124.     struct BigNum const *b);
  125.  
  126. /* dest = a * b, where 0 <= b < 2^16.  dest and a may be the same. */
  127. extern int (*bnMulQ)(struct BigNum *dest, struct BigNum const *a, unsigned b);
  128.  
  129. /*
  130.  * q = n/d, r = n%d.  r may be the same as n, but not d,
  131.  * and q may not be the same as n or d.
  132.  * re-entrancy issue: this temporarily modifies d, but restores
  133.  * it for return.
  134.  */
  135. extern int (*bnDivMod)(struct BigNum *q, struct BigNum *r,
  136.     struct BigNum const *n, struct BigNum const *d);
  137. /*
  138.  * dest = src % d.  dest and src may be the same, but not dest and d.
  139.  * re-entrancy issue: this temporarily modifies d, but restores
  140.  * it for return.
  141.  */
  142. extern int (*bnMod)(struct BigNum *dest, struct BigNum const *src,
  143.     struct BigNum const *d);
  144.  
  145. /* return src % d, where 0 <= d < 2^16.  */
  146. extern unsigned int (*bnModQ)(struct BigNum const *src, unsigned d);
  147.  
  148. /* n = n^exp, modulo "mod"   "mod" *must* be odd */
  149. extern int (*bnExpMod)(struct BigNum *result, struct BigNum const *n,
  150.     struct BigNum const *exp, struct BigNum const *mod);
  151.  
  152. /*
  153.  * dest = n1^e1 * n2^e2, modulo "mod".  "mod" *must* be odd.
  154.  * dest may be the same as n1 or n2.
  155.  */
  156. extern int (*bnDoubleExpMod)(struct BigNum *dest,
  157.     struct BigNum const *n1, struct BigNum const *e1,
  158.     struct BigNum const *n2, struct BigNum const *e2,
  159.     struct BigNum const *mod);
  160.  
  161. /* n = 2^exp, modulo "mod"   "mod" *must* be odd */
  162. extern int (*bnTwoExpMod)(struct BigNum *n, struct BigNum const *exp,
  163.     struct BigNum const *mod);
  164.  
  165. /* dest = gcd(a, b).  The inputs may overlap arbitrarily. */
  166. extern int (*bnGcd)(struct BigNum *dest, struct BigNum const *a,
  167.     struct BigNum const *b);
  168.  
  169. /* dest = src^-1, modulo "mod".  dest may be the same as src. */
  170. extern int (*bnInv)(struct BigNum *dest, struct BigNum const *src,
  171.     struct BigNum const *mod);
  172.  
  173. /* Shift dest left "amt" places */
  174. extern int (*bnLShift)(struct BigNum *dest, unsigned amt);
  175. /* Shift dest right "amt" places, discarding low-order bits */
  176. extern void (*bnRShift)(struct BigNum *dest, unsigned amt);
  177.  
  178. /* For the largest 2^k that divides n, divide n by it and return k. */
  179. extern unsigned (*bnMakeOdd)(struct BigNum *n);
  180.  
  181. #ifdef __cplusplus
  182. }
  183. #endif
  184.  
  185. #endif/* !BN_H */
  186.