Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to factor a polynomial modulo p?

  1. Feb 24, 2012 #1
    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.
  2. jcsd
  3. Feb 25, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Do you have any specific questions? For general reading material, you could try googling "factoring polynomials over finite fields".
  4. Feb 25, 2012 #3
    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" [Broken]


    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?)
    Last edited by a moderator: May 5, 2017
  5. Mar 5, 2012 #4
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook