4.

Number Theory

Number theory has various applications in computer science; we will focus on

cryptography.

At the end of these lectures, we will be capable of understanding the basics of a

cryptography system, namely the “RSA Public Key Cryptosystem”.
RSA – A Public Key Cryptosystem (Rivest, Shamir, Adleman) 76 MIT

Let p, q be large primes (~600 digits) and e be relatively prime to (p – 1)(q – 1) and
n = pq.

Encryption: C = M e mod n e: public encryption key

Decryption: M = C d mod n d: private decryption key

Decryption key d is the inverse of e modulo (p – 1)(q – 1).

To understand this, we first need to learn about prime numbers, greatest common
divisor algorithms, modular arithmetic, and so on.
4.1/4.2/4.3 Divisibility & Prime Numbers

Divisibility:

Let a and b are integers s.t. a ≠ 0.

We say “a divides b”
iff c integer s.t. b = ac (where a is a factor of b).

Notation: a|b
a b a does not divide b.
Theorem: Let a, b, c be integers.

1. If a | b  a | c then a | (b + c).
2. If a | b then a | bc c .
3. If a | b  b | c, then a | c.

Proof: (Use the definition of divisibility)

1. If a | b  a | c then k1,k2 integers s.t. b = k1a  c = k2a

 b + c = (k1 + k2) a  a | (b + c).

3. k1, k2 s.t. b = k1a and c = k2b = k2k1a  a | c.

2. Prove as an exercise.
Prime Number:

An integer p > 1 is called prime iff the only positive factors of p are 1 and p.
If p is not prime, then it is called composite.

Prime numbers were and still are of interest,

for philosophical reasons (ancient times)

for practical reasons (today)
(such as cryptography)

• How to find prime numbers?

• How to devise an efficient algorithm to determine whether a given integer is
prime or not?

These are important problems in number theory.

Hunt for the largest known prime:
p
The integer 2 – 1, where p is prime,
is called Mersenne Prime if it is prime.

e.g.

22 – 1 = 3, 23 – 1 = 7, 25 – 1 = 31 are Mersenne primes

211 – 1 = 2047 = 23 × 89 is not a Mersenne prime

The largest known Mersenne Prime:

(as of 2005) 225,964,951 – 1 7,816,230 digits
(as of 2007) 232,582,657 – 1 9,808,358 digits
(as of 2010) 243,112,609 – 1 12,978,189 digits
(as of 2013) 257,885,161 – 1 17,425,170 digits
(as of 2017) 274,207,281 – 1 22,338,618 digits
(as of 2020) 282,589,933 – 1 24,862,048 digits
(as of 2024) check it out!
• Great Internet Mersenne Prime Search is a distributed computing effort to find Mersenne primes,
which has used various methods to test for primality, such as the Lucas-Lehmer algorithm with
complexity O(p2 log p log log p) (which was deprecated in 2021).
Theorem: Fundamental Theorem of Arithmetic

“Every positive integer, greater than 1, is either prime or can be written uniquely as the
product of primes.”

100 = 2×2×5×5
999 = 3×3×3×37
7=7

Note that this theorem is about existence of prime factorization as well as its uniqueness.

Proof: The uniqueness part of the theorem can easily be proved by using proof by
contradiction. See your textbook.
We will prove the existence part later when we learn strong induction.
Theorem: There are infinitely many primes.

Proof (by contradiction):

Assume otherwise, that the primes are finite: p1, p2, …, pn (with n finite)

Let q = p1 p2 … pn + 1.
By the Fundamental Theorem of Arithmetic, q is either prime or can be written as product
of primes.

We then need to consider two cases (hence proof by cases):

 If q is prime, it is a new prime number, so we have contradiction!

 If q is not prime, we can write it as a product of primes.

- Then, some prime pi divides q.
- But this would mean pi | 1, which is not, however, possible for integers larger than 1.
- Hence, contradiction!

We have a contradiction in both cases. So, our initial assumption was false. There are
indeed infinitely many prime numbers.
Here is how chatGPT proves it in a poetic way: 🙂
Greatest Common Divisor:

Let a, b be integers, not both zero at a time.

The largest integer d s.t. d | a  d | b is called greatest common divisor of a and b.

d = gcd (a, b)

Definition: Integers a1, a2, …, an are pairwise relatively prime,

iff gcd (ai , aj) = 1 i , j 1  i < j  n.
How to find gcd of two numbers?
One possible way: Use prime factorization

