boolcrypt.findpolymodp module

Functions to search for non-binary permutation polynomials.

boolcrypt.findpolymodp.get_anf(poly, degree_extension, verbose=False)

Return the ANF over a non-binary field.

>>> p, n = 3, 2
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = 2*x**6 + 4*x**4 + 3*x**3 + x**2
>>> get_anf(poly, n, verbose=True)
irreducible: x^2 + 2*x + 2 -> x by t -> t^2 - t - 1
input_ext: x1*t + x0
poly_ext: x0*x1*t - x1^2*t + x0^2 - x0*x1 + x1^2
[x0^2 - x0*x1 + x1^2, x0*x1 - x1^2]
>>> p, n = 3, 3
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> get_anf(poly, n, verbose=False)
[x0^2 + x1*x2, -x0*x1 - x1*x2 - x2^2, x1^2 - x0*x2 + x2^2]
>>> p, n = 3, 4
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> get_anf(poly, n, verbose=False)  
[x0^2 + x2^2 - x1*x3 - x2*x3 + x3^2,
-x0*x1 - x2*x3 + x3^2, x1^2 - x0*x2 + x3^2,
-x1*x2 + x2^2 - x0*x3 - x1*x3 - x2*x3 + x3^2]

boolcrypt.findpolymodp.is_quadratic_poly(poly, degree_extension, verbose=False)

Return whether the polynomial has algebraic degree 2.

The given poly must be defined over the base field, not the extension field.

>>> p, n = 3, 2
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = 2*x**6 + 4*x**4 + 3*x**3 + x**2
>>> is_quadratic_poly(poly, n, verbose=True)
irreducible: x^2 + 2*x + 2 -> x by t -> t^2 - t - 1
input_ext: x1*t + x0
poly_ext: x0*x1*t - x1^2*t + x0^2 - x0*x1 + x1^2
degree(x0^2 - x0*x1 + x1^2) = 2
degree(x0*x1 - x1^2) = 2
True
>>> p, n = 3, 3
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> is_quadratic_poly(poly, n, verbose=False)
True
>>> p, n = 3, 4
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> is_quadratic_poly(poly, n, verbose=False)
True

boolcrypt.findpolymodp.int2basep(integer, p, bin_format=False)

Convert the given integer to its representation in base p.

>>> for i in range(0, 8): sage.all.Integer(i).bits()
[]
[1]
[0, 1]
[1, 1]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]
>>> for i in range(0, 8): int2basep(i, 2)
[0]
[1]
[0, 1]
[1, 1]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]

boolcrypt.findpolymodp.get_degd_exponents(p, degree_extension, d, verbose=False)

Return the exponents of the extension field with algebraic degree d.

>>> get_degd_exponents(3, 2, 1)
[1, 3]
>>> get_degd_exponents(3, 2, 2)
[2, 4, 6]

boolcrypt.findpolymodp.get_algebraic_degree_poly(polynomial)

Return the algebraic degree of a polynomial.

>>> p, n = 3, 2
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = 2*x**6 + 4*x**4 + 3*x**3 + x**2
>>> get_algebraic_degree_poly(poly)
2
>>> p, n = 3, 3
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> get_algebraic_degree_poly(poly)
2
>>> p, n = 3, 4
>>> ff = GF(p, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = x**2
>>> get_algebraic_degree_poly(poly)
2

boolcrypt.findpolymodp.invert_poly(polynomial)

Return the inverse of a permutation polynomial.

>>> p, n = 3, 2
>>> ff = GF(p**n, repr="int")
>>> x = PolynomialRing(ff, 'x').gen()
>>> poly = 2 * x
>>> inv_poly = invert_poly(poly)
>>> inv_poly
2*x
>>> inv_poly(poly).mod(x**(p**n) - x)
x
>>> poly = x**6 + x**4 + x**3 + x**2
>>> inv_poly = invert_poly(poly)
>>> inv_poly
2*x^6 + 2*x^4 + x^3 + 2*x^2
>>> inv_poly(poly).mod(x**(p**n) - x)
x

boolcrypt.findpolymodp.find_quadratic_krssb(p, n, terms, k=None, field_var=None, print_alg_deg_inverse=False, print_anf=False, filename=None, verbose=False, debug=False, print_time=False)

Find quadratic “rotation-symmetric” permutations over non-binary fields.

>>> p, n, terms, k = 3, 2, 2, 1
>>> find_quadratic_krssb(p, n, terms, k, verbose=True)  # smallest n
# find_quadratic_krssb(3, 2, 2, 1)
valid_exponents: [6, 4, 3, 2, 1]
get_exponents_algdeg2: [2, 4, 6]
get_exponents_algdeg1: [1, 3]
subfield: [1, 2]
recursion(x^2, 1, 3)
recursion(x^4, 1, 1)
recursion(x^6, 1, 0)
>>> p, n, terms, k = 3, 2, 4, 1
>>> find_quadratic_krssb(p, n, terms, k, verbose=False, print_alg_deg_inverse=True, print_anf=True)  # smallest binomials
# alg deg of inverse:  2
# [-x1^2 + x0 + x1, -x1]
x^6 + x^4 + x^3 + x^2
# alg deg of inverse:  2
# [-x1^2 - x0 - x1, x1]
x^6 + x^4 + 2*x^3 + x^2
# alg deg of inverse:  2
# [-x1^2 + x0, x1]
x^6 + x^4 + x^2 + x
# alg deg of inverse:  2
# [-x1^2 - x0, -x1]
x^6 + x^4 + x^2 + 2*x