This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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)
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
