Talk:Factorization of polynomials

Definition of integer polynomials?

This article talks about them but doesn't explain what they are. —Preceding unsigned comment added by 69.172.124.198 (talk) 09:42, 19 November 2009 (UTC)

Title: Polynomial Factorization

Shouldn't the title of this article be Polynomial factorization? Bender2k14 (talk) 20:32, 6 April 2011 (UTC)

I think that title is less transparent. (If a word ending in –ial comes before a noun, I tend to read it as an adjective.) Why do you prefer it? —Tamfang (talk) 05:14, 7 April 2011 (UTC)

This article mentions only methods that are not actually used in computer algebra systems. Also, the section on factoring over Q(alpha) is a rewrite of Trager's method. 12 April 2012. — Preceding unsigned comment added by 71.229.31.123 (talk) 01:25, 13 April 2012 (UTC)

Kronecker's method

As for as I know, Kronecker's method is different and clever than that which is described. This should be verified on the sources. The method which is described uses implicitly Lagrange interpolation (this should be said explicitly). The Kronecker's method that I know consists in using a single value for evaluating the polynomial, which is larger than twice a bound for the magnitude of the coefficient of the factors. This is known as "Kronecker's tricks", as Kronecker remarked that, under this hypothesis, the coefficients of a factor are uniquely determined by the value of this factor, which is always positive. For the example of the article and x=12, the polynomial evaluates to 2×157×859 and there are only 3 cases to test, 2, 157 and 314. Presently, Kronecker's trick is not used for factorization, but it is used in Magma for the fast multiplication of polynomials with integer coefficients. D.Lazard (talk) 10:45, 16 September 2012 (UTC)

Daniel, the paper http://www.jstor.org/stable/2301633 describes Kronecker's method as using Lagrange interpolation, so that is consistent with the current text on wikipedia. Mark van Hoeij. — Preceding unsigned comment added by 128.186.104.253 (talk) 16:00, 6 December 2013 (UTC)

Kronecker's method is presented here as an application of the method for the factorization of an example polynomial. This treatment needs:

1. background discussion
2. when to use Kronecker's method
3. the form of the resultant factors, and
4. how the test roots are determined.

I remember from my college algebra class ages ago that Kronecker's method works best with integer coefficients and that it is best used to rational test roots. I think the test roots were of the form a0/an where a0 is an integer factor of the x^0 term and an is an integer factor of x^n, but my memory may be faulty. I know that there are also methods that can restrict the range of the search by examining the signs of the coefficients of the quotient polynomial after each test for a root. Note also that the current discussion includes, without explaining why, a quick test for roots by evaluating f(0), f(-1), and f(1). (This is because they are easy to evaluate and can save you a lot of work if you get lucky.) In short, this discussion needs expansion and clarification. --OhioFred (talk) 20:52, 23 November 2014 (UTC)

Complexity

Which is the complexity of each algorithm? 195.77.88.66 (talk) 20:26, 6 November 2013 (UTC)

For the content-primitive part factorization, it is the complexity of GCD computation in the ring of coefficients. For square free factorization, it is mentioned in the main article : less than twice the computation of the GCD of the polynomial and its derivative. For factorization of polynomials over finite fields see this article. For the lifting process, all the sections are yet lacking. D.Lazard (talk) 21:38, 6 November 2013 (UTC)

The complexity of factoring a content-free polynomial f in Z[x] is explained in http://www.math.fsu.edu/~hoeij/papers/issac13/slides.pdf Let h be the number of digits of the largest coefficient, let N be the degree, and let r be the number of factors mod p (modern factoring algorithms start with factoring f mod p, see the main page). Then the complexity is bounded by O~(r^6 + Pol(N,h)) where O~ indicates that logarithmic factors are ignored, and Pol is a polynomial whose degree is proven to be <= 5 (and conjectured to be lower still). So the term of highest degree depends solely on r; the dependence on N,h appears in terms of lower degree. MvH (talk) 01:44, 12 February 2014 (UTC)MvH

Modern methods

The quote in the introduction is interesting from a historical point of view, but if we tell the reader what the state of the art was in 1982, shouldn't we also tell them what the state of the art is in a year that starts with a 2? Nowadays you can quickly factor polynomials of degree 1000 with coefficients having thousands of digits. Mark van Hoeij. — Preceding unsigned comment added by 128.186.104.253 (talk) 16:17, 4 December 2013 (UTC)

