Math behind key pairs — Web3 Hash Lab

Modular Arithmetic Foundations

Modular Arithmetic

The modulus m defines the wrap-around space. Every integer maps to one output from 0 to m-1.
These outputs are called residues.

MOD

mod 3 has exactly 3 possible residues

Residues set

mod 3 { 0, 1, 2 }

Modulus space

Integers space

Congruence check (mod 3)

A

=/=

B

A and B are not congruent modulo 3, because they map to different residues {0} and {2}.

In the modulus space, they are different numbers.

When divided by modulus 3, they have different remainders {0} and {2}.

Modular Operations

Modular Arithmetic Examples

Calculation examples

Click on an example to expand it and see the steps.

Divisibility rules

Decimal decomposition of an integer

Any number in decimal system can be represented as a sum of powers of 10.

General form

N = \overline{a_n a_{n-1}\ldots a_1 a_0}

N = a_0 + 10\cdot \overline{a_n a_{n-1}\ldots a_1}

N = a_0 + a_1\cdot 10 + 10^2\cdot \overline{a_n a_{n-1}\ldots a_2}

N = a_0 + a_1\cdot 10 + a_2\cdot 10^2 + \cdots + a_n\cdot 10^n

N

1234 = \overline{1234}

1234 = 4 + 10\cdot \overline{123}

1234 = 4 + 3\cdot 10 + 10^2\cdot \overline{12}

1234 = 4 + 3\cdot 10 + 2\cdot 10^2 + 10^3\cdot \overline{1}

1234 = 4 + 3\cdot 10 + 2\cdot 10^2 + 1\cdot 10^3

1234 = 4 + 30 + 200 + 1000

Rule for division by: none

Click a value on the line to see its divisibility rule.

Primes

Numbers decomposition

Prime numbers - the building blocks that combine to build all other numbers.

3

·

5

·

11

= 495

Primes lie rather unpredictably on the number line.

Every integer greater than 1 can be broken down as a product of primes. This prime set is unique for each number, like a fingerprint.

6 =

2

·

3

Greatest common divisor

Divisibility

Intuition: "3 divides 12" means 12 = 3 * 4, or easier to think 12 is a multiple of 3.

Divisibility Definition

\text{Let } a,b \in \mathbb{Z}.\ \text{We say } a \mid b \text{ if there exists } c \in \mathbb{Z} \text{ such that } ac = b.

\text{Notation: }

a \mid b \text{ - "a divides b" - a statement}

\frac{a}{b} \text{ - "a divided by b" - a number}

Number a divides b if you can build b using all blocks from a.
For example, 12 divides 60:

60 =

12

2

·

2

·

3

·

5

GCD Definition

\text{Let } a,b \in \mathbb{Z}\ \text{. Then gdc of a and b, denoted } \gcd(a,b) \text{ is the largest integer } g \text{ such that } g \mid a \text{ and } g \mid b.

a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n},

b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_n^{\beta_n},

\gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_n^{\min(\alpha_n,\beta_n)}

A

B

12 =

18 =

2

·

2

·

3

2

·

3

·

3

GCD(12, 18) =

2

·

3

=6

LCM Definition

\text{Let } a,b \in \mathbb{Z}\ \text{. Then the lcm of } a \text{ and } b, \text{ denoted } \operatorname{lcm}(a,b), \text{ is the smallest positive integer } m \text{ such that } a \mid m \text{ and } b \mid m.

a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n},

b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_n^{\beta_n},

\operatorname{lcm}(a,b) = p_1^{\max(\alpha_1,\beta_1)} p_2^{\max(\alpha_2,\beta_2)} \cdots p_n^{\max(\alpha_n,\beta_n)}

LCM includes all blocks from a, and all blocks from b, repeating blocks can be shared between a and b.

A

B

12 =

18 =

2

·

2

·

3

2

·

3

·

3

LCM(12, 18) =

2

·

2

·

3

·

3

=36

Euclidean algorithm

Find gcd(A, B) by playing with piles of pebbles

Having two piles of pebbles, what happens if you remove smaller pile from the larger one, and repeat until piles are equal?
Turns out, the final pile size is the greatest common divisor of the original piles.

A

B

Show hint

