Tomcat, J2Ee, Hibernate Programming, Shared Web Hosting, Comcast Web Hosting Java Blog

438 ARITHMETIC 4.6.2 16. [M.W] (a) Given that f(x) is an irreducible polynomial modulo a prime p, of degree n, prove that the pn polynomials of degree less than n form a field under arithmetic modulo f(x) and p. (Note: The existence of irreducible polynomials of each degree is proved in exercise 4; therefore fields with p elements exist for all primes p and all n 2: 1.) (b) Show that any field with p elements has a primitive root element < such that the elements of the field are (0, 1, [, t2,. . . , Epne2}. [Hint: Exercise 3.2.1.2-16 provides a proof in the special case n = 1.1 (c) If f( z ) is an irreducible polynomial modulo p, of degree n, prove that xpm -x is divisible by f(x) if and only if m is a multiple of n. (It follows that we can test irreducibility rather quickly: A given nth degree polynomial f(x) is irreducible modulo p if and only if xpn -x is divisible by f(x) and gcd(xP -2, f(z)) = 1 for all primes o dividing n.) 17. [MB] Let F be a field with 132 elements. How many elements of F have order f, for each integer f with 1 5 f < 132? (The order of an element a is the least positive integer m such that urn = 1.) F 18. [M%] Let U(X) = ~~5~ + . . . + ~0, ZL~ # 0, be a primitive polynomial with integer coefficients, and let V(Z) be the manic polynomial defined by V(X) = IL, - . u(x/u,) = xn + I&-1x-l + un-2unxn-2 +. . .uou, - . (a) Given that w(x) has the complete factorization PI(X). pr(x) over the integers, where each pj(x) is manic, what is the complete factorization of U(X) over the integers? (b) If W(X) = xm + W,-#---l + . . . + Wc iS a faCtOr Of 21(X), prove that wk iS a IUUkipk ofu,"-lpk for0 <- k Searching for affordable and proven webhost to host and run your servlet applications? Go to Linux Web Hosting services and you will find it.

4.6.2 FACTORIZATION OF POLYNOMIALS 437 3. [M.%] Let us, . . . . u7(z) be polynomials over a field S, with 2~j(z) relatively prime to uk(z) for all j # k. For any given polynomials WI(X), . . . , wI(z) over S, prove that there is a unique polynomial V(X) over S such that d&v) < deg(ul) + . . + deg(u,) and V(Z) = I+(Z) (modulo uj(z) for 1 2 j 5 r. (Compare with Theorem 4.3.2C.) 4. [HA4%?] Let anp be the number of manic irreducible polynomials of degree n, modulo a prime p. Find a formula for the generating function G,,(z) = c, unpzn. [Hint: Prove the following identity connecting power series: f(z) = cj2] g(zj)/j if and only if g(z) = xn>l p(n)f(z )/n .] What is lim,,, a,,/p ? - 5. [HMXI] Let A,, be the average number of factors of a randomly selected poly- nomial of degree n, modulo a prime p. Show that lim,,,A,, = H,. What is the limiting average value of 27, when there are r factors? 6. [M~I] (J. L. Lagrange, 1771.) Prove the congruence (9). [Hint: Factor x1, - z in the field of p elements.] 7. [AL% ] Prove Eq. (14). 8. [HiWW] How can we be sure that the vectors output by Algorithm N are linearly independent? 9. [20] Explain how to construct a table of reciprocals mod 101 in a simple way, given that 2 is a primitive root of 101. b 10. [.zI] Find the complete factorization of the polynomial U(X) in (22), modulo 2, using Berlekamp s procedure. 11. [,% ,!?IFind the complete factorization of the polynomial u(x) in (22), modulo 5. b 12. [IV@,% ] Use Berlekamp s algorithm to determine the number of factors of u(z) = x4 + 1, modulo p, for all primes p. [Hint: Consider the cases p = 2, p = 8k + 1, p=8k+3,p=8k+5,p=8k+7s eparately; what is the matrix Q? You need not discover the factors; just determine how many there are.] 13. [M,%] Give an explicit formula for the factors of x4 + 1, modulo p, for all odd primes p, in terms of the quantities m, fi, m (if such square roots exist modulo p). 14. [A4,%] (H. Zassenhaus.) Let W(X) be a solution to (8), and let W(X) = n(z -s) where the product is over all 0 2 s < p such that gcd(u(z), V(X) -s) # 1. Explain how to compute w(z), given U(Z) and v(z). [Hint: Eq. (14) implies that ,w(z) is the polynomial of least degree such that u(z) divides zu(v(z)).] b 15. [A& 71 Design an algorithm to calculate the square root of a given integer u modulo a given prime p, i.e., to find an integer v such that v2 = u (modulo p) whenever such a w exists. Your algorithm should be efficient even for very large primes p. (Note that a solution to this problem leads to a procedure for solving any given quadratic equation modulo p, using the quadratic formula in the usual way.)
Looking for affordable and reliable webhost to host and run your business application? Then look no more and go to servlet web hosting services.

436 ARITHMETIC 4.6.2 method to determine 4~) modulo pe for sufficiently large e. Hensel s construction appears to be computationally superior to the Chinese remainder approach; but it is valid directly only when gcd(d(s), u(z)/d(z)) = 1 or w@(x), 4+W) = 1, (27) since the idea is to apply the techniques of exercise 22 to one of the factorizations @)u(z) = ij(z)ul(z) or @)u(x) G $z)vl(z) (modulo p). Exercises 34 and 35 show that it is possible to arrange things so that (27) holds whenever necessary. The gcd algorithms sketched here are significantly faster than those of Section 4.6.1 except when the polynomial remainder sequence is very short. Perhaps the best general procedure would be to start with the computation of gcd(u(s), V(X)) modulo a fairly small prime p, not a divisor of both e(v) and e(v). If the result q(x) is 1, we re done; if it has high degree, we use Algorithm 4.6.lC; otherwise we use one of the above methods, first computing a bound for the coefficients of a(~) based on the coefficients of U(X) and W(Z), and on the (small) degree of q(z). As in the factorization problem, we should apply this procedure to the reverses of u(z), V(X) and reverse the result, if the trailing coefficients are simpler than the leading ones. Multivariate polynomials. Similar techniques lead to useful algorithms for fac- torization or gcd calculations on multivariate polynomials with integer coeffi- cients. It is convenient to deal with the polynomial u(z1, . . . , Q) by working modulo the irreducible polynomials 22 -a~, . . . , it —at, which play the r61e of p in the above discussion. Since W(X) mod (x-a) = w(a), the value of u(zl, . . . , xt) is the univariate polynomial u(x~, ~2,. . . , at). When the integers u2, . . . , at have been chosen so that u(zl, as, . . . , at) has the same degree in ~1 as ~(21, ~2,. . . , Q), an appropriate generalization of Hensel s construction will lift squarefree fac- torizations of this univariate polynomial to factorizations modulo (~2 -u2)Q, . ..) (xt -utp, where nj is the degree of x3 in u; at the same time we can also work modulo an appropriate integer prime p. As many as possible of the uj should be zero, so that sparseness of the intermediate results is retained. For details, see P. S. Wang, Math. Comp. 32 (1978), 1215-1231, in addition to the papers by Musser and by Moses and Yun cited earlier. EXERCISES b 1. [M24] Let p be prime. What is the probability that a random polynomial of degree n has a linear factor (a factor of degrea l), when n 2 p? Show that this probability is more than 4. (Assume that each of the pn manic polynomials modulo p is equally likely.) What is the average number of linear factors? b 2. [A& 5] (a) Show that any manic polynomial U(Z), over a unique factorization domain, may be expressed uniquely in the form u(5) = ?J(x)2w(x), where W(Z) is squarefree (has no factor of positive degree of the form d(z) ) and both W(Z) and W(X) are manic. (b) (E. R. Berlekamp.) How many manic polynomials of degree n are squarefree modulo p, when p is prime?
We would like to recommend you tested and proved virtual web hosting services, which you will surely find to be of great quality.

4.6.2 FACTORIZATION OF POLYNOMIALS 435 of w-+44, 44) modulo 13 in 4.6.1-6 is enough to prove that U(Z) and U(X) are relatively prime over the integers; the comparatively laborious ca.lculations of Algorithm 4.6.1E or Algorithm 4.6.lC are unnecessary. Since two random primitive polynomials are almost always relatively prime over the integers, and since they are relatively prime modulo p with probability 1 - l/p, it is usually a good idea to do the computations modulo p. As remarked before, we need good methods also for the nonrandom polyno- mials that arise in practice. Therefore we wish to sharpen our techniques and discover how to find gcd(u(z),v(z)) g m eneral, over the integers, based entirely on information that we obtain working modulo primes p. We may assume that U(X) and W(X) are primitive. Instead of calculating gcd(u(z), V(X)) d irectly, it will be convenient to search instead for the polynomial d(z) = c . gcd(u(z), V(X)), (25) where the constant c is chosen so that l(;i) = gcd(l(u), 1(w)). (26) This condition will always hold for suitable c, since the leading coefficient of any common divisor of U(X) and W(X) must be a divisor of gcd(l(u), l(w)). Once a(~) has been found satisfying these conditions, we can readily compute pp(;i(z)), which is the true greatest common divisor of U(X) and V(X). Condition (26) is convenient since it avoids the uncertainty of unit multiples of the gcd; we have used essentially the same idea to control the leading coefficients in our factorization routine. If p is a sufficiently large prime, based on the bounds for coeflicients in exercise 20 applied either to @)u(z) or C@)V(Z), let us compute the unique polynomial P(X) = @)q(~) (modulo p) h aving all coefficients in [–Jp, 4~). When pp(?j(~)) divides both U(X) and W(Z), it must equal gcd(u(z), V(Z)) because of (24). On the other hand if it does not divide both U(X) and V(X) we must have deg(q) > deg(d). A study of Algorithm 4.6.1E reveals that this will be the case only if p divides the leading coefficient of one of the nonzero remainders computed by that algorithm with exact integer arithmetic; otherwise Euclid s algorithm modulo p deals with precisely the same sequence of polynomials as Algorithm 4.6.1E except for nonzero constant multiples (modulo p). So only a small number of unlucky)) primes can cause us to miss the gcd, and we will soon find a lucky prime if we keep trying. If the bound on coefficients is so large that single-precision primes p are insufficient, we can compute a(~) modulo several primes p until it has been determined via the Chinese remainder algorithm of Section 4.3.2. This approach, which is due to W. S. Brown and G. E. Collins, has been described in detail by Brown in JACA4 18 (19 71), 4 78-504. Alternatively, as suggested by J. Moses and D. Y. Y. Yun [Roe. ACM Conf. 28 (1973), 159-1661, we can use Hensel s
Please visit our professional web hosting services to find out about cheap and reliable webhost service that will surely answer all your demands.

434 ARITHMETIC 4.6.2 At the conclusion of this process, the current value of U(X) will be the final irreducible factor of the originally given polynomial. Note that if lzlol < 1~~1, it is preferable to do all of the work with the reverse polynomial UOZ~ + . . . + Us, whose factors are the reverses of the factors of U(Z). The procedure as stated requires pe > 2B, where B is a bound on the co- efficients of any divisor of u,u(z), but we can use a much smaller value of B if we only guarantee it to be valid for divisors of degree 5 Jdeg(u). In this case the divisibility test in step F2 should be applied to w(z) = Q(Z). . . v,(z)/v(z) instead of V(Z), whenever deg(w) > adeg(u). The above algorithm contains an obvious bottleneck: We may have to test as many as 27-1 potential factors W(X). The average value of 2 in a random situation is about 72, or perhaps n1.5 (see exercise 5), but in nonrandom situations we will want to speed up this part of the routine as much as we can. One way to rule out spurious factors quickly is to compute the trailing coefficient U(0) first, continuing only if this divides e(u)u(O); the complication explained in the preceding paragraph does not have to be considered unless this divisibility condition is satisfied, since such a test is valid even when deg(v) > &deg(u). Another important way to speed up the procedure is to reduce r so that it tends to reflect the true number of factors. The distinct degree factorization algorithm above can be applied for various small primes pj, thus obtaining for each prime a set 03 of possible degrees of factors modulo pj; see exercise 26. We can represent Dj as a string of n binary bits. Now we compute the intersection n Dj, namely the logical and of these bit strings, and we perform step F2 only for ii + … + id E n Dj. Furthermore p is chosen to be that pj having the smallest value of r. This technique is due to David R. Musser, whose experience suggests trying about five primes pj (see JACM 25 (1978), 271-282). Of course we would stop immediately if the current n Dj shows that U(Z) is irreducible. Musser has given a complete discussion of a factorization method similar to the steps above, in JACK 22 (1975), 291-308. The procedure above incorporates an improvement suggested in 1978 by G. E. Collins, namely to look for trial divisors by taking combinations of d factors at a time rather than combinations of total degree d. This improvement is important because of the statistical behavior of the modulo-p factors of polynomials that are irreducible over the rationals (cf. exercise 37). Greatest common divisors. Similar techniques can be used to calculate greatest common divisors of polynomials: If gcd(u(z), V(X)) = d(z) over the integers, and if gcd(u(z), W(X)) = q(x) (modulo p) w h ere q(x) is manic, then d(z) is a common divisor of U(X) and V(X) modulo p; hence d(z) divides q(x) (modulo p). (24 If p does not divide the leading coefficients of both u and v, it does not divide the leading coefficient of d; in such a case deg(d) 5 deg(q). When q(z) = 1 for such a prime p, we must therefore have deg(d) = 0, and d(z) = gcd(cont(u), cant(v)). This justifies the remark made in Section 4.6.1 that the simple computation
If you are looking for cheap and quality webhost to host and run your website check Jboss Web Hosting services.

4.6.2 FACTORIZATION OF POLYNOMIALS 433 factors whose coefficients exceed exp(n lllglgn) for infinitely many n. [See R. C. Vaughan, Michigan Math. J. 21 (1974), 289-295.1 The factorization of Z -1 is discussed in exercise 32. Instead of using a large prime p, which might have to be truly enormous if U(X) has large degree or large coefficients, we can also make use of small p, provided that U(X) is squarefree mod p. For in this case, an important con- struction introduced by K. Hensel [Theorie der Algebraischen Zahlen (Leipzig: Teubner, 1908), Chapter 41 can be used to extend a factorization modulo p in a unique way to a factorization modulo pe for arbitrarily high e. Hensel s method is described in exercise 22; if we apply it to (23) with p = 13 and e = 2, we obtain the unique factorization u(x) E (x -36)( x3 -182 + 82~ 66)(x4 + 541~~ - 10~~ + 69a: + 84) (modulo 169). Calling these factors 2)1(2)213(2)214(2), we see that VI(X) and ~(5) are not factors of U(X) over the integers, nor is their product v~(x)u~(z) when the coefficients have been reduced modulo 169 to the range (-y, 9). Thus we have exhausted all possibilities, proving once again that, U(X) is irreducible over the integers-this time using only its factorization modulo 13. The example we have been considering is atypical in one important respect: We have been factoring the monk polynomial U(X) in (22), so we could assume that all its factors were manic. What should we do if un > l? In such a case, the leading coefficients of all but one of the polynomial factors can be varied almost arbitrarily modulo pe; we certainly don t want to try all possibilities. Perhaps the reader has already noticed this problem. Fortunately there is a simple way out: the factorization U(X) = w(s)w(z) implies a factorization U,%(Z) = IJ~(z)w~(z) where f?(~) = e(w,) = Us = e(u). ( Do you mind if I multiply your polynomial by its leading coefficient before factoring it? ) We can proceed essentially as above, but using pe > 2B where B now bounds the maximum coefficient for factors of U,U(Z) instead of U(X). Putting these observations all together results in the following procedure: Fl. Find the unique squarefree factorization U(X) G TV, . . . U,(Z) (modulo p ), where pe is sufficiently large as explained above, and where the vj(~) are manic. (This will be possible for all but a few primes p, see exercise 23.) Also set d c 1. F2. For every combination of factors U(X) = zlil(z). . . vid(z), with il = 1 if d = +r, form the unique polynomial $2) E e(u)w(z) (modulo p ) whose co- efficients all lie in the interval [-ip , 3~~). If V(X) divides C(U)U(X), output the factor pp(B(z)), divide U(X) by this factor, and remove the corresponding Q(X) from the list of factors modulo pe; decrease r by the number of factors removed, and terminate the algorithm if d > 4~. F3. Increase d by 1, and return to F2 if d > ir. I
Go visit our java server pages services for a reliable, lowcost webhost to satisfy all your needs.

432 ARITHMETIC 4.6.2 We have seen above in (19) that U(Z) z (cc~+~z~+~cc~+~z+~)(cc~+~x~+~cc+~~)(x+~) (modulo 13); (23) and the complete factorization of U(X) modulo 2 shows one factor of degree 6 and another of degree 2 (see exercise 10). From (23) we can see that U(X) has no factor of degree 2, so it must be irreducible over the integers. This particular example was perhaps too simple; experience shows that most irreducible polynomials can be recognized as such by examining their factors modulo a few primes, but it is not always so easy to establish irreducibility. For example, there are polynomials that can be properly factored modulo p for all primes p, with consistent degrees of the factors, yet they are irreducible over the integers (see exercise 12). Almost all polynomials are irreducible over the integers, as shown in exer- cise 27. But we usually aren t trying to factor a random polynomial; there is probably some reason to expect a nontrivial factor or else the calculation would not have been attempted in the first place. We need a method that identifies factors when they are there. In general if we try to find the factors of U(X) by considering its behavior modulo different primes, the results will not be easy to combine; for example, if U(Z) actually is the product of four quadratic polynomials, it will be hard to match up their images with respect to different prime moduli. Therefore it is desirable to stick to a single prime and to see how much mileage we can get out of it, once we feel that the factors modulo this prime have the right degrees. One idea is to work modulo a very large prime p, big enough so that the coefficients in any true factorization U(X) = V(Z)W(Z) over the integers must actually lie between -p/2 and p/2. Then all possible integer factors can be read ofI from the mod p factors we know how to compute. Exercise 20 shows how to obtain fairly good bounds on the coefficients of polynomial factors. For example, if (22) were reducible it would have a factor V(X) of degree 5 4, and the coefficients of v would be at most 34 in magnitude by the results of that exercise. So all potential factors of U(Z) will be fairly evident if we work modulo any prime p > 68. Indeed, the complete factorization modulo 71 is (z + 12)(x + 25)(x2 -13 -7)(x4 -24~~ - 16~~ + 312 - 12), and we see immediately that none of these polynomials are factors of (22) over the integers since their constant terms do not divide 5; furthermore there is no way to obtain a divisor of (22) by grouping two of these factors, since none of the conceivable constant terms 12 X 25, -12 X 7, 12 X (-12) is congruent to fl or &5 (modulo 71). Incidentally, it is not trivial to obtain good bounds on the coefficients of poly- nomial factors, since a lot of cancellation can occur when polynomials are mul- tiplied. For example, the innocuous-looking polynomial Z? - 1 has irreducible
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision J2ee Web Hosting services.

4.6.2 FACTORIZATION OF POLYNOMIALS 431 gcd(f(z), (z + s)13 -1) for 0 5 s < 3: f(x) s=o s=l s=2 x3 + 2x + 1 x3 + 2x + 2 ; i : i fb x3 + x2 + 2 X x3+ x2+ x+2 f(Z) fh, x3 + x2 + 2x + 1 1 ;f; fi x3 + 2x2 + 1 1 X x3 + 2x2 + x + 1 1 f(x) x3 + 2x2 + 2x + 2 r;., 1 1 Exercise 31 contains a partial explanation of why linear polynomials can be effective; however, when the number of irreducible polynomials of degree d ex- ceeds 2P, it is clear that there will exist irreducibles that cannot be distinguished by linear choices of t(x). An alternative to (21) that works when p = 2 is discussed in exercise 30. Factoring over the integers. It is somewhat more difficult to find the complete factorization of polynomials with integer coefficients when we are not working modulo p, but some reasonably efficient methods are available for this purpose. Isaac Newton gave a method for finding linear and quadratic factors of polynomials with integer coefficients in his Arithmetica Universalis (1707). This method was extended by an astronomer named F riedrich von Schubert in 1793, who showed how to find all factors of degree n in a finite number of steps; see M. Cantor, Geschichte der Mathematik 4 (Leipzig: Teubner, 1908), 136-137. L. Kronecker rediscovered von Schubert s method independently about 90 years later; but unfortunately the method is very inefficient when n is five or more. Much better results can be obtained with the help of the (mod p factorization methods presented above. Suppose that we want to find the irreducible factors of a given polynomial u(x) = u,xn + u,-lxn--l + - * * + 210, % # 0, over the integers. As a first step, we can divide by the greatest common divisor of the coefficients; this leaves us with a primitive polynomial. We may also assume that U(X) is squarefree, by dividing out gcd(u(x), U (X)) as in exercise 34. Now if U(X) = v(s)w(x), where each of these polynomials has integer coef- ficients, we obviously have U(X) c V(Z)W(X) (modulo p) for all primes p, so there is a nontrivial factorization modulo p unless p divides l(u). An efficient algorithm for factoring U(X) modulo p can therefore be used in an attempt to reconstruct possible factorizations of U(X) over the integers. For example, let u(x) = x8 + x6 - 3x4 - 3x3 + 8x2 + 2x - 5. (22)
Searching for affordable and proven webhost to host and run your servlet applications? Go to Linux Web Hosting services and you will find it.

430 ARITHMETIC 4.6.2 D2. (At this point w(z) = xpd modv(z); all of the irreducible factors of v(z) are distinct and have degree > d.) If d+ 1 > &deg(v), the procedure terminates since we either have V(X) = 1 or V(X) is irreducible. Otherwise increase d by 1 and replace W(X) by W(X) modw(z). D3. Find gd(Z) = gcd(w(s) -z, W(X)). (Th is is the product of all the irreducible factors of u(z) whose degree is d.) If gd(Z) # 1, replace W(X) by 2)(z)/gd(x) and W(X) by W(X) mod V(X); and if the degree of gd(Z) is greater than d, use the algorithm below to find its factors. Return to step D2. 1 This procedure determines the product of all irreducible factors of each degree d, and therefore it tells us how many factors there are of each degree. Since the three factors of our example polynomial (19) have different degrees, they would all be discovered without any need to factorize the polynomials gd(Z). The distinct degree factorization technique was known to several people in 1960 [cf. S. W. Golomb, L. R. Welch, A. Hales, On the factorization of trinomials over GF(2), Jet Propulsion Laboratory memo 20-189 (July 14, 1959)], but there seem to be no references to it in the open literature. Previous work by S. Schwarz, Quart. J. Math., Oxford (2) 7 (1956), 110-124, had shown how to determine the number of irreducible factors of each degree, but not their product, using the matrix Q. To complete the method, we need a way to split the polynomial gd(Z) into its irreducible factors when deg(gd) > d. Michael Rabin pointed out in 1976 that this can be done by doing arithmetic in the field of pd elements. David G. Cantor and Hans Zassenhaus discovered in 1979 that there is an even simpler way to proceed, based on the following identity: If p is any odd prime, we have asi(Z)= gcd(g&), t(s)) . gcd(g&), W(pd-1) 2 + 1) . gcd(g&), t(~)(~+)/~ -1) (21) for all polynomials t(z), since t(z) pd - t(z) is a multiple of all irreducible polyno- mials of degree d. (We may regard t(s) as an element of the held of size pd, when that field consists of all polynomials modulo an irreducible f(a;) as in exercise 16.) Now exercise 29 shows that gcd(gd(z), t(z)(pd-1)/2) will be a nontrivial factor of gd(Z) about 50 per cent of the time, when t(z) is a random polynomial of degree < 2d -1; hence it will not take long to discover all of the factors. We may assume without loss of generality that t(z) is manic, since integer multiples of t(z) make no difference except possibly to change t(~)(@- )/~ into its negative. Thus in the case d = 1, we can take t(z) = z + s, where s is chosen at random. [See SIAM J. Computing 9 (1980), 273-280; Math. Comp., to appear.] Sometimes this procedure will in fact succeed for d > 1 when only linear polynomials t(z) are used. For example, there are eight irreducible polynomials f(z) of degree 3, modulo 3, and they will all be distinguished by calculating
In case you need affordable webhost to host your website, our recommendation is ecommerce web host services.

4.6.2 FACTORIZATION OF POLYNOMIALS 429 s!*- )/~ -1 (modulo p). W e k now that exactly (p - 1)/2 of the integers s in (he range 0 < s < p satisfy .s(P- )/~ -1 (modulo p), hence about half of the pj(z) will appear in the gcd (20). More precisely, if V(X) is a random solution of (8), where all pr solutions are equally likely, the probability that the gcd (20) equals u(5) is exactly ((P -wP)r, and the probability that it equals 1 is ((p + 1)/2p)?. The probability that a nontrivial factor will be obtained is therefore 1-(~) -(~~=1-&(1+(;),-~+(;>,-~+-…), ;, for all r 2 2 and p 2 3. It is therefore a good idea to replace step B4 by the following procedure, unless p is quite small: Set w(z) t alvlll(z) + u~v[~](z) + a.. + Us&], where the coefficients aj are randomly chosen in the range 0 5 aj < p. Let the current partial factorization of U(X) be Us . . . Us where t is initially 1. Compute gi(x) = gcd(u+), v(z)(P-~) ~ -1) for all i such that deg(ui) > 1; replace ui(z) by gi(z) . (ui(z)/gi(z)) and increase the value of t, whenever a nontrivial gcd is found. Repeat this process for different choices of V(Z) until t = 7. If we assume (as we may) that only O(logr) random solutions W(Z) to (8) will be needed, we can give an upper bound on the time required to perform this alternative to step B4. It takes O(r(logp) ) steps to compute W(Z); and if deg(ui) = d, it takes O(d (logp)3) steps to compute w(z)(P-~)/~ mod Q(Z) and O(d2(logp)2) further steps to compute gcd(ui(z), w(z)(P-~)/~ -1). Thus the total time is O(n2(logp)3 logy). For further discussion, see the articles by E. R. Berlekamp, Math. Comp. 24 (1970), 713-735, and Robert T. Moenck, Math. Comp. 31 (1977), 235-250. Distinct-degree factoriaation. We shall now turn to a somewhat simpler way to find factors modulo p. The ideas we have studied so far in this section involve many instructive insights into computational algebra, so the author does not apologize to the reader for presenting them; but it turns out that the problem of factorization modulo p can actually be solved without relying on so many concepts. In the first place we can make use of the fact that an irreducible polynomial q(x) of degree d is a divisor of xPd -2, and it is not a divisor of xpc - x for c < d; see exercise 16. We can therefore cast out the irreducible factors of each degree separately, by adopting the following strategy. Dl. Rule out squared factors, as in Berlekamp s method. Also set w(x) + U(X), W(Z) t x , and d c 0. (Here w(x) and w(x) are variables that have polynomials as values.)
We would like to recommend you tested and proved virtual web hosting services, which you will surely find to be of great quality.