def __init__(self, field = None):
        """
        Create a linear feedback shift cryptosystem.

        INPUT: A string monoid over a binary alphabet.

        OUTPUT:

        EXAMPLES::

            sage: E = LFSRCryptosystem(FiniteField(2))
            sage: E
            LFSR cryptosystem over Finite Field of size 2

        TESTS::

            sage: E = LFSRCryptosystem(FiniteField(2))
            sage: E == loads(dumps(E))
            True

        TODO: Implement LFSR cryptosystem for arbitrary rings. The current
        implementation is limited to the finite field of 2 elements only
        because of the dependence on binary strings.
        """
        if field is None:
           field = FiniteField(2)
        if field.cardinality() != 2:
            raise NotImplementedError("Not yet implemented.")
        S = BinaryStrings()
        P = PolynomialRing(FiniteField(2),'x')
        SymmetricKeyCryptosystem.__init__(self, S, S, None)
        self._field = field

    def test_generic_02(self):

        F = FiniteField(2**8, 'a')
        shares = [(1,1), (2,121), (3,97), (4,77), (5,29)]
        points = [(F.fetch_int(x), F.fetch_int(y)) for x,y in shares]
        p = berlekamp_welsh(5, points)
        print(p)
        print([coeff.integer_representation() for coeff in p])
        print(map(lambda x: x.integer_representation(), p))

