文稿說明講稿1811sol

1、A Solution toPOJ1811 Prime TestSTYCProblem DescriptionGiven an integer N which satisfies the relation 2 N 1 that has no positive integer divisors other than 1 and p itself.Framework of the SolutionDetermine whether the given N is prime or not.If N is prime, print “Prime” and exit.Factorize N for its

2、 smallest prime factor.The Brute-force WayTrial DivisionIf N is even, then 2 is its smallest prime factor.Try dividing N by every odd number k between 2 and N1/2. The smallest k by which N is divisible is the smallest prime factor of N. If such k does not exist, then N is prime.Complexity: O(N1/2) f

3、or time, O(1) for spaceModified Brute-forceConstruct a table that stores all prime numbers not greater than N1/2. Try dividing N only by prime numbers.Complexity: O(N1/2logN) for time, O(N1/2) for space using Sieve of EratosthenesEstimation of space consumption: 226 bits = 223 bytes = 8,192 kilobyte

4、sMuch time is used in the process of sievingModified Brute-force 2Embed a table of prime numbers smaller than Nmax1/4 into the source. Extend the table to N1/2 by runtime calculation.Complexity: O(N3/4/logN) for time, O(N1/2/logN) for spaceEstimation of time consumption: Finding all 7,603,553 primes

5、 smaller than 227 takes approx. 1.32 x 1011 divisions or 73 minutes on a Pentium 1.5 GHz.Brute-force with TrickStart from N1/2 rather than 2. Do factorization recursively once a factor is found.Efficient in handling N = pq where p and q relatively close to each other.POJ accepts this! - westevers so

6、lutionBrute-force with Trick 2Wheel FactorizationTest whether N is a multiple of 2, 3 or 5. If it is, the problem has been solved.If not, do trial division using only integers which are not multiples of 2, 3, and 5.Saves 7/15 of work.Key Concepts (cont.)Prime factorization algorithms: Algorithms dev

7、ised for determining the prime factors of a given numberPrimality tests: Tests to determine whether or not a given number is prime, as opposed to actually posing the number into its constituent prime factorsPrimality TestsDeterministic: Adleman-Pomerance-Rumely Primality Test, Elliptic Curve Primali

8、ty ProvingProbabilistic: Rabin-Miller Strong Pseudoprime TestRabin-MillerStrong Pseudoprime TestGiven an odd integer N, let N = 2rs + 1 with s odd. Then choose a random integer a between 1 and N - 1. If as = 1 (mod N) or a2j s = -1 (mod N) for some j between 0 and r - 1, then N passes the test. A pr

9、ime will pass the test for all a.Rabin-MillerStrong Pseudoprime TestRequires no more than (1 + o(1)logN multiplications (mod N).A number which passes the test is not necessarily prime. But a composite number passes the test for at most 1/4 of the possible bases a.If n multiple independent tests are

10、performed on a composite number, the probability that it passes each test is 1/4n or less.Rabin-MillerStrong Pseudoprime TestSmallest composite numbers passing the RMSPT using the first k primes as bases: 2,047; 1,373,653; 25,326,001; 3,215,031,751; 2,152,302,898,747; 3,474,749,660,383; 341,550,071,

11、728,321, 341,550,071,728,321; at most 41,234,316,135,705,689,041341,550,071,728,321 = 244.957, 41,234,316,135,705,689,041 = 265.160Tests show that randomized bases may fail sometimes.Pseudocode of RMSPT (Sprache)function powermod(a, s, n)p := 1b := awhile s 0if s & 1 = 1 then p := p * b % nb := b *

12、b % ns := s 1Pseudocode of RMSPT (cont.)function rabin-miller(n)if n 2 AND powermod(2, n - 1, n) != 1 then return FALSEif n 3 AND powermod(3, n - 1, n) != 1 then return FALSEif n 5 AND powermod(5, n - 1, n) != 1 then return FALSEif n 7 AND powermod(7, n - 1, n) != 1 then return FALSEif n 11 AND powe

13、rmod(11, n - 1, n) != 1 then return FALSEif n 13 AND powermod(13, n - 1, n) != 1 then return FALSEif n 17 AND powermod(17, n - 1, n) != 1 then return FALSEif n 19 AND powermod(19, n - 1, n) != 1 then return FALSEif n 23 AND powermod(23, n - 1, n) != 1 then return FALSEreturn TRUEPrime Factorization

14、AlgorithmsContinued Fraction Algorithm, Lenstra Elliptic Curve Method, Number Field Sieve, Pollard Rho Method, Quadratic Sieve, Trial DivisionPollard RhoFactorization MethodAlso known as Pollard Monte Carlo factorization method.Runs at O(p1/2) where p is the largest prime factor of the number to be

15、factored.Two aspects to this method: iteration and cycle detection.Pollard RhoFactorization MethodIteration:Iterate the formula xn+1 = xn2 + a (mod N). Almost any polynomial formula (two exceptions being xn2 and xn2 - 2) for any initial value x0 will produce a sequence of numbers that eventually fal

16、ls into a cycle.Pollard RhoFactorization MethodCycle detection:Keep one running copy of xi. If i is power of 2, let y = xi, and at each step, compute GCD(|xi - y|, N). If the result is neither 1 nor N, then a cycle is detected and GCD(|xi - y|, N) is a factor (not necessarily prime) of N. If the res

17、ult is N, the method fails, choose another a and redo iteration.Pseudocode of RRFM (Sprache)function pollard-rho(n)doa := random()while a = 0 OR a = -2y := xk := 2i := 1Pseudocode of RRFM (cont.)while TRUEi := i + 1x := (x * x + a) % ne := abs(x - y)d := GCD(e, n)if d != 1 AND d != n then return del

18、se if i = k theny := xk := k b) in PRFM: Following properties of GCD helps avoiding divisions:If a = b, then GCD(a, b) = a.GCD(a, b) = 2 * GCD(a/2, b/2) with both a and b even.GCD(a, b) = GCD(a/2, b) with a even but b odd.GCD(a, b) = GCD(a - b, b) with both a and b odd.Time complexity: O(logb)Notes

19、on Implementation (cont.)Combination with brute-force algorithms: Embed a prime table. Do brute-force trial division for small divisors.Minor optimizations: Use 32-bit integer division instead of the 64-bit version when possibleActual Timing PerformancePlatform: Windows XP SP1 on a Pentium M 1.5 GHzAlgorithms tested: Adapted versions of westevers, TNs, lhs and zsuyrls solutions and my later fixed versionTiming method: Process user time returned by the GetProcessTimes Windows APIActual Timing PerformanceTest data: Original data set on POJ, two pseudorandom data sets generated by Mathem