2
$\begingroup$

I want to calculate do calculate $\frac{a}{b} \pmod{P}$ where $a$ is an integer less $P$ and $P$ is a large prime, $b=5$, a fixed integer.

How can I implement it? Any algorithm which will work well?

  • 0
    To compute $b^{-1} \pmod{p}$, use the [extended Euclidean algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm). (edit: Oh, now I see "large" prime. see Andre's answer then.)2012-09-04

4 Answers 4

0

If $a$ were divisible by $5$, we could just do ordinary exact integer divison.

All of $a, a+p, a+2p, a+3p, a+4p$ have the same value modulo $p$. As one of them is guaranteed to be divisible by $5$, we can pick that one and divide it by $5$.

For added optimization, divide $a$ by $5$ with remainder, to obtain $a = 5q + r$. Now, if I haven't made an off by one error, you can compute:

$ \frac{a}{5} \equiv q + \left\lceil \frac{rp}{5} \right\rceil \pmod p $

You can, of course, store a lookup table of the four non-zero values of the second term.

  • 0
    For an extra bit of speed on the precomputation, you can do it by dividing $p$ by $5$ with remainder just once, and then working out the four possible values without any further division. I'll leave that as an exercise.2012-09-04
4

First calculate an inverse $k$ of $5$ modulo $p$, and store it as a constant.

We want $k$ such that $5k\equiv 1\pmod{p}$. So just look at $p+1$, $2p+1$, $3p+1$, $4p+1$. One of them will be a multiple of $5$, if $p\gt 5$. Divide by $5$ to get $k$.

Now given any $a$, calculate $ka\bmod{p}$.

Remark: The procedure took advantage of the smallness of the constant $5$. The way we produced $k$ would be quite unsuitable for large $b$. Then we would want to use the Extended Euclidean Algorithm to find $k$.

1

Hint $\ $ Below are closed forms for $\rm\:1/5\pmod m\,$ computed by Inverse Reciprocity, e.g. as here.

$\rm(1)\ \ \ \ mod\,\ 5k\pm1\!:\ \ 5 k\,\equiv\, \mp1\:\Rightarrow\: 1/5\, \equiv\, \mp k, $

$\rm\qquad\ \,e.g.\ \ mod\ 501 = 5\cdot\color{#C00}{100}\color{#0A0}{+1}\!:\,\ 1/5\, \equiv\, \color{#0A0}{-}\color{#C00}{100}$

$\rm\qquad\ \,e.g.\ \ mod\ 499 = 5\cdot\color{#C00}{100}\color{#0A0}{-1}\!:\,\ 1/5\, \equiv\, \color{#0A0}{+}\color{#C00}{100}$

$\rm(2)\ \ \ \ mod\,\ 5k\pm 2\!:\ \ 5(1\!\pm\!2k)\, =\, 2(2\pm5k)+1\, \equiv\, 1\:\Rightarrow\:1/5\, \equiv\, 1\pm2k$

$\rm\qquad\ \,e.g.\ \ mod\ 502=5\cdot\color{#C00}{100}\color{#0A0}{+2}\!:\,\ 1/5\,\equiv\, 1 \color{#0A0}{+ 2}\cdot\color{#C00}{100}\,\equiv\ 201 $

$\rm\qquad\ \,e.g.\ \ mod\ 498=5\cdot\color{#C00}{100}\color{#0A0}{-2}\!:\,\ 1/5\,\equiv\, 1 \color{#0A0}{- 2}\cdot\color{#C00}{100}\,\equiv -199 $

0

I only know of the Euclidean algorithm. I think it works well.