Proof for the Euclidean algorithm

\text{Proposition. Let } a,b \in \mathbb{Z}_{>0} \text{ with } a \le b. \text{ Then } \gcd(a,b) = \gcd(a,b-a).

\text{Suppose } g = \gcd(a,b).

g \mid a \text{ and } g \mid b.

\text{So there exist } \alpha,\beta \in \mathbb{Z} \text{ such that } a = \alpha g,\ b = \beta g.

b-a = \beta g - \alpha g = g(\beta-\alpha),

\text{hence } g \mid (b-a).

\text{Therefore } g \text{ is a common divisor of } a \text{ and } b-a, \text{ so } g \le \gcd(a,b-a).

\text{Conversely, suppose } h = \gcd(a,b-a).

h \mid a \text{ and } h \mid (b-a).

\text{So there exist } \alpha,\beta \in \mathbb{Z} \text{ such that } a = \alpha h,\ b-a = \beta h.

\text{Trick: rewrite } b \text{ as } (b-a)+a.

b = (b-a)+a = \beta h + \alpha h = h(\beta+\alpha),

\text{hence } h \mid b.

\text{Therefore } h \text{ is a common divisor of } a \text{ and } b, \text{ so } h \le \gcd(a,b).

\gcd(a,b) \le \gcd(a,b-a) \quad \text{and} \quad \gcd(a,b-a) \le \gcd(a,b).

\text{Both} \le \text{ and } \ge \text{ are true only when the two numbers are equal.}

\text{Hence } \gcd(a,b) = \gcd(a,b-a).

\text{Base case: } \gcd(n,0) = n.

\text{Reason: } n \mid n \text{ and } n \mid 0 \text{ since } 0 = n \cdot 0.

Faster Euclidean algorithm

Subtraction removes one copy of the smaller number at a time. Division removes all full copies at once, reducing the number of steps.

\text{If } b = qa + r \text{ with } 0 \le r < a,\ \text{then } \gcd(a,b) = \gcd(a,r).

Calculate gcd(12, 18):

1. 18 = 1 * 12 + 6, so gcd(12, 18) = gcd(12, 6). Quotient 1 means removing 1 full copy of 12 in one jump.

2. 12 = 2 * 6 + 0, so gcd(12, 6) = gcd(6, 0). Quotient 2 means removing 2 full copies of 6 in one jump.

3. The last non-zero remainder is 6, so gcd(12, 18) = 6.

Extended Euclidean algorithm

Enhancing Euclidean algorithm to solve more problems

Add bookkeeping - track how each remainder is build from the original inputs, that is keep a "recipe chain" for a remainder r in terms of ingredients a and b. This tiny extra piece of information upgrades an algorithm for gcd into a tool for linear Diophantine equations, multiplicative inverses, and the Chinese remainder theorem.

Pattern aⁿ-n (mod n)

Fermat's little theorem

Cancellation in modular arithmetic

Let's start with $ac \equiv bc \pmod{m}$ . It is tempting to cancel the shared factor and jump to $a \equiv b \pmod{m}$ , but is this always valid?

A counterexample is $2\cdot 3 \equiv 2\cdot 6 \pmod{6}$ , where $3 \not\equiv 6 \pmod{6}$ .

In what cases we can be sure that cancellation is valid?

ac \equiv bc \pmod{m} \Rightarrow ac-bc \equiv 0 \pmod{m}

\Rightarrow c(a-b) \equiv 0 \pmod{m}\text{, here either }c \equiv 0 \text{ or } a-b\equiv 0\text{ or a combination of factors from both } a-b \text{ and } c

To conclude $a-b \equiv 0 \pmod{m}$ , we need to be sure that $c$ is not having common factors with $m$ . That is, $\gcd(c,m)=1$ .

