Botan  1.11.15
src/lib/math/mp/mp_core.h
Go to the documentation of this file.
00001 /*
00002 * MPI Algorithms
00003 * (C) 1999-2010 Jack Lloyd
00004 *     2006 Luca Piccarreta
00005 *
00006 * Botan is released under the Simplified BSD License (see license.txt)
00007 */
00008 
00009 #ifndef BOTAN_MP_CORE_OPS_H__
00010 #define BOTAN_MP_CORE_OPS_H__
00011 
00012 #include <botan/mp_types.h>
00013 
00014 namespace Botan {
00015 
00016 /*
00017 * The size of the word type, in bits
00018 */
00019 const size_t MP_WORD_BITS = BOTAN_MP_WORD_BITS;
00020 
00021 extern "C" {
00022 
00023 /**
00024 * Two operand addition
00025 * @param x the first operand (and output)
00026 * @param x_size size of x
00027 * @param y the second operand
00028 * @param y_size size of y (must be >= x_size)
00029 */
00030 void bigint_add2(word x[], size_t x_size,
00031                  const word y[], size_t y_size);
00032 
00033 /**
00034 * Three operand addition
00035 */
00036 void bigint_add3(word z[],
00037                  const word x[], size_t x_size,
00038                  const word y[], size_t y_size);
00039 
00040 /**
00041 * Two operand addition with carry out
00042 */
00043 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size);
00044 
00045 /**
00046 * Three operand addition with carry out
00047 */
00048 word bigint_add3_nc(word z[],
00049                     const word x[], size_t x_size,
00050                     const word y[], size_t y_size);
00051 
00052 /**
00053 * Two operand subtraction
00054 */
00055 word bigint_sub2(word x[], size_t x_size,
00056                  const word y[], size_t y_size);
00057 
00058 /**
00059 * Two operand subtraction, x = y - x; assumes y >= x
00060 */
00061 void bigint_sub2_rev(word x[], const word y[], size_t y_size);
00062 
00063 /**
00064 * Three operand subtraction
00065 */
00066 word bigint_sub3(word z[],
00067                  const word x[], size_t x_size,
00068                  const word y[], size_t y_size);
00069 
00070 /*
00071 * Shift Operations
00072 */
00073 void bigint_shl1(word x[], size_t x_size,
00074                  size_t word_shift, size_t bit_shift);
00075 
00076 void bigint_shr1(word x[], size_t x_size,
00077                  size_t word_shift, size_t bit_shift);
00078 
00079 void bigint_shl2(word y[], const word x[], size_t x_size,
00080                  size_t word_shift, size_t bit_shift);
00081 
00082 void bigint_shr2(word y[], const word x[], size_t x_size,
00083                  size_t word_shift, size_t bit_shift);
00084 
00085 /*
00086 * Simple O(N^2) Multiplication and Squaring
00087 */
00088 void bigint_simple_mul(word z[],
00089                        const word x[], size_t x_size,
00090                        const word y[], size_t y_size);
00091 
00092 void bigint_simple_sqr(word z[], const word x[], size_t x_size);
00093 
00094 /*
00095 * Linear Multiply
00096 */
00097 void bigint_linmul2(word x[], size_t x_size, word y);
00098 void bigint_linmul3(word z[], const word x[], size_t x_size, word y);
00099 
00100 /**
00101 * Montgomery Reduction
00102 * @param z integer to reduce, of size exactly 2*(p_size+1).
00103            Output is in the first p_size+1 words, higher
00104            words are set to zero.
00105 * @param p modulus
00106 * @param p_size size of p
00107 * @param p_dash Montgomery value
00108 * @param workspace array of at least 2*(p_size+1) words
00109 */
00110 void bigint_monty_redc(word z[],
00111                        const word p[], size_t p_size,
00112                        word p_dash,
00113                        word workspace[]);
00114 
00115 /*
00116 * Montgomery Multiplication
00117 */
00118 void bigint_monty_mul(word z[], size_t z_size,
00119                       const word x[], size_t x_size, size_t x_sw,
00120                       const word y[], size_t y_size, size_t y_sw,
00121                       const word p[], size_t p_size, word p_dash,
00122                       word workspace[]);
00123 
00124 /*
00125 * Montgomery Squaring
00126 */
00127 void bigint_monty_sqr(word z[], size_t z_size,
00128                       const word x[], size_t x_size, size_t x_sw,
00129                       const word p[], size_t p_size, word p_dash,
00130                       word workspace[]);
00131 
00132 /**
00133 * Compare x and y
00134 */
00135 s32bit bigint_cmp(const word x[], size_t x_size,
00136                   const word y[], size_t y_size);
00137 
00138 /**
00139 * Compute ((n1<<bits) + n0) / d
00140 */
00141 word bigint_divop(word n1, word n0, word d);
00142 
00143 /**
00144 * Compute ((n1<<bits) + n0) % d
00145 */
00146 word bigint_modop(word n1, word n0, word d);
00147 
00148 /*
00149 * Comba Multiplication / Squaring
00150 */
00151 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
00152 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
00153 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
00154 void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
00155 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
00156 
00157 void bigint_comba_sqr4(word out[8], const word in[4]);
00158 void bigint_comba_sqr6(word out[12], const word in[6]);
00159 void bigint_comba_sqr8(word out[16], const word in[8]);
00160 void bigint_comba_sqr9(word out[18], const word in[9]);
00161 void bigint_comba_sqr16(word out[32], const word in[16]);
00162 
00163 }
00164 
00165 /*
00166 * High Level Multiplication/Squaring Interfaces
00167 */
00168 void bigint_mul(word z[], size_t z_size, word workspace[],
00169                 const word x[], size_t x_size, size_t x_sw,
00170                 const word y[], size_t y_size, size_t y_sw);
00171 
00172 void bigint_sqr(word z[], size_t z_size, word workspace[],
00173                 const word x[], size_t x_size, size_t x_sw);
00174 
00175 }
00176 
00177 #endif