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
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
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