Unit 2 Flashcards
1
Q
the branch of mathematics concerned with the study of integers.
A
number theory,
2
Q
In blank, the input and output values must always be integers.
A
integer division
3
Q
Let x and y be two integers. Then x blank y (denoted x|y) if there is an integer k such that y = kx. “x does not divide y” is denoted by x y. If x divides y, then y is said to be a multiple of x, and x is a factor or divisor of y.
A
divides
4
Q
In most situations, the number in front of the variable, or the blank, can be any real number
A
coefficient
5
Q
A lank of two numbers is the sum of multiples of those numbers.
A
linear combination
6
Q
A statement about blank uses variables to denote the integer coefficients. For example, sx + ty is a linear combination of x and y.
A
a generic linear combination
7
Q
Let x, y, and z be integers. If x|y and x|z, then blank for any integers s and t.
A
x|(sy + tz)
8
Q
Blank, states that the result of the division (the quotient) and the remainder are unique.
A
Division Algorithm
9
Q
Let n be an integer and let d be a positive integer. Then, there are unique integers q and r, with 0 ≤ r ≤ d - 1, such that blank
A
n = qd + r.
10
Q
In the lank , the number q is called the quotient and the number r is called the remainder. The operations div and mod produce the quotient and the remainder as a function of n and d.
q = n div d
r = n mod d
A
Division Algorithm
11
Q
The blank is the result of the division of two integers. The quotient and the remainder are unique.
A
Division Algorithm
12
Q
The Division Algorithm works with blank; if any of the inputs is negative, the quotient will be negative per the rules of division.
A
positive integers only
13
Q
The operations div and mod produce the quotient (q) and the remainder (r). The blank is d.
A
divisor
14
Q
The blank is computed by n div d; q = n div d
A
quotient
15
Q
The blank is computed by n mod d; r = n mod d
A
remainder
16
Q
To compute the remainder using blank, divide the quotient by n until the remainder is less than n. The remainder is the result. For example, to calculate 38 mod 5, calculate 38 ÷ 5. Five divides into 38 seven times with a remainder of 3. So the quotient is 7 and the remainder is 3. Therefore 38 mod 5 = 3.
A
modular division
17
Q
The operation defined by adding two numbers and applying modulo n to the result is called blank.
A
addition modulo n
18
Q
The operation defined by multiplying two numbers and applying modulo n to the result is called blank.
A
multiplication modulo n
19
Q
To compute blank follow these steps: add the integers, then apply the modulo. For example, 3 mod 7 + 38 mod 7 = 41 mod 7 = 6.
A
modular addition
20
Q
To compute blank follow these steps: multiply the integers, then apply the modulo. For example, (10 mod 3) (7 mod 3) = 70 mod 3 = 1.
A
modular multiplication
21
Q
The blank is completed as the last step in the process.
A
modular operation
22
Q
Let n be an integer greater than 1. Let x and y be any two integers. Then x is blank if x mod n = y mod n. The fact that x is congruent to y modulo n is denoted
x ≡ y (mod n).
A
congruent to y modulo n
23
Q
Let n be an integer greater than 1. Let x and y be any two integers. Then x ≡ y (mod n) if and only if blank.
A
n|(x - y)
24
Q
Two integers x and y are blank if and only if x mod n = y mod n.
A
equivalent
25
blank of two integers is denoted by x ≡ y (mod n) and is only true if n|(x − y). In otherwords, 17 and 92 are equivalent mod 5. 17 mod 5 = 2 and 92 mod 5 = 2. The difference between 92 and 17 is a multiple of 5, 75. In formal notation, 17 ≡ 92 (mod 5) is true if and only if 5|(92 − 17) or 5|75-which it does.
Congruence
26
blank can be useful in the computation of very large values. Therefore, the modular operation does not necessarily have to be performed after the multiplication or addition processes, but can be utilized throughout a computation without changing the final result.
Intermediate results
27
A number p is blank if it is an integer greater than 1 and its only factors are 1 and p.
prime
28
A positive integer is blank if it has a factor other than 1 or itself.
composite
29
every integer greater than 1 is either blank or blank
prime or composite
30
blank are the basic building blocks of all integers.
Prime numbers
31
Every positive integer greater than one can be expressed as a product of primes called its blank.
prime factorization
32
Moreover, the prime factorization is unique up to ordering of the blank
factors.
33
The fact that every integer greater than one has a unique prime factorization is central to number theory and is called blank.
The Fundamental Theorem of Arithmetic
34
Every positive integer other than blank can be expressed uniquely as a product of prime numbers where the prime factors are written in non-decreasing order.
1
35
A blank is a sequence in which each number is equal to or greater than the one that came before.
non-decreasing sequence
36
The blankl of a prime factor p in a prime factorization is the number of times p appears in the product of primes.
multiplicity
37
In order to express the prime factorization more compactly, we use blank in which each distinct prime factor occurs only once and is raised to an exponent that is equal to its multiplicity.
exponential notation
38
The blank states that every positive integer greater than 1 can be expressed as a unique product of prime numbers.
fundamental theorem of arithmetic
39
A blank (e.g., 1, 1, 2, 3, 17) can have repeated values as long as the values to the right are larger or equal to the values on the left.
non-decreasing sequence
40
blank is just a term referring to the number of times a value repeats itself in multiplication. For example, the prime factorization of 40 is 2 x 2 x 2 x 5. The factor 2 has a multiplicity of 3.
Multiplicity
41
The blank of non-zero integers x and y is the largest positive integer that is a factor of both x and y.
greatest common divisor (GCD)
42
The blank of non-zero integers x and y is the smallest positive integer that is an integer multiple of both x and y.
least common multiple (LCM)
43
Two numbers are said to be blank if their greatest common divisor is 1.
relatively prime
44
GCD uses the blank between the prime factorization of two number
min
45
LCM uses the blank between the prime factorization of two numbers
max
46
GCD(24,50)
2min(3,1) * 3min(1,0)*5min(0,2) = 2^1*3^0*5^0 = 2
47
LCM(24,50)
2max(3,1) * 3max(1,0) * 5max(0,2) = 2^3 * 3^1 * 5^2 = 600
48
The blank is the largest number that divides the given numbers.
GCD
49
To determine the GCD:
Find the prime factors of each number, using prime factorization and exponents.
Write both values as the product of the same prime values.
Identify those prime factors that both numbers have in common.
To make a common set you may need to use an integer raised to the power 0, since it is equal to 1 and will not change the product of the prime factors.
Take the smallest exponent of each factor and multiply them.
50
The blank is the lowest common multiple of given numbers.
LCM
51
To determine the LCM
Find the prime factors of each number, using prime factorization and exponents.
Write both values as the product of the same prime values.
Identify those prime factors that both numbers have in common.
To make a common set you may need to use an integer raised to the power 0, since it is equal to 1 and will not change the product of the prime factors.
Take the maximum exponent of each factor and multiply them.
52
Input: Integer N greater than 1.
Output: "Prime" if N is prime and "Composite" if N is composite.
Primality Testing
53
Input: Integer N greater than 1.
Output: "Prime" if N is prime. If N is composite, return two integers greater than 1 whose product is N.
Factoring
54
A blank solves a problem by exhaustively searching all possible solutions without using an understanding of the mathematical structure in the problem to eliminate steps.
brute force algorithm
55
If N is a composite number, then N has a factor greater than 1 and at most
square root of N
Small factors
56
There are an infinite number of blank.
primes
57
The blank says how dense primes numbers are among the integers.
Prime Number Theorem
58
The blank uses an exhaustive method of dividing the number by every number less than the number. Using this algorithm, start with 2|N. If 2|N yields a result, the N is composite. If not, then continue to test 3|N etc. Continue this process until either N is reached (N is prime) or an integer less than N is found (N is composite).
brute force algorithm
59
To shorten the number of possible iterations of divisors, apply the blank. According to this theorem, if a number is composite, then the largest possible factor will be at most the square root of the number. For example, if you were searching for factors of 29, using the brute force method you would divide by 2, 3, 4, 5, 6, 7, 8, 9, . . . , 27, 28, before determining that 29 was prime. However, with the small factors theorem, using the square root of 29, ≈ 5.4, we would only need to divide by 2, 3, 4, and 5 before deciding 29 was prime.
small factors theorem
60
The blank addresses the issue of how likely finding a prime number value is out of a range of numbers and provides a formula for determining the density of prime numbers within a range of integers. For example, if you needed to know how likely it is that you will randomly find a prime number between 2 and 1,000,000, the prime number theorem states the likelihood will be 1/ln(1,000,000) ≈ 0.072 or about a 7.2% chance of finding a prime number between 2 and one million. (As a reminder, ln is the abbreviation for natural logarithm.)
prime number theorem
61
Let x and y be two positive integers. Then GCD(x, y) = blank
GCD(y mod x, x).
62
The greatest common divisor theorem [GCD(x, y) = GCD(y mod x, x)], sometimes referred to as blank, shows that a number k is a factor of both x and y if and only if it is a factor of both x and (y mod x). This is an iterative process, where the variables are reassigned the smaller value results from a previous iteration until y mod x = 0. The point of this process is to divide the divisor by the remainder over and over again (iteratively) until the remainder is 0-the final divisor is the GCD.
Euclid's algorithm
63
Using blank makes the second value y much smaller, and since the result would be the same with either the original or the smaller modular value, the computation is less cumbersome.
modular arithmetic
64
Find GCD (32, 48). By inspection you may notice the largest divisor of 32 and 48 is 16. We can verify this using Euclid's algorithm.
First iteration: x = 32 and y = 48, find y mod x. 48 mod 32 ≡ 16
answer not 0, so continue.
Second iteration: now x = 16 and y = 32. Again, find y mod x. 32 mod 16 ≡ 0, so stop the process.
16
65
Let x and y be integers, then there are integers s and t such that
GCD(x, y) = blank
sx + ty
66
The blank is not really an "extended" process, it is an add-on process leading to some important ideas used in cryptography.
extended Euclidean algorithm
67
The extended Euclidean algorithm states the GCD of x and y can be expressed as a linear combination of x and y [GCD(x, y) = blank
sx + ty].
68
To apply the extended Euclidean algorithm, find the blank. Then show that there is an equation that exists where you can write x times some number s plus y times some number t that is equal to the GCD. For example, if x = 874 and y =2415, GCD (874, 2415) = s874 + t2415. To apply the extended Euclidean algorithm find s and t integers. To find the integers, solve the equation r = y - (y div x) x. Recall (y div x) is just the quotient d, so the equation can be written r= y - dx. In this example GCD is 23, s = 47 and t = -17. The equation for the GCD (874, 2415) is 23 = 47(874) - 17(2415).
GCD (x, y)
69
A blank of an integer x, is an integer s ∈ {1, 2, …, n-1} such that sx mod n = 1.
Alternatively, we could say that s is the multiplicative inverse of x in Zn.
multiplicative inverse mod n (or just inverse mod n)
70
The blank can be used to find the multiplicative inverse of x mod n when it exists.
If GCD(x, n) ≠ 1, then x does not have a multiplicative inverse mod n.
If x and n are relatively prime, then the Extended Euclidean Algorithm finds integers s and t such that 1 = sx + tn.
sx - 1 = -tn. Therefore, (sx mod n) = (1 mod n) = 1. It was shown earlier that if A - B is a multiple of n then (A mod n) = (B mod n).
(s mod n) is the unique multiplicative inverse of x in {0, 1, …, n - 1}.
Extended Euclidean Algorithm
71
In ordinary arithmetic the definition of a multiplicative inverse is the product of a number and its multiplicative inverse is always blank.
1
72
In blank, an integer x has a multiplicative inverse mod n, s. If the product of integer x and s equal 1 mod n, then x and s are multiplicative inverses.
modular arithmetic
73
An interesting characteristic of multiplicative inverses mod n is that they must be blank. It can be shown that not every integer has an inverse mod n. For example, 10 does not have an inverse using modulo 6, but it does using modulo 7. This gives a small hint into what lies in the upcoming lessons where we begin to put all this modular arithmetic together with the quest for large prime numbers.
relatively prime
74
Our number system represents integers in blank notation in which each number is represented as sequences of digits. The set of digits has ten symbols: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The place of a digit in the sequence represents its value. The rightmost digit is multiplied by 1 = 100, the digit that is second to the right is multiplied by 10 = 101. The digit that is kth from the right is multiplied by 10(k-1). For example, the number 256 represents 2·10^2 + 5·10^1 + 6·10^0.
decimal
75
A digit in binary notation is called a blank.
bit
76
In blank, each place value is a power of 2. For example, the binary number 1011 corresponds to the decimal number 1·23 + 0·22 + 1·21 + 1·20 = 11. In fact, any integer greater than 1 can be used as the base of a number representation system.
binary notation
77
Numbers represented in base b require b distinct symbols and each place value is a blank. The fact that every integer greater than 1 gives rise to a unique system for number representation
power of b
78
The representation of n base b is called the blank and is denoted by (akak-1...a1a0)b.
base b expansion of n
79
The binary number system has only two digits, blank and blank, and the digits are referred to as "bits."
0 and 1
80
Each place value is a power of blank.
2
81
Numbers in base b require b distinct symbols and each place value is a power of b. The blank says that any number, n base b, can be uniquely written in a series or decimal expansion of each digit multiplied by its place value.
number representation theorem
82
to convert a binary number (e.g., 1001
base2)to a decimal number, follow these steps:
Work from left to right to determine the place value. The first digit has a base 2 place value of 2^3
, next is 2^2
, 2^1
, then 2^0
.
Multiply the digit by its base 2 place value. (1 x 2^3
+ 0 x 2^2
+ 0 x 2^1
+ 1 x 2^0
= 1 x 8 + 0 x 4 + 0 x 2 + 1 x 1 = 9base10
)
83
In blank, numbers are represented base 16.
hexadecimal notation (or hex for short),
84
The 16 digits in hex are the usual 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 along with blank.The table below shows each hexadecimal digit, its decimal encoding, and its binary encoding. Leading zeroes are added to the binary encodings so that all the encodings have exactly 4 bits.
A, B, C, D, E, F.
85
A blank which consists of 8 bits, can be represented by a 2-digit hexadecimal number.
byte
86
The blank system has sixteen digits 0-9 and A-F. Each digit in a hex number is a power of 16.
hexadecimal (hex) number
87
A byte is blank (binary digits). Each byte can be represented by a 2-digit hexadecimal number.
8 bits
88
To convert the hex number, 3AFbase16
to a decimal value multiply each digit by its place value
3 x 16^2
+ A x 16^1
+ F x 16^0
= 3 x 16^2
+ 10 x 16^1
+ 15 x 16^0
= 3 x 256 + 10 x 16 + 15 x 1 = 943
89
To convert a decimal value to a blank requires an iterative process of the mod and div functions. The smallest valued digits (right-most digit in the iteration) is found using n mod b. The next digits are determined using n div b in the iteration
number n, base b
90
convert the decimal value 482 to a base 7 number.
482base10 -> base7
(482 div 7 )(482 mod7)
(68)(6)
(68 div7)(68 mod 7)(6)
(9)(5)(6)
(9 div 7)(9 mod 7)(5)(6)
(1)(2)(5)(6)
1256 base 7 is equal to 482 base10
91
The formula blank
determines the length of an integer value.
log base b (n+1)
92
the number of digits required to display 4,324,783 in base 16 would be:
log base 16 (4324783 + 1) = 6 digits
93
The number of loops in the algorithm is the blank in the binary representation of the exponent.
number of bits
94
The following are the steps in fast integer exponentiation
Create a binary expansion of the exponent.
Use this expansion as the new exponent of the base.
Using the addition of exponents property (
) write the expression as a multiplication of the bases with each term of the expansion as an exponent.
Because each exponent is now a power of 2, calculate each successive exponentiation using a "squaring function."
95
The binary representation of 18 is 10010. What expression is equivalent to b18?
18 = 1·24 + 0·23 + 0·22 + 1·21 + 0·20 = 24 + 21
b^2^4 + + b^2^1
96
Blank applies intermediate modular arithmetic steps that keep the values within the iterative process smaller.
Iterative fast exponentiation (modular exponentiation)
97
The blank in the iterative algorithm is the number of bits in the binary representation of the exponent.
number of loops
98
Yhe encryption is a function whose domain (input value) is the characters possible in the message (m), and range (output value) is the set of all ciphertexts, c. Because this function is one-to- one, then the inverse function or blank function's domain is c and range is m; therefore, mapping the ciphertext back to the correct original plaintext message.
decryption
99
In a blank, Alice and Bob must meet in advance (or communicate over a reliably secure channel) to decide on the value of a shared secret key.
symmetric key cryptosystem,
100
To accurately map plaintext (unencrypted message) to blank and then reverse the process (decryption) requires a mathematical function that is one-to- one. Each input maps to one and only one output, and each output maps back to one and only one input.
ciphertext (encrypted message)
101
One simple cryptosystem uses blank to encode and decode a plaintext message. Specifically, ciphertext can be expressed as c = (m + k) mod N; where m is the plaintext message, N is an integer, and k is a secret value known only to the sender and receiver. Then the decryption function can be expressed as m = (c - k) mod N. Note that the addition/subtraction inverse operations use the secret value k.
modular arithmetic
102
The systems used in this lesson are blank. In a private key system both Bob and Alice must meet to decide upon the value of the secret key-in our example the value of k-prior to sending encrypted messages.
private key cryptosystems.
103
n a public key cryptosystem, anyone can encrypt the message, but only the blank has the correct decryption key to ultimately read the encrypted message.
receiver
104
In public key cryptography, Bob has an encryption key that he provides blank so that anyone can use it to send him an encrypted message. Bob holds a matching decryption key that he keeps privately to decrypt messages. While anyone can use the public key to encrypt a message, the security of the scheme depends on the fact that it is difficult to decrypt the message without having the matching blank.
publicly
private decryption key.
105
The security of the blank rests on the assumption that it is difficult to factor large numbers. If there were an efficient algorithm to factor numbers, then messages encrypted through RSA could be decrypted by someone who does not hold the matching decryption key.
RSA cryptosystem
106
Preparation of public and private keys in RSA
Bob selects two large prime numbers, p and q.
Bob computes N = pq and φ = (p-1)(q-1). [Note the symbol φ is read Phi.]
Bob finds an integer e such that gcd(e, φ) = 1.
Bob computes the multiplicative inverse of e mod φ: an integer d such that (ed mod φ) = 1.
Public (encryption) key: N and e.
Private (decryption) key: d.
107
RSA encryption
c = m^e mod N
108
To begin RSA encryption, blank are selected. The product of those numbers, N, and another value found through a GCD process, e, are the public encryption key. The private key used to decrypt the message, d, involves the multiplicative inverse process learned in the "Multiplicative Inverse and Euclidean Algorithm" lesson in this unit.
two very large prime values
109
The RSA encryption process for a specific message involves the formula blank
where m is the integer value of the message.
c = m^e mod N
110
