Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
To compute $b^{-1} \pmod{p}$, use the extended Euclidean algorithm. (edit: Oh, now I see "large" prime. see Andre's answer then.) –  user2468 Sep 4 '12 at 21:38

4 Answers 4

up vote 1 down vote accepted

Hint $\ $ Below are the closed forms for $\rm\:1/5\pmod m$

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

share|improve this answer
    
See also this answer. –  Bill Dubuque Oct 6 '12 at 14:30

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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. –  Hurkyl Sep 4 '12 at 22:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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