Fast constant-time GCD algorithm and modular inversion
It seems &quot;constant-time&quot; isn&#x27;t used to mean &quot;the time taken is O(1) regardless of the size of the input n&quot;, but rather, &quot;for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks&quot;.  This took me a bit of time to figure out.<p>To illustrate the kind of thing it&#x27;s talking about, consider the naive algorithm for computing a^n via exponentiation by squaring:<p><pre><code>  total = 1
  while n &gt; 0:
    if n is odd:
      total = total*a
      n = n-1
    a = a*a
    n = n&#x2F;2
  return total
</code></pre>
If n has k bits, and j of them are 1s, then there will be k-1 squarings of a, and j multiplications of total by a.  An attacker who can measure the total time may be able to at least figure out the number of 1 bits in n.  If they can get fine-grained observations of power draw or something, then they might even be able to tell which bits are 1.<p>Consider this alternative:<p><pre><code>  total = 1
  while n &gt; 0:
    maybe_total = total * a
    if n is odd:
      total = maybe_total
    a = a * a
    n = n &gt;&gt; 1
  return total
</code></pre>
This will do the same number of multiplications, if you can convince the compiler to not do any optimizations.  Note that it still has a branch, though, which might conceivably be detectable.  To plug that hole, something like this might work:<p><pre><code>  # if n is odd:
  #   total = maybe_total
  # becomes this:
    low_bit = n &amp; 1 # i.e. 0 or 1 if n is odd or even
    mask = low_bit - 1 # i.e. &quot;all 1s&quot; or 0 respectively
    total = (total &amp; mask) | (maybe_total &amp; ~mask)</code></pre>