Discrete Mathematics Multiple Choice Questions on “Number Theory – Modular Exponentiation”.
1. If the multiplicative inverse of “53 modulo 21” exists, then which of the following is true?
a) GCD(53,21) = 1
b) GCD(53,21) = 29
c) GCD(53,21) = 53
d) GCD(53,21) = 12
Answer: a
Clarification: The multiplicative inverse of “a modulo m” can be found out by extended Euler’s GCD algorithm, and the time complexity of this method is O(logm). We know that the multiplicative inverse of “x modulo n” exists if and only if x and n are relatively prime (i.e., if gcd(a, m) = 1). So, in this case GCD(53,21) = 1.
2. A multiplicative monoid defines the property of exponentiation with ________
a) integer exponents
b) fractional exponents
c) rational exponents
d) negative integer exponents
Answer: a
Clarification: Exponentiation with integer exponents is termed in any multiplicative monoid. Exponentiation is described inductively by 1) h0 = 1 for all h ∈ S, hn+1 = hn h and non-negative integers n, If n is a negative integer then hn is only defined if h has an inverse in S. Monoids define many structures including groups and rings (under multiplication).
3. Which of the following algorithms has better computational complexity than standard division algorithms?
a) Montgomery algorithm
b) Classical modular exponentiation algorithm
c) ASM algorithm
d) FSM algorithm
Answer: b
Clarification: To multiply m and n, they are converted to Montgomery form: mR mod X and nR mod X. When multiplied, these produce mnR2 mod X, and the Montgomery reduction produces abR mod N which is the Montgomery form of the desired product. After that, the low bits are discarded which gives a result less than 2X. One final subtraction reduces this to less than X. Hence, this procedure can have a better computational complexity than standard division algorithms.
4. Which of the following methods uses the concept that exponentiation is computationally inexpensive in the finite field?
a) Diffie-HEllman key exchange
b) RSA key exchange
c) Arithmetic key exchange
d) FSM method
Answer: a
Clarification: Exponentiation in the finite fields has its many applications in the public key cryptography system. Now, the Diffie–Hellman key exchange can have the concept that exponentiation is computationally inexpensive in the finite fields and the discrete logarithm which is the inverse of exponentiation, can be computationally expensive.
5. If there is a unique prime number p1 then a finite field F has the property of ______________
a) p1x = 0 for all x in F
b) f(x) = f(xp1) for all x in F
c) p1 = y for all y in F
d) xy + p1 for all x, y in F
Answer: a
Clarification: A field can be defined as an algebraic structure in which multiplication, addition, subtraction, and division are well-defined and satisfy similar properties. If there is a unique prime number p1 then a finite field F has the property of p1x = 0, for all x in F and this prime number is called the characteristics of the field.
6. Evaluate the expression 6359 mod 320.
a) 681
b) 811
c) 3781
d) 279
Answer: d
Clarification: By definition, we can have 6359 ≡ 279 (mod320), hence the answer is 279.
7. The time complexity to perform the modular exponentiation of a ≡ cg (mod m).
a) O(m+a)
b) O(a*g)
c) O(gm)
d) O(g)
Answer: d
Clarification: The modular exponentiation completely depends on the operating system environment and the processor for its performance. The above said method requires a time complexity of O(g) for its completion.
8. According to congruence relation, find the remainder of 56 mod 24.
a) 10
b) 12
c) 6
d) 4
Answer: c
Clarification: According to congruence relation, 56 ≡ 6 (mod 24), because 56 − 32 = 24, which is a multiple of 24. So, the remainder is 6.
9. In cryptography system, the value of z in x ≡ ze (mod m) should be at least ______
a) 1024 bits
b) 1GB
c) 596 bits
d) 54 Bytes
Answer: a
Clarification: In cryptography system, the value of z in x ≡ ze (mod m) should be at least 1024 bits.
10. Determine the value of x, where y = 7, e = 12 and n = 566 using modular exponentiation method (x ≡ ye (mod n)).
a) 735
b) 321
c) 872
d) 487
Answer: d
Clarification: Given y = 5, e = 12, and n = 566 and so x ≡ 512 (mod 566). Now 512 comes out to 244140625 and taking this value modulo 566, x is determined to be 487.