# 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 != 1 or abs(L)>9 or abs(L)>10 or f.is_irreducible() == False:
f = R.random_element(2)
L = f.list()
print(f)


L 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)>9 or abs(L)>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$.