#15915: add discrete Gaussian samplers to Sage
-------------------------------------------------+-------------------------
Reporter: malb | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: statistics | Resolution:
Keywords: sd59 | Merged in:
Authors: Martin Albrecht | Reviewers: Julian
Report Upstream: N/A | Rueth
Branch: | Work issues:
caa8ccf49a6ffd2794fd13f0933c47d26336ecbc | Commit:
Dependencies: | Stopgaps:
-------------------------------------------------+-------------------------
Comment (by malb):
Replying to [comment:56 nbruin]:
> The name `DiscreteGaussianIntegerSampler` might be a bit confusing to
some people: at first reading it seems you're sampling from the Gaussian
integers (which are discrete).
> Wouldn't `DiscreteGaussianDistributionSampler` be a more descriptive
name? I get the impression that Discrete Gaussian Distribution is normally
used for the distributions on the integers you're referring to.
The name was chosen to allow for samplers over lattices and polynomial
rings as well: `DiscreteGaussianLatticeSampler` and
`DiscreteGaussianPolynomialSampler`.
I can change it to `DiscreteGaussianDistributionIntegerSampler` or
something if I get a commitment that this change is reviewed in a timely
fashion. This patch has had a hard time getting reviewed so I am not
opening it up again lightly.
> The fact that you truncate at `tau*sigma` also seems to disqualify this
from legitimately being called "sampling from a discrete gaussian
distribution", but I hope this is standard abuse of terminology in the
field (and the difference is hard to see).
The difference is hard to see due to the tail bound. Roughly: Pr[x <- D |
|x| > C*sigma] <= 2/(C sqrt(2*pi)) * exp(-C^2^/2). This is also the
standard approach in the literature.
> It also suggests that if the rejection rate is high (it would be for
larger values of `tau`) it might be worth sampling from a binomial
distribution with adapted rejection rates. The shape should be much closer
to your desired distribution and hence should lead to a much lower
rejection rate. It depends a bit on whether the new rejection
probabilities are sufficiently easy to compute to be worth it.
Sampling from other distributions has been considered in the literature.
The "sigma2+logtable" algorithm is a result of such an investigation in:
[DDLL13] Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim
Lyubashevsky. *Lattice Signatures and Bimodal Gaussians*; in Advances
in
Cryptology – CRYPTO 2013; Lecture Notes in Computer Science Volume
8042,
2013, pp 40-56 http://www.di.ens.fr/~lyubash/papers/bimodal.pdf
--
Ticket URL: <http://trac.sagemath.org/ticket/15915#comment:57>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