\left\{\begin{array}{l}ac \equiv bc \pmod{m}\\ \gcd(c,m)=1\end{array}\right.\;\Longrightarrow\; a \equiv b \pmod{m}

Pattern aⁿ-n (mod n)

The section above demonstrates that for some numbers, such as $m=3,5,7,37$ , the quantity $a^{m-1}-1$ is always divisible by $m$ . For other numbers, such as $m=9$ , the pattern does not hold.

Fermat's little theorem proves that for prime moduli $p$ , the quantity $a^{p-1}-1$ (or, in the same pattern form, $a^p-a$ ) is always divisible by $p$ , provided $p \nmid a$ .

Proof for Fermat's little theorem

\text{If } p \text{ is prime and } p \nmid a,\ \text{then } a^{p-1} \equiv 1 \pmod{p}.

Residues

Possible non-zero residues modulo $p$ are $\{1,2,\dots,p-1\}$ .

$r \pmod{p}$	$a \cdot r \pmod{p}$	$\equiv r_1, r_2, \dots, r_{p-1} \pmod{p}$
$1$	$a$	$\equiv r_1$
$2$	$2a$	$\equiv r_2$
$3$	$3a$	$\equiv r_3$
$\vdots$	$\vdots$	$\vdots$
$p-1$	$(p-1)a$	$\equiv r_{p-1}$

Setup

\text{The non-zero residues modulo } p \text{ are } 1,2,\dots,p-1.

\text{Multiply each of them by } a. \text{ Let } r_k \equiv ka \pmod{p} \text{ for } k=1,2,\dots,p-1.

Distinctness

\text{Suppose two of the new residues are equal: } r_l \equiv r_k \pmod{p} \text{ with } l \ne k.

\text{Then } la \equiv ka \pmod{p}.

\text{Since } p \nmid a,\ \gcd(a,p)=1,\ \text{we can cancel } a \text{ and obtain } l \equiv k \pmod{p}.

\text{But } l,k \in \{1,2,\dots,p-1\},\ \text{so this implies } l=k, \text{ a contradiction.}

\text{Therefore } r_1,r_2,\dots,r_{p-1} \text{ are all distinct.}

Non-zero

\text{None of them is } 0 \pmod{p}.

\text{If } r_k \equiv ka \equiv 0 \pmod{p},\ \text{then } p \mid ka.

\text{This is impossible because } p \nmid a \text{ and } p \nmid k \text{ for } 1 \le k \le p-1.

Rearrangement

\text{Thus } r_1,r_2,\dots,r_{p-1} \text{ are exactly the numbers } 1,2,\dots,p-1 \text{ in some order modulo } p.

Permutation Intuition

Each arrow shows r -> a*r (mod p). Multiplying every residue by a rearranges the circle.

prime p

multiplier a

Every arrow lands on a different non-zero residue. Changing a rewires the same circle into a new permutation.

Effective Multiplier

3 (since 3 mod 7 = 3)

Behavior

Permutes the non-zero residues

Cycles

(1 3 2 6 4 5)

Multiplying by a permutes the non-zero residues modulo p.

Product

\text{Multiply the congruences } ka \equiv r_k \pmod{p} \text{ for } k=1,2,\dots,p-1.

\text{The left side becomes } (1a)(2a)\cdots((p-1)a) = a^{p-1}(1\cdot2\cdots(p-1)).

\text{So } a^{p-1}(1\cdot2\cdots(p-1)) \equiv r_1 r_2 \cdots r_{p-1} \pmod{p}.

\text{Because } r_1,r_2,\dots,r_{p-1} \text{ is the same residue set as } 1,2,\dots,p-1,\ \text{when multiplied together it is the same as } r_1 r_2 \cdots r_{p-1} \equiv 1\cdot2\cdots(p-1) \pmod{p}.

\text{Rewriting } 1\cdot2\cdots(p-1) \text{ as factorial} (p-1)!,\ \text{we get } a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}.

a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}

\gcd((p-1)!,p)=1 \text{ because } p \text{ is prime and none of } 1,2,\dots,p-1 \text{ is divisible by } p \text{, so we can cancel } (p-1)! \text{ from both sides}

\therefore a^{p-1} \equiv 1 \pmod{p}

\text{Multiplying both sides by } a \text{ gives another form: } a^p-a \equiv 0 \pmod{p} \text{ or } a^p \equiv a \pmod{p}

Euler's theorem

Generalizing Fermat's little theorem

Euler extended the idea from the Fermat's little theorem from primes (mod p) to modulus (mod n), using the totient function $\varphi(n)$ .

