Function REDI_IL

IntegerProgramming/LLL.cc:55–92

void REDI_IL(const short& k, const short& l, BigInt** b,
             const short& vector_dimension, BigInt* d, BigInt** lambda)
// the REDI procedure for the integer LLL algorithm (algorithm 2.6.7 in
// Cohen's book)
{
#ifdef GMP
  if(abs(BigInt(2)*lambda[k][l])<=d[l+1])
#else   // GMP
  if(labs(2*lambda[k][l])<=d[l+1])
    // labs is the abs-function for long ints
#endif  // GMP
    return;

#ifdef GMP
  BigInt q=(BigInt(2)*lambda[k][l]+d[l+1])/(BigInt(2)*d[l+1]);
#else   // GMP
  long q=(long int) floor(((float)(2*lambda[k][l]+d[l+1]))/(2*d[l+1]));
#endif  // GMP

  // q is the integer quotient of the division
  // (2*lambda[k][l]+d[l+1])/(2*d[l+1]).
  // Because of the rounding mode (always towards zero) of GNU C++,
  // we cannot use the built-in integer division
  // here; it causes errors when dealing with negative numbers. Therefore
  // the complicated casts: The divident is first casted to a float which
  // causes the division result to be a float. This result is explicitly
  // rounded downwards. As the floor-function returns a double (for range
  // reasons), this has to be casted to an integer again.

  for(short m=0;m<vector_dimension;m++)
    b[k][m]-=q*b[l][m];
  // b[k]=b[k]-q*b[l]

  lambda[k][l]-=q*d[l+1];

  for(short i=0;i<=l-1;i++)
    lambda[k][i]-=q*lambda[l][i];
}