New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

3 of 8
Link to original question; polish.
fgrieu
• 141.7k
• 12
• 309
• 591

This answers the original question in the particular case of $$p=2^{64}$$. It quickly computes the modular inverse of any odd 64-bit integer, on most modern C compilers with 64-bit support. It is constant-time if basic operations are (which is often a worry for multiplication).

#include <stdint.h>                     // for uint64_t and uint32_t

// given odd a, compute x such that a*x = 1 over 64 bits.
uint64_t invmod(uint64_t a)
{
uint32_t b = (uint32_t)a;           // low 32 bits of a
uint32_t x = (((b+0x2)&0x4)<<1)+b;  // low  4 bits of inverse
x =    (0x2-b*x)*x;                 // low  8 bits of inverse
x =    (0x2-b*x)*x;                 // low 16 bits of inverse
x =    (0x2-b*x)*x;                 // low 32 bits of inverse
return (0x2-a*x)*x;                 //     64 bits of inverse
}


Justification: $$a\cdot x\equiv1\pmod{2^k}\implies a\cdot(2-a\cdot x)\cdot x\equiv1\pmod{2^{2\cdot k}}$$

Note: The code uses intermediary 32-bit variable b only in order to optimize speed on 32-bit CPUs; we could otherwise use a, or/and make x wider than 32-bit.

fgrieu
• 141.7k
• 12
• 309
• 591