The theorem says that if $\gcd(a,n)=1$ , then powers of $a$ cycle in a way controlled by Euler's totient function $\varphi(n)$ :

a^{\varphi(n)} \equiv 1 \pmod{n}

Totient Function

Totient function $\varphi(n)$ counts the numbers from $1$ up to $n-1$ that are coprime to $n$ .

n

Prime Factors of n

Totient

Totient Filter

Integers 1 to n-1

φ1

1

2

3

4

φ2

5

6

φ3

7

8

9

10

φ4

11

Euler Product

Each distinct prime divisor removes a fraction of the residue classes, leaving exactly $\varphi(n)$ survivors.

These surviving residues are the ones Euler's theorem multiplies and permutes, just like Fermat permutes the full non-zero set when the modulus is prime.

\varphi(12) = 12

\left(1-\frac{1}{\textcolor{deeppink}{2}}\right)

\left(1-\frac{1}{\textcolor{firebrick}{3}}\right)

= 4

Proof for Euler's theorem

\text{If } \gcd(a,n)=1,\ \text{then } a^{\varphi(n)} \equiv 1 \pmod{n}.

Possible residues

The possible residues set is the reduced residue system modulo $n$ :

\{\alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)}\},\ \text{where } \gcd(\alpha_i,n)=1 \text{ for every } i

$\alpha_i$	$a \cdot \alpha_i$	$\equiv r_i \pmod{n}$
$\alpha_1$	$a\alpha_1$	$\equiv r_1$
$\alpha_2$	$a\alpha_2$	$\equiv r_2$
$\alpha_3$	$a\alpha_3$	$\equiv r_3$
$\vdots$	$\vdots$	$\vdots$
$\alpha_{\varphi(n)}$	$a\alpha_{\varphi(n)}$	$\equiv r_{\varphi(n)}$

Setup

\text{Let } \{\alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)}\} \text{ be the reduced residue system modulo } n.

\text{Each } \alpha_i \text{ satisfies } 1 \le \alpha_i < n \text{ and } \gcd(\alpha_i,n)=1.

\text{Multiply each of them by } a. \text{ Let } r_i \equiv a\alpha_i \pmod{n} \text{ for } i=1,2,\dots,\varphi(n).

Distinctness

\text{Suppose two new residues are equal: } r_i \equiv r_j \pmod{n} \text{ with } i \ne j.

\text{Then } a\alpha_i \equiv a\alpha_j \pmod{n}.

\text{Since } \gcd(a,n)=1,\ \text{we may cancel } a \text{ and obtain } \alpha_i \equiv \alpha_j \pmod{n}.

\text{But } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)} \text{ are distinct residues modulo } n, \text{ so this is impossible.}

\text{Therefore } r_1,r_2,\dots,r_{\varphi(n)} \text{ are all different.}

Still Coprime

\text{Each } r_i \text{ is also coprime to } n.

\gcd(r_i,n)=\gcd(a\alpha_i,n)=1 \text{ because } \gcd(a,n)=1 \text{ and } \gcd(\alpha_i,n)=1.

\text{So every } r_i \text{ is another residue from the same reduced residue system modulo } n.

Rearrangement

\text{There are } \varphi(n) \text{ of these residues, they are all different, and each is coprime to } n.

\text{Hence } r_1,r_2,\dots,r_{\varphi(n)} \text{ are exactly } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)} \text{ in some order modulo } n.

Permutation Intuition

Each arrow shows r -> a*r (mod n), but only on residues coprime to n. Grey nodes are filtered out by Euler's totient.

modulus n

multiplier a

Effective Multiplier

5 (since 5 mod 12 = 5)

Behavior

Permutes the reduced residues

Reduced Set

4 residues, cycles (1 5) (7 11)

Multiplying by a permutes only the residues coprime to n; the grey residues are excluded from Euler's theorem.

Product

\text{Multiply the congruences } a\alpha_i \equiv r_i \pmod{n} \text{ for } i=1,2,\dots,\varphi(n).

\text{The left side becomes } (a\alpha_1)(a\alpha_2)\cdots(a\alpha_{\varphi(n)}) = a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)}.

\text{Thus } a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \equiv r_1r_2\cdots r_{\varphi(n)} \pmod{n}.