a = p1a1 p2a2 … pnan b = p1b1 p2b2 … pnbn where pi’s are prime.

gcd (a, b) = p1min (a1, b1) p2min (a2, b2) … pnmin (an,bn)

e.g.

gcd(120, 500) = ?

120 = 23 ∙ 3 ∙ 5 500 = 22 ∙ 53
gcd (120, 500) = 22 ∙ 30 ∙ 51 = 20

But how to find the greatest common divisor of two integers on a computer, especially
when the integers are very large?
The Euclidean Algorithm

An efficient method for finding the greatest common divisor of two integers

Example: Find gcd (287, 91)

287 = 91∙3 + 14

a | 287  a | 91  a | 14

 gcd (287, 91) = gcd (91, 14)

91 = 14∙6 + 7

 gcd (91, 14) = gcd (14, 7) = 7

Lemma:
A lemma is a
less important
Let a = bq + r, where a, b, q and r are integers. Then gcd(a, b) = gcd(b, r). theorem that
is helpful in
the proof of
The Euclidean algorithm is based on this lemma
(as demonstrated in the previous slide): Euclidean algorithm:

Lemma: Let a = bq + r, where a, b, q and r are integers. Example:

Then gcd(a, b) = gcd(b, r).
155 = 125  1 + 30
Let a, b positive integers s.t. a  b.
125 = 304 + 5
Let r0 = a and r1 = b.
30 = 56
r0 = r1 q 1 + r2 0  r2 < r1  gcd (155, 125) = 5
r1 = r2 q2 + r3, 0  r3 < r2
.
.
rn-2 = rn-1 qn-1 + rn, 0  rn < rn-1
rn-1 = rn qn

where a = r0 > r1 > r2 > ∙∙∙  0

At most in a steps, remainder will be zero.

 gcd (a,b) = gcd (r0, r1) = gcd (r1, r2)  The greatest common divisor is the last non-
zero remainder.
= ∙∙∙ = gcd (rn-1, rn) = gcd (rn, 0) = rn
Pseudocode:

procedure gcd(a, b: positive integers) Example:

x := a
y := b
while y ≠ 0 155 = 125  1 + 30
r := x mod y 125 = 304 + 5
x := y 30 = 56
y := r  gcd (155, 125) = 5
return x {gcd(a, b) is x}

Complexity is O(log b), but we’ll study it later.

Theorem 1:
Hence gcd(a,b) can be written as
Let a, b > 0, then s,t integers such that gcd(a,b) = sa + tb some linear combination of a and b.

We won’t prove this theorem formally, but the example below demonstrates that by
reversing the steps of the Euclidean algorithm, we can always find such integers s and t :

e.g.
gcd (22, 6) = 2
Note that 2 = 4∙6 – 22, where s = 4 and t = -1, but how to find it?

22 = 3∙6 + 4
6 = 1∙4 +2 applying the Euclidean algorithm

4 = 2∙2

2 = 6 – 1∙4
= 6 – (22 – 3∙6) reversing the Euclidean algorithm

= 4∙6 – 22

We will use this theorem to find

Note that this is not a proof but a demonstration! modular inverse and thereby to
solve linear congruences
Definition: Least Common Multiple

Smallest positive integer d s.t. a | d  b | d.

lcm (a,b) = d

Smallest: cZ (a | c  b | c) → d | c

Fact:
Let a = p1a1 p2a2 … pnan, b = p1b1 p2b2 … pnbn where pi’s are prime.

Note that some of the ai or bi may be 0.

gcd (a, b) = p1min (a1, b1) p2min (a2, b2) … pnmin (an, bn)

lcm (a,b) = p1max(a ,b ) . p2max(a ,b ) … pnmax(a ,b )

1 1 2 2 n n

WHY ?? (Prove this at home.)

e.g., 120 = 23 ∙ 3 ∙ 5 500 = 22 ∙ 53
Theorem:
Let a, b integers. gcd (120, 500) = 22 ∙ 30 ∙ 51 = 20
ab = gcd (a,b) ∙ lcm (a,b)
lcm (120, 500) = 23 ∙ 31 ∙ 53 = 3000
PROOF ?? 120 * 500 = 20 * 3000 = 60000
4.4 Solving Linear Congruences

ax  b (mod m) m > 0, a, b integers

x is a variable

How to find x that satisfies this congruence?

We will need the notion of modular inverse to solve

such linear congruences in a systematical manner.
Modular Arithmetic

Definition: Modulo Example:

