w7 - number theory

Question 1

what does x|y mean

Answer 1

y is divisible by x

Question 2

What is coprime

Answer 2

Two number are coprime (AKA relatively prime) if gcd⁡(a,b)=1

Question 3

Integer linear combinations

If d | m and d | n, then?

Answer 3

If d | m and d | n, then d | m+n and d | m−n

Question 4

Euclidean algorithm

Subtraction and standard version

Finding gcd(a,b)

Answer 4

Finding gcd(a,b)
Swap order of a,b where a<b
* If b|a, then b=gcd(a,b)

Otherwise
* gcd(b, a mod b) (standard ver)
* OR
* gcd(b, a-b) (sub version)

Question 5

Extended version for euclidean algorithm and finding the modular inverse

Answer 5

If we need to find x^-1 in Z*_n

Set up the equation:
n= k0 * x + r0 where r0 is the remainder and k0 is the largest integer multipled by x to get n

n = k₀ × x + r₀
x = k₁ × r₀ + r₁
r₀ = k₂ × r₁ + r₂
r₁ = k₃ × r₂ + r₃
⋮
rₙ₋₂ = kₙ × rₙ₋₁ + 1

Then reverse the process to find r=..... and sub in the equations above

eventually, you should get
1=m*n + a*x where m and a are integers.

The solution is then a and make sure it is in Z*_n. If not, reduce it by mod n until it is

Question 6

Fermat’s Little Theorem for modular exponentiation

what is the formula?

Answer 6

x^(y mod φ(n)) ≡ x^y (mod n)

Question 7

What does [a] mean and what are the formulas you can use for [a]

Answer 7

If a is an integer, then [a] is the equivalence class containing all integers of the form a + nk where k is any integer.

[a] = {a + nk : k ∈ ℤ}

Doing maths with them
* [a] + [b] = [a + b]
* [a] − [b] = [a− b]
* [a]·[b] = [a·b]

Example:
If n=4 then:

Numbers that leave a remainder of 0 when divided by 4: [0]={0,4,8,12,…}
Numbers that leave a remainder of 1 when divided by 4: [1]={1,5,9,13,…}
Can also write statements for [2] and [3]

Question 7

Euler totient function

for p, p^m and n=pq where p and q are co-prime

Answer 7

p is prime
φ(p)= p− 1
φ(p^m) = [p^(m−1)]*(p− 1) for any m ∈N

n= pq such that p and q are coprime then
φ(n)= φ(p)·φ(q)= (p− 1)·(q− 1)

φ(n) = |Z_n^∗ |

Question 8

What is a Modular inverse?

Answer 8

The multiplicative inverse of a in Z_n is the number a^(−1) such that
a∗a^(−1)≡1 (mod n)

===–

Using EEA:
If we need to find x^-1 in Z*_n

Eventually, there should be;
1=m*n + a*x where m and a are integers.

The solution is then a and make sure it is in Z*_n. If not, reduce it by mod n until it is

Question 9

Primitive roots

Where does primitive root exists and how to find a primitive root?

Answer 9

x is a primitive root of n iff n∈{1, 2, 4, p^k, or 2p^k } where p is an odd prime and k∈N

To find the primitive root of x in mod n:
we need:
{x^1, x^2, . . . , x^φ(n) }= Z_n^∗

In other words:
a primitive root, x, rasied to the power from 1 to n−1, can generate all elements of Z_n^∗

Example:
Let n=7, then φ(7)=6
Z_n^∗={1,2,3,4,5,6}

Suppose we try to find whether 3 is a primitive root mod 7
3^1=3
…
3^6=1 in mod 7

By 3^y where y is a number from 1 to 6, we should eventually get {1,2,3,4,5,6}, which is all the numbers in Z_n^∗

3^1, 3^2, 3^3…3^6 are all elements of Z_n^∗

Therefore 3 is a primitive root of 5

Question 10

Diffie-Hellman key exchange

Answer 10

Public information P and G

Alice private key a
Key generated x=G^a mod P (give this to bob)
exchange of keys
Key received = y
Generate secret key = y^a mod P=(received key)^(own private key) mod P