| 286 | |
| 287 | |
| 288 | int matrix::compute_nonzero_kernel_vector() |
| 289 | { |
| 290 | |
| 291 | if(_kernel_dimension==-2) |
| 292 | // lattice basis not yet computed |
| 293 | LLL_kernel_basis(); |
| 294 | |
| 295 | if(_kernel_dimension==-1) |
| 296 | { |
| 297 | cerr<<"\nWARNING: int matrix::compute_non_zero_kernel_vector(BigInt*&):" |
| 298 | "\nerror in kernel basis, cannot compute the desired vector"<<endl; |
| 299 | return 0; |
| 300 | } |
| 301 | |
| 302 | if(_kernel_dimension==0) |
| 303 | { |
| 304 | cerr<<"\nWARNING: int matrix::compute_non_zero_kernel_vector(BigInt*&): " |
| 305 | "\nkernel dimension is zero"<<endl; |
| 306 | return 0; |
| 307 | } |
| 308 | |
| 309 | // Now, the kernel dimension is positive. |
| 310 | |
| 311 | BigInt *M=new BigInt[_kernel_dimension]; |
| 312 | // M stores a number by which the algorithm decides which vector to |
| 313 | // take next. |
| 314 | |
| 315 | |
| 316 | // STEP 1: Determine the vector with the least zero components (if it is not |
| 317 | // unique, choose the smallest). |
| 318 | |
| 319 | // determine number of zero components |
| 320 | for(int i=0;i<_kernel_dimension;i++) |
| 321 | { |
| 322 | M[i]=0; |
| 323 | for(int j=0;j<columns;j++) |
| 324 | if(H[i][j]==BigInt(0)) |
| 325 | M[i]++; |
| 326 | } |
| 327 | |
| 328 | // determine minimal number of zero components |
| 329 | BigInt min=columns; |
| 330 | // columns is an upper bound (not reached because the kernel basis cannot |
| 331 | // contain the zero vector) |
| 332 | for(int i=0;i<_kernel_dimension;i++) |
| 333 | if(M[i]<min) |
| 334 | min=M[i]; |
| 335 | |
| 336 | // add the square of the norm to the vectors with the least zero components |
| 337 | // and discard the others (the norm computation is why we have chosen the |
| 338 | // M[i] to be BigInts) |
| 339 | for(int i=0;i<_kernel_dimension;i++) |
| 340 | if(M[i]!=min) |
| 341 | M[i]=-1; |
| 342 | else |
| 343 | for(int j=0;j<columns;j++) |
| 344 | M[i]+=H[i][j]*H[i][j]; |
| 345 | // As the lattice basis does not contain the zero vector, at least one M[i] |