Calculating modular inverses of p mod $2^p$

Primes, divisors, arithmetic, number properties, ...
Post Reply
castrate
Posts: 30
Joined: Mon Aug 19, 2019 2:34 pm

Calculating modular inverses of p mod $2^p$

Post by castrate »

Let p an odd prime. We want to calculate $I(p)=p^{-1}\mod 2^p$.
If we use EXGCD, it takes $O(\log_22^p)=O(p)$ time, which is not efficient enough.
Some small values are 3, 13, 55, 931, 3781, 61681, 248347, 4011943, 259179061......
It seems that $I(p)$ is slightly smaller than $2^{p-1}$, but I didn't find more explicit patterns, nor did I find the sequence on OEIS.

So is there a closed form of $I(p)$, or at least can we calculate that more efficiently?
Any idea would be appreciated! :D
User avatar
jaap
Posts: 587
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Calculating modular inverses of p mod $2^p$

Post by jaap »

After some experimentation it turns out that if $p=2k+1$ then the inverse of $p$ mod $2^p$ is $\frac{k\cdot2^p + 1}{p}$.

Clearly if that fraction is actually an integer, then it works as the inverse of $p$ mod $2^p$.
To prove that it is an integer for prime $p$, you can use Fermat's little theorem ($2^p\equiv2 \bmod p$):
We have:
$$k\cdot2^p + 1 = k\cdot2 + 1 = p \equiv 0 \mod p$$
so for prime $p=2k+1$ the number $k\cdot2^p + 1$ is divisible by $p$, and that division produces the inverse you want.
pjt33
Posts: 99
Joined: Mon Oct 06, 2008 6:14 pm

Re: Calculating modular inverses of p mod $2^p$

Post by pjt33 »

jaap wrote: Thu Mar 11, 2021 2:04 pm After some experimentation it turns out that if $p=2k+1$ then the inverse of $p$ mod $2^p$ is $\frac{k\cdot2^p + 1}{p}$.
Which is $2^{p-1} - \frac{2^{p-1} - 1}{p}$, explaining the observation that it's slightly smaller than $2^{p-1}$.

A variant approach is to use the form of Fermat's little theorem that says that $2^{p-1} \equiv 1 \pmod p$, so that $\frac{2^{p-1} - 1}{p}$ is an integer. We have a $-1$ rather than a $+1$ in the numerator, so square the numerator to get $q = \frac{(2^{p-1} - 1)^2}{p} = \frac{2^{2p-2} - 2^p + 1}{p} = \frac{2^p (2^{p-2} - 1) + 1}{p}$. Since $p > 2$, $q$ is a multiplicative inverse of $p$ modulo $2^p$. The big disadvantage with respect to jaap's approach is that $q$ isn't inherently reduced modulo $2^p$.
Post Reply