Ask Your Question
1

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

asked 2022-09-18 21:03:42 +0100

DreDd gravatar image

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

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2022-09-19 03:09:44 +0100

dazedANDconfused gravatar image

updated 2022-09-19 23:58:00 +0100

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)
edit flag offensive delete link more

Comments

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$.

rburing gravatar imagerburing ( 2022-09-19 12:43:58 +0100 )edit

Good idea! I revised code to do that.

dazedANDconfused gravatar imagedazedANDconfused ( 2022-09-19 23:58:42 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2022-09-18 21:02:39 +0100

Seen: 349 times

Last updated: Sep 19 '22