Scribd
Upload
4 views2 pages

Module4 Mathematical Cryptography Questions

This document contains a series of mathematical problems related to cryptography, focusing on modular arithmetic, Fermat's and Euler's theorems, the Chinese Remainder Theorem, finite fields, and discrete logarithms. Each section includes specific tasks such as finding multiplicative inverses, calculating Euler's Totient function, solving congruences, and performing primality tests. The problems require detailed calculations and step-by-step solutions to demonstrate understanding of the mathematical concepts involved.

Uploaded by

abd4ind
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Module4 Mathematical Cryptography Questions

This document contains a series of mathematical problems related to cryptography, focusing on modular arithmetic, Fermat's and Euler's theorems, the Chinese Remainder Theorem, finite fields, and discrete logarithms. Each section includes specific tasks such as finding multiplicative inverses, calculating Euler's Totient function, solving congruences, and performing primality tests. The problems require detailed calculations and step-by-step solutions to demonstrate understanding of the mathematical concepts involved.

Uploaded by

abd4ind
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MODULE 4 QUESTIONS

Mathematical Foundations of Cryptography

Modular Arithmetic & Euclid's Algorithm

1. Use the Extended Euclidean Algorithm to find the multiplicative inverse of 117 modulo 269 .
Provide the step-by-step tabular calculation showing the quotients and remainders to arrive at
your final answer.

2. In the finite field GF(17), calculate the exact value of the expression (5 × 8 - 12) / 7 mod 17 . Show
the intermediate steps, specifically demonstrating how division by 7 is handled using modular
inversion.

Fermat's, Euler's Theorem & Prime Numbers

1. Calculate the remainder when 72026 is divided by 15 . You must use Euler's Totient Theorem to
reduce the exponent. Show the calculation of φ(15) and the reduction steps.

2. Calculate Euler's Totient function φ(N) for N = 3150 . If a cryptographic system uses the modulus
N = 3150 , exactly how many elements in the set {1, 2, ..., 3149} are relatively prime to N?

The Chinese Remainder Theorem & Primality Testing

1. An RSA key generation system requires finding a common variable x that satisfies the following
system of congruences: x ≡ 3 (mod 7) , x ≡ 5 (mod 11) , and x ≡ 2 (mod 13) . Solve for x using the
Chinese Remainder Theorem (CRT).

2. Perform exactly one iteration of the Miller-Rabin primality test on n = 221 using the base a = 5 .

Detail the factorization of n - 1 into 2kq , and determine whether 221 is declared "composite" or
"inconclusive" (a strong pseudoprime) based on this specific base.

Finite Fields & Polynomial Arithmetic

1. In the finite field GF(24) defined by the irreducible polynomial P(x) = x4 + x + 1 , multiply the

two polynomials A(x) = x3 + x2 + 1 and B(x) = x2 + x . Express the final reduced result as a
polynomial and as its equivalent 4-bit binary sequence.
2. Find the Greatest Common Divisor (GCD) of the polynomials f(x) = x5 + x4 + x3 + x2 + x + 1 and

g(x) = x3 + x2 + x + 1 over GF(2) using the polynomial Euclidean algorithm. Show your
polynomial long division steps.

Groups, Rings & Discrete Logarithms

1. Consider the set of 2×2 matrices with integer elements over the finite ring Z . Given the matrix A
5
= [[2, 3], [1, 4]] , calculate the determinant of A modulo 5. Then, construct the adjugate matrix to
find the exact inverse matrix A-1 over Z5.

2. In the multiplicative group Z* , first verify mathematically whether g = 2 is a primitive root.


19
Then, solve the discrete logarithm problem 2x ≡ 14 (mod 19) to find the value of x .

You might also like