| 134 | |
| 135 | |
| 136 | void SWAPK(const short& k, const short& k_max, BigInt** b, BigInt** H, |
| 137 | char *f, BigInt* d, BigInt** lambda) |
| 138 | // the SWAPK procedure of algorithm 2.7.2 |
| 139 | { |
| 140 | // exchange H[k] and H[k-1] |
| 141 | // This can be done efficiently by swapping pointers (not entries). |
| 142 | BigInt *swap=H[k]; |
| 143 | H[k]=H[k-1]; |
| 144 | H[k-1]=swap; |
| 145 | |
| 146 | // exchange b[k] and b[k-1] by the same method |
| 147 | swap=b[k]; |
| 148 | b[k]=b[k-1]; |
| 149 | b[k-1]=swap; |
| 150 | |
| 151 | if(k>1) |
| 152 | for(short j=0;j<=k-2;j++) |
| 153 | { |
| 154 | // exchange lambda[k][j] and lambda[k-1][j] |
| 155 | BigInt swap=lambda[k][j]; |
| 156 | lambda[k][j]=lambda[k-1][j]; |
| 157 | lambda[k-1][j]=swap; |
| 158 | } |
| 159 | |
| 160 | BigInt _lambda=lambda[k][k-1]; |
| 161 | |
| 162 | if(_lambda==BigInt(0)) |
| 163 | { |
| 164 | d[k]=d[k-1]; |
| 165 | f[k-1]=0; |
| 166 | f[k]=1; |
| 167 | lambda[k][k-1]=0; |
| 168 | for(short i=k+1;i<=k_max;i++) |
| 169 | { |
| 170 | lambda[i][k]=lambda[i][k-1]; |
| 171 | lambda[i][k-1]=0; |
| 172 | } |
| 173 | } |
| 174 | else |
| 175 | // lambda!=0 |
| 176 | { |
| 177 | for(short i=k+1;i<=k_max;i++) |
| 178 | lambda[i][k-1]=(_lambda*lambda[i][k-1])/d[k]; |
| 179 | |
| 180 | // Multiplie lambda[i][k-1] by _lambda/d[k]. |
| 181 | // One could also write |
| 182 | // lambda[i][k-1]*=(lambda/d[k]); (*) |
| 183 | // Without a BigInt class, this can prevent overflows when computing |
| 184 | // _lambda*lambda[i][k-1]. |
| 185 | // But examples show that lambda/d[k] is in general not an integer. |
| 186 | // So (*) could lead to problems due to the inexact floating point |
| 187 | // arithmetic... |
| 188 | // Therefore, we chose the secure evaluation order in all such cases. |
| 189 | |
| 190 | BigInt t=d[k+1]; |
| 191 | d[k]=(_lambda*_lambda)/d[k]; |
| 192 | d[k+1]=d[k]; |
| 193 | |