Key Terms Flashcards
a|b ( a divides b)
there is an integer c such that b = ac
a and b are congruent modulo m
m divides a - b
prime
an integer greater than 1 with exactly 2 positive integer divisors
composite
not prime
mersenne prime
a prime of the form 2^p - 1 where p is prime
gcd(a,b)
the largest integer that divides both a and b
lcm(a,b)
the smallest positive integer that is a multiple of both a and b
relatively prime integers a and b
gcd(a,b) = 1
a mod b
the remainder when the integer a is divided by the positive integer b
linear combination of a and b
sa + tb
lcm(a,b) * gcd(a,b)
a*b
bezout coefficients of and b
s and t such that sa + tb = gcd(a,b) holds
inverse of a modulo m
a’ s.t. aa’ = 1 mod m
linear congruence
ax = b mod m
pseudoprime to the base b
n s.t. b^(n-1) = 1 mod n
carmicheal number
composite integer n s.t. n is a pseudoprime to all integers b with gcd(b,n) = 1
primitive root of a prime p:
r s.t. for all k belonging to zp k = r^j mod p
encryption
the process of making a secret message
decryption
the process of returning a secret message to its original form
encryption key
a value that determines which of a family of encryption functions is to be used
shift cipher
you know what this is
affine cipher
p is encrypted as (ap + b) mod m
character cipher
a cipher that encrypts characters one by one
block cipher
a cipher that encrypts blocks of text
private key encryption
both the encryption and decryption keys must be kept secret
public key encryption
encryption where encryption keys are public knowledge, but decryption keys are kept secret
RSA
Encryption keys: pq and e s.t. gcd(e,(p-1)(q-1)) = 1
Decryption key: e’
key exchange protocol
a protocol used for two parties to generate a shared key
digital signature
yenno
fully homomorphic cryptosystem
operations performed on encrypted data generate the same data as if the operation was performed on the data before encryption
bezouts theorem
gcd(a,b) is a linear combination of a and b
sieve of eratosthenes
a procedure for finding all primes smaller than n
euclidean algorithm
repeat the division algorithm with divisor as dividend and remainder and divisor until remainder = 0. the last remainder is gcd(a,b)
fermats little theorem
a^p = a mod p
