Find inverses of all number 1 through P-1 where P is a prime number in O(P) time.
C++
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
mod_inverses.cc

README.md

fast-mod-inverses

Find inverses of all numbers 1 through P-1 where P is a prime number in O(P) time. One can find mod inverses of all numbers from 1 to P-1 by using Fermat's little theorem but that takes time (P lg P). This technique is much more efficient. It is based on the following recurrence relation:

inverse[1] = 1
inverse[i] = -(P / i) * inverse[P mod i];