Botan
1.11.15
|
00001 /* 00002 * Simple O(N^2) Multiplication and Squaring 00003 * (C) 1999-2008 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/mp_core.h> 00009 #include <botan/internal/mp_madd.h> 00010 #include <botan/internal/mp_asmi.h> 00011 #include <botan/mem_ops.h> 00012 00013 namespace Botan { 00014 00015 extern "C" { 00016 00017 /* 00018 * Simple O(N^2) Multiplication 00019 */ 00020 void bigint_simple_mul(word z[], const word x[], size_t x_size, 00021 const word y[], size_t y_size) 00022 { 00023 const size_t x_size_8 = x_size - (x_size % 8); 00024 00025 clear_mem(z, x_size + y_size); 00026 00027 for(size_t i = 0; i != y_size; ++i) 00028 { 00029 const word y_i = y[i]; 00030 00031 word carry = 0; 00032 00033 for(size_t j = 0; j != x_size_8; j += 8) 00034 carry = word8_madd3(z + i + j, x + j, y_i, carry); 00035 00036 for(size_t j = x_size_8; j != x_size; ++j) 00037 z[i+j] = word_madd3(x[j], y_i, z[i+j], &carry); 00038 00039 z[x_size+i] = carry; 00040 } 00041 } 00042 00043 /* 00044 * Simple O(N^2) Squaring 00045 * 00046 * This is exactly the same algorithm as bigint_simple_mul, however 00047 * because C/C++ compilers suck at alias analysis it is good to have 00048 * the version where the compiler knows that x == y 00049 * 00050 * There is an O(n^1.5) squaring algorithm specified in Handbook of 00051 * Applied Cryptography, chapter 14 00052 * 00053 */ 00054 void bigint_simple_sqr(word z[], const word x[], size_t x_size) 00055 { 00056 const size_t x_size_8 = x_size - (x_size % 8); 00057 00058 clear_mem(z, 2*x_size); 00059 00060 for(size_t i = 0; i != x_size; ++i) 00061 { 00062 const word x_i = x[i]; 00063 word carry = 0; 00064 00065 for(size_t j = 0; j != x_size_8; j += 8) 00066 carry = word8_madd3(z + i + j, x + j, x_i, carry); 00067 00068 for(size_t j = x_size_8; j != x_size; ++j) 00069 z[i+j] = word_madd3(x[j], x_i, z[i+j], &carry); 00070 00071 z[x_size+i] = carry; 00072 } 00073 } 00074 00075 } 00076 00077 }