Number Theory Paper Research the following topic: In cryptography the Chinese Re
ID: 3674531 • Letter: N
Question
Number Theory Paper
Research the following topic:
In cryptography the Chinese Reminder Theorem can be used for the purpose of generating random numbers. Explain how the algorithm is used for functionality for modular computation. Discuss how this can be used to prevent the reply attack and for countermeasures. Hint: What is a nonce?
Explain how Euler's totient function is used in cryptography. Describe this funciton and its relationship to public key cryptography.
Finally, compare Fermat's primality test to the Miller-Rabin. What are the differences, strengths, and advantages?
Prepare a 350- to 1,050-word paper that fully discusses the topic questions
Explanation / Answer
Random numbers are the numbers, which play an important role for various network security applications. hers are some techniques that are used to generating random numbers such as” pseudorandom number generator” and “linear congruent generator” also cryptographically generated random numbers” etc. but here we are using the Chinese Reminder Theorem for the purpose of generating Random numbers. In essence, CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pair wise relatively prime modulo.
Theorem 1: Let m1 ,m2 ...........,mn be a pairwise relatively prime, i.e gcd(mi , mj ) =1 for all i and j less than or equal to n where i j . Then, the system of congruences
Theorem 1 (Fermat’s Little Theorem). Let p be a prime and a be an integer which is not a multiple of p. Then a p1 1 (mod p).
Definition 2. Let n be a positive integer. The Euler totient of n, denoted (n), is the number of positive integers less than n which are relatively prime to n. Equivalently, (n) is the number of units in Z/nZ.
Theorem 3 (Euler’s Theorem). Let n be a positive integer and a an integer relatively prime to n. Then a (n) 1 (mod n).
(b) This allows simplifications of the computation of a b (mod n), because if b b 0 (mod (n)), a b a b 0 (mod n). To see this, just write b = b 0 + t(n) for an integer t, and compute a b a b 0+t(n) a b 0 a (n) t a b 0 (mod n). This means we can replace a general b with its least residue modulo (n), an integer between 0 and (n), which will potentially be much smaller than b.
Taking the contrapositive of Fermat’s little theorem, if there an a and p such that a p1 6 1 (mod p), it would follow that p is not prime. So to test whether a number is not prime, one can simply search for an a where this happens; a = 2 is a good starting place. If you find one, it is not prime. If you can’t find any, then it is highly likely that p is prime, but not guaranteed. In fact, there are integers that are not prime and where no such a exists: they are called Carmichael numbers.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.