The comment beginning "nowadays" is unclear as to time -- especially since there are no references later than 2002 -- and vague in saying "quickly" and "thousands of digits". More precision is needed. Deltahedron (talk) 18:26, 7 February 2014 (UTC)

That's true. I added a reference to a paper, it gives a table with CPU timings in 3 computer algebra systems. Degree 1000 is an understatement, the table has an example of degree 2401 that only takes 7.35 seconds.MvH —Preceding undated comment added 22:39, 9 February 2014 (UTC)

multivariate factorization

Article doesn't say much about multivariate factorization. It would be nice to have some info. Thanks! 70.36.142.114 (talk) 09:58, 16 April 2014 (UTC)

Schubert's work

"The history of polynomial factorization starts with Hermann Schubert who in 1793 described the first polynomial factorization algorithm": This cannot be true, because Hermann Schubert lived from 22 May 1848 – 20 July 1911. I think it should be Theodor von Schubert and the reference is: F. T. Schubert, De Inventione Divisorum, Nova Acta Academiae Scientiarum Petropolitanae, 11 (1793), p. 172-182, Saint-Pétersbourg, 1798. See also this paper. -- Martin B. 85.181.231.93 (talk) 17:00, 14 June 2015 (UTC)

Yes, I noticed the discrepancy in dates, and after looking at your citations it seems clear that you found the right Schubert (together with a link to earlier work by N. Bernoulli. I'll edit accordingly.Hardmath (talk) 00:26, 13 October 2017 (UTC)

Better cross reference for "typical" visitors

When a young student does a (google) web search for "factoring polynomials wikipedia", this article is the top hit. But clearly the vast majority of people doing such a search will be struggling young students, not advanced mathematicians. This article will make no sense to them and they are unlikely to even realize the importance of the deeply buried "see also" section. This article should BEGIN with a friendly cross reference for more ordinary visitors, directing them to: https://en.wikipedia.org/wiki/Factorization#Polynomials — Preceding unsigned comment added by 104.5.72.176 (talk) 17:58, 7 September 2015 (UTC)

Agreed! Considering this is a topic most young students will have questions about, the intro to this article is terrible. It reads like it's written for professionals. (The cross-ref to Factorization#Polynomials is inadequate; it's also written very badly for non-professional visitors and it just links back to *this* article as the main description!) This article needs to start with at least one plain English paragraph (as either the first or second paragraph) using only terms that would already be familiar to a high school math student who is new to the subject. It should just describe some basics like what factorization is useful for (e.g. finding roots/solving... what else?) and making analogy to factoring composite numbers into primes etc. DKEdwards (talk) 19:29, 23 January 2022 (UTC)

"Integer polynomials must factor into integer polynomial factors"(in "Kronecker's method")

Quiz: In most cases, the following polynomial

$x^{2}+bx+c$

can be decomposed into such a form

$(x+{\frac {b+{\sqrt {b^{2}-4c}}}{2}})(x+{\frac {b-{\sqrt {b^{2}-4c}}}{2}}).$

However, in some cases, it doesn't work. Can you show one of exceptional cases?

Answer: Like

$b=3,c=1.$

Because as "integer polynomials must factor into integer polynomial factors", decomposing into

$(x+{\frac {3+{\sqrt {5}}}{2}})(x+{\frac {3-{\sqrt {5}}}{2}}).$

is inhibited.

But, is the answer right? Opinions requested. Tsukitakemochi (talk) 15:54, 16 October 2021 (UTC)

This has nothing to do with Kronecker's method. However, the sentence that you have quoted is ambiguous, and the presentation of the method was confusing. I have edited the article for clarifying this. I hope this will help you. D.Lazard (talk) 20:45, 1 November 2021 (UTC)

Thanks anyway. I'm glad there was someone who understood my point. Amelioration you made shall unmistakably save numbers of students from disliking mathematics because of irrational things enforced on by his or her teachers even not from their intentions but apparently from their actual words. Tsukitakemochi (talk) 06:13, 2 November 2021 (UTC)