def __init__(self, n, instance='key', m=None):
        """
        Construct LWE instance parameterised by security parameter ``n`` where
        all other parameters are chosen as in [CGW2013]_.

        INPUT:

        - ``n`` - security parameter (integer >= 89)
        - ``instance`` - one of

          - "key" - the LWE-instance that hides the secret key is generated
          - "encrypt" - the LWE-instance that hides the message is generated
            (default: ``key``)

        - ``m`` - number of allowed samples or ``None`` in which case ``m`` is
          chosen as in [CGW2013]_.  (default: ``None``)

        EXAMPLES::

            sage: from sage.crypto.lwe import UniformNoiseLWE
            sage: UniformNoiseLWE(89)
            LWE(89, 154262477, UniformSampler(0, 351), 'noise', 131)

            sage: UniformNoiseLWE(89, instance='encrypt')
            LWE(131, 154262477, UniformSampler(0, 497), 'noise', 181)
        """

        if n<89:
            raise TypeError("Parameter too small")

        n2 = n
        C  = 4/sqrt(2*pi)
        kk = floor((n2-2*log(n2, 2)**2)/5)
        n1 = floor((3*n2-5*kk)/2)
        ke = floor((n1-2*log(n1, 2)**2)/5)
        l  = floor((3*n1-5*ke)/2)-n2
        sk = ceil((C*(n1+n2))**(3/2))
        se = ceil((C*(n1+n2+l))**(3/2))
        q = next_prime(max(ceil((4*sk)**((n1+n2)/n1)), ceil((4*se)**((n1+n2+l)/(n2+l))), ceil(4*(n1+n2)*se*sk+4*se+1)))

        if kk<=0:
            raise TypeError("Parameter too small")

        if instance == 'key':
            D  = UniformSampler(0, sk-1)
            if m is None:
                m = n1
            LWE.__init__(self, n=n2, q=q, D=D, secret_dist='noise', m=m)
        elif instance == 'encrypt':
            D   = UniformSampler(0, se-1)
            if m is None:
                m = n2+l
            LWE.__init__(self, n=n1, q=q, D=D, secret_dist='noise', m=m)
        else:
            raise TypeError("Parameter instance=%s not understood."%(instance))

    def holonomy_representation(self):
        r"""
        Return the holonomy representation in `SO(2)` as two lists.

        The first list correspond to cycles around vertices, while the second
        correspond to a cycle basis that generate homology.

        EXAMPLES::

            sage: from surface_dynamics.all import *

            sage: e = '(0,1)(2,3)'
            sage: f = '(0,2,1,3)'
            sage: a = [1/2,1/2,1/2,1/2]
            sage: r = RibbonGraphWithAngles(edges=e,faces=f,angles=a)
            sage: r.holonomy_representation()
            ([0], [0, 0])

        The standard cube::

            sage: e = tuple((i,i+1) for i in xrange(0,24,2))
            sage: f = '(0,20,7,10)(16,22,19,21)(2,9,5,23)(14,3,17,1)(12,8,15,11)(18,4,13,6)'
            sage: a = [1/2]*24
            sage: r = RibbonGraphWithAngles(edges=e,faces=f,angles=a)
            sage: r.holonomy_representation()
            ([3/2, 3/2, 3/2, 3/2, 3/2, 3/2, 3/2, 3/2], [])

        Two copies of a triangle::

            sage: e = '(0,1)(2,3)(4,5)'
            sage: f = '(0,2,4)(1,5,3)'
            sage: a = [1/2,1/6,1/3,1/3,1/6,1/2]
            sage: r = RibbonGraphWithAngles(edges=e,faces=f,angles=a)
            sage: r.holonomy_representation()
            ([1, 1/2, 1/2], [])

            sage: a = [1/3,7/15,1/5,1/5,7/15,1/3]
            sage: r = RibbonGraphWithAngles(edges=e,faces=f,angles=a)
            sage: r.holonomy_representation()
            ([2/3, 2/3, 2/3], [])
        """
        from sage.functions.other import floor

        l1 = []
        for c in xrange(self.num_vertices()):
            w = self.angle_at_vertex(c)
            l1.append(w - 2*floor(w/2))

        l2 = []
        for c in self.cycle_basis():
            w = self.winding(c)
            l2.append(w - 2*floor(w/2))

        return l1,l2

