Generating random polynomials in R/I

asked 2014-11-19 21:31:31 +0100

amaloz
11 ●1 ●1 ●2

updated 2015-01-14 11:56:22 +0100

FrédéricC

5206 ●3 ●43 ●114

I'm trying to generate random polynomials in ring R/I. Here's an example:

P.<x> = PolynomialRing(ZZ)
R = P.quotient(x**256 + 1)
I = R.ideal(g) # for some appropriate polynomial g
S = QuotientRing(R, I)
S.random_element()

Instead of this last command outputting a polynomial, it outputs a small integer. Looking through the sage code, the QuotientRing_nc class doesn't appear to be overloading random_element, so I guess the default random_element method from the Ring class is being called, which just outputs random integers.

Is there any way to generate random polynomials in S, or is that functionality not implemented currently?

Thanks.

answered 2014-11-20 02:02:50 +0100

tmonteil
27413 ●31 ●204 ●517 http://wiki.sagemath.o...

The problem with the .random_element() methods in Sage is that the distribution is usually far from being uniform. In some cases, it is very hard to sample according to a particular distribution (even theoretically).

In this case the distribution is indeed concentrated to the integers, as it is specified in the documentation, see:

sage: S.random_element?

Note however that the elements are not integers but belong to S:

sage: S.random_element().parent()
Quotient of Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^256 + 1 by the ideal (xbar^4 - 3)
sage: S.random_element().parent() == S
True

Other distributions are not implemented for such quotient rings, so there is room for interesting development, which is more than welcome !

In the meantime, you can still do something like:

sage: S(ZZ[x].random_element(degree=256))

edit flag offensive delete link

add a comment

Your Answer

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

Generating random polynomials in R/I

1 Answer

Your Answer

Question Tools

Stats

Related questions

Generating random polynomials in R/I edit

1 Answer

Your Answer

Question Tools

Stats

Related questions

Generating random polynomials in R/I