# How to caculate the summation of successive modular inverses?

$$p$$ is a big prime. $$p>2^{2048}$$. So how to caculate the summation of successive modular inverses over $$p$$? $$\sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p$$ As to $$p$$ is a big prime, it's impossible to caculate the modular inverses one by one and sum them at last. I found someone give a formula which approximates the result, but I couldn't prove it. $$p - \frac{2^{p}\pmod {p^2}-1}{p} \pmod p$$ Can you help me prove the formula, or give your answers to calculate the summation? Thanks sincerely!

• Could you give us a hint where this is used in Cryptography? And the link of the someone? – kelalaka Nov 26 '20 at 9:34
• @kelalaka Someone give the formula here in their code about the problem "more calc". I don't know where this is used, I just meet the problem in a CTF, then I used google search, but found nothing related. – x1st Nov 26 '20 at 9:41

The sum you are inquiring about is pretty much the right side of the Fermat quotient identity discovered by Eisenstein (proof here): $$-2q_p(2) = \sum_{i=1}^{(p-1)/2} 1/i \pmod{p}\,,$$ where $$q_p(a) = \frac{a^{p-1} - 1}{p}$$.
Thus the sum can be computed as $$-2 \frac{2^{p-1} - 1}{p} \bmod p$$. Because computing $$2^{p-1}$$ is not feasible for very large $$p$$, and because one only requires the result divided by $$p$$ and then reduced again by $$p$$, computing $$\frac{2^{p-1} - 1}{p}$$ can be performed as $$\frac{(2^{p-1} \bmod p^2) - 1}{p}$$ without any precision loss. And to absorb that factor of $$2$$, one can compute instead $$-\frac{(2^{p} \bmod p^2) - 1}{p} \bmod p$$, which is exactly the formula you found.