lopy4/components/Bliss-master/tools/rev_shoup_red_scaled_table.c
/*
 * Check whether n is invertible modulo q and return the inverse in *inv_n
 */
Check whether n is invertible modulo q and return the inverse in *inv_n
Check whether n is invertible modulo q and return the inverse in * inv_n
static bool inverse(uint32_t n, uint32_t q, uint32_t *inv_n) {
  int32_t r1, r2, u1, u2, v1, v2, g, x;
  r1 = n; u1 = 1; v1 = 0;
  r2 = q; u2 = 0, v2 = 1;
  while (r2 > 0) {
    assert(r1 == (int32_t) n * u1 + (int32_t) q * v1);
    assert(r2 == (int32_t) n * u2 + (int32_t) q * v2);
    assert(r1 >= 0);
    g = r1/r2;
    x = r1; r1 = r2; r2 = x - g * r2;
    x = u1; u1 = u2; u2 = x - g * u2;
    x = v1; v1 = v2; v2 = x - g * v2;
  }
  if (r1 == 1) {
    u1 = u1 % (int32_t) q;
    if (u1 < 0) u1 += q;
    assert(((((int32_t) n) * u1) % (int32_t) q) == 1);
    *inv_n = u1;
    return true;
  } else {
    return false;
  }
}
static bool inverse ( uint32_t n , uint32_t q , uint32_t * inv_n ) { int32_t r1 , r2 , u1 , u2 , v1 , v2 , g , x ; r1 = n ; u1 = 1 ; v1 = 0 ; r2 = q ; u2 = 0 , v2 = 1 ; while ( r2 > 0 ) { assert ( r1 == ( int32_t ) n * u1 + ( int32_t ) q * v1 ) ; assert ( r2 == ( int32_t ) n * u2 + ( int32_t ) q * v2 ) ; assert ( r1 >= 0 ) ; g = r1 / r2 ; x = r1 ; r1 = r2 ; r2 = x - g * r2 ; x = u1 ; u1 = u2 ; u2 = x - g * u2 ; x = v1 ; v1 = v2 ; v2 = x - g * v2 ; } if ( r1 == 1 ) { u1 = u1 % ( int32_t ) q ; if ( u1 < 0 ) u1 += q ; assert ( ( ( ( ( int32_t ) n ) * u1 ) % ( int32_t ) q ) == 1 ) ; * inv_n = u1 ; return true ; } else { return false ; } }
Check whether n is invertible modulo q and return the inverse in *inv_n
Check whether n is invertible modulo q and return the inverse in * inv_n
// invariant: r1 = n * u1 + q * v1 //            r2 = n * u2 + q * v2 // r1 is gcd(n, q) = n * u1 + q * v1