4.5.4 FACTORING INTO PRIMES 365 Al. Initialize No (Top ten web hosting)
4.5.4 FACTORING INTO PRIMES 365 Al. Initialize No A3. Divide A5. Factor found A7. n is prime Fig. 10. A simple factoring algorithm. A3. [Divide.] Set 4 t Ln/&J, T t n mod &. (Here 4 and r are the quotient and remainder obtained when n is divided by dk.) A4. [Zero remainder?] If r # 0, go to step A6. A5. [Factor found.] Increase t by 1, and set pt t d,+, n t q. Return to step A2. A6. [Low quotient?] If q > dk, increase Ic by 1 and return to step A3. A7. [n is prime.] Increase t by 1, set pt t n, and terminate the algorithm. 1 As an example of Algorithm A, consider the factorization of the number N = 25852. We immediately find that iV = 2 a 12926; hence pl = 2. Further- more, 12926 = 2.6463, so ~2 = 2. But now n = 6463 is not divisible by 2, 3, 5, * * . , 19; we find that n = 23.281, hence ps = 23. Finally 281 = 12 + 23 + 5 and 12 5 23; hence p4 = 281. The determination of 25852 s factors has therefore involved a total of 12 division operations; on the other hand, if we hadbtried to factor the slightly smaller number 25849 (which is prime), at least 38 division operations would have been performed. This illustrates the fact that Algorithm A requires a running time roughly proportional to max(pt-1, @). (If t = 1, this formula is valid if we adopt the convention ~0 = 1.) The sequence do, dl, dz, . . . of trial divisors used in Algorithm A can be taken to be simply 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, . . . , where we alternately add 2 and 4 after the first three terms. This sequence contains all numbers that +re not multiples of 2 or 3; it also includes numbers such as 25, 35, 49, etc., which are not prime, but the algorithm will still give the correct answer. A further savings of 20 percent in computation time can be made by removing the numbers 30m f 5 from the list for m 2 1, thereby eliminating all of the spurious multiples of 5. The exclusion of multiples of 7 shortens the list by 14 percent more, etc. A compact bit table can be used to govern the choice of trial divisors. If N is known to be small, it is reasonable to have a table of all the necessary primes as part of the program. For example, if N is less than a million, we need only include the 168 primes less than a thousand (followed by the value dlss = 1000, to terminate the list in case N is a prime larger than 9972). Such a table