# Loop over integers mod p [closed]

What is the most efficient way to factor a polynomial mod $p$ for various $p$ all at once, perhaps to be assembled into a table with more fancy code?

For example, suppose I want to factor $x^2-17 mod p$ for the first 100 primes. My first guess is to type out the proper code to factor $x^2-17$ over the ring Integers(i) where i runs through an appropriate prime_range. But Sage says I am not allowed to put a variable into Integers(). So what is the best way to do this?

edit retag reopen merge delete

### Closed for the following reason the question is answered, right answer was accepted by Supersingularity close date 2016-04-05 13:19:04.881841

Please provide the code you are trying and the error you are getting.

( 2016-04-05 05:10:34 -0500 )edit

Sort by » oldest newest most voted

It would be interesting to know what code you tried and what error you got.

This would allow to explain precisely what failed in what you tried and why.

The following works for me.

sage: for p in primes_first_n(100):
....:     x = polygen(GF(p))
....:     print("%4d %s" %(p, (x^2 - 17).factor()))
....:


This runs through the first 100 primes, and for each of them declares x as the generator for a polynomial ring over the finite field with p elements, and prints out the factorization of the polynomial x^2 - 17 in that ring.

Note that Zmod(p) or Integers(p) creates the ring of integers modulo p, considered with its ring structure, while GF(p) (for Galois Field) creates it as a field.

more