Unit 2

Question 1

the branch of mathematics concerned with the study of integers.

Answer 1

number theory,

Question 2

In blank, the input and output values must always be integers.

Answer 2

integer division

Question 3

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.

Answer 3

divides

Question 4

In most situations, the number in front of the variable, or the blank, can be any real number

Answer 4

coefficient

Question 5

A lank of two numbers is the sum of multiples of those numbers.

Answer 5

linear combination

Question 6

A statement about blank uses variables to denote the integer coefficients. For example, sx + ty is a linear combination of x and y.

Answer 6

a generic linear combination

Question 7

Let x, y, and z be integers. If x|y and x|z, then blank for any integers s and t.

Answer 7

x|(sy + tz)

Question 8

Blank, states that the result of the division (the quotient) and the remainder are unique.

Answer 8

Division Algorithm

Question 9

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

Answer 9

n = qd + r.

Question 10

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

Answer 10

Division Algorithm

Question 11

The blank is the result of the division of two integers. The quotient and the remainder are unique.

Answer 11

Division Algorithm

Question 12

The Division Algorithm works with blank; if any of the inputs is negative, the quotient will be negative per the rules of division.

Answer 12

positive integers only

Question 13

The operations div and mod produce the quotient (q) and the remainder (r). The blank is d.

Answer 13

divisor

Question 14

The blank is computed by n div d; q = n div d

Answer 14

quotient

Question 15

The blank is computed by n mod d; r = n mod d

Answer 15

remainder

Question 16

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.

Answer 16

modular division

Question 17

The operation defined by adding two numbers and applying modulo n to the result is called blank.

Answer 17

addition modulo n

Question 18

The operation defined by multiplying two numbers and applying modulo n to the result is called blank.

Answer 18

multiplication modulo n

Question 19

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.

Answer 19

modular addition

Question 20

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.

Answer 20

modular multiplication

Question 21

The blank is completed as the last step in the process.

Answer 21

modular operation

Question 22

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).

Answer 22

congruent to y modulo n

Question 23

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.

Answer 23

n|(x - y)

Question 24

Two integers x and y are blank if and only if x mod n = y mod n.

Answer 24

equivalent

Question 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.

Answer 25

Congruence

Question 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.

Answer 26

Intermediate results

Question 27

A number p is blank if it is an integer greater than 1 and its only factors are 1 and p.

Answer 27

prime

Question 28

A positive integer is blank if it has a factor other than 1 or itself.

Answer 28

composite

Question 29

every integer greater than 1 is either blank or blank

Answer 29

prime or composite

Question 30

blank are the basic building blocks of all integers.

Answer 30

Prime numbers

Question 31

Every positive integer greater than one can be expressed as a product of primes called its blank.

Answer 31

prime factorization

Question 32

Moreover, the prime factorization is unique up to ordering of the blank

Answer 32

factors.

Question 33

The fact that every integer greater than one has a unique prime factorization is central to number theory and is called blank.

Answer 33

The Fundamental Theorem of Arithmetic

Question 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.

Answer 34

1

Question 35

A blank is a sequence in which each number is equal to or greater than the one that came before.

Answer 35

non-decreasing sequence

Question 36

The blankl of a prime factor p in a prime factorization is the number of times p appears in the product of primes.

Answer 36

multiplicity

Question 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.

Answer 37

exponential notation

Question 38

The blank states that every positive integer greater than 1 can be expressed as a unique product of prime numbers.

Answer 38

fundamental theorem of arithmetic

Question 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.

Answer 39

non-decreasing sequence

Question 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.

Answer 40

Multiplicity

Question 41

The blank of non-zero integers x and y is the largest positive integer that is a factor of both x and y.

Answer 41

greatest common divisor (GCD)

Question 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.

Answer 42

least common multiple (LCM)

Question 43

Two numbers are said to be blank if their greatest common divisor is 1.

Answer 43

relatively prime

Question 44

GCD uses the blank between the prime factorization of two number

Answer 44

min

Question 45

LCM uses the blank between the prime factorization of two numbers

Answer 45

max

Question 46

GCD(24,50)

Answer 46

2min(3,1) * 3min(1,0)5min(0,2) = 2^13^0*5^0 = 2

Question 47

LCM(24,50)

Answer 47

2max(3,1) * 3max(1,0) * 5max(0,2) = 2^3 * 3^1 * 5^2 = 600

Question 48

The blank is the largest number that divides the given numbers.

Answer 48

GCD

Question 49

To determine the GCD:

Answer 49

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.

Question 50

The blank is the lowest common multiple of given numbers.

Answer 50

LCM

Question 51

To determine the LCM

Answer 51

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.

Question 52

Input: Integer N greater than 1.

Output: “Prime” if N is prime and “Composite” if N is composite.

