网络安全08数论入门课件(743KB).ppt

* 西安电子科技大学计算机学院 * 第八章 作 业 习题：8.4 8.11.a 8.11.d * * * * * * * * * Traditionally sieve for primes using trial division of all possible prime factors of some number, but this only works for small numbers. Alternatively can use repeated statistical primality tests based on properties of primes, and then for certainty, use a slower deterministic primality test, such as the AKS test. * * If Miller-Rabin returns “composite” the number is definitely not prime, otherwise it is either a prime or a pseudo-prime. The chance it detects a pseudo-prime is 1/4 So if apply test repeatedly with different values of a, the probabiility that the number is a pseudo-prime can be made as small as desired, eg after 10 tests have chance of error 0.00001 If really need certainty, then would now expend effort to run a deterministic primality proof such as AKS. * A result from number theory, known as the prime number theorem, states that primes near n are spaced on the average one every (ln n) integers. Since you can ignore even numbers, on average need only test 0.5 ln(n) numbers of size n to locate a prime. eg. for numbers round 2^200 would check 0.5ln(2^200) = 69 numbers on average. This is only an average, can see successive odd primes, or long runs of composites. * One of the most useful results of number theory is the Chinese remainder theorem (CRT), so called because it is believed to have been discovered by the Chinese mathematician Sun-Tse in around 100 AD. It is very useful in speeding up some operations in the RSA public-key scheme, since it allows you to do perform calculations modulo factors of your modulus, and then combine the answers to get the actual result. Since the computational cost is proportional to size, this is faster than working in the full modulus sized modulus. * One of the useful features of the Chinese remainder theorem is that it provides a way to manipulate (potentially very large) numbers mod M, in terms of tuples of smaller numbers.This can be usef