3

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?

Thomas Russell
  • 10,157
  • 5
  • 37
  • 64
thedarkknight
  • 33
  • 2
  • 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.) –  Sep 04 '12 at 21:38

4 Answers4

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

André Nicolas
  • 499,065
  • 47
  • 537
  • 970
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 $

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • https://math.stackexchange.com/questions/25390/how-to-find-the-inverse-modulo-m – Max Mar 08 '19 at 21:28
  • @Max The point is to give a *closed form* so we don't need to resort to general algorithms. – Bill Dubuque Mar 08 '19 at 21:45
  • Sure. Still, I see no harm in linking to the general algorithm, so that the reason behind this closed form and others like it can be understood. – Max Mar 08 '19 at 22:54
0

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

Tunococ
  • 10,093
  • 26
  • 38
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.

  • 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. –  Sep 04 '12 at 22:30