0
$\begingroup$

I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in circuits? Can someone point me to a resource or describe the modular step here?

$\endgroup$
  • $\begingroup$ Please note: I asked this question previously, and was asked to show my research. I've was locked out of that account, and this other question were closed. So I repost question with link showing my research $\endgroup$ – bob Apr 8 '14 at 22:04
  • $\begingroup$ In some sense, adders do modular arithmetic with modulo 2^n, where n is the number of bits it can represent. In general, you should be able to use the remainder from the division circuit to get the modulo for an operation. $\endgroup$ – Tushar Apr 8 '14 at 22:12
  • $\begingroup$ This question does not meet my expectations for the level of research. So you read a textbook chapter that describes how to do addition, multiplication, division, etc., but that didn't describe how to do modular reduction. OK, so where else did you look? Do you know how to design an algorithm for modular reduction? If you can divide and multiply and subtract, you have everything needed to do a modular reduction. This is covered in many textbooks. Questions that ask us to regurgitate material found in textbooks tend not to be a good fit for this site. $\endgroup$ – D.W. Apr 10 '14 at 19:06
1
$\begingroup$

In general, everything that you can describe in pseudocode, you can convert into a circuit. So if you can do modular arithmetic by hand, then a circuit can do it. More to the point, here are some concrete ideas for doing modular arithmetic, where the modulus is $m$:

  1. Addition: You already know how to add two numbers. Assuming both numbers were in $\{0,\ldots,m-1\}$, the answer lies in $\{0,\ldots,2m-2\}$, so it is enough to check whether the results is at least $m$, and if so, subtract $m$.

  2. Subtraction: This is similar to addition. The idea is that $-a = m-a$.

  3. Multiplication: Here the basic idea is to compute the result $ab$, divide by $m$, and keep the remainder. You can (possibly) optimize this by doing modular reductions along the way.

  4. Division: This is more complicated, and is probably better implemented in microcode or software. Suppose we want to compute $a/b$. If $m$ is prime then we can assume that $b \neq 0$. We compute the modular reciprocal $b^{-1}$ of $b$ using the extended Euclidean algorithm, and then multiply $a$ by $b^{-1}$. If $m$ is composite then the situation is slightly more complicated since $b$ doesn't always have an inverse. In that case we first compute the GCD $g = (a,b)$, and $a' = a/g$, $b' = b/g$. There is a quotient $a/b$ only if $(b',m) = 1$, in which case we can proceed as before.

  5. Powering: This is again quite complicated, and better implemented in microcode or software. Here the idea is to use the repeated squaring algorithm, reducing modulo $m$ at every step.

  6. Discrete logarithm: Given $g$ and $g^a$, find $a$. This is complicated enough that it probably isn't implemented in hardware.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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