(a mod m) = r iff a = mq + r 0r<m
169 mod 24 = 1
Definition: Congruence
169  1 (mod 24)
If (a mod m) = (b mod m), then a is congruent to b modulo m.
169  25 (mod 24)
Then we write a  b (mod m). 169  49 (mod 24)
.
Note that .
a  b (mod m) ↔ m | (a – b)  congruence
= equality

Theorem:
a  b (mod m) ↔ a = b + km, for some integer k
Theorem:
If a  b (mod m) and c  d (mod m) then
a + c  b + d (mod m) and ac  bd (mod m).
Definition: Modular inverse

ā : inverse of a in modulo m
s.t. aā  1 (mod m)

Theorem:

If a and m are relatively prime, and m > 1, then ā exists.

Furthermore, it is unique (in modulo m).

Proof: (Existence) s,t integers such that gcd(a,b) = sa + tb.

gcd (a, m) = 1
s,t sa + tm = 1 (by Thm 1)
 sa + tm  1 (mod m)
since tm  0 (mod m)
sa  1 (mod m)
 s=ā
Hence, the inverse exists, and we know how to find it.

Remark: Inverse does not exist if gcd(a, m) ≠ 1.

e.g. Find the inverse of 3 modulo 7.

Solution:

Since gcd (3, 7) = 1, inverse exists.

7 = 2∙3 + 1  –2∙3 + 1∙7 = 1 (by reversing Euclidean algorithm)
 –2 is an inverse of 3 mod 7.

Also are 5, –9, 12, so on.

Solution for linear congruence:

ax  b (mod m)
 āax  āb (mod m) multiply both sides by the inverse
 x  āb (mod m)

e.g.
3x  4 (mod 7)

 x  –2∙4 (mod 7)
 –8  6 (mod 7)
e.g. Solve 75x  5 (mod 13)

Solution:
Since gcd (75, 13) = 1, inverse exists.
75 = 13∙5 + 10  13 = 10∙1 + 3  10 = 3∙3 + 1 (by Euclidean algorithm)

Reversing the steps of the Euclidean algorithm: (so that express 1 in terms of 75 and 13)
1 = 10  3∙3 = 10  3∙(13  10∙1) = (75  13∙5)  3∙(13  75 + 13∙5)
= 4∙75  23∙13
 Inverse of 75 modulo 13 is 4.

75x  5 (mod 13)

4∙75 x  4∙5 (mod 13)
x  20  7 (mod 13)

 x = 7 is a solution, and so are 20, 33, 46…

Remark: If an inverse exists, the linear congruence has a unique solution in modulo m.
However, if an inverse does not exist, there may still be a solution! (e.g., 2x  4 mod 6)
Remark: The inverse of an integer in modulo m, if exists, can always be found by
reversing the Euclidean algorithm.

In fact there is an efficient algorithm to do this, which is called extended Euclidean

algorithm (see Exercise 30, Chapter 4.3).
Algorithms on Binary Integers
n: number of bits in the binary representation of an integer

Addition: Takes O(n) steps. Why?

Multiplication: Takes O(n2) steps. Why?

Division: Takes O(n2) steps with optimized algorithms.

Overall: Addition is easy, multiplication is hard, division is harder.

(Modular) Exponentiation: ba (mod m)

Bad way of doing it: Compute b mod m, b2 mod m, b3 mod m, …, ba mod m

Good way of doing it: Compute b mod m, b2 mod m, b4 mod m, b8 mod m, …, ba mod m

“Square-and-multiply” algorithm takes O(n3) steps. Lots of research in the area.

Overall: (Modular) Exponentiation is the hardest. Know these when creating algorithms!!!
The Chinese Remainder Problem

The original problem was

How many soldiers are there in Han Xin's army? – If you let them parade in rows of 3 soldiers,
two soldiers will be left. If you let them parade in rows of 5, 3 will be left, and in rows of 7, 2 will
be left.
The Chinese Remainder Problem

The original problem was

How many soldiers are there in Han Xin's army? – If you let them parade in rows of 3 soldiers,
two soldiers will be left. If you let them parade in rows of 5, 3 will be left, and in rows of 7, 2 will
be left.

x  2 (mod 3)
x  3 (mod 5)
x  2 (mod 7)

What is x then?
The Chinese Remainder Theorem
Let m1, m2, …, mn be pairwise relatively prime positive integers. The system
x  a1 (mod m1)
x  a2 (mod m2)
.
.
x  an (mod mn)
has a unique solution in modulo m = m1 ∙ m2 ∙… mn .
(In other words, there is only one integer between 0 and m1 that satisfies all these n congruences at once.)

