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?
$\begingroup$
$\endgroup$
3
-
$\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$– bobCommented Apr 8, 2014 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$– TusharCommented Apr 8, 2014 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. ♦Commented Apr 10, 2014 at 19:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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$:
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$.
Subtraction: This is similar to addition. The idea is that $-a = m-a$.
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.
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.
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.
Discrete logarithm: Given $g$ and $g^a$, find $a$. This is complicated enough that it probably isn't implemented in hardware.
answered Apr 8, 2014 at 23:02
$\begingroup$
$\endgroup$
1
Yes, you should study the field of "residue numbers". This is a field in computer science and electrical engineering that has all sorts of fascinating circuits that deal with modular arithmetic. You can find circuits that deal with arithmetic that also includes an arbitrary, non-binary (power of two) modulus.
-
$\begingroup$ Interesting! Nice to see someone from a "different" field to share their perspective. I tried to look it up, but the Wikipedia article en.wikipedia.org/wiki/Residue_number_system has warning signs all over. What would be a good resource to learn more? $\endgroup$– Discrete lizard ♦Commented Nov 14, 2021 at 10:46