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)
 

1. 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.

2. 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.

3. 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.

4. 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.

5. 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

  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
3
Views
748
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Linear and Abstract Algebra
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
877
  • Programming and Computer Science
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Programming and Computer Science
Replies
8
Views
820
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
2
Replies
36
Views
4K
Back
Top