def gfq_gap_to_sage(x, F):
    """
    INPUT:
    
    
    -  ``x`` - gap finite field element
    
    -  ``F`` - Sage finite field
    
    
    OUTPUT: element of F
    
    EXAMPLES::
    
        sage: x = gap('Z(13)')
        sage: F = GF(13, 'a')
        sage: F(x)
        2
        sage: F(gap('0*Z(13)'))
        0
        sage: F = GF(13^2, 'a')
        sage: x = gap('Z(13)')
        sage: F(x)
        2
        sage: x = gap('Z(13^2)^3')
        sage: F(x)
        12*a + 11
        sage: F.multiplicative_generator()^3
        12*a + 11
    
    AUTHOR:

    - David Joyner and William Stein
    """
    from sage.rings.finite_rings.constructor import FiniteField
    
    s = str(x)
    if s[:2] == '0*':
        return F(0)
    i1 = s.index("(")
    i2 = s.index(")")
    q  = eval(s[i1+1:i2].replace('^','**'))
    if q == F.order():
        K = F
    else:
        K = FiniteField(q, F.variable_name())
    if s.find(')^') == -1:
        e = 1
    else:
        e = int(s[i2+2:])
    if F.degree() == 1:
        g = int(gap.eval('Int(Z(%s))'%q))
    else:
        g = K.multiplicative_generator()
    return F(K(g**e))

    def test_generic_01(self):

        F = FiniteField(2**8, 'a')

        #shares = [(1, 22), (2, 82), (3, 110), (4, 218), (5, 230)]
        points = [(1, 22), (2, 82), (3, 110), (4, 219)]
        points = [(F.fetch_int(x), F.fetch_int(y)) for x,y in shares]
        p = berlekamp_welsh(1, points)
        pint = ([coeff.integer_representation() for coeff in p])
        #pint = (map(lambda x: x.integer_representation(), p))
        print(p, pint)
        assert [42,60] == pint

    def check_consistency(self, n):
        """
        Check that the pseudo-Conway polynomials of degree dividing
        `n` in this lattice satisfy the required compatibility
        conditions.

        EXAMPLES::

            sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
            sage: PCL = PseudoConwayLattice(2, use_database=False)
            sage: PCL.check_consistency(6)
            sage: PCL.check_consistency(60)  # long

        """
        p = self.p
        K = FiniteField(p**n, modulus = self.polynomial(n), names='a')
        a = K.gen()
        for m in n.divisors():
            assert (a**((p**n-1)//(p**m-1))).minimal_polynomial() == self.polynomial(m)

def BIBD_5q_5_for_q_prime_power(q):
    r"""
    Return a `(5q,5,1)`-BIBD with `q\equiv 1\pmod 4` a prime power.

    See Theorem 24 [ClaytonSmith]_.

    INPUT:

    - ``q`` (integer) -- a prime power such that `q\equiv 1\pmod 4`.

    EXAMPLES::

        sage: from sage.combinat.designs.bibd import BIBD_5q_5_for_q_prime_power
        sage: for q in [25, 45, 65, 85, 125, 145, 185, 205, 305, 405, 605]: # long time
        ....:     _ = BIBD_5q_5_for_q_prime_power(q/5)                      # long time
    """
    from sage.rings.arith import is_prime_power
    from sage.rings.finite_rings.constructor import FiniteField

    if q%4 != 1 or not is_prime_power(q):
        raise ValueError("q is not a prime power or q%4!=1.")

    d = (q-1)/4
    B = []
    F = FiniteField(q,'x')
    a = F.primitive_element()
    L = {b:i for i,b in enumerate(F)}
    for b in L:
        B.append([i*q + L[b] for i in range(5)])
        for i in range(5):
            for j in range(d):
                B.append([        i*q + L[b          ],
                          ((i+1)%5)*q + L[ a**j+b    ],
                          ((i+1)%5)*q + L[-a**j+b    ],
                          ((i+4)%5)*q + L[ a**(j+d)+b],
                          ((i+4)%5)*q + L[-a**(j+d)+b],
                          ])

    return B

    def test_01(self):
        order = 2**8
        F = FiniteField(order, 'a')
        P = PolynomialRing(F, 'x')
        n = 7
        deg = 2
        poly = F.fetch_int(42)
        for i in range(1, deg+1):
            poly += F.random_element() * P.gen()**i

        # evaluate polynomial at different points (shares)
        print(poly)
        points = [(F.fetch_int(i), poly(F.fetch_int(i))) for i in range(1, n+1)]
        points[0] = (points[0][0], points[0][1] + F.fetch_int(9))
        print(points)
        assert poly == berlekamp_welsh(deg, points)

    def __init__(self, n=7, k=3, order=2**8):
        r"""
        Sharmir secret sharing.

        EXAMPLES::

            sage: from sage.crypto.smc.shamir_ss import ShamirSS
            sage: sss = ShamirSS()
            sage: secret = 42
            sage: shares = sss.share(secret)
            sage: secret == sss.reconstruct(shares)
            True
        """
        self._k = k  # threshold
        self._n = n  # number shares
        self._order = order  # order of field

        from sage.rings.finite_rings.constructor import FiniteField
        self._F = FiniteField(self._order, 'a')
        if not self._F.is_prime_field() and not hasattr(self._F, 'fetch_int'):
            raise TypeError("field order not supported")

        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
        self._P = PolynomialRing(self._F, 'x')

def T2starGeneralizedQuadrangleGraph(q, dual=False, hyperoval=None, field=None, check_hyperoval=True):
    r"""
    Return the collinearity graph of the generalized quadrangle `T_2^*(q)`, or of its dual

    Let `q=2^k` and `\Theta=PG(3,q)`.  `T_2^*(q)` is a generalized quadrangle [GQwiki]_
    of order `(q-1,q+1)`, see 3.1.3 in [PT09]_. Fix a plane `\Pi \subset \Theta` and a
    `hyperoval <http://en.wikipedia.org/wiki/Oval_(projective_plane)#Even_q>`__
    `O \subset \Pi`. The points of `T_2^*(q):=T_2^*(O)` are the points of `\Theta`
    outside `\Pi`, and the lines are the lines of `\Theta` outside `\Pi`
    that meet `\Pi` in a point of `O`.

    INPUT:

    - ``q`` -- a power of two

    - ``dual`` -- if ``False`` (default), return the graph of `T_2^*(O)`.
      Otherwise return the graph of the dual `T_2^*(O)`.

    - ``hyperoval`` -- a hyperoval (i.e. a complete 2-arc; a set of points in the plane
      meeting every line in 0 or 2 points) in the plane of points with 0th coordinate
      0 in `PG(3,q)` over the field ``field``. Each point of ``hyperoval`` must be a length 4
      vector over ``field`` with 1st non-0 coordinate equal to 1. By default, ``hyperoval`` and
      ``field`` are not specified, and constructed on the fly. In particular, ``hyperoval``
      we build is the classical one, i.e. a conic with the point of intersection of its
      tangent lines.

    - ``field`` -- an instance of a finite field of order `q`, must be provided
      if ``hyperoval`` is provided.

    - ``check_hyperoval`` -- (default: ``True``) if ``True``,
      check ``hyperoval`` for correctness.


    EXAMPLES:

    using the built-in construction::

        sage: g=graphs.T2starGeneralizedQuadrangleGraph(4); g
        T2*(O,4); GQ(3, 5): Graph on 64 vertices
        sage: g.is_strongly_regular(parameters=True)
        (64, 18, 2, 6)
        sage: g=graphs.T2starGeneralizedQuadrangleGraph(4,dual=True); g
        T2*(O,4)*; GQ(5, 3): Graph on 96 vertices
        sage: g.is_strongly_regular(parameters=True)
        (96, 20, 4, 4)

    supplying your own hyperoval::

        sage: F=GF(4,'b')
        sage: O=[vector(F,(0,0,0,1)),vector(F,(0,0,1,0))]+map(lambda x: vector(F, (0,1,x^2,x)),F)
        sage: g=graphs.T2starGeneralizedQuadrangleGraph(4, hyperoval=O, field=F); g
        T2*(O,4); GQ(3, 5): Graph on 64 vertices
        sage: g.is_strongly_regular(parameters=True)
        (64, 18, 2, 6)

    TESTS::

        sage: F=GF(4,'b') # repeating a point...
        sage: O=[vector(F,(0,1,0,0)),vector(F,(0,0,1,0))]+map(lambda x: vector(F, (0,1,x^2,x)),F)
        sage: graphs.T2starGeneralizedQuadrangleGraph(4, hyperoval=O, field=F)
        Traceback (most recent call last):
        ...
        RuntimeError: incorrect hyperoval size
        sage: O=[vector(F,(0,1,1,0)),vector(F,(0,0,1,0))]+map(lambda x: vector(F, (0,1,x^2,x)),F)
        sage: graphs.T2starGeneralizedQuadrangleGraph(4, hyperoval=O, field=F)
        Traceback (most recent call last):
        ...
        RuntimeError: incorrect hyperoval
    """
    from sage.combinat.designs.incidence_structures import IncidenceStructure
    from sage.combinat.designs.block_design import ProjectiveGeometryDesign as PG
    from sage.modules.free_module_element import free_module_element as vector

    p, k = is_prime_power(q,get_data=True)
    if k==0 or p!=2:
       raise ValueError('q must be a power of 2')
    if field is None:
        F = FiniteField(q, 'a')
    else:
        F = field

    Theta = PG(3, 1, F, point_coordinates=1)
    Pi = set(filter(lambda x: x[0]==F.zero(), Theta.ground_set()))
    if hyperoval is None:
        O = filter(lambda x: x[1]+x[2]*x[3]==0 or (x[1]==1 and x[2]==0 and x[3]==0), Pi)
        O = set(O)
    else:
        map(lambda x: x.set_immutable(), hyperoval)
        O = set(hyperoval)
        if check_hyperoval:
            if len(O) != q+2:
                raise RuntimeError("incorrect hyperoval size")
            for L in Theta.blocks():
                if set(L).issubset(Pi):
                    if not len(O.intersection(L)) in [0,2]:
                        raise RuntimeError("incorrect hyperoval")
    L = map(lambda z: filter(lambda y: not y in O, z),
            filter(lambda x: len(O.intersection(x)) == 1, Theta.blocks()))
    if dual:
        G = IncidenceStructure(L).intersection_graph()
#.........这里部分代码省略.........

def GDD_4_2(q,existence=False,check=True):
    r"""
    Return a `(2q,\{4\},\{2\})`-GDD for `q` a prime power with `q\equiv 1\pmod{6}`.

    This method implements Lemma VII.5.17 from [BJL99] (p.495).

    INPUT:

    - ``q`` (integer)

    - ``existence`` (boolean) -- instead of building the design, return:

        - ``True`` -- meaning that Sage knows how to build the design

        - ``Unknown`` -- meaning that Sage does not know how to build the
          design, but that the design may exist (see :mod:`sage.misc.unknown`).

        - ``False`` -- meaning that the design does not exist.

    - ``check`` -- (boolean) Whether to check that output is correct before
      returning it. As this is expected to be useless (but we are cautious
      guys), you may want to disable it whenever you want speed. Set to ``True``
      by default.

    EXAMPLE::

        sage: from sage.combinat.designs.group_divisible_designs import GDD_4_2
        sage: GDD_4_2(7,existence=True)
        True
        sage: GDD_4_2(7)
        Group Divisible Design on 14 points of type 2^7
        sage: GDD_4_2(8,existence=True)
        Unknown
        sage: GDD_4_2(8)
        Traceback (most recent call last):
        ...
        NotImplementedError
    """
    if q <=1 or q%6 != 1 or not is_prime_power(q):
        if existence:
            return Unknown
        raise NotImplementedError
    if existence:
        return True

    from sage.rings.finite_rings.constructor import FiniteField as GF
    G = GF(q,'x')
    w = G.primitive_element()
    e = w**((q-1)/3)

    # A first parallel class is defined. G acts on it, which yields all others.
    first_class = [[(0,0),(1,w**i),(1,e*w**i),(1,e*e*w**i)] for i in range((q-1)/6)]

    label = {p:i for i,p in enumerate(G)}
    classes = [[[2*label[x[1]+g]+(x[0]+j)%2 for x in S]
                for S in first_class]
               for g in G for j in range(2)]

    return GroupDivisibleDesign(2*q,
                                groups = [[i,i+1] for i in range(0,2*q,2)],
                                blocks = sum(classes,[]),
                                K      = [4],
                                G      = [2],
                                check  = check,
                                copy   = False)

def hadamard_matrix_paleyII(n):
    """
    Implements the Paley type II construction.

    The Paley type II case corresponds to the case `p \cong 1 \mod{4}` for a
    prime `p` (see [Hora]_).

    EXAMPLES::

        sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(12).det()
        2985984
        sage: 12^6
        2985984

    We note that the method returns a normalised Hadamard matrix ::

        sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(12)
        [ 1  1| 1  1| 1  1| 1  1| 1  1| 1  1]
        [ 1 -1|-1  1|-1  1|-1  1|-1  1|-1  1]
        [-----+-----+-----+-----+-----+-----]
        [ 1 -1| 1 -1| 1  1|-1 -1|-1 -1| 1  1]
        [ 1  1|-1 -1| 1 -1|-1  1|-1  1| 1 -1]
        [-----+-----+-----+-----+-----+-----]
        [ 1 -1| 1  1| 1 -1| 1  1|-1 -1|-1 -1]
        [ 1  1| 1 -1|-1 -1| 1 -1|-1  1|-1  1]
        [-----+-----+-----+-----+-----+-----]
        [ 1 -1|-1 -1| 1  1| 1 -1| 1  1|-1 -1]
        [ 1  1|-1  1| 1 -1|-1 -1| 1 -1|-1  1]
        [-----+-----+-----+-----+-----+-----]
        [ 1 -1|-1 -1|-1 -1| 1  1| 1 -1| 1  1]
        [ 1  1|-1  1|-1  1| 1 -1|-1 -1| 1 -1]
        [-----+-----+-----+-----+-----+-----]
        [ 1 -1| 1  1|-1 -1|-1 -1| 1  1| 1 -1]
        [ 1  1| 1 -1|-1  1|-1  1| 1 -1|-1 -1]

    TESTS::

        sage: from sage.combinat.matrices.hadamard_matrix import (hadamard_matrix_paleyII, is_hadamard_matrix)
        sage: test_cases = [2*(x+1) for x in range(50) if is_prime_power(x) and x%4==1]
        sage: all(is_hadamard_matrix(hadamard_matrix_paleyII(n),normalized=True,verbose=True)
        ....:     for n in test_cases)
        True
    """
    q = n//2 - 1
    if not(n%2==0 and is_prime_power(q) and (q % 4 == 1)):
        raise ValueError("The order %s is not covered by the Paley type II construction." % n)

    from sage.rings.finite_rings.constructor import FiniteField
    K = FiniteField(q,'x')
    K_list = list(K)
    K_list.insert(0,K.zero())
    H = matrix(ZZ, [[(1 if (x-y).is_square() else -1)
                     for x in K_list]
                    for y in K_list])
    for i in range(q+1):
        H[0,i] = 1
        H[i,0] = 1
        H[i,i] = 0

    tr = { 0: matrix(2,2,[ 1,-1,-1,-1]),
           1: matrix(2,2,[ 1, 1, 1,-1]),
          -1: matrix(2,2,[-1,-1,-1, 1])}

    H = block_matrix(q+1,q+1,[tr[v] for r in H for v in r])

    return normalise_hadamard(H)

def OA_from_Vmt(m,t,V):
    r"""
    Return an Orthogonal Array from a `V(m,t)`

    **Definition**

    Let `q` be a prime power and let `q=mt+1` for `m,t` integers. Let `\omega`
    be a primitive element of `\mathbb{F}_q`. A `V(m,t)` vector is a vector
    `(a_1,\dots,a_{m+1}` for which, for each `1\leq k < m`, the differences

    .. MATH::

        \{a_{i+k}-a_i:1\leq i \leq m+1,i+k\neq m+2\}

    represent the `m` cyclotomic classes of `\mathbb{F}_{mt+1}` (compute subscripts
    modulo `m+2`). In other words, for fixed `k`, is
    `a_{i+k}-a_i=\omega^{mx+\alpha}` and `a_{j+k}-a_j=\omega^{my+\beta}` then
    `\alpha\not\equiv\beta \mod{m}`

    *Construction of a quasi-difference matrix from a `V(m,t)` vector*

    Starting with a `V(m,t)` vector `(a_1,\dots,a_{m+1})`, form a single column
    of length `m+2` whose first entry is empty, and whose remaining entries are
    `(a_1,\dots,a_{m+1})`. Form `t` columns by multiplying this column by the
    `t` th roots, i.e. the powers of `\omega^m`. From each of these `t` columns,
    form `m+2` columns by taking the `m+2` cyclic shifts of the column. The
    result is a `(a,m+2;1,0;t)-QDM`.

    For more information, refer to the Handbook of Combinatorial Designs
    [DesignHandbook]_.

    INPUT:

    - ``m,t`` (integers)

    - ``V`` -- the vector `V(m,t)`.

    .. SEEALSO::

        :func:`OA_from_quasi_difference_matrix`

    EXAMPLES::

        sage: _ = designs.orthogonal_array(6,46) # indirect doctest
    """
    from sage.rings.finite_rings.constructor import FiniteField
    q = m*t+1
    Fq = FiniteField(q)
    w = Fq.primitive_element()

    # Cyclic shift of a list
    cyclic_shift = lambda l,i : l[-i:]+l[:-i]

    M = []
    wm = w**m
    for i in range(t):
        L = [None]
        for e in V:
            L.append(e*wm**i)
        for ii in range(m+2):
            M.append(cyclic_shift(L,ii))

    M.append([0]*q)
    M = zip(*M)
    M = OA_from_quasi_difference_matrix(M,Fq,add_col = False)

    return M

    def polynomial(self, n):
        r"""
        Return the pseudo-Conway polynomial of degree `n` in this
        lattice.

        INPUT:

        - ``n`` -- positive integer

        OUTPUT:

        - a pseudo-Conway polynomial of degree `n` for the prime `p`.

        ALGORITHM:

        Uses an algorithm described in [HL99]_, modified to find
        pseudo-Conway polynomials rather than Conway polynomials.  The
        major difference is that we stop as soon as we find a
        primitive polynomial.

        REFERENCE:

        .. [HL99] L. Heath and N. Loehr (1999).  New algorithms for
           generating Conway polynomials over finite fields.
           Proceedings of the tenth annual ACM-SIAM symposium on
           discrete algorithms, pp. 429-437.

        EXAMPLES::

            sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
            sage: PCL = PseudoConwayLattice(2, use_database=False)
            sage: PCL.polynomial(3)
            x^3 + x + 1
            sage: PCL.polynomial(4)
            x^4 + x^3 + 1
            sage: PCL.polynomial(60)
            x^60 + x^59 + x^58 + x^55 + x^54 + x^53 + x^52 + x^51 + x^48 + x^46 + x^45 + x^42 + x^41 + x^39 + x^38 + x^37 + x^35 + x^32 + x^31 + x^30 + x^28 + x^24 + x^22 + x^21 + x^18 + x^17 + x^16 + x^15 + x^14 + x^10 + x^8 + x^7 + x^5 + x^3 + x^2 + x + 1
        """
        if n in self.nodes:
            return self.nodes[n]

        p = self.p

        if n == 1:
            f = self.ring.gen() - FiniteField(p).multiplicative_generator()
            self.nodes[1] = f
            return f

        # Work in an arbitrary field K of order p**n.
        K = FiniteField(p**n, names='a')

        # TODO: something like the following
        # gcds = [n.gcd(d) for d in self.nodes.keys()]
        # xi = { m: (...) for m in gcds }
        xi = {q: self.polynomial(n//q).any_root(K, -n//q, assume_squarefree=True)
              for q in n.prime_divisors()}

        # The following is needed to ensure that in the concrete instantiation
        # of the "new" extension all previous choices are compatible.
        _frobenius_shift(K, xi)

        # Construct a compatible element having order the lcm of orders
        q, x = xi.popitem()
        v = p**(n//q) - 1
        for q, xitem in xi.iteritems():
            w = p**(n//q) - 1
            g, alpha, beta = v.xgcd(w)
            x = x**beta * xitem**alpha
            v = v.lcm(w)

        r = p**n - 1
        # Get the missing part of the order to be primitive
        g = r // v
        # Iterate through g-th roots of x until a primitive one is found
        z = x.nth_root(g)
        root = K.multiplicative_generator()**v
        while z.multiplicative_order() != r:
            z *= root
        # The following should work but tries to create a huge list
        # whose length overflows Python's ints for large parameters
        #Z = x.nth_root(g, all=True)
        #for z in Z:
        #    if z.multiplicative_order() == r:
        #         break
        f = z.minimal_polynomial()
        self.nodes[n] = f
        return f

def BIBD_from_arc_in_desarguesian_projective_plane(n,k,existence=False):
    r"""
    Returns a `(n,k,1)`-BIBD from a maximal arc in a projective plane.

    This function implements a construction from Denniston [Denniston69]_, who
    describes a maximal :meth:`arc
    <sage.combinat.designs.bibd.BalancedIncompleteBlockDesign.arc>` in a
    :func:`Desarguesian Projective Plane
    <sage.combinat.designs.block_design.DesarguesianProjectivePlaneDesign>` of
    order `2^k`. From two powers of two `n,q` with `n<q`, it produces a
    `((n-1)(q+1)+1,n,1)`-BIBD.

    INPUT:

    - ``n,k`` (integers) -- must be powers of two (among other restrictions).

    - ``existence`` (boolean) -- whether to return the BIBD obtained through
      this construction (default), or to merely indicate with a boolean return
      value whether this method *can* build the requested BIBD.

    EXAMPLES:

    A `(232,8,1)`-BIBD::

        sage: from sage.combinat.designs.bibd import BIBD_from_arc_in_desarguesian_projective_plane
        sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
        sage: D = BIBD_from_arc_in_desarguesian_projective_plane(232,8)
        sage: BalancedIncompleteBlockDesign(232,D)
        (232,8,1)-Balanced Incomplete Block Design

    A `(120,8,1)`-BIBD::

        sage: D = BIBD_from_arc_in_desarguesian_projective_plane(120,8)
        sage: BalancedIncompleteBlockDesign(120,D)
        (120,8,1)-Balanced Incomplete Block Design

    Other parameters::

        sage: all(BIBD_from_arc_in_desarguesian_projective_plane(n,k,existence=True)
        ....:     for n,k in
        ....:       [(120, 8), (232, 8), (456, 8), (904, 8), (496, 16),
        ....:        (976, 16), (1936, 16), (2016, 32), (4000, 32), (8128, 64)])
        True

    Of course, not all can be built this way::

        sage: BIBD_from_arc_in_desarguesian_projective_plane(7,3,existence=True)
        False
        sage: BIBD_from_arc_in_desarguesian_projective_plane(7,3)
        Traceback (most recent call last):
        ...
        ValueError: This function cannot produce a (7,3,1)-BIBD

    REFERENCE:

    .. [Denniston69] R. H. F. Denniston,
       Some maximal arcs in finite projective planes.
       Journal of Combinatorial Theory 6, no. 3 (1969): 317-319.
       http://dx.doi.org/10.1016/S0021-9800(69)80095-5

    """
    q = (n-1)//(k-1)-1
    if (k % 2                 or
        q % 2                 or
        q <= k                or
        n != (k-1)*(q+1)+1    or
        not is_prime_power(k) or
        not is_prime_power(q)):
        if existence:
            return False
        raise ValueError("This function cannot produce a ({},{},1)-BIBD".format(n,k))

    if existence:
        return True

    n = k

    # From now on, the code assumes the notations of [Denniston69] for n,q, so
    # that the BIBD returned by the method will have the requested parameters.

    from sage.rings.finite_rings.constructor import FiniteField as GF
    from sage.libs.gap.libgap import libgap
    from sage.matrix.constructor import Matrix

    K   = GF(q,'a')
    one = K.one()

    # An irreducible quadratic form over K[X,Y]
    GO = libgap.GeneralOrthogonalGroup(-1,2,q)
    M  = libgap.InvariantQuadraticForm(GO)['matrix']
    M  = Matrix(M)
    M  = M.change_ring(K)
    Q  = lambda xx,yy : M[0,0]*xx**2+(M[0,1]+M[1,0])*xx*yy+M[1,1]*yy**2

    # Here, the additive subgroup H (of order n) of K mentioned in
    # [Denniston69] is the set of all elements of K of degree < log_n
    # (seeing elements of K as polynomials in 'a')

    K_iter = list(K) # faster iterations
    log_n = is_prime_power(n,get_data=True)[1]
#.........这里部分代码省略.........

def hadamard_matrix_paleyI(n, normalize=True):
    """
    Implements the Paley type I construction.

    The Paley type I case corresponds to the case `p \cong 3 \mod{4}` for a
    prime `p` (see [Hora]_).

    INPUT:

    - ``n`` -- the matrix size 

    - ``normalize`` (boolean) -- whether to normalize the result.

    EXAMPLES:

    We note that this method by default returns a normalised Hadamard matrix ::

        sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_paleyI
        sage: hadamard_matrix_paleyI(4)
        [ 1  1  1  1]
        [ 1 -1  1 -1]
        [ 1 -1 -1  1]
        [ 1  1 -1 -1]

    Otherwise, it returns a skew Hadamard matrix `H`, i.e. `H=S+I`, with
    `S=-S^\top`  ::

        sage: M=hadamard_matrix_paleyI(4, normalize=False); M
        [ 1  1  1  1]
        [-1  1  1 -1]
        [-1 -1  1  1]
        [-1  1 -1  1]
        sage: S=M-identity_matrix(4); -S==S.T
        True

    TESTS::

        sage: from sage.combinat.matrices.hadamard_matrix import is_hadamard_matrix
        sage: test_cases = [x+1 for x in range(100) if is_prime_power(x) and x%4==3]
        sage: all(is_hadamard_matrix(hadamard_matrix_paleyI(n),normalized=True,verbose=True)
        ....:     for n in test_cases)
        True
        sage: all(is_hadamard_matrix(hadamard_matrix_paleyI(n,normalize=False),verbose=True)
        ....:     for n in test_cases)
        True
    """
    p = n - 1
    if not(is_prime_power(p) and (p % 4 == 3)):
        raise ValueError("The order %s is not covered by the Paley type I construction." % n)

    from sage.rings.finite_rings.constructor import FiniteField
    K = FiniteField(p,'x')
    K_list = list(K)
    K_list.insert(0,K.zero())
    H = matrix(ZZ, [[(1 if (x-y).is_square() else -1)
                     for x in K_list]
                    for y in K_list])
    for i in range(n):
        H[i,0] = -1
        H[0,i] =  1
    if normalize:
        for i in range(n):
            H[i,i] = -1
        H = normalise_hadamard(H)
    return H

#.........这里部分代码省略.........
      returning it. As this is expected to be useless (but we are cautious
      guys), you may want to disable it whenever you want speed. Set to
      ``True`` by default.

    EXAMPLES::

        sage: H = designs.HughesPlane(9)
        sage: H
        (91,10,1)-Balanced Incomplete Block Design

    We prove in the following computations that the Desarguesian plane ``H`` is
    not Desarguesian. Let us consider the two triangles `(0,1,10)` and `(57, 70,
    59)`. We show that the intersection points `D_{0,1} \cap D_{57,70}`,
    `D_{1,10} \cap D_{70,59}` and `D_{10,0} \cap D_{59,57}` are on the same line
    while `D_{0,70}`, `D_{1,59}` and `D_{10,57}` are not concurrent::

        sage: blocks = H.blocks()
        sage: line = lambda p,q: (b for b in blocks if p in b and q in b).next()

        sage: b_0_1 = line(0, 1)
        sage: b_1_10 = line(1, 10)
        sage: b_10_0 = line(10, 0)
        sage: b_57_70 = line(57, 70)
        sage: b_70_59 = line(70, 59)
        sage: b_59_57 = line(59, 57)

        sage: set(b_0_1).intersection(b_57_70)
        {2}
        sage: set(b_1_10).intersection(b_70_59)
        {73}
        sage: set(b_10_0).intersection(b_59_57)
        {60}

        sage: line(2, 73) == line(73, 60)
        True

        sage: b_0_57 = line(0, 57)
        sage: b_1_70 = line(1, 70)
        sage: b_10_59 = line(10, 59)

        sage: p = set(b_0_57).intersection(b_1_70)
        sage: q = set(b_1_70).intersection(b_10_59)
        sage: p == q
        False

    TESTS:

    Some wrong input::

        sage: designs.HughesPlane(5)
        Traceback (most recent call last):
        ...
        EmptySetError: No Hughes plane of non-square order exists.

        sage: designs.HughesPlane(16)
        Traceback (most recent call last):
        ...
        EmptySetError: No Hughes plane of even order exists.

    Check that it works for non-prime `q`::

        sage: designs.HughesPlane(3**4)    # not tested - 10 secs
        (6643,82,1)-Balanced Incomplete Block Design
    """
    if not q2.is_square():
        raise EmptySetError("No Hughes plane of non-square order exists.")
    if q2%2 == 0:
        raise EmptySetError("No Hughes plane of even order exists.")
    q = q2.sqrt()
    K = FiniteField(q2, prefix='x', conway=True)
    F = FiniteField(q, prefix='y', conway=True)
    A = q3_minus_one_matrix(F)
    A = A.change_ring(K)
    m = K.list()
    V = VectorSpace(K, 3)
    zero = K.zero()
    one = K.one()
    points = [(x, y, one) for x in m for y in m] + \
             [(x, one, zero) for x in m] + \
             [(one, zero, zero)]
    relabel = {tuple(p):i for i,p in enumerate(points)}
    blcks = []
    for a in m:
        if a not in F or a == 1:
            # build L(a)
            aa = ~a
            l = []
            l.append(V((-a, one, zero)))
            for x in m:
                y = - aa * (x+one)
                if not y.is_square():
                    y *= aa**(q-1)
                l.append(V((x, y, one)))
            # compute the orbit of L(a)
            blcks.append([relabel[normalize_hughes_plane_point(p,q)] for p in l])
            for i in range(q2 + q):
                l = [A*j for j in l]
                blcks.append([relabel[normalize_hughes_plane_point(p,q)] for p in l])
    from bibd import BalancedIncompleteBlockDesign
    return BalancedIncompleteBlockDesign(q2**2+q2+1, blcks, check=check)

#.........这里部分代码省略.........
        sage: shares = sss.share(secret)
        sage: secret == sss.reconstruct(shares[:-2])
        True

        sage: shares[0] = (shares[0][0], shares[0][1]+1)
        sage: secret == sss.reconstruct(shares, decoder='bw')
        True

        sage: shares[1] = (shares[1][0], shares[1][1]+1)
        sage: secret == sss.reconstruct(shares, decoder='bw')
        True

        sage: shares[-1] = (shares[-1][0], shares[-1][1]+1)
        sage: secret == sss.reconstruct(shares, decoder='bw')
        False
    """
    def __init__(self, n=7, k=3, order=2**8):
        r"""
        Sharmir secret sharing.

        EXAMPLES::

            sage: from sage.crypto.smc.shamir_ss import ShamirSS
            sage: sss = ShamirSS()
            sage: secret = 42
            sage: shares = sss.share(secret)
            sage: secret == sss.reconstruct(shares)
            True
        """
        self._k = k  # threshold
        self._n = n  # number shares
        self._order = order  # order of field

        from sage.rings.finite_rings.constructor import FiniteField
        self._F = FiniteField(self._order, 'a')
        if not self._F.is_prime_field() and not hasattr(self._F, 'fetch_int'):
            raise TypeError("field order not supported")

        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
        self._P = PolynomialRing(self._F, 'x')

    ### begin module private api

    def _latex_(self):
        r"""
        Return Latex representation of self.

        EXAMPLES::

            sage: from sage.crypto.smc.shamir_ss import ShamirSS
            sage: sss=ShamirSS()
            sage: latex(sss)
            `(7,3)`-Shamir secret sharing over the field `\Bold{F}_{2^{8}}`
        """
        from sage.misc.latex import latex
        return "`({},{})`-Shamir secret sharing over the field `{}`".format(
            self._n, self._k, latex(self._F))


    def _to_GF(self, x):
        r""" 
        Convert integer representation to finite field

        INPUT:

        - ``x`` --  the integer representation to be converted.

def kirkman_triple_system(v,existence=False):
    r"""
    Return a Kirkman Triple System on `v` points.

    A Kirkman Triple System `KTS(v)` is a resolvable Steiner Triple System. It
    exists if and only if `v\equiv 3\pmod{6}`.

    INPUT:

    - `n` (integer)

    - ``existence`` (boolean; ``False`` by default) -- whether to build the
      `KTS(n)` or only answer whether it exists.

    .. SEEALSO::

        :meth:`IncidenceStructure.is_resolvable`

    EXAMPLES:

    A solution to Kirkmman's original problem::

        sage: kts = designs.kirkman_triple_system(15)
        sage: classes = kts.is_resolvable(1)[1]
        sage: names = '0123456789abcde'
        sage: to_name = lambda (r,s,t): ' '+names[r]+names[s]+names[t]+' '
        sage: rows = [join(('Day {}'.format(i) for i in range(1,8)), '   ')]
        sage: rows.extend(join(map(to_name,row), '   ') for row in zip(*classes))
        sage: print join(rows,'\n')
        Day 1   Day 2   Day 3   Day 4   Day 5   Day 6   Day 7
         07e     18e     29e     3ae     4be     5ce     6de
         139     24a     35b     46c     05d     167     028
         26b     03c     14d     257     368     049     15a
         458     569     06a     01b     12c     23d     347
         acd     7bd     78c     89d     79a     8ab     9bc

    TESTS::

        sage: for i in range(3,300,6):
        ....:     _ = designs.kirkman_triple_system(i)
    """
    if v%6 != 3:
        if existence:
            return False
        raise ValueError("There is no KTS({}) as v!=3 mod(6)".format(v))

    if existence:
        return False

    elif v == 3:
        return BalancedIncompleteBlockDesign(3,[[0,1,2]],k=3,lambd=1)

    elif v == 9:
        classes = [[[0, 1, 5], [2, 6, 7], [3, 4, 8]],
                   [[1, 6, 8], [3, 5, 7], [0, 2, 4]],
                   [[1, 4, 7], [0, 3, 6], [2, 5, 8]],
                   [[4, 5, 6], [0, 7, 8], [1, 2, 3]]]
        KTS = BalancedIncompleteBlockDesign(v,[tr for cl in classes for tr in cl],k=3,lambd=1,copy=False)
        KTS._classes = classes
        return KTS

    # Construction 1.1 from [Stinson91] (originally Theorem 6 from [RCW71])
    #
    # For all prime powers q=1 mod 6, there exists a KTS(2q+1)
    elif ((v-1)//2)%6 == 1 and is_prime_power((v-1)//2):
        from sage.rings.finite_rings.constructor import FiniteField as GF
        q = (v-1)//2
        K = GF(q,'x')
        a = K.primitive_element()
        t = (q-1)/6

        # m is the solution of a^m=(a^t+1)/2
        from sage.groups.generic import discrete_log
        m = discrete_log((a**t+1)/2, a)
        assert 2*a**m == a**t+1

        # First parallel class
        first_class = [[(0,1),(0,2),'inf']]
        b0 = K.one(); b1 = a**t; b2 = a**m
        first_class.extend([(b0*a**i,1),(b1*a**i,1),(b2*a**i,2)]
                            for i in range(t)+range(2*t,3*t)+range(4*t,5*t))
        b0 = a**(m+t); b1=a**(m+3*t); b2=a**(m+5*t)
        first_class.extend([[(b0*a**i,2),(b1*a**i,2),(b2*a**i,2)]
                            for i in range(t)])

        # Action of K on the points
        action = lambda v,x : (v+x[0],x[1]) if len(x) == 2 else x

        # relabel to integer
        relabel = {(p,x): i+(x-1)*q
                   for i,p in enumerate(K)
                   for x in [1,2]}
        relabel['inf'] = 2*q

        classes = [[[relabel[action(p,x)] for x in tr] for tr in first_class]
                   for p in K]

        KTS = BalancedIncompleteBlockDesign(v,[tr for cl in classes for tr in cl],k=3,lambd=1,copy=False)

        KTS._classes = classes
#.........这里部分代码省略.........

def v_4_1_rbibd(v,existence=False):
    r"""
    Return a `(v,4,1)`-RBIBD.

    INPUT:

    - `n` (integer)

    - ``existence`` (boolean; ``False`` by default) -- whether to build the
      design or only answer whether it exists.

    .. SEEALSO::

        - :meth:`IncidenceStructure.is_resolvable`
        - :func:`resolvable_balanced_incomplete_block_design`

    .. NOTE::

        A resolvable `(v,4,1)`-BIBD exists whenever `1\equiv 4\pmod(12)`. This
        function, however, only implements a construction of `(v,4,1)`-BIBD such
        that `v=3q+1\equiv 1\pmod{3}` where `q` is a prime power (see VII.7.5.a
        from [BJL99]_).

    EXAMPLE::

        sage: rBIBD = designs.resolvable_balanced_incomplete_block_design(28,4)
        sage: rBIBD.is_resolvable()
        True
        sage: rBIBD.is_t_design(return_parameters=True)
        (True, (2, 28, 4, 1))

    TESTS::

        sage: for q in prime_powers(2,30):
        ....:     if (3*q+1)%12 == 4:
        ....:         _ = designs.resolvable_balanced_incomplete_block_design(3*q+1,4) # indirect doctest
    """
    # Volume 1, VII.7.5.a from [BJL99]_
    if v%3 != 1 or not is_prime_power((v-1)//3):
        if existence:
            return Unknown
        raise NotImplementedError("I don't know how to build a ({},{},1)-RBIBD!".format(v,4))
    from sage.rings.finite_rings.constructor import FiniteField as GF
    q = (v-1)//3
    nn = (q-1)//4
    G = GF(q,'x')
    w = G.primitive_element()
    e = w**(nn)
    assert e**2 == -1

    first_class = [[(w**i,j),(-w**i,j),(e*w**i,j+1),(-e*w**i,j+1)]
                   for i in range(nn) for j in range(3)]

    first_class.append([(0,0),(0,1),(0,2),'inf'])

    label = {p:i for i,p in enumerate(G)}

    classes = [[[v-1 if x=