Key Terms

Question 1

a|b ( a divides b)

Answer 1

there is an integer c such that b = ac

Question 2

a and b are congruent modulo m

Answer 2

m divides a - b

Question 3

prime

Answer 3

an integer greater than 1 with exactly 2 positive integer divisors

Question 4

composite

Answer 4

not prime

Question 5

mersenne prime

Answer 5

a prime of the form 2^p - 1 where p is prime

Question 6

gcd(a,b)

Answer 6

the largest integer that divides both a and b

Question 7

lcm(a,b)

Answer 7

the smallest positive integer that is a multiple of both a and b

Question 8

relatively prime integers a and b

Answer 8

gcd(a,b) = 1

Question 9

a mod b

Answer 9

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

Question 10

linear combination of a and b

Answer 10

sa + tb

Question 11

lcm(a,b) * gcd(a,b)

Answer 11

a*b

Question 12

bezout coefficients of and b

Answer 12

s and t such that sa + tb = gcd(a,b) holds

Question 13

inverse of a modulo m

Answer 13

a’ s.t. aa’ = 1 mod m

Question 14

linear congruence

Answer 14

ax = b mod m

Question 15

pseudoprime to the base b

Answer 15

n s.t. b^(n-1) = 1 mod n

Question 16

carmicheal number

Answer 16

composite integer n s.t. n is a pseudoprime to all integers b with gcd(b,n) = 1

Question 17

primitive root of a prime p:

Answer 17

r s.t. for all k belonging to zp k = r^j mod p

Question 18

encryption

Answer 18

the process of making a secret message

Question 19

decryption

Answer 19

the process of returning a secret message to its original form

Question 20

encryption key

Answer 20

a value that determines which of a family of encryption functions is to be used

Question 21

shift cipher

Answer 21

you know what this is

Question 22

affine cipher

Answer 22

p is encrypted as (ap + b) mod m

Question 23

character cipher

Answer 23

a cipher that encrypts characters one by one

Question 24

block cipher

Answer 24

a cipher that encrypts blocks of text

Question 25

private key encryption

Answer 25

both the encryption and decryption keys must be kept secret

Question 26

public key encryption

Answer 26

encryption where encryption keys are public knowledge, but decryption keys are kept secret

Question 27

RSA

Answer 27

Encryption keys: pq and e s.t. gcd(e,(p-1)(q-1)) = 1

Decryption key: e’

Question 28

key exchange protocol

Answer 28

a protocol used for two parties to generate a shared key

Question 29

digital signature

Answer 29

yenno

Question 30

fully homomorphic cryptosystem

Answer 30

operations performed on encrypted data generate the same data as if the operation was performed on the data before encryption

Question 31

bezouts theorem

Answer 31

gcd(a,b) is a linear combination of a and b

Question 32

sieve of eratosthenes

Answer 32

a procedure for finding all primes smaller than n

Question 33

euclidean algorithm

Answer 33

repeat the division algorithm with divisor as dividend and remainder and divisor until remainder = 0. the last remainder is gcd(a,b)

Question 34

fermats little theorem

Answer 34

a^p = a mod p