e.g.
Since 3, 5 and 7 are pairwise relatively prime in the previous example, by Chinese
Remainder Thm., there is only one solution for x between 0 ≤ x < 105.

OK, but what is this x? x  2 (mod 3)

x  3 (mod 5)
x  2 (mod 7)
The Chinese Remainder Theorem
Let m1, m2, …, mn be pairwise relatively prime positive integers. The system
x  a1 (mod m1)
x  a2 (mod m2)
.
.
x  an (mod mn)
has a unique solution in modulo m = m1 ∙ m2 ∙… mn.

Solution:
Let Mk = m / mk for k = 1, 2, …, n.
Hence gcd (mk, Mk) = 1
and so yk inverse of Mk s.t. Mk yk  1 (mod mk)

A solution can then be given as:

x = a1 M1 y1 + a2 M2 y2 + … + ak Mk yk + … + an Mn yn Why?
because Mi  0 (mod mk) whenever i  k and Mk yk  1 (mod mk), which leads to
x  ak + 0 +… + 0  ak (mod mk).

Remark: Uniqueness can be proved using proof by contradiction.

See Exercise 30 in Chapter 4.4 (also a homework question).
Example:
x  2 (mod 3)
x  3 (mod 5)
x  2 (mod 14) x=?

m = 3∙5∙14 = 210

Note that 3, 5 and 14 are pairwise relatively prime, so we can apply Chinese Rem. Thm:

M1 = 5∙14 = 70, M2 = 3∙14 = 42, M3 = 3∙5

Then find the inverses of M1, M2 and M3:

M1 = 70  1 (mod 3) y1 = 1 Recall that y1 is inverse of M1 in mod 3

M2 = 42  2 (mod 5) y2 = 3
M3 = 15  1 (mod 14) y3 = 1

x = a1M1 y1 + a2M2 y2 + a3M3 y3 = 2∙70∙1 + 3∙42∙3 + 2∙15∙1 = 548  128 (mod 210).

Note that 128 is the only solution in mod 210, which means there is no other
number between 0 and 209, which satisfies the above congruences.
Computer Arithmetic with Large Numbers:
e.g. Suppose our computer can perform arithmetic operations with integers < 100 much faster
than with larger integers. (In reality, they work with numbers up to 264.)

Let us pick a group of pairwise relatively prime numbers: 99, 98, 97, 95.

By Chinese Remainder Thm, every n < m = 99 ∙98 ∙97 ∙95 = 89403930 can be represented
uniquely by remainders when divided by these four moduli.

WHY CAN WE ADD PER MODULI ??

BECAUSE (a+b) mod m = ((a mod m) + (b mod m)) mod m

All we need to do to find the sum is to solve the following system of congruences:

x  65 mod 99
x  2 mod 98
x  51 mod 97
x  10 mod 95
Pseudoprimes

Recall the question:

Is there an efficient way to determine whether an integer is prime or not?

Ancient Chinese believed that

2n-1  1 (mod n) ↔ n is prime

Reasons:
i) They observed this holds whenever n is prime (←)
ii) They couldn’t find a composite number for which the congruence holds (→)

However, they were wrong: e.g., 2340  1 (mod 341) and 341=11∙31

Hence, 341 is called a pseudoprime!

But how to compute 2340 (mod 341) in the first place? 2340 is too large!
How to compute 2340 (mod 341)?

One way of doing it: Compute successively 2 mod 341, 22 mod 341, 23 mod 341, …,
2340 mod 341

Note that all computations above are in modulo 341, hence numbers never exceed 340
during computation:

2 mod 341 = 2, 22 mod 341 = 4, 23 mod 341 = 8, 24 mod 341 = 16,

25 mod 341 = 32, …, 28 mod 341 = 256,
29  2∙256  512 171 (mod 341)  29 mod 341 = 171
210  2∙171  342  1 (mod 341)  210 mod 341 = 1, … and so on

See also Fast Modular Exponentiation algorithm (Algorithm 5, Chapter 4.2) for a more
efficient version.
Yet an even better way to compute ab mod m is to write the prime factorization of m and
then use Chinese Remainder Theorem and Fermat’s Little Theorem (if possible):

Fermat’s Little Theorem:

If p is prime and a is an integer not divisible by p, then Ancient Chinese believed

ap-1  1 (mod p) n is prime ↔ 2n-1  1 (mod n)
Note that 2 is not divisible by n>2

