1

I've found this snippet in the guts of GCC compiler. This is modulo inverse.

/* Computes inverse to X modulo (1 << MOD).  */

static uint64_t
inverse (uint64_t x, int mod)
{
  uint64_t mask =
      ((uint64_t) 1 << (mod - 1) << 1) - 1;
  uint64_t rslt = 1;
  int i;

  for (i = 0; i < mod - 1; i++)
    {
      rslt = (rslt * x) & mask;
      x = (x * x) & mask;
    }

  return rslt;
}

https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/gcc/loop-iv.c#L1291

And it works. But how? This is obviously not extended euclidian algorithm. Am I correct that a product of quadratic residues is computed here?

Where to read more about this method?

Xenia Galinskaya
  • 11
  • The << part, is that a bitwise shift? Are these bitwise operators generally? – Chris Jul 17 '17 at 03:48
  • I believe they may be using Euler's theorem for the totient function and exponentiation by squarings. – Tob Ernack Jul 17 '17 at 03:49
  • 1
    Ultimately, rslt is going to equal x raised to the power $1 + 2 + 2^2 + \ldots + 2^{\text{mod} - 2} = 2^{\text{mod} - 1} - 1 = \phi\left(2^\text{mod}\right) - 1$ computed modulo $2^{\text{mod}}$. Which is a clever use of the fact that $x^{\phi\left(2^{\text{mod}}\right)} \equiv 1 \pmod {2^{\text{mod}}}$ if $x$ is odd. – Tob Ernack Jul 17 '17 at 03:55
  • Chris, mask is just 0xffffffffffffffff here, i.e., $(2^{64})-1$, in other words, has as many bits, as modulo has. – Xenia Galinskaya Jul 17 '17 at 03:56
  • Chris, << is bitwise shift left, yes. – Xenia Galinskaya Jul 17 '17 at 04:01
  • @TobErnack You can post that as an answer.] – user202729 May 23 '18 at 11:05

0 Answers0