\text{Because } r_1,r_2,\dots,r_{\varphi(n)} \text{ is the same residue set as } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)},

r_1r_2\cdots r_{\varphi(n)} \equiv \alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \pmod{n}.

a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \equiv \alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \pmod{n}

\gcd(\alpha_1\alpha_2\cdots\alpha_{\varphi(n)},n)=1 \text{ because every } \alpha_i \text{ is coprime to } n \text{, so we can cancel the product}

\therefore a^{\varphi(n)} \equiv 1 \pmod{n}

\text{When } n=p \text{ is prime, the reduced residue system is } 1,2,\dots,p-1 \text{, so this becomes Fermat's little theorem.}

Asymmetric cryptography

The major problem of symmetric cryptography is key distribution - sending private keys over public channels is unsafe, and meeting in person is obviously not convenient.

Public-key cryptography addresses this using mathematical trapdoor functions: operations that are easy to compute with a public key but infeasible to reverse without a corresponding private key. This allows secure key exchange, encryption, and digital signatures even when the public key is openly shared.

Symmetric cryptography

Asymmetric cryptography is powerful, but it is comparatively expensive. Real systems usually use it first to exchange a secret or authenticate the parties, then move to symmetric encryption for the actual message data.

That second phase is where symmetric cryptography takes over. Once both sides share the same secret key, they can encrypt large amounts of data much faster than with public-key operations.

Cryptographic hash functions

A cryptographic hash function turns any input into a fixed-length fingerprint. The output is deterministic, fast to compute, and changes completely when the input changes, making hashes ideal for integrity checks.

Hashes are one-way. Given only a hash, it should be infeasible to recover the original input or find another input that produces the same digest. Hashes provide tamper evidence, not secrecy.

See how hashes secure blockchains in the main demo: tweak a block and the downstream hashes break. Go to the Blockchain Hashing demo.

Modular Arithmetic Foundations

Convert integer C (mod 3)Break C into full groups of m plus the leftover residue.

Modular Operations

Add A and B in modular space (mod 3)Compare adding first versus reducing each addend first.

Multiply A and B in modular space (mod 3)Compare multiplying first versus reducing each factor first.

Exponentiate A by B in modular space (mod 3)Compare the direct power with reducing the base and using square-and-multiply.

Modular Arithmetic Examples

Example 1: 521637 (mod 17)Reduce early and keep the numbers small.

Example 2: 7128 (mod 33)Reduce and use powers of 2.

Example 3: 22018 (mod 15)Use a short cycle when a small power becomes 1.

Example 4: 22018 (mod 17)Use -1 as an anchor to collapse the exponent.

Example 5: 7n - 1 (mod 6)If the base is 1 modulo m, every power stays 1.

Example 6: 13n + 3n+2 (mod 10)Reduce first, then factor a common power.

Example 7: 7n+2 + 82n+1 (mod 57)Rewrite powers to expose a common factor.

Example 8: (2n - 1)n - 3 (mod 2n - 3)When the modulus has n, rename it and reduce normally.

Divisibility rules

Divisibility by 2, 5, 10

Divisibility by 4, 20, 25, 50

Divisibility by 8, 40

Divisibility by 3, 9

Divisibility by 11

Divisibility by 7, 13

Primes

Greatest common divisor

Euclidean algorithm

Extended Euclidean algorithm

Example 1: Solving a linear Diophantine equationUse Bezout and the extended Euclidean algorithm to solve ax + by = c.

Example 2: Finding a multiplicative inverseTurn ax ≡ 1 (mod b) into a Diophantine equation and read the inverse from the x-coefficient.

Pattern aⁿ-n (mod n)

n³ - n (mod 3)

n⁵ - n (mod 5)

n⁷ - n (mod 7)

n⁹ - n (mod 9)

n³⁷ - n (mod 37)

Fermat's little theorem

Euler's theorem

Asymmetric cryptography

Diffie-Hellman (DH)

RSA

Elliptic Curve (ECC)

DSA

Post-Quantum

Symmetric cryptography

Groups, Rings and Fields

Finite Fields

Feistel Cipher

Substitution-Permutation Network

AES

Modes of operation

Cryptographic hash functions

SHA-1