Chapter 4 - Number Theory and Cryptography

Question 1

a | b (a divides b)

Answer 1

there is an integer x such that b = ac

Question 2

a and b are congruent modulo m

Answer 2

m divides a - b

Question 3

modular arithmetic

Answer 3

arithmetic done modulo an integer m ≥ 2

Question 4

prime

Answer 4

an integer greater than 1 with exactly two positive integer divisors

Question 5

composite

Answer 5

an integer greater than 1 that is not prime

Question 6

Mersenne prime

Answer 6

a prime in the form 2ᵖ - 1, where p is prime

Question 7

gcd(a, b) (greatest common divisor of A and b)

Answer 7

the largest integer that divides both a and b

Question 8

relatively prime integers

Answer 8

integers a and b such that gcd(a, b) = 1

Question 9

pairwise relatively prime integers

Answer 9

a set of integers with the property that every pair of these integers is relatively prime

Question 10

lcm(a, b) (least common multiple of a and b)

Answer 10

the smallest positive integer that is divisible by both a and b

Question 11

a mod b

Answer 11

the remainder when the integer a is divided by the positive integer b

Question 12

a ≡ b (mod m) (a is congruent to b modulo m)

Answer 12

a - b is divisible by m

Question 13

n = (aₖaₖ₋₁ . . . a₁a₀)ₓ

Answer 13

the base x representation of n

Question 14

binary representation

Answer 14

the base 2 representation of an integer

Question 15

octal representation

Answer 15

the base 8 representation of an integer

Question 16

hexadecimal representation

Answer 16

the base 16 representation of an integer

Question 17

linear combination of A and b with integer coefficients

Answer 17

an expression of the form sa + tb, where a and e are integers

Question 18

Bezout coefficients of a and b

Answer 18

integers a and t such that the Bezout identity sa + tb = gcd(a, b) holds

Question 19

inverse of a modulo m

Answer 19

an integer ā such that āa ≡ 1 (mod m)

Question 20

linear congruence

Answer 20

a congruence of the form ax ≡ b (mod m), where x is an integer variable

Question 21

pseudoprime to the base b

Answer 21

a composite integer b such that bⁿ⁻¹ ≡ 1 (mod n)

Question 22

Carmichael number

Answer 22

a composite integer n such that n is a pseudoprime to the base b for all positive integers b with gcd(b, n) = 1

Question 23

primitive root of a prime p

Answer 23

an integer r in Zₚ such that every integer not divisible by p is congruent modulo p to a power of r

Question 24

discrete logarithm of a to the base r modulo p

Answer 24

the integer e with 0 ≤ e ≤ p - 1 such that rᵉ ≡ a (mod p)