How can I determine a polynomial is irreducible in C？

  • MHB
  • Thread starter Nonad
  • Start date
  • Tags
    Polynomial
In summary, Eisenstein's irreducibility criterion is hard to apply when the coefficients are larger than 1e9, and it is not possible to know when to change x into x+a without a heuristic. Factorization theorem of real coefficient polynomials can help solve the problem.
  • #1
Nonad
2
0
Hello!(Blush)

I learned about Eisenstein's irreducibility criterion. But it's still hard for me to implement it when the integer coefficients may be as larger as 1e9.
What's more, how can I (or my computer?) know when to change x into x+a?

It really puzzles me(o_O)??
 
Technology news on Phys.org
  • #2
Nonad said:
Hello!

I learned about Eisenstein's irreducibility criterion. But it's still hard for me to implement it when the integer coefficients may be as larger as 1e9.

Welcome to MHB Nonad! (Wave)

What is the problem with such large coefficients?
If we use a [m]int64_t[/m] we support up to [m]9e18[/m].
It may become more problematic to verify primality of integers within a reasonable time, but there are some optimizations that can be done there.

Nonad said:
What's more, how can I (or my computer?) know when to change x into x+a?

It really puzzles me(o_O)??

If the criterion is satisfied, we are done.
If it is not, then the result is inconclusive.
Shifting with $x+a$, or reversing coefficients will not necessarily lead to a conclusive result.
It is just something to try so that we get conclusive results in more cases.
I'm not aware yet of a heuristic how to pick $a$.
We might simply try every $a$ from $1$ up to the highest coefficient or some such.
 
  • #3
Klaas van Aarsen said:
It is just something to try so that we get conclusive results in more cases.
I'm not aware yet of a heuristic how to pick $a$.
We might simply try every $a$ from $1$ up to the highest coefficient or some such.

Thank you very much(Blush)
Yes, you are right. I have to enumerate using Eisenstein's irreducibility criterion.
It's not acceptable for my task which includes large data and, as a sufficient condition, it may provide wrong answers.
Finally, we implemented Factorization theorem of real coefficient polynomials to solve the problem.

Thanks again(Smile)
 

FAQ: How can I determine a polynomial is irreducible in C？

What is a polynomial?

A polynomial is an algebraic expression consisting of variables and coefficients, combined using addition, subtraction, and multiplication. It can also include exponents, but not division or variables in denominators. Examples of polynomials are x^2+3x-2 and 5x^3+2x^2+7x-9.

What does it mean for a polynomial to be irreducible?

A polynomial is irreducible if it cannot be factored into two or more polynomials with lower degrees. In other words, it cannot be broken down into simpler forms.

How do I determine if a polynomial is irreducible in the complex numbers (C)?

In order for a polynomial to be irreducible in the complex numbers, it must not have any complex roots. This means that the polynomial cannot be factored into linear factors with complex coefficients. One way to check this is by using the Rational Root Theorem, which states that if a polynomial with integer coefficients has a rational root, then it must be a divisor of the constant term. By checking all possible rational roots, you can determine if the polynomial is irreducible in the complex numbers.

Can a polynomial be irreducible in some number systems but not in others?

Yes, a polynomial can be irreducible in some number systems but not in others. For example, a polynomial may be irreducible in the complex numbers but reducible in the real numbers. This is because different number systems have different sets of numbers that can be used as coefficients and roots, and some polynomials may have roots in one number system but not in another.

Are there any general methods for determining if a polynomial is irreducible in any number system?

Yes, there are some general methods for determining if a polynomial is irreducible in any number system. These include the Rational Root Theorem mentioned above, the Eisenstein's Criterion, and the Newton Polygon Method. However, these methods may not always work for every polynomial, and it may also require some trial and error to determine if a polynomial is irreducible in a specific number system.

Similar threads

Factoring polynomials with finite field coeffcients
Replies
3
Views
920
MHB The polynomial is irreducible over Q(i)
Replies
16
Views
3K
Python How can I evaluate a Chebishev polynomial in python?
Replies
3
Views
2K
I Irreducible polynomials and prime elements
Replies
5
Views
1K
MHB Showing a polynomial is irreducible
Replies
1
Views
1K
MHB The irreducible polynomial is not separable
Replies
1
Views
2K
MHB Two different algorithms for valuation of polynomial
Replies
27
Views
6K
MHB Polynomial Arithmetic in Lisp: How to Begin?
2
Replies
37
Views
9K
MHB Prove that there are infinitely many irreducible polynomials in Z5.
Replies
3
Views
3K
Finding Integer Solutions to Polynomial Equations: Can it be Done Easily?
Replies
9
Views
2K

Hot Threads

Recent Insights

Back
Top