Loop over integers mod p [closed]

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

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?

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

Comments

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

slelievre ( 2016-04-05 12:10:34 +0200 )edit

add a comment

answered 2016-04-05 13:23:42 +0200

slelievre
17654 ●22 ●160 ●348 http://carva.org/samue...

updated 2016-04-05 13:25:49 +0200

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

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.

Supersingularity ( 2016-04-05 20:18:42 +0200 )edit

add a comment

Loop over integers mod p [closed]

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

Comments

1 Answer

Comments

Question Tools

Stats

Related questions

Loop over integers mod p [closed] edit

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

Comments

1 Answer

Comments

Question Tools

Stats

Related questions

Loop over integers mod p [closed]

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