# How to randomly generate a quadratic, monic, irreducible polynomial over ring of integers ZZ with small coefficients?

In finite fields, we can use irreducible_element, is there any similar way for an integer ring?

edit retag close merge delete

Sort by » oldest newest most voted

You haven't made it clear how big integers can be and still be small. The following code can easily be modified as needed

R.<x>=ZZ[]  #ring of polynomials with integral coefficients
f = R.random_element(2) #choose polynomial from the ring with degree at most 2
L = f.list() #get the coefficients
while L[2] != 1 or abs(L[1])>9 or abs(L[0])>10 or f.is_irreducible() == False:
f = R.random_element(2)
L = f.list()
print(f)


L[2] is the coefficient of x^2, so we insist that if it isn't 1 then we throw the polynomial away. We also throw the polynomial away if the coefficient of x in absolute value is >9 or the constant (in absolute value) is >10 or the polynomial is not irreducible.

There's probably a less clunky way to do it but this works.

EDIT: following rburing comment below will mean not having to throw out so many polynomials for not being monic.

R.<x>=ZZ[]  #ring of polynomials with integral coefficients
poly = R.random_element(1) #choose polynomial from the ring with degree at most 1
f = x^2+poly
L = f.list() #get the coefficients
while abs(L[1])>9 or abs(L[0])>10 or f.is_irreducible() == False:
poly = R.random_element(1)
f = x^2+poly
L = f.list()
print(f)

more

1

Instead of generating polynomials of degree at most $d$ and throwing away all which are not monic of degree $d$, you could just start with $x^d$ and add arbitrary polynomials of degree at most $d-1$.

( 2022-09-19 12:43:58 +0200 )edit

Good idea! I revised code to do that.

( 2022-09-19 23:58:42 +0200 )edit