Modulo: A Remainder

Definition

Modulo is the remainder of a division.

Notation

$13 \equiv 1 \mod 6$ , means 1 is the remainder of 13 divided by 6. We call 6 "modulus"

Example

Value	Modulo	Result	Formula
13	6	1	$13 \mod 6 = 1$
14	6	2	$14 \mod 6 = 2$
15	6	3	$15 \mod 6 = 3$
16	6	4	$16 \mod 6 = 4$
17	6	5	$17 \mod 6 = 5$
18	6	0	$18 \mod 6 = 0$
19	6	1	$19 \mod 6 = 1$

Why Matters?

Why Modulo Matters in Cryptography

Applying modulo to operations can transform an infinite set of a group into a finite one.

Open Ended

Explain by giving an example how applying modulo to operations can transform an infinite set of a group into a finite one.

By applying modulo to operation, we mean that we perform operation, then modulo it. For example, addition under modulo is (a+b) mod n

In cryptography, we often need to work with finite sets because infinite sets can make computations impractical.

Imagine trying to encrypt a message over and over. If you're working with an infinite set of numbers, the resulting number could get out of control, becoming impossible to manage. Modulo solves this by limiting the results to a fixed range, making computations much easier to handle.

Modulo also boosts security by "hiding" the full result of a calculation, revealing only the remainder. This makes it harder for someone to figure out the original number that produces the result, adding a layer of protection. The difficulty in reversing certain operations, known as a "hardness assumption," is a key factor in keeping encrypted data secure (we’ll dig deeper into this concept later).

Open Ended

Explain by giving an example why having modulo makes it harder to find the original number.

Can compare how to solve $y = 2^x$ vs $y = 2^x\ mod\ n$

Random

Are you ready to take on more challenges?

Select a difficulty level to get started.

Prev Next