Ask Your Question

# 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

## Comments

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

## 1 Answer

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

## Comments

After looking at your code, I realize my error came from a Python/Sage related syntax error, not a genuine error in using the integers mod p. But thank you for the GF(p) suggestion, which helped shorten my code.

## Stats

Asked: 2016-04-05 05:59:05 +0200

Seen: 198 times

Last updated: Apr 05 '16