From: Nigel.Smart@cm.cf.ac.uk (Nigel Smart) Newsgroups: sci.math.research Subject: Another Complexity Question Date: Wed, 15 Feb 1995 10:44:12 +0000 Keywords: Number Theory, Complexity It is well known that finding an integral basis of a number field is polynomial time equivalent to finding the largest square free factor of the discriminant of a generating polynomial. As no algorithm to find the largest square free factor exists the best one can do is factor the whole of the discriminant. What I would like is the complexity of factoring a polynomial p-adically (with degree fixed). There seems two ways of going about this... Method 1 Factor discriminant of polynomial. For each prime divisor apply ROUND 4. This will give a p-maximal overorder and a p-adic factorization of the polynomial. Method 2 Factor discriminant of polynomial. For each prime divisor apply ROUND 2. Then apply Exercise 9 p 357 of Cohens book to find a p-adic factorization. Question Which is the fastest ? (Method 1 surely ?) What is the complexity ? My gut feeling is the complexity is given by O(e^((ln D ( ln ln D)^2)^(1/3)))^c i.e. the complexity of GNFS. But my gut feeling was wrong on my last question on principal ideal testing. Yours (Thankfully) Nigel ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Irreducibility of Polynomials on Q Date: 6 Apr 1995 01:01:24 GMT In article <3lu8fh$fel@newsflash.concordia.ca>, Alexander Hulpke wrote: ab276@cfn.cs.dal.ca (Robert MacAusland) writes: <>I have a polynomial of degree 4 -> x^4 - 10x^2 + 1 for which I need <>to demonstrate irreducibility over Q. < , where Timothy Y Chow wrote: >In case the original writer doesn't understand the above: simply factor >the given polynomial over the complex numbers (which is easy to do: it's >a quadratic in x^2), and check by brute force that none of the roots is >rational and that no pair of factors combines to give a rational quadratic >factor. An alternative which also involves "taking all combinations..." is this: If you thought the quartic f(x) had factors in Q[x], it would have factors in Z[x], say f(x)=g(x)*h(x). Since f(0)=1, g(0) and h(0) must be +1 or -1. Replace g and h by their negatives as necessary to get g(0)=1. Since f(2)=-23, g(2) must be +-1 or +-23; switching g and h as necessary, we may assume g(2)=+-1. Thus g(x) is either +1 or +1-x respectively, plus some multiple of (x-0)(x-2). Now, f clearly has no linear factors, so these g and h must be quadratic, and thus g(x) is either 1 or 1-x plus a _constant_ multiple of x(x-2). So now try another value for x, say x=-2. We have g(-2) | f(-2)=-23, so from g(x) = ( 1 or 1-x) + c.x.(x-2) we have g(-2)= (1 or 3) + 8c. The only numbers of this form dividing -23 are 1 + 8.0 and 1 + 8.(-3). So now we know the term 1-x does not occur, and know c = 0 or -3. That is, g(x) = 1 or 1-3x(x-2). The latter does not divide f and the former is a unit. This is a completely general way to factor integer polynomials if you can factor integers. If you expect a factor of degree d, factor the values of f(n) for d+1 distinct integers; choose a factor d_n of each; use Lagrange interpolation to find a polynomial g(x) with g(n) = d_n for each n; check to see if g(x) divides f(x). If there is a factor g you'll find it in this way for some choice of the d_n. Thus factorizations of integer polynomials are more or less trivial. dave ============================================================================== Date: Wed, 12 Apr 1995 17:53:26 +0200 (MET DST) From: [Permission pending] To: Dave Rusin Subject: Re: [MUG] How to get references ("How does maple do that?") Dear Dave, > A recent thread on sci.math concerned the question of factoring integer > polynomials. I suggested one method I knew which was reasonably > efficient (factor f(n) for lots of n and then use Lagrange interpolation > to construct the possible factors) but it's not clear that this method > could possibly work as quickly as Maple seems to. This method is known as Kronecker's method, but can be traced back to an astronomer F.T. van Schubert (1793). However, I would call it rather ineffective, since its cost grows exponentially with the degree of the polynomial to be factored. Anyway, I have a question: Do you know any way to make this method somehow effective? > This prompts the following question: how does a user query Maple for a > description of the algorithm it uses for execution of commands? Obviously > one can consult the source for any routine invoked with a readlib(...) > but even with that, it is not immediately clear what the heck is going > on, mathematically speaking. Is there a function call which will report > a bibliographic reference to the mathematical work on which an algorithm > is based? Or an email address to which such requests can be forwarded? > I realize a fair amount of this is either "trivial", "ad hoc", or "trade > secret", but on the other hand, this seems like a natural and fair line > of inquiry. Try ?userinfo; In fact, userinfo gives only names of algorithms used, but then you can try to find them in the literature. What I know about and can recommend is: [1] D.E. Knuth, The Art of Computer Programming Vol. 2, Seminumerical Algorithms, Section 4.6.2 [2] E. Kaltofen, Factorization of polynomials, in: B. Buchberger et al., eds., Computer Algebra, Symbolic and Algebraic Computation (Springer, 1983) [3] A.K. Lenstra, H.W. Lenstra and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515-534. I am sorry not to know more fresh citations, I will be glad if you send me any after you find more. > Oh, and while I have your attention -- how _does_ maple factor polynomials? I would say, without any attempt to check, that some modification of the LLL algorithm [3]. Best regards, [sig deleted -- djr] ============================================================================== Date: Sun, 23 Apr 1995 13:25:24 +0800 To: rusin@math.niu.edu (Dave Rusin) From: TangSimon@cuhk.hk (Tang Simon) Subject: Re: Irreducibility of Polynomials on Q >I think the state of the art in factoring polynomials over Q - which >uses Hensel lifting -- is described in a Lenstra, Lenstra, and Lovasz >article in Mathematische Annalen about 8 years ago. They provide an >algorithm for factoring which takes an amount of time polyomial in the >number of characters needed to write down the polynomial. > >dave Dear dave, This seems not quite exact. See M. Mignotte," ... computer algebra ..", Springer-Verlag, 1992. Do you have time to study this? Don't forget to post the progress at Usenet. Regards, TangSimon@cuhk.hk