The Modular Calculator

loopspace

2017-08-27

# Contents

This is a modular arithmetic calculator, inspired by wanting to make it possible to experiment with the mathematics behind cryptography.

That mathematics is the mathematics of modular arithmetic. We use this in many places in every day life, the most obvious being clock arithmetic where we wrap around the clock: 4 hours on from 11 o'clock is not 15 o'clock but 3 o'clock.

Modular arithmetic is easy enough to do with a small "clock number" (aka the modulus) and with addition, subtraction, and multiplication: simply do the arithmetic as normal and then add or subtract the modulus until you get a positive number less than the modulus. But division and powers can be problematic: division can't be done that way as we can't allow fractions and taking powers can easily lead to an arithmetic overflow where the numbers are just too big to work with.

This calculator avoids those issues by reimplementing the arithmetic algorithms using the modular reduction at every stage. This ensures that the numbers stay nice, though at the expense of speed.

### Instructions

In the first input box, enter an expression to be worked out. At the moment, it only handles a single expression at a time. In the second input box, put the modulus to be used. Valid expressions are things like the following:

 `32` This will compute 32 modulo the modulus. `7 + 8` This will compute the sum of 7 and 8 modulo the modulus. `7 - 8` This will subtract 8 from 7 modulo the modulus. `7 * 8` This will compute the product of 7 and 8 modulo the modulus. `7 / 8` This will try to divide 7 by 8 modulo the modulus. This tries to find a number k such that 8k ≡ 7 modulo the modulus. This might not exist, or there might be more than one answer (in which case it gives just one answer). `7 ^ 8` This will raise 7 to the 8th power modulo the modulus.

### Workthroughs

• An introduction to the theory of modular arithmetic, ending with an example of using it to securely share a secret.