def mod_one(x):
    """
    Return ``x`` mod 1.

    INPUT:

    - ``x`` -- a real number

    OUTPUT:

    ``x`` mod 1, a number in `[0,1)`.

    TESTS::

        sage: from sage.dynamics.foliations.base import mod_one
        sage: mod_one(2.5)
        0.500000000000000
        sage: mod_one(-1.7)
        0.300000000000000
        sage: mod_one(7/6)
        1/6
        sage: mod_one(-1/6)
        5/6
        sage: a = QQbar(sqrt(2)); a
        1.414213562373095?
        sage: mod_one(a)
        0.4142135623730951?

    """
    return x - floor(x)

def calcPrecisionDimension(B_cF, S):
	"""
	When calculating the Fourier expansion `a[S]` of the reduction Elliptic modular form,
	this gives the maximum precision we can calculate from a Fourier expansion `a` of
	a Hermitian modular form, where the precision of `a` is given by `B_cF`.

	See the text for details.

	Note: This is like the C++ implementation `calcPrecisionDimension()` in `algo_cpp.cpp`.
	We don't actually need this function in Python, except for testing.

	INPUT:

	- `B_cF` -- an integer: the precision of the FE of the Hermitian modular forms.

	- `S` -- the reduction matrix for `a[S]`.

	OUTPUT:

	- an integer: the precision of the FE of the Elliptic modular forms.
	"""

	assert S[0,1] == S[1,0].conjugate()
	s,t,u = S[0,0], S[0,1], S[1,1]
	s, u = QQ(s), QQ(u)
	precDim = B_cF * (min(s, u) - 2 * abs(t))
	precDim = RR(precDim)
	if precDim < 0: return 0
	precDim = floor(precDim)
	return precDim