Remark: For proof, see Exercise 13 in Chapter 4.4 of your textbook.

To compute 2340 (mod 341),
If p is prime and a is an integer not
341 = 11∙31 (prime factorization) divisible by p, then ap-1  1 (mod p)

(i) 210  1 (mod 11) by Fermat’s Little Theorem

2340 = (210)34  1 (mod 11)

(ii) 230  1 (mod 31) by Fermat’s Little Theorem

2330 = (230)11  1 (mod 31)
210 = 25 25  1 (mod 31) since 25 = 32  1 (mod 31)
Hence 2340 = 2330 210  1 (mod 31)

Then, by Chinese Remainder Thm, 2340  1 (mod 11)

(i)  (ii)  2340  1 (mod 341) since gcd (11,31) = 1 2340  1 (mod 31)
What is 2340 in mod 341?
To understand this, you can reason in this way:
2340 is congruent to 1 in both mod 11 and mod 31.
By Chinese Rem. Thm, there exists only one integer in modulo 341 (that is, between 0 and 340), which
satisfies both congruences; and this integer is already 1.
Hence, 2340 must be congruent to 1 in mod 341, since otherwise there would be another integer between 0 and
340, that satisfies both congruences!
Recall the Theorem:

Let a, b > 0, then s,t integers such that gcd(a,b) = sa + tb.

This theorem has two important consequences:

1) It can be used to find modular inverse and thereby solve linear

congruences of type ax  b (mod m).
(See previous slides)

2) One can not simply eliminate equal factors from both sides of the
congruence as in usual arithmetic.
e.g., 5 ∙ 2  3 ∙ 2 (mod 4) but 5  3 (mod 4)

(See next slide)

Theorem:

Let m > 0 and a, b, c integers.

If ac  bc (mod m) and gcd(c, m) = 1, then a  b (mod m).

Proof:

ac  bc (mod m)  m | ac – bc = c (a – b) (by definition of modulo)

Since gcd (c, m) = 1, m cannot divide c, thus m | a – b
 a  b (mod m)
gcd (a,b) = 1 and a | bc, then a | c.
See the lemma in Section 4.3.8, page 287

Remark: You can not simply eliminate equal factors from both sides of the congruence as in usual
arithmetic!
e.g., 5 ∙ 2  3 ∙ 2 (mod 4) but 5  3 (mod 4)
4.6 Cryptography

Earliest known cryptology was used by J. Caesar:

h(p) = (p + k) mod 26, where p is an integer code for alphabet letters, and k is the key.

YES  AGU (for k = 2)

24-5-18  0720

A: 0
B: 1
…

Z: 25
h(p) = (p + k) mod 26, where p is an integer code for alphabet letters;
not a very high level of security!

A better alternative: h(p) = (ap + b) mod 26 (as if there are two keys a and b)
Choose a and b s.t. h(p) is one-to-one.

Still not a secure encryption scheme:

Generally broken using frequency analysis: Given an encrypted sentence, guess that the
most commonly used number represents “E” since it is the most common letter used in
English. Then continue with the next common letter…

There exist, of course, much better more recent cryptography methods. Next, we’ll learn
one of them, which is RSA, a “public key” cryptosystem.

First let’s see what “public key” means…

Private key vs Public key

Private key cryptology:

e.g.
Encryption: C = (M + k) (mod 26) M: original message code

Decryption: M = (C  k) (mod 26) C: encrypted message code

k: private key (used for both encryption and decryption)

Everybody knows the encryption method, but nobody, supposedly, can get the original
message without knowing the private key k.
Problem: How to share the secret key between two parties?

Public key cryptology:

Encryption and decryption keys are different!

Everybody knows the encryption method and the public encryption key, but nobody
can get the original message without knowing the private decryption key.
RSA – A Public Key Cryptosystem (Rivest, Shamir, Adleman) 76 MIT

Let p, q be large primes (~600 digits) and e be relatively prime to (p – 1)(q – 1) and
n = pq.

Encryption: C = (M e mod n) e: public encryption key

Decryption: M = (C d mod n) d: private decryption key

Decryption key d is the inverse of e modulo (p – 1)(q – 1).

Inverse exists since gcd(e, ( p – 1)(q – 1)) = 1.

Remark: In practice, it is almost impossible to find d even if one knows e and n = pq

since these are very large numbers. No polynomial time algorithm exists for prime
factorization, which is an NP class problem (the size of the problem being the number
of digits (or bits) needed to represent n).
e.g.
p = 43, q = 59 n = 43∙59 = 2537 e = 13
 gcd (13, 58∙42) = 1 Assume that messages are encoded in
