How to factor a polynomial modulo p?


by joebohr
Tags: factor, modulo, polynomial
joebohr
joebohr is offline
#1
Feb24-12, 02:25 PM
P: 57
I can understand most of Galois Theory and Number Theory dealing with factorization and extension fields, but I always run into problems that involve factorization mod p, which I can't seem to figure out how to do. I can't find any notes anywhere either, so I was wondering if someone could give me some steps. p is prime, of course.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
morphism
morphism is offline
#2
Feb25-12, 04:33 AM
Sci Advisor
HW Helper
P: 2,020
Do you have any specific questions? For general reading material, you could try googling "factoring polynomials over finite fields".
joebohr
joebohr is offline
#3
Feb25-12, 09:55 AM
P: 57
Quote Quote by morphism View Post
Do you have any specific questions? For general reading material, you could try googling "factoring polynomials over finite fields".
I seem to have figured out how to factor mod p (in a prime field) between a couple documents:

www.science.unitn.it/~degraaf/compalg/polfact.pdf

http://www.math.uiuc.edu/~r-ash/Ant/AntChapter4.pdf

However, I'm still wondering what other types of finite fields it would be useful to factor over (am I correct in assuming that not all finite fields are prime fields?)

camilus
camilus is offline
#4
Mar5-12, 12:42 PM
P: 150

How to factor a polynomial modulo p?


You usually reduce the polynomial using the small Fermat theorem, xp [itex]\equiv[/itex] x (mod p) for every variable x that has a power greater than p-1


Register to reply

Related Discussions
Bijectivity proof concerning congruence class in F[x] modulo a fixed polynomial p(x) Calculus & Beyond Homework 3
Factor a 4th order polynomial Precalculus Mathematics Homework 4
Group isomorphism and Polynomial ring modulo ideal Linear & Abstract Algebra 4
uniform distributed modulo 1, exp factor Linear & Abstract Algebra 0
Solving polynomial congruences modulo a prime power Calculus & Beyond Homework 0