def repr_matrix(coeffs):
    from sage.functions.other import floor
    ncols = 0
    lengths = [ ]
    for row in coeffs:
        l = len(row)
        if ncols < l:
            lengths.extend([0] * (l-ncols))
            ncols = l
        for j in range(l):
            elt = str(row[j]); l = len(elt)
            if lengths[j] < len(elt)+2:
                lengths[j] = len(elt)+2
    s = ""
    for row in coeffs:
        s += "["
        for j in range(len(row)):
            elt = str(row[j]); l = len(elt)
            nbspace = floor((lengths[j]-l)/2)
            s += " " * nbspace
            s += elt
            s += " " * (lengths[j]-l-nbspace)
        for j in range(len(row),ncols):
            s += " " * lengths[j]
        s += "]\n"
    return s[:-1]

    def iter_positive_forms_with_content(self) :
        if self.__disc is infinity :
            raise ValueError, "infinity is not a true filter index"
        
        
        if self.__reduced :        
            for a in xrange(1,isqrt(self.__disc // 3) + 1) :
                for b in xrange(a+1) :
                    g = gcd(a, b)
                    for c in xrange(a, (b**2 + (self.__disc - 1))//(4*a) + 1) :
                        yield (a,b,c), gcd(g,c)
        else :
            maxtrace = floor(5*self.__disc / 15 + sqrt(self.__disc)/2)
            for a in xrange(1, maxtrace + 1) :
                for c in xrange(1, maxtrace - a + 1) :
                    g = gcd(a,c)
                    
                    Bu = isqrt(4*a*c - 1)

                    di = 4*a*c - self.__disc
                    if di >= 0 :
                        Bl = isqrt(di) + 1 
                    else :
                        Bl = 0
                    
                    for b in xrange(-Bu, -Bl + 1) :
                        yield (a,b,c), gcd(g,b)
                    for b in xrange(Bl, Bu + 1) :
                        yield (a,b,c), gcd(g,b)
        #! if self.__reduced

        raise StopIteration

 def calc_prec():
     if self.prec != None:
         return self.prec
     iv0 = IntuitiveAbel(self.bsym,self.N-1,iprec=self.iprec,x0=self.x0sym)
     self.iv0 = iv0
     self.err = abs(iv0.sexp(0.5) - self.sexp(0.5))
     print "err:", self.err.n(20)
     self.prec = floor(-log(self.err)/log(2.0))

	def normalize_aws(self):
		"""Arizona Winter School filtration (for families) -- reduces the j-th moment modulo p^(floor((N+1-j)*(p-2)/(p-1))"""
		p=self.p
		N=self.num_moments()
		assert self.valuation() >= 0, "moments not integral in normalization"
		
		v=vector([self.moment(j)%(p**(floor((N+1-j)*(p-2)/(p-1)))) for j in range(0,self.num_moments())])	
		return dist(self.p,self.weight,v)

	def divmod(self, a, b):
		"""
		Returns q,r such that a = q*b + r.
		This is division with remainder.
		It holds that `self.euclidean_func(r) < `self.euclidean_func(b)`.
		"""
		# Note that this implementation is quite naive!
		# Later, we can do better with QuadraticForm(...). (TODO)
		# Also, read here: http://www.fen.bilkent.edu.tr/~franz/publ/survey.pdf

		if b == 0: raise ZeroDivisionError
		a1,a2 = self.as_tuple_b(a)
		b1,b2 = self.as_tuple_b(b)

		#B = matrix([
		#	[b1, -b2 * (self.D**2 - self.D)/4],
		#	[b2, b1 + b2*self.D]
		#])
		Bdet = b1*b1 + b1*b2*self.D + b2*b2*(self.D**2 - self.D)/4
		Bdet = _simplify(Bdet)
		assert Bdet > 0
		qq1 = (a1*b1 + a1*b2*self.D + a2*b2*(self.D**2 - self.D)/4) / Bdet
		qq2 = (-a1*b2 + a2*b1) / Bdet
		assert _simplify(self.from_tuple_b(qq1,qq2) * b - a) == 0

		# Not sure on this.
		# From qq1 and qq2, we want to select q1,q2 \in \Z such that
		# `r = a - q * b` is minimal with regards to `self.euclidean_func`,
		# where `q = self.from_tuple_b(q1,q2)`.
		# Simply using `round` will not work in all cases; neither does `floor`.
		# Many test cases are (indirectly) in `test_solveR()`.
		# Now we are just checking multiple possibilities and use
		# the smallest one. Note that these are not all possible cases.
		solutions = []
		for q1 in [int(floor(qq1)) + i for i in [-1,0,1,2]]:
			for q2 in [int(floor(qq2)) + i for i in [-1,0,1,2]]:
				q = self.from_tuple_b(q1,q2)
				# q * b + r == a
				r = _simplify(a - q * b)
				euc_r = self.euclidean_func(r)
				solutions += [(euc_r, q, r)]
		euc_b = self.euclidean_func(b)
		euc_r, q, r = min(solutions)
		assert euc_r < euc_b, "%r < %r; r=%r, b=%r, a=%r" % (euc_r, euc_b, r, b, a)
		return q, r

 def calc_prec(self):
     if self.prec != None:
         return self.prec
     iv0 = IntuitiveTetration(self.bsym,self.N-1,iprec=self.iprec,x0=self.x0sym)
     self.iv0 = iv0
     d = lambda x: self.slog(x) - iv0.slog(x)
     maximum = find_maximum_on_interval(d,0,1,maxfun=20)
     minimum = find_minimum_on_interval(d,0,1,maxfun=20)
     print "max:", maximum[0].n(20), 'at:', maximum[1]
     print "min:", minimum[0].n(20), 'at:', minimum[1]
     self.err = max( abs(maximum[0]), abs(minimum[0]))
     print "slog err:", self.err.n(20)
     self.prec = floor(-self.err.log(2))
     
     self.sexp_err = abs(iv0.sexp(0.5) - self.sexp(0.5))
     print "sexp err:", self.sexp_err.n(20)
     self.sexp_prec = floor(-log(self.sexp_err)/log(2.0))
     return self

    def _transposition_to_reduced_word(self, t):
        r"""
        Converts the transposition `t = [r,s]` to a reduced word.

        INPUT:

        - a tuple `[r,s]` such that `r` and `s` are not equivalent mod `k`

        OUTPUT:

        - a list of integers in `\{0,1,\ldots,k-1\}` representing a reduced word for the transposition `t`

        EXAMPLE::

            sage: c = Core([],4)
            sage: c._transposition_to_reduced_word([2, 5])
            [2, 3, 0, 3, 2]
            sage: c._transposition_to_reduced_word([2, 5]) == c._transposition_to_reduced_word([5,2])
            True
            sage: c._transposition_to_reduced_word([2, 2])
            Traceback (most recent call last):
            ...
            ValueError: t_0 and t_1 cannot be equal mod k

            sage: c = Core([],30)
            sage: c._transposition_to_reduced_word([4, 12])
            [4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 5, 4]

            sage: c = Core([],3)
            sage: c._transposition_to_reduced_word([4, 12])
            [1, 2, 0, 1, 2, 0, 2, 1, 0, 2, 1]
        """
        k = self.k()
        if (t[0] - t[1]) % k == 0:
            raise ValueError("t_0 and t_1 cannot be equal mod k")
        if t[0] > t[1]:
            return self._transposition_to_reduced_word([t[1], t[0]])
        else:
            return [i % k for i in range(t[0], t[1] - floor((t[1] - t[0]) / k))] + [
                (t[1] - floor((t[1] - t[0]) / k) - 2 - i) % (k)
                for i in range(t[1] - floor((t[1] - t[0]) / k) - t[0] - 1)
            ]

 def calc_diff(self,iv0,debug=0):
     self.prec=None
     iv0.prec=None
     d = lambda x: self.abel(x) - iv0.abel(x)
     a = find_root(lambda x: (self.f(x)+x)/2-self.x0,self.x0-100,self.f(self.x0))
     maximum = find_maximum_on_interval(d,self.x0-a,self.x0+self.f(a),maxfun=20)
     minimum = find_minimum_on_interval(d,self.x0-a,self.x0+self.f(a),maxfun=20)
     if debug>=1: print "max:", maximum[0].n(20), 'at:', maximum[1]
     if debug>=1: print "min:", minimum[0].n(20), 'at:', minimum[1]
     self.err = max( abs(maximum[0]), abs(minimum[0]))
     print "err:", self.err.n(20)
     self.prec = floor(-self.err.log(2))

 def find_integral_max(real_max, f):
     """Given a real (local) maximum of a function `f`, return that of
     the integers around `real_max` which gives the (local) integral
     maximum, and the value of at that point."""
     if real_max in ZZ:
         int_max = Integer(real_max)
         return (int_max, f(int_max))
     else:
         x_f = floor(real_max)
         x_c = x_f + 1
         f_f, f_c = f(x_f), f(x_c)
         return (x_f, f_f) if f_f >= f_c else (x_c, f_c)

 def log(self,workprec=Infinity):
     from sage.functions.log import log
     from sage.functions.other import floor
     if workprec is Infinity:
         raise ApproximationError("unable to compute log to infinite precision")
     parent = self.parent()
     pow = parent(-1)
     res = parent(0)
     t = parent(1) - self
     iter = workprec + floor(log(workprec)/log(parent._p)) + 1
     for i in range(1,iter):
         pow *= t
         res += pow / parent(i)
         res = res.truncate(workprec)
     return res

def ligt(x):
    r"""
    Returns the least integer greater than ``x``.

    EXAMPLES::

        sage: from sage.coding.guruswami_sudan.utils import ligt
        sage: ligt(41)
        42

    It works with any type of numbers (not only integers)::

        sage: ligt(41.041)
        42
    """
    return floor(x+1)

def trunc(i):
    """
    Truncates to the integer closer to zero

    EXAMPLES::

        sage: from sage.combinat.crystals.tensor_product import trunc
        sage: trunc(-3/2), trunc(-1), trunc(-1/2), trunc(0), trunc(1/2), trunc(1), trunc(3/2)
        (-1, -1, 0, 0, 0, 1, 1)
        sage: isinstance(trunc(3/2), Integer)
        True
    """
    if i>= 0:
        return floor(i)
    else:
        return ceil(i)

    def P(self, x, y):
        """
        Returns the Kazhdan-Lusztig P polynomial.

        If the rank is large, this runs slowly at first but speeds up
        as you do repeated calculations due to the caching.

        INPUT:

        - ``x``, ``y`` -- elements of the underlying Coxeter group

        .. SEEALSO::

            :mod:`~sage.libs.coxeter3.coxeter_group.CoxeterGroup.kazhdan_lusztig_polynomial`
            for a faster implementation using Fokko Ducloux's Coxeter3 C++ library.

        EXAMPLES ::

            sage: R.<q>=QQ[]
            sage: W = WeylGroup("A3", prefix="s")
            sage: [s1,s2,s3]=W.simple_reflections()
            sage: KL = KazhdanLusztigPolynomial(W, q)
            sage: KL.P(s2,s2*s1*s3*s2)
            q + 1
        """
        if x == 1:
            x = self._one
        if y == 1:
            y = self._one
        if x == y:
            return self._base_ring.one()
        if not x.bruhat_le(y):
            return self._base_ring.zero()
        if y.length() == 0:
            if x.length() == 0:
                return self._base_ring.one()
            else:
                return self._base_ring.zero()
        p = sum(-self.R(x,t)*self.P(t,y) for t in self._coxeter_group.bruhat_interval(x,y) if t != x)
        tr = floor((y.length()-x.length()+1)/2)
        try:
            ret = p.truncate(tr)
        except StandardError:
            ret = laurent_polynomial_truncate(p, tr)
        if self._trace:
            print "    P(%s,%s)=%s"%(x, y, ret)
        return ret

    def __call__(self, x):
        """
        Returns `self(x)`

        INPUT:

        - ``x`` -- a real number

        OUTPUT:

        The value of this Newton polygon at abscissa `x`

        EXAMPLES:

            sage: from sage.geometry.newton_polygon import NewtonPolygon
            sage: NP = NewtonPolygon([ (0,0), (1,1), (3,6) ]); NP
            Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 6)

            sage: [ NP(i) for i in range(4) ]
            [0, 1, 7/2, 6]
        """
        # complexity: O(log(n))
        from sage.functions.other import floor
        vertices = self.vertices()
        lastslope = self.last_slope()
        if len(vertices) == 0 or x < vertices[0][0]:
            return Infinity
        if x == vertices[0][0]:
            return vertices[0][1]
        if x == vertices[-1][0]:
            return vertices[-1][1]
        if x > vertices[-1][0]:
            return vertices[-1][1] + lastslope * (x - vertices[-1][0])
        a = 0; b = len(vertices)
        while b - a > 1:
            c = floor((a+b)/2)
            if vertices[c][0] < x:
                a = c
            else:
                b = c
        (xg,yg) = vertices[a]
        (xd,yd) = vertices[b]
        return ((x-xg)*yd + (xd-x)*yg) / (xd-xg)

def gilt(x):
    r"""
    Returns the greatest integer smaller than ``x``.

    EXAMPLES::

        sage: from sage.coding.guruswami_sudan.utils import gilt
        sage: gilt(43)
        42

    It works with any type of numbers (not only integers)::

        sage: gilt(43.041)
        43
    """
    if x in ZZ:
        return Integer(x-1)
    else:
        return floor(x)

 def _repr_(self,model):
     from sage.functions.other import floor
     l = [ ]
     maxlen = self.ncols() * [0]
     for i in range(self.nrows()):
         lp = [ ]
         for j in range(self.ncols()):
             s = self[i,j].__repr__()
             if len(s) > maxlen[j]: maxlen[j] = len(s)
             lp.append(s)
         l.append(lp)
     s = ""
     for i in range(self.nrows()):
         s += "["
         lp = l[i]
         for j in range(self.ncols()):
             length = len(lp[j]) 
             nbspace = floor((maxlen[j]-length) / 2)
             s += (nbspace + 1)*" " + lp[j] + (maxlen[j] - length - nbspace + 1)*" "
         s += "]\n"
     return s[:-1]