Number theory, groups and finite fields

Question 1

How can we denote that a divides b?

Answer 1

a|b

ak = b

Question 2

What is trivial division?

Answer 2

Testing for prime numbers by checking for factors up to the square root of the number being tested.

Question 3

Properties of factors

Answer 3

1.
If a|b and a|c

then

a| (b + c)

2.
If p is prime and p divides ab, then p divides a or p divides b

Question 4

What is Euclidean division?

Answer 4

a = bq + r

Question 5

What are some properties of modular arithmetic?

Answer 5

Given a≡b (mod n) and c ≡ d (mod n):

1: a + c ≡ b + d (mod n)
2: ac ≡ bd (mod n)
3: ka ≡ kb (mod n)

Question 6

How do we denote the complete set of residues?

Answer 6

Z_n = {0, 1, 2, …, n - 1}

A set is a complete set of residues mod n, if for every integer a, a ≡r_i (mod n) for exactly one r_1 in the set

Question 7

What does a mod n denote?

Answer 7

The remainder after dividing a by n

Question 8

Define a group

Answer 8

A group is a set G with a binary operation, *

A group satisfies the following conditions:

Closure
Identity
Inverse
Associative

Question 9

What is the Closure property of groups?

Answer 9

a * b is an element of G for all
a, b element in G

(* is the operation, this can be multiplication, addition, etc.)

Question 10

What is the identity property of groups?

Answer 10

There exist an element 1 so that a1 = 1a = a for all a in G

Question 11

What is the inverse property of groups?

Answer 11

For all a element in G, a b exist so that:
a*b = 1, for all a in G

Question 12

What is the associative property of groups?

Answer 12

For all a,b,c in G:

(ab)c = a(bc)

Question 13

What are commutative groups?

Answer 13

Also satisfy the commutative property:

For all a,b in G

ab=ba

Question 14

What does |G| mean?

Answer 14

Number of elements in a group

Question 15

What does g^k mean?

Answer 15

Denotes repeated application of the group operation.

For example g³ = ggg

Question 16

What is the order of an element in a group? |g|

Answer 16

|g|: smallest integer k such that

g^k=1

Question 17

When is a group element a generator?

Answer 17

When |g|=|G|

Question 18

When is a group cyclic?

Answer 18

When it has a generator, meaning when |g|=|G|, for an element g in G

Question 19

Define the inverse modulo n

Answer 19

The inverse of a exist and is the value x if:

ax ≡ 1 (mod n)

x = a-¹

Question 20

When does a have an inverse modulo n?

Answer 20

gcd(a,n) = 1

Question 21

What is Z_p*

Answer 21

Complete set of residues, with 0 removed from a group under multiplication.

Multiplicative group of ints: {1, 2, 3,…, p-1}

Order: p - 1

Cyclic

Has many generators

Question 22

What is a Field?

Answer 22

Set with 2 binary operations (+, *)

It is a commutative group under +, identity element=0

It is a commutative group under *, with 0 removed

Obay the distributive property:
a*(b+c) = ab + ac

Question 23

What does the famous theorem say for finite fields?

Answer 23

Finite fields exist of size p^n for any prime p and positive int n.

No finite field exist of other sized

Question 24

Describe the finite field GF(p)

Answer 24

GF(p) = Z_p

Multiplication and addition are done modulo p

Multiplicative group is exactly Z_p^*

Question 25

Describe the finite field GF(2)

Answer 25

The simplest field

2 elements (0, 1)

Addition: Binary addition modulo 2, XOR

Trivial multiplicative group with the single element 1: Because there is only one non-zero element

Question 26

Describe the finite fields GF(2^n)

Answer 26

Arithmetic in these fields can be considered polynomial arithmetic, where field elements are polynomials with binary coefficients

Can equate any n-bit string with a polynomial:
00101101 -> x^5 + x^3 + x^2 + 1

The field can be represented in different ways by use of a primitive polynomial m(x)

Addition | multiplication -> polynomial add and mul mod m(x)

Polynomial division done using shift registers in HW

Question 27

In GF(2^8) how can we add 2 strings?

Answer 27

Add their coefficients modulo 2 (XOR)

Question 28

In cryptography, what is the field GF(2^8) used for?

Answer 28

Calculation in the AES block cipher

Question 29

How is multiplication done in GF(2^8)

Answer 29

In respect to a generator polynomial

In AES this polynomial is:
m(x) = x^8 + x^4 + x^3 + x + 1

Multiply strings by multiplying them as polynomials, and then take their remainder after dividing by m(x)

Question 30

What is a boolean function?

Answer 30

any function with output in the set {0, 1}

Can be represented by a truth-table