Ask Your Question

Loop over integers mod p [closed]

asked 2016-04-04 22:59:05 -0500

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 flag offensive 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.

slelievre gravatar imageslelievre ( 2016-04-05 05:10:34 -0500 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2016-04-05 06:23:42 -0500

updated 2016-04-05 06:25:49 -0500

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.

edit flag offensive delete link more


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.

Supersingularity gravatar imageSupersingularity ( 2016-04-05 13:18:42 -0500 )edit

Question Tools


Asked: 2016-04-04 22:59:05 -0500

Seen: 69 times

Last updated: Apr 05 '16