3
$\begingroup$

I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated.

Thank you,

  • 1
    @Zev Chonoles: It was from my lecture notes. My teacher said there were 3 methods to calculate the inverse, first one is extended Euclidean, second one is $a^{\phi(m) - 1 } \pmod{m}$, and third one is Voronoi.2011-04-25

1 Answers 1

5

Voronoi's formula is named after Georgi Voronoi. It goes a bit like this:

If we have $ax \equiv 1 \pmod m$ and we have that $\gcd(a,m) = 1$ (as otherwise we know that there is no solution), then the solution is given by $ x \equiv \left(3 - 2a + 6 \sum\limits_{k=1}^{a-1} \left\lfloor \frac{mk}{a} \right\rfloor^2 \right) \pmod m$

You can quickly see that this is impractical in many cases, but for large m and small a, it works quickly. I should also note that in general, Euclid's algorithm is much faster. I hope this helps.

  • 0
    @Bill: I don't know his paper, I just happened to have seen it in Tattersall's Elementary Number Theory in Nine Chapters a while back.2011-04-25