Answer 52

Primality Testing

Question 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.

Answer 53

Factoring

Question 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.

Answer 54

brute force algorithm

Question 55

If N is a composite number, then N has a factor greater than 1 and at most
square root of N

Answer 55

Small factors

Question 56

There are an infinite number of blank.

Answer 56

primes

Question 57

The blank says how dense primes numbers are among the integers.

Answer 57

Prime Number Theorem

Question 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).

Answer 58

brute force algorithm

Question 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.

Answer 59

small factors theorem

Question 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.)

Answer 60

prime number theorem

Question 61

Let x and y be two positive integers. Then GCD(x, y) = blank

Answer 61

GCD(y mod x, x).

Question 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.

Answer 62

Euclid’s algorithm

Question 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.

Answer 63

modular arithmetic

Question 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.

Answer 64

16

Question 65

Let x and y be integers, then there are integers s and t such that

GCD(x, y) = blank

Answer 65

sx + ty

Question 66

The blank is not really an “extended” process, it is an add-on process leading to some important ideas used in cryptography.

Answer 66

extended Euclidean algorithm

Question 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

Answer 67

sx + ty].

Question 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).

Answer 68

GCD (x, y)

Question 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.

Answer 69

multiplicative inverse mod n (or just inverse mod n)

Question 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}.

Answer 70

Extended Euclidean Algorithm

Question 71

In ordinary arithmetic the definition of a multiplicative inverse is the product of a number and its multiplicative inverse is always blank.

Answer 71

1

Question 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.

Answer 72

modular arithmetic

Question 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.

Answer 73

relatively prime

Question 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.

Answer 74

decimal

Question 75

A digit in binary notation is called a blank.

Answer 75

bit

Question 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.

Answer 76

binary notation

Question 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

Answer 77

power of b

Question 78

The representation of n base b is called the blank and is denoted by (akak-1…a1a0)b.

Answer 78

base b expansion of n

Question 79

The binary number system has only two digits, blank and blank, and the digits are referred to as “bits.”

Answer 79

0 and 1

Question 80

Each place value is a power of blank.

Answer 80

2

Question 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.

Answer 81

number representation theorem

Question 82

to convert a binary number (e.g., 1001
base2)to a decimal number, follow these steps:

Answer 82

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
)

Question 83

In blank, numbers are represented base 16.

Answer 83

hexadecimal notation (or hex for short),

Question 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.

Answer 84

A, B, C, D, E, F.

Question 85

A blank which consists of 8 bits, can be represented by a 2-digit hexadecimal number.

Answer 85

byte

Question 86

The blank system has sixteen digits 0-9 and A-F. Each digit in a hex number is a power of 16.

Answer 86

hexadecimal (hex) number

Question 87

A byte is blank (binary digits). Each byte can be represented by a 2-digit hexadecimal number.

Answer 87

8 bits

Question 88

To convert the hex number, 3AFbase16
to a decimal value multiply each digit by its place value

Answer 88

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

Question 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

Answer 89

number n, base b

Question 90

convert the decimal value 482 to a base 7 number.

Answer 90

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

Question 91

The formula blank
determines the length of an integer value.

Answer 91

log base b (n+1)

Question 92

the number of digits required to display 4,324,783 in base 16 would be:

Answer 92

log base 16 (4324783 + 1) = 6 digits

Question 93

The number of loops in the algorithm is the blank in the binary representation of the exponent.

Answer 93

number of bits

Question 94

The following are the steps in fast integer exponentiation

Answer 94

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.”

Question 95

The binary representation of 18 is 10010. What expression is equivalent to b18?

Answer 95

18 = 1·24 + 0·23 + 0·22 + 1·21 + 0·20 = 24 + 21
b^2^4 + + b^2^1

Question 96

Blank applies intermediate modular arithmetic steps that keep the values within the iterative process smaller.

Answer 96

Iterative fast exponentiation (modular exponentiation)

Question 97

The blank in the iterative algorithm is the number of bits in the binary representation of the exponent.

Answer 97

number of loops

Question 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.

Answer 98

decryption

Question 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.

Answer 99

symmetric key cryptosystem,

Question 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.

Answer 100

ciphertext (encrypted message)

Question 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.

Answer 101

modular arithmetic

Question 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.

Answer 102

private key cryptosystems.

Question 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.

Answer 103

receiver

Question 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.

Answer 104

publicly
private decryption key.

Question 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.

Answer 105

RSA cryptosystem

Question 106

Preparation of public and private keys in RSA

Answer 106

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.

Question 107

RSA encryption

Answer 107

c = m^e mod N

Question 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.

Answer 108

two very large prime values

Question 109

The RSA encryption process for a specific message involves the formula blank
where m is the integer value of the message.

Answer 109

c = m^e mod N