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