bn_mp_toom_sqr.c
Go to the documentation of this file.00001 #include <tommath.h> 00002 #ifdef BN_MP_TOOM_SQR_C 00003 /* LibTomMath, multiple-precision integer library -- Tom St Denis 00004 * 00005 * LibTomMath is a library that provides multiple-precision 00006 * integer arithmetic as well as number theoretic functionality. 00007 * 00008 * The library was designed directly after the MPI library by 00009 * Michael Fromberger but has been written from scratch with 00010 * additional optimizations in place. 00011 * 00012 * The library is free for all purposes without any express 00013 * guarantee it works. 00014 * 00015 * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 00016 */ 00017 00018 /* squaring using Toom-Cook 3-way algorithm */ 00019 int 00020 mp_toom_sqr(mp_int *a, mp_int *b) 00021 { 00022 mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2; 00023 int res, B; 00024 00025 /* init temps */ 00026 if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL)) != MP_OKAY) { 00027 return res; 00028 } 00029 00030 /* B */ 00031 B = a->used / 3; 00032 00033 /* a = a2 * B**2 + a1 * B + a0 */ 00034 if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) { 00035 goto ERR; 00036 } 00037 00038 if ((res = mp_copy(a, &a1)) != MP_OKAY) { 00039 goto ERR; 00040 } 00041 mp_rshd(&a1, B); 00042 mp_mod_2d(&a1, DIGIT_BIT * B, &a1); 00043 00044 if ((res = mp_copy(a, &a2)) != MP_OKAY) { 00045 goto ERR; 00046 } 00047 mp_rshd(&a2, B*2); 00048 00049 /* w0 = a0*a0 */ 00050 if ((res = mp_sqr(&a0, &w0)) != MP_OKAY) { 00051 goto ERR; 00052 } 00053 00054 /* w4 = a2 * a2 */ 00055 if ((res = mp_sqr(&a2, &w4)) != MP_OKAY) { 00056 goto ERR; 00057 } 00058 00059 /* w1 = (a2 + 2(a1 + 2a0))**2 */ 00060 if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) { 00061 goto ERR; 00062 } 00063 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 00064 goto ERR; 00065 } 00066 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 00067 goto ERR; 00068 } 00069 if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) { 00070 goto ERR; 00071 } 00072 00073 if ((res = mp_sqr(&tmp1, &w1)) != MP_OKAY) { 00074 goto ERR; 00075 } 00076 00077 /* w3 = (a0 + 2(a1 + 2a2))**2 */ 00078 if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) { 00079 goto ERR; 00080 } 00081 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 00082 goto ERR; 00083 } 00084 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 00085 goto ERR; 00086 } 00087 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 00088 goto ERR; 00089 } 00090 00091 if ((res = mp_sqr(&tmp1, &w3)) != MP_OKAY) { 00092 goto ERR; 00093 } 00094 00095 00096 /* w2 = (a2 + a1 + a0)**2 */ 00097 if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) { 00098 goto ERR; 00099 } 00100 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 00101 goto ERR; 00102 } 00103 if ((res = mp_sqr(&tmp1, &w2)) != MP_OKAY) { 00104 goto ERR; 00105 } 00106 00107 /* now solve the matrix 00108 00109 0 0 0 0 1 00110 1 2 4 8 16 00111 1 1 1 1 1 00112 16 8 4 2 1 00113 1 0 0 0 0 00114 00115 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication. 00116 */ 00117 00118 /* r1 - r4 */ 00119 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) { 00120 goto ERR; 00121 } 00122 /* r3 - r0 */ 00123 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) { 00124 goto ERR; 00125 } 00126 /* r1/2 */ 00127 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) { 00128 goto ERR; 00129 } 00130 /* r3/2 */ 00131 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) { 00132 goto ERR; 00133 } 00134 /* r2 - r0 - r4 */ 00135 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) { 00136 goto ERR; 00137 } 00138 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) { 00139 goto ERR; 00140 } 00141 /* r1 - r2 */ 00142 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 00143 goto ERR; 00144 } 00145 /* r3 - r2 */ 00146 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 00147 goto ERR; 00148 } 00149 /* r1 - 8r0 */ 00150 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) { 00151 goto ERR; 00152 } 00153 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) { 00154 goto ERR; 00155 } 00156 /* r3 - 8r4 */ 00157 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) { 00158 goto ERR; 00159 } 00160 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) { 00161 goto ERR; 00162 } 00163 /* 3r2 - r1 - r3 */ 00164 if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) { 00165 goto ERR; 00166 } 00167 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) { 00168 goto ERR; 00169 } 00170 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) { 00171 goto ERR; 00172 } 00173 /* r1 - r2 */ 00174 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 00175 goto ERR; 00176 } 00177 /* r3 - r2 */ 00178 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 00179 goto ERR; 00180 } 00181 /* r1/3 */ 00182 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) { 00183 goto ERR; 00184 } 00185 /* r3/3 */ 00186 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) { 00187 goto ERR; 00188 } 00189 00190 /* at this point shift W[n] by B*n */ 00191 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) { 00192 goto ERR; 00193 } 00194 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) { 00195 goto ERR; 00196 } 00197 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) { 00198 goto ERR; 00199 } 00200 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) { 00201 goto ERR; 00202 } 00203 00204 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) { 00205 goto ERR; 00206 } 00207 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) { 00208 goto ERR; 00209 } 00210 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) { 00211 goto ERR; 00212 } 00213 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) { 00214 goto ERR; 00215 } 00216 00217 ERR: 00218 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL); 00219 return res; 00220 } 00221 00222 #endif 00223 00224 /* $Source: /cvsroot/tcl/libtommath/bn_mp_toom_sqr.c,v $ */ 00225 /* $Revision: 1.1.1.3 $ */ 00226 /* $Date: 2006/12/01 00:08:11 $ */
Generated on Wed Mar 12 12:18:25 2008 by
1.5.1