0
$\begingroup$

$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!

$\endgroup$
  • $\begingroup$ Could you give us a hint where this is used in Cryptography? And the link of the someone? $\endgroup$ – kelalaka Nov 26 '20 at 9:34
  • $\begingroup$ @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. $\endgroup$ – x1st Nov 26 '20 at 9:41
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.