Discrete Gaussian Samplers for \(\ZZ[x]\)¶

This class realizes oracles which returns polynomials in \(\ZZ[x]\) where each coefficient is sampled independently with a probability proportional to \(\exp(-(x-c)²/(2σ²))\).

AUTHORS:

Martin Albrecht, Robert Fitzpatrick, Daniel Cabracas, Florian Göpfert, Michael Schneider: initial version

EXAMPLES:

Sage

sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: sigma = 3.0; n = 1000
sage: l = [DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 64, sigma)()
....:      for _ in range(n)]
sage: l = [vector(f).norm().n() for f in l]                                         # needs sage.symbolic
sage: from numpy import mean                                                        # needs numpy
sage: mean(l), sqrt(64)*sigma  # abs tol 5e-1                                       # needs numpy sage.symbolic
(24.0, 24.0)

Python

>>> from sage.all import *
>>> from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
>>> sigma = RealNumber('3.0'); n = Integer(1000)
>>> l = [DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(64), sigma)()
...      for _ in range(n)]
>>> l = [vector(f).norm().n() for f in l]                                         # needs sage.symbolic
>>> from numpy import mean                                                        # needs numpy
>>> mean(l), sqrt(Integer(64))*sigma  # abs tol 5e-1                                       # needs numpy sage.symbolic
(24.0, 24.0)

class sage.stats.distributions.discrete_gaussian_polynomial.DiscreteGaussianDistributionPolynomialSampler(P, n, sigma)[source]¶

Bases: SageObject

Discrete Gaussian sampler for polynomials.

EXAMPLES:

Sage

sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: p = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 3.0)()
sage: p.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: p.degree() < 8
True
sage: gs = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 3.0)
sage: [gs() for _ in range(3)]  # random
[4*x^7 + 4*x^6 - 4*x^5 + 2*x^4 + x^3 - 4*x + 7, -5*x^6 + 4*x^5 - 3*x^3 + 4*x^2 + x, 2*x^7 + 2*x^6 + 2*x^5 - x^4 - 2*x^2 + 3*x + 1]

Python

>>> from sage.all import *
>>> from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
>>> p = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(8), RealNumber('3.0'))()
>>> p.parent()
Univariate Polynomial Ring in x over Integer Ring
>>> p.degree() < Integer(8)
True
>>> gs = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(8), RealNumber('3.0'))
>>> [gs() for _ in range(Integer(3))]  # random
[4*x^7 + 4*x^6 - 4*x^5 + 2*x^4 + x^3 - 4*x + 7, -5*x^6 + 4*x^5 - 3*x^3 + 4*x^2 + x, 2*x^7 + 2*x^6 + 2*x^5 - x^4 - 2*x^2 + 3*x + 1]

__init__(P, n, sigma)[source]¶

Construct a sampler for univariate polynomials of degree n-1 where coefficients are drawn independently with standard deviation sigma.

INPUT:

P – a univariate polynomial ring over the Integers
n – number of coefficients to be sampled
sigma – coefficients \(x\) are accepted with probability proportional to \(\exp(-x²/(2σ²))\). If an object of type sage.stats.distributions.discrete_gaussian_integer.DiscreteGaussianDistributionIntegerSampler is passed, then this sampler is used to sample coefficients.

EXAMPLES:

Sage

sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: p = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 3.0)()
sage: p.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: p.degree() < 8
True
sage: gs = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 3.0)
sage: [gs() for _ in range(3)]  # random
[4*x^7 + 4*x^6 - 4*x^5 + 2*x^4 + x^3 - 4*x + 7, -5*x^6 + 4*x^5 - 3*x^3 + 4*x^2 + x, 2*x^7 + 2*x^6 + 2*x^5 - x^4 - 2*x^2 + 3*x + 1]

Python

>>> from sage.all import *
>>> from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
>>> p = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(8), RealNumber('3.0'))()
>>> p.parent()
Univariate Polynomial Ring in x over Integer Ring
>>> p.degree() < Integer(8)
True
>>> gs = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(8), RealNumber('3.0'))
>>> [gs() for _ in range(Integer(3))]  # random
[4*x^7 + 4*x^6 - 4*x^5 + 2*x^4 + x^3 - 4*x + 7, -5*x^6 + 4*x^5 - 3*x^3 + 4*x^2 + x, 2*x^7 + 2*x^6 + 2*x^5 - x^4 - 2*x^2 + 3*x + 1]

__call__()[source]¶

Return a new sample.

EXAMPLES:

Sage

sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: sampler = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 12.0)
sage: sampler().parent()
Univariate Polynomial Ring in x over Integer Ring
sage: sampler().degree() <= 7
True

Python

>>> from sage.all import *
>>> from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
>>> sampler = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], Integer(8), RealNumber('12.0'))
>>> sampler().parent()
Univariate Polynomial Ring in x over Integer Ring
>>> sampler().degree() <= Integer(7)
True