网络安全-08：数论入门幻灯片.ppt

定义： 若m 1, (a,m) = 1, 则使得同余式 ai ≡ 1(mod m) 成立的最小正整数i，叫做a对模m的离散对数。 指数一定是欧拉函数的因子 对任意整数b和模数p的本原根a，有唯一的幂i，使得 b ≡ ai mod p, 其中0 ≤ i ≤ p-1 该指数i称为以a为底模p的离散对数，记为 dloga, p(b) 离散对数不仅与模有关，而且与本原根有关。 例如： 2对模7的指数是3，对模11的指数是10，所以，2是模11的一个本原根，而不是模7的本原根； dlog2, 9(8) = 3 * 西安电子科技大学计算机学院 * * 西安电子科技大学计算机学院 * 小 结 素数 Fermat和Euler定理 欧拉函数 ?(n) 素性测试（Miller-Rabin算法） 中国剩余定理 离散对数 * 西安电子科技大学计算机学院 * 第八章 作 业 习题：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