blocks of two letters, where each letter
is represented with the integer that
Let M = 1819 1415 (STOP) represents its order in the alphabet:
M1 M2
A  00
B  01
C  02
C1  181913 (mod 2537) = 2081 …
C2  141513 (mod 2537) = 2182

d = 937 (inverse of 13 modulo 42∙58)

937
M1 = C1 (mod 2537) = 1819
937
M2 = C2 (mod 2537) = 1415
Use Examples of RSA Cryptosystem

Encryption:
1. Suppose Alice wants to send a message M to Bob.
2. Alice creates the ciphertext C by exponentiating s.t. C = M e mod n, where e and n
are Bob's public keys.
3. She sends C to Bob.
4. To decrypt, Bob also exponentiates, but this time with d s.t. M = C d mod n
5. The relationship between e and d ensures that Bob correctly recovers M.
6. Since only Bob knows d, only Bob can decrypt this message. Anyone who knows
Bob’s public keys can send an encrypted message to Bob.
Finally, why RSA works:

RSA – A Public Key Cryptosystem

Let p, q be large primes (~600 digits) and e be relatively prime to (p – 1)(q – 1) and n = pq.

Encryption: C = (M e mod n) e: public encryption key

Decryption: M = (C d mod n) d: private decryption key

Decryption key d is the inverse of e modulo (p – 1)(q – 1).

Why is C d congruent to M in modulo n = pq?

Finally, why RSA works: ?

Why is C d congruent to M in modulo n = pq?

M p – 1  1 (mod p) by Fermat’s little theorem,

M q – 1  1 (mod q) assuming p and q do not divide M (since p, q are very large)

and C d  ( M e )d = M ed = M 1 + k (p – 1) (q – 1) (mod n) since ed  1 mod (p – 1)(q – 1) by design

Hence we can write

Note also that if two integers
Cd  M (M p – 1)k (q – 1)  M∙1 M (mod p) are congruent in mod n = pq,
Cd  M (M q – 1)k (p – 1)  M∙1 M (mod q) then they are congruent also in
mod p and in mod q.

Finally, since gcd(p,q) = 1, by Chinese Remainder Thm we can write

Cd  M (mod pq)
Hash functions: Given a longer value, hash it to a smaller representative.
Goal: Two different values should ideally hash to two different representatives.
IMPOSSIBLE: Hashing longer values to smaller ones means that collisions must occur.

e.g., h(k) = k mod m

Let m = 111
h(64212848) = 64212848 mod 111 = 14
h(37149212) = 37149212 mod 111 = 65
h(107405723) = 107405723 mod 111 = 14 (collision)

Such hash functions are used in hash table data structure. (more in COMP 202 Data Structures)

There are cryptographic hash functions. For those, finding collisions is extremely hard if the
domain is very large.
Use case: Passwords.
Your login password is not stored on your computer. Only the hash of your password is stored.
Each time you try to login, the password you enter is hashed, and the resulting value is compared
with the stored value. Since collisions are hard to find, no one else can login on your behalf. Since
only a hash is stored, if your laptop is stolen, your password is still safe. (more in COMP 443
Modern Cryptography and COMP 434 Computer and Network Security)
Pseudo-random functions and pseudo-random number generators:
Goal: Generate random-looking numbers with a systematic way.

e.g., Linear congruential method:

xn+1 = (a xn + c) mod m
2a<m
0c<m
2  x0 < m
Start with seed x0

e.g., Let m = 9, a = 7, c = 4, x0 = 3
x1 = (7x0 + 4) mod 9 = (7*3 + 4) mod 9 = 25 mod 9 = 7
x2 = (7x1 + 4) mod 9 = (7*7 + 4) mod 9 = 53 mod 9 = 8
…

The sequence is 3, 7, 8, 6, 1, 2, 0, 4, 5, … (repeats) All pseudo-random generators are bound to repeat.

Use case: Everywhere that we need random numbers. For example, in many computer games, to generate
random levels, random enemies, random rewards, etc.

In cryptography, you need cryptographically-secure pseudo-random number generators that are proven to be
indistinguishable from real random numbers under some assumptions.
e.g. java.security.SecureRandom

Remark: If you are working on a secure program, never employ a regular random number generator.
Remark: If you do not need cryptographically-strong randomness, use a regular random number generator since
the cryptographic ones will be slower.