Number Theory Flashcards
What are the benefits of number theory?
- Key Exchange & Secure Channels to establish a secure channel against eavesdropping.
- Public-key Encryption to encrypt a message with public key.
- Digital Signatures to sign a message electronically
- Zero-knowledge. Proofs of Knowledge to prove knowledge of a secret without disclosing the secret
What is a ring group? Which properties establish that Zm forms a ring group?
A ring group is a set of numbers which addition and multiplication are well behaved
Properties:
Addition and multiplication is closed, commutative, associative, 0 is an additive identity, 1 is a multiplicative property. Additive inverse of any a in Zm is m-a, the distributive property
What is an abelian group? What properties establish that Zm forms an abelian group?
An abelian group is a groupin which the result of applying thegroup operationto two group elements does not depend on the order in which they are written.
Properties:
Addition is closed, commutative, associative, 0 is an additive identity, Additive inverse of any a in Zm is m-a
17 in Z_{12} is?
5
33(mod 13) is?
7
6 + 13 (mod 7) is?
5
-6 . 15 (mod 7) is?
1
gcd(18,24), gcd(12,32)
6, 4
Whats the formula for Bezouts identity? what is it used for?
For all non-zero x,y in Z, there exists a,b in Z, such that a.x + b.y = gcd(x,y)
used for computing multiplicative inverses
what can we use the euclidean algorithm to compute and whats the formula?
- computing gcd
- Key observation:Compute q =[x/y] w/ remainder r=x mod y
= y.q +r
If d divides both y and r; then it also divides x.
If d divides both × and y, then it also divides r.
gcd(x,y) = gcd(y,r) so basically (y, x mod y) until y is zero
What are the steps to compute extended euclidean algorithm?
- Compute gcd(x,y)
- Store all intermediary states d_i = x_i a_i + y_i b_i
- Backtrack; substitute for the remainders d_i
- Write as linear combination of x and y which is ax + by = gcd(x,y)
Whats the extended euclidean algorithm for gcd(1776, 987)?
3 = (-5)1776 + 9(987)
sagemath: xgcd(1776,987) : (3, -5, 9)
Whats the formula for multiplicative modular inverse?
x.y -= 1 (mod N)
5^(-1) in Z_17?
y = 7
sagemath: xgcd(5 , 17) : (1, 7, -2)
How do we know if x has a multiplicative inverse modulo N?
if gcd(x, N) = 1
How do you compute modular inverses using the extended euclidean algorithm?
ax + bN = 1 = gcd(x, N)
What does it mean for two numbers to be coprime?
Two numbers are coprime if their greatest common divisor (gcd) is 1. In other words, x is invertible in Z N if gcd(x,N)=1
What is a cyclic group? give an example of a cyclic group
A cyclic group is a type of group that can be generated b) repeatedly applying the group operation (g) to a single element, known as a generator. The elements of the group are the powers of g up to g^(p-2), which will generate all the elements of (Zp)* when p is prime.
Which statements are equivalent for a congruence modulo N?
→ a = b + kN for some k
→ a = b (mod N)
→ (b-a) | N
→ N | (a-b)
→ a = b + kN for some k
→ a = b (mod N)
→ N | (a-b)
Which of the following congruences are fulfilled?
→ 13 = 27 (mod 37)
→ 11 = 49 (mod 39)
→ -11 = 28 (mod 39)
→ 13 = 124 (mod 37)
→ -11 = 28 (mod 39)
→ 13 = 124 (mod 37)
What is the greatest common divisor gcd(7302, 9354)?
6
True or false: Two numbers x and y are coprime if and only if the gcd(x, y) = 1.
true
When does a multiplicative inverse of an integer x exist modulo N?
-> When gcd(x, N) = 1.
-> When x and modulus N are coprime.
-> When N is divisible by x.
-> When x > N.
→ When gcd(x, N) = 1.
→ When x and modulus N are coprime
It’s important to realize that coprimality between x and a modulus N is a necessary and sufficient criterion for the multiplicative inverse of x under modulus N to exist.
What is the multiplicative inverse of x=17 modulo 231
68
sagemath xgcd(17, 231) is (1, 68, -5)