{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Primitive Polynomial Testing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Counting the number of primitive polynomials of degree n modulo p. The probability that a polynomial chosen at random is primitive." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def numPolynomials(p,n):\n", " # The total number of polynomials of degree n modulo p.\n", " return p ^ n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def numPrimitivePolynomials(p,n):\n", " # The number of primitive polynomials of degree n modulo p.\n", " return euler_phi( p ^ n - 1 ) / n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "def probabilityRandomPolynomialIsPrimitive(p,n):\n", " # Probability that a polynomial of degree n modulo p chosen at random is primitive.\n", " return numPrimitivePolynomials( p, n ) / numPolynomials( p, n )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Let's do a low degree example with a small modulus." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "p = 5 ; n = 4" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "625" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "numPolynomials(p,n)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "48" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "numPrimitivePolynomials(p,n)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0768" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "N(probabilityRandomPolynomialIsPrimitive(p,n),digits=3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Testing whether a is a primitive root of p" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "def isPrimRoot(a,p):\n", " # If the smallest n for which a^n = 1 is p-1, the a is a primitive root of p.\n", " if Mod(a,p) == 0:\n", " return False\n", " elif Mod(a,p).multiplicative_order() == p-1:\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isPrimRoot(3,p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3 is a primitive root of 5, thus it generates the nonzero elements of GF(5)." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3, 4, 2, 1]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[Mod(3^i,p) for i in range(1,p)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4 is not a primitive root of 5 since its order is only 2 instead of 4." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[4, 1, 4, 1]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[Mod(4^i,p) for i in range(1,p)]" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Mod(4,p).multiplicative_order()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## How to define the ring of polynomials with coefficients modulo p with generator x." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "R.=PolynomialRing(GF(p))" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Finite Field of size 5" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test if polynomials have linear factors." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def numPolynomialsWithLinearFactors(p,n):\n", " # The number of polynomials of degree n modulo p which have one or more linear factors.\n", " if n >= p:\n", " return p^n - ((p-1)^p) * p^(n-p)\n", " else:\n", " var('i')\n", " return sum( -((-1)^i) * binomial( p, i ) * p^(n-i), i, 1, n)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "def probRandomPolyHasLinearFactors(p,n):\n", " # The probability that a polynomial of degree n modulo p has one or more linear factors.\n", " if n >= p:\n", " return 1 - (1 - 1 / p)^p\n", " else:\n", " return numPolynomialsWithLinearFactors(p,n) / (p^n)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "def polynomialHasLinearFactor(f):\n", " # A test whether a polynomial of degree n modulo p has one or more linear factors.\n", " hasRoot=false\n", " for i in range(0,p):\n", " if f(i) == 0:\n", " return True\n", " return False" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### An example polynomial of low degree." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "x^4 + x^2 + 2*x + 3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = x^4 + x^2 + 2*x + 3 ; pretty_print(f)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "420" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "numPolynomialsWithLinearFactors(p,n)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.672" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "N(probRandomPolyHasLinearFactors(p,n),digits=3)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "polynomialHasLinearFactor(f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Confirm that f has no linear factors." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3, 2, 2, 4, 3]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[f(k) for k in range(0,p)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Confirm that this polynomial with two roots has indeed one or more linear factors." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "polynomialHasLinearFactor((x-2)*(x-3))" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[6, 2, 0, 0, 2]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[(k-2)*(k-3) for k in range(0,p)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Is a polynomial constant?" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "def isConstantPolynomial(f):\n", " # Get the polynomial coefficients and their number. \n", " # e.g. if f = x^4 + x^2 + 2*x + 3 then f.list() = [3, 2, 1, 0, 1] and f.list()[0] = 3.\n", " coeffList = f.list()\n", " numCoeff = len( coeffList )\n", " # Polynomial has only the constant term.\n", " if numCoeff == 1:\n", " return True\n", " else:\n", " # Do the powers x, x^2, ... have even one nonzero coefficient?\n", " hasNonZeroPowers = False\n", " for k in range(1, numCoeff):\n", " if coeffList[ k ] != 0:\n", " hasNonZeroPowers = True\n", " break\n", " return not hasNonZeroPowers" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isConstantPolynomial(f)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isConstantPolynomial(3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## How to define a quotient ring Q of polynomials modulo f(x) with generator z. Since we previously defined the generator x for the polynomial ring with coefficients over GF(p), Q will also use mod p arithmetic on the coefficients." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "Q.=R.quotient( f )" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "Univariate Quotient Polynomial Ring in z over Finite Field of size 5 with modulus x^4 + x^2 + 2*x + 3" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Powers of z modulo f(x) and p" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "def powersOfXModfp(f,n,p):\n", " # Define the quotient ring Q of polynomials modulo f(x) and p.\n", " R.=PolynomialRing(GF(p))\n", " Q.=R.quotient( f )\n", " # Compute the powers {z^0, z^p, z^2p, ..., z^(np)} modulo f(x) and p.\n", " return [z ^ (p * k) for k in range(0,n)]" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "[1, 4*z^3 + 3*z^2 + 2*z, z^3 + 4*z^2 + 3, 3*z^3 + 4*z^2 + 4*z]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "listOfPowers = powersOfXModfp(f,n,p) ; pretty_print( listOfPowers )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Irreducibility Testing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Compute Q-I where the n rows of matrix Q are the coefficients of the powers z^0, z^p, ..., z^(np) mod f(x) and p. " ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "def generateQIMatrix(f,n,p):\n", " # Define the quotient ring Q of polynomials modulo f(x) and p.\n", " R.=PolynomialRing(GF(p))\n", " Q.=R.quotient( f )\n", " # Compute the powers {z^0, z^p, z^2p, ..., z^(np)} modulo f(x) and p.\n", " # e.g. for f = x^4 + x^2 + 2*x + 3 modulo p=5, \n", " # listOfPowers = [1, 4*z^3 + 3*z^2 + 2*z, z^3 + 4*z^2 + 3, 3*z^3 + 4*z^2 + 4*z]\n", " listOfPowers = powersOfXModfp(f,n,p)\n", " # e.g. row 1 is listOfPowers[1].list() = [0, 2, 3, 4]\n", " rows = [listOfPowers[k].list() for k in range(0,n)]\n", " # Define a matrix space of n x n matrices modulo p.\n", " M = MatrixSpace(GF(p),n,n)\n", " # Load the rows.\n", " m = M.matrix( rows )\n", " # Q-I\n", " return m - matrix.identity(n)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "[0 0 0 0]\n", "[0 1 3 4]\n", "[3 0 3 1]\n", "[0 4 4 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m = generateQIMatrix(f,n,p) ; pretty_print( m )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### This is the left kernel, i.e. all vectors w satisfying w A = 0" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 1 over Finite Field of size 5\n", "Basis matrix:\n", "[1 0 0 0]" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "k = kernel(m) ; k" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m.left_nullity()" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "def hasTwoOrMoreDistinctIrreducibleFactors(f,n,p):\n", " m=generateQIMatrix(f,n,p)\n", " return m.left_nullity() >= 2" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hasTwoOrMoreDistinctIrreducibleFactors(f,n,p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Factor the expression r into distinct primes. " ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "156" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r=(p^n-1)//(p-1) ; r" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "2^2 * 3 * 13" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "factorization = factor(r) ; pretty_print( factorization )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Use // for integer divide instead of / or else we'll get a rational number type for the answer even if (p-1) divides (p^n-1)." ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type( 156 / 4 )" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type( 156 // 4 )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Distinct prime factors of r" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "def distinctPrimeFactors(r):\n", " # Factorization object. e.g. for r = 156, factor(r) = 2^2 * 3 * 13\n", " factorization = factor(r)\n", " # List of prime factors to powers. e.g. list(factor(r)) = [(2, 2), (3, 1), (13, 1)]\n", " listOfPrimesToPowers = list(factorization)\n", " # Pull out the prime factors only. e.g. [2, 3, 13]\n", " distinctPrimeFactors = [listOfPrimesToPowers[k][0] \\\n", " for k in range(0,len(listOfPrimesToPowers))]\n", " return distinctPrimeFactors" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Testing whether a polynomial f(x) modulo p is primitive." ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "def isPrimitivePolynomial( f, n, p ):\n", " # Determine if the nth degree polynomial f(x) modulo p is primitive.\n", " isPrimitive = False\n", " # Polynomial must be at least degree 2 modulo p >= 2\n", " if p < 2 or n < 2:\n", " return False\n", " print( \"Passed step 1: p = %d >=2 and n = %d >= 2\" % (p, n) )\n", " a0=f[0]\n", " if isPrimRoot( a0 * (-1)^n, p ):\n", " print( \"Passed step 2: a0 = %d is a primitive root\" % a0 )\n", " if not polynomialHasLinearFactor(f):\n", " print( \"Passed step 3: f(x) has no linear factors\" )\n", " if not hasTwoOrMoreDistinctIrreducibleFactors(f,n,p):\n", " print( \"Passed step 4: f(x) is either irreducible or irreducible ^ power\" )\n", " R.=PolynomialRing(GF(p))\n", " Q.=R.quotient( f )\n", " r=(p^n-1)//(p-1)\n", " a=z^r\n", " if isConstantPolynomial(a):\n", " print( \"Passed step 5: a = %d is constant\" % a )\n", " if a == Mod( a0 * (-1)^n, p):\n", " print( \"Passed step 6: a = a0 (-1)^n mod p where a0 = %d\" % a0 )\n", " # Tentatively say it's primitive.\n", " isPrimitive = True\n", " primes = distinctPrimeFactors(r)\n", " print( \"Begin step 7: Testing on prime factors pi\" )\n", " for k in range( 0 , len( primes )):\n", " # Skip the test for kth prime pk if (p-1) | pk\n", " if Mod( (p-1), primes[k] ) == 0:\n", " print( \" Skip step 7 test since prime pi = %d divides p-1 = %d\" \\\n", " % (primes[k], p-1) )\n", " else:\n", " # Oops! Failed the test for prime pk.\n", " if isConstantPolynomial( z^(r//primes[k]) ):\n", " print( \" Failed step 7 since x^m is an integer for prime pi = %d\" \\\n", " % primes[k] )\n", " isPrimitive = False\n", " else:\n", " print( \" Passed step 7 since x^m is not an integer for prime pi = %d\" \\\n", " % primes[k] )\n", " return isPrimitive" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A primitive polynomial generates all of the p^n - 1 nonzero field elements." ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [], "source": [ "p = 5 ; n = 4" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "x^4 + x^2 + 2*x + 2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = x^4 + x^2 + 2*x + 2 ; pretty_print( f )" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Passed step 1: p = 5 >=2 and n = 4 >= 2\n", "Passed step 2: a0 = 2 is a primitive root\n", "Passed step 3: f(x) has no linear factors\n", "Passed step 4: f(x) is either irreducible or irreducible ^ power\n", "Passed step 5: a = 2 is constant\n", "Passed step 6: a = a0 (-1)^n mod p where a0 = 2\n", "Begin step 7: Testing on prime factors pi\n", " Skip step 7 test since prime pi = 2 divides p-1 = 4\n", " Passed step 7 since x^m is not an integer for prime pi = 3\n", " Passed step 7 since x^m is not an integer for prime pi = 13\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isPrimitivePolynomial( f, n, p )" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [], "source": [ "def generateAllNonzeroFieldElements( f, n, p ):\n", " # Define the quotient ring Q of polynomials modulo f(x) and p.\n", " R.=PolynomialRing(GF(p))\n", " Q.=R.quotient( f )\n", " # A primitive polynomial f generates the nonzero elements of the field:\n", " # z^m = 1 for m = p^n - 1 but z^m != 1 for 1 <= m <= p^n - 2\n", " fieldElements = [z^m for m in range(1,p^n)]\n", " return fieldElements" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "[z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3*z + 3,\n", " 4*z^3 + 3*z^2 + 3*z,\n", " 3*z^3 + 4*z^2 + 2*z + 2,\n", " 4*z^3 + 4*z^2 + z + 4,\n", " 4*z^3 + 2*z^2 + z + 2,\n", " 2*z^3 + 2*z^2 + 4*z + 2,\n", " 2*z^3 + 2*z^2 + 3*z + 1,\n", " 2*z^3 + z^2 + 2*z + 1,\n", " z^3 + 2*z + 1,\n", " z^2 + 4*z + 3,\n", " z^3 + 4*z^2 + 3*z,\n", " 4*z^3 + 2*z^2 + 3*z + 3,\n", " 2*z^3 + 4*z^2 + 2,\n", " 4*z^3 + 3*z^2 + 3*z + 1,\n", " 3*z^3 + 4*z^2 + 3*z + 2,\n", " 4*z^3 + z + 4,\n", " 2*z^2 + z + 2,\n", " 2*z^3 + z^2 + 2*z,\n", " z^3 + z + 1,\n", " 4*z + 3,\n", " 4*z^2 + 3*z,\n", " 4*z^3 + 3*z^2,\n", " 3*z^3 + z^2 + 2*z + 2,\n", " z^3 + 4*z^2 + z + 4,\n", " 4*z^3 + 2*z + 3,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4*z + 4,\n", " 4*z^3 + 4*z^2 + 4*z,\n", " 4*z^3 + 2*z + 2,\n", " 3*z^2 + 4*z + 2,\n", " 3*z^3 + 4*z^2 + 2*z,\n", " 4*z^3 + 4*z^2 + 4*z + 4,\n", " 4*z^3 + z + 2,\n", " 2*z^2 + 4*z + 2,\n", " 2*z^3 + 4*z^2 + 2*z,\n", " 4*z^3 + z + 1,\n", " 2*z^2 + 3*z + 2,\n", " 2*z^3 + 3*z^2 + 2*z,\n", " 3*z^3 + z + 1,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4*z + 4,\n", " z^3 + 4*z^2 + 4*z,\n", " 4*z^3 + 3*z^2 + 3*z + 3,\n", " 3*z^3 + 4*z^2 + 2,\n", " 4*z^3 + 2*z^2 + z + 4,\n", " 2*z^3 + 2*z^2 + z + 2,\n", " 2*z^3 + 4*z^2 + 3*z + 1,\n", " 4*z^3 + z^2 + 2*z + 1,\n", " z^3 + 3*z^2 + 3*z + 2,\n", " 3*z^3 + 2*z^2 + 3,\n", " 2*z^3 + 2*z^2 + 2*z + 4,\n", " 2*z^3 + 1,\n", " 3*z^2 + 2*z + 1,\n", " 3*z^3 + 2*z^2 + z,\n", " 2*z^3 + 3*z^2 + 4*z + 4,\n", " 3*z^3 + 2*z^2 + 1,\n", " 2*z^3 + 2*z^2 + 4,\n", " 2*z^3 + 3*z^2 + 1,\n", " 3*z^3 + 3*z^2 + 2*z + 1,\n", " 3*z^3 + 4*z^2 + 4,\n", " 4*z^3 + 2*z^2 + 3*z + 4,\n", " 2*z^3 + 4*z^2 + z + 2,\n", " 4*z^3 + 4*z^2 + 3*z + 1,\n", " 4*z^3 + 4*z^2 + 3*z + 2,\n", " 4*z^3 + 4*z^2 + 4*z + 2,\n", " 4*z^3 + 4*z + 2,\n", " 4*z + 2,\n", " 4*z^2 + 2*z,\n", " 4*z^3 + 2*z^2,\n", " 2*z^3 + z^2 + 2*z + 2,\n", " z^3 + 3*z + 1,\n", " 2*z^2 + 4*z + 3,\n", " 2*z^3 + 4*z^2 + 3*z,\n", " 4*z^3 + z^2 + z + 1,\n", " z^3 + 2*z^2 + 3*z + 2,\n", " 2*z^3 + 2*z^2 + 3,\n", " 2*z^3 + 3*z^2 + 4*z + 1,\n", " 3*z^3 + 2*z^2 + 2*z + 1,\n", " 2*z^3 + 4*z^2 + 4,\n", " 4*z^3 + 3*z^2 + 1,\n", " 3*z^3 + z^2 + 3*z + 2,\n", " z^3 + z + 4,\n", " 2*z + 3,\n", " 2*z^2 + 3*z,\n", " 2*z^3 + 3*z^2,\n", " 3*z^3 + 3*z^2 + z + 1,\n", " 3*z^3 + 3*z^2 + 4,\n", " 3*z^3 + 2*z^2 + 3*z + 4,\n", " 2*z^3 + 3*z + 4,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3*z + 3,\n", " 3*z^2 + 3*z,\n", " 3*z^3 + 3*z^2,\n", " 3*z^3 + 2*z^2 + 4*z + 4,\n", " 2*z^3 + z^2 + 3*z + 4,\n", " z^3 + z^2 + 1,\n", " z^3 + 4*z^2 + 4*z + 3,\n", " 4*z^3 + 3*z^2 + z + 3,\n", " 3*z^3 + 2*z^2 + 2,\n", " 2*z^3 + 2*z^2 + z + 4,\n", " 2*z^3 + 4*z^2 + 1,\n", " 4*z^3 + 3*z^2 + 2*z + 1,\n", " 3*z^3 + 3*z^2 + 3*z + 2,\n", " 3*z^3 + z + 4,\n", " 3*z^2 + 3*z + 4,\n", " 3*z^3 + 3*z^2 + 4*z,\n", " 3*z^3 + z^2 + 4*z + 4,\n", " z^3 + z^2 + 3*z + 4,\n", " z^3 + 2*z^2 + 2*z + 3,\n", " 2*z^3 + z^2 + z + 3,\n", " z^3 + 4*z^2 + 4*z + 1,\n", " 4*z^3 + 3*z^2 + 4*z + 3,\n", " 3*z^3 + 2,\n", " 2*z^2 + z + 4,\n", " 2*z^3 + z^2 + 4*z,\n", " z^3 + 2*z^2 + z + 1,\n", " 2*z^3 + 4*z + 3,\n", " 2*z^2 + 4*z + 1,\n", " 2*z^3 + 4*z^2 + z,\n", " 4*z^3 + 4*z^2 + z + 1,\n", " 4*z^3 + 2*z^2 + 3*z + 2,\n", " 2*z^3 + 4*z^2 + 4*z + 2,\n", " 4*z^3 + 2*z^2 + 3*z + 1,\n", " 2*z^3 + 4*z^2 + 3*z + 2,\n", " 4*z^3 + z^2 + 3*z + 1,\n", " z^3 + 4*z^2 + 3*z + 2,\n", " 4*z^3 + 2*z^2 + 3,\n", " 2*z^3 + z^2 + 2,\n", " z^3 + 3*z^2 + 3*z + 1,\n", " 3*z^3 + 2*z^2 + 4*z + 3,\n", " 2*z^3 + z^2 + 2*z + 4,\n", " z^3 + 1,\n", " 4*z^2 + 4*z + 3,\n", " 4*z^3 + 4*z^2 + 3*z,\n", " 4*z^3 + 4*z^2 + 2*z + 2,\n", " 4*z^3 + 3*z^2 + 4*z + 2,\n", " 3*z^3 + 4*z + 2,\n", " z^2 + z + 4,\n", " z^3 + z^2 + 4*z,\n", " z^3 + 3*z^2 + 3*z + 3,\n", " 3*z^3 + 2*z^2 + z + 3,\n", " 2*z^3 + 3*z^2 + 2*z + 4,\n", " 3*z^3 + 1,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + z + 1,\n", " 2*z^3 + z^2 + z,\n", " z^3 + 4*z^2 + z + 1,\n", " 4*z^3 + 4*z + 3,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + z + 1,\n", " 3*z^3 + z^2 + z,\n", " z^3 + 3*z^2 + 4*z + 4,\n", " 3*z^3 + 3*z^2 + 2*z + 3,\n", " 3*z^3 + 4*z^2 + 2*z + 4,\n", " 4*z^3 + 4*z^2 + 3*z + 4,\n", " 4*z^3 + 4*z^2 + z + 2,\n", " 4*z^3 + 2*z^2 + 4*z + 2,\n", " 2*z^3 + 4*z + 2,\n", " 2*z^2 + 3*z + 1,\n", " 2*z^3 + 3*z^2 + z,\n", " 3*z^3 + 4*z^2 + z + 1,\n", " 4*z^3 + 3*z^2 + 4,\n", " 3*z^3 + z^2 + z + 2,\n", " z^3 + 3*z^2 + z + 4,\n", " 3*z^3 + 2*z + 3,\n", " 4*z^2 + 2*z + 4,\n", " 4*z^3 + 2*z^2 + 4*z,\n", " 2*z^3 + 2*z + 2,\n", " 3*z + 1,\n", " 3*z^2 + z,\n", " 3*z^3 + z^2,\n", " z^3 + 2*z^2 + 4*z + 4,\n", " 2*z^3 + 3*z^2 + 2*z + 3,\n", " 3*z^3 + 4*z + 1,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3*z + 3,\n", " 3*z^3 + 3*z^2 + 3*z,\n", " 3*z^3 + 4*z + 4,\n", " z^2 + 3*z + 4,\n", " z^3 + 3*z^2 + 4*z,\n", " 3*z^3 + 3*z^2 + 3*z + 3,\n", " 3*z^3 + 2*z + 4,\n", " 4*z^2 + 3*z + 4,\n", " 4*z^3 + 3*z^2 + 4*z,\n", " 3*z^3 + 2*z + 2,\n", " 4*z^2 + z + 4,\n", " 4*z^3 + z^2 + 4*z,\n", " z^3 + 2*z + 2,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3*z + 3,\n", " 2*z^3 + 3*z^2 + 3*z,\n", " 3*z^3 + z^2 + z + 1,\n", " z^3 + 3*z^2 + 4,\n", " 3*z^3 + 4*z^2 + 2*z + 3,\n", " 4*z^3 + 4*z^2 + 2*z + 4,\n", " 4*z^3 + 3*z^2 + z + 2,\n", " 3*z^3 + 2*z^2 + 4*z + 2,\n", " 2*z^3 + z^2 + z + 4,\n", " z^3 + 4*z^2 + 1,\n", " 4*z^3 + 4*z^2 + 4*z + 3,\n", " 4*z^3 + 2,\n", " z^2 + 4*z + 2,\n", " z^3 + 4*z^2 + 2*z,\n", " 4*z^3 + z^2 + 3*z + 3,\n", " z^3 + 4*z^2 + 2,\n", " 4*z^3 + 4*z^2 + 3,\n", " 4*z^3 + z^2 + 2,\n", " z^3 + z^2 + 4*z + 2,\n", " z^3 + 3*z^2 + 3,\n", " 3*z^3 + 4*z^2 + z + 3,\n", " 4*z^3 + 3*z^2 + 2*z + 4,\n", " 3*z^3 + 3*z^2 + z + 2,\n", " 3*z^3 + 3*z^2 + z + 4,\n", " 3*z^3 + 3*z^2 + 3*z + 4,\n", " 3*z^3 + 3*z + 4,\n", " 3*z + 4,\n", " 3*z^2 + 4*z,\n", " 3*z^3 + 4*z^2,\n", " 4*z^3 + 2*z^2 + 4*z + 4,\n", " 2*z^3 + z + 2,\n", " 4*z^2 + 3*z + 1,\n", " 4*z^3 + 3*z^2 + z,\n", " 3*z^3 + 2*z^2 + 2*z + 2,\n", " 2*z^3 + 4*z^2 + z + 4,\n", " 4*z^3 + 4*z^2 + 1,\n", " 4*z^3 + z^2 + 3*z + 2,\n", " z^3 + 4*z^2 + 4*z + 2,\n", " 4*z^3 + 3*z^2 + 3,\n", " 3*z^3 + z^2 + 2,\n", " z^3 + 2*z^2 + z + 4,\n", " 2*z^3 + 2*z + 3,\n", " 4*z + 1,\n", " 4*z^2 + z,\n", " 4*z^3 + z^2,\n", " z^3 + z^2 + 2*z + 2,\n", " z^3 + z^2 + 3,\n", " z^3 + 4*z^2 + z + 3,\n", " 4*z^3 + z + 3,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " z + 1,\n", " z^2 + z,\n", " z^3 + z^2,\n", " z^3 + 4*z^2 + 3*z + 3,\n", " 4*z^3 + 2*z^2 + z + 3,\n", " 2*z^3 + 2*z^2 + 2,\n", " 2*z^3 + 3*z^2 + 3*z + 1,\n", " 3*z^3 + z^2 + 2*z + 1,\n", " z^3 + 4*z^2 + 4,\n", " 4*z^3 + 4*z^2 + 2*z + 3,\n", " 4*z^3 + 3*z^2 + 2,\n", " 3*z^3 + z^2 + 4*z + 2,\n", " z^3 + z^2 + z + 4,\n", " z^3 + 2*z + 3,\n", " z^2 + z + 3,\n", " z^3 + z^2 + 3*z,\n", " z^3 + 2*z^2 + 3*z + 3,\n", " 2*z^3 + 2*z^2 + z + 3,\n", " 2*z^3 + 4*z^2 + 4*z + 1,\n", " 4*z^3 + 2*z^2 + 2*z + 1,\n", " 2*z^3 + 3*z^2 + 3*z + 2,\n", " 3*z^3 + z^2 + 3*z + 1,\n", " z^3 + 4,\n", " 4*z^2 + 2*z + 3,\n", " 4*z^3 + 2*z^2 + 3*z,\n", " 2*z^3 + 4*z^2 + 2*z + 2,\n", " 4*z^3 + 3*z + 1,\n", " 4*z^2 + 3*z + 2,\n", " 4*z^3 + 3*z^2 + 2*z,\n", " 3*z^3 + 3*z^2 + 2*z + 2,\n", " 3*z^3 + 4*z^2 + z + 4,\n", " 4*z^3 + 3*z^2 + 3*z + 4,\n", " 3*z^3 + 4*z^2 + z + 2,\n", " 4*z^3 + 3*z^2 + z + 4,\n", " 3*z^3 + 2*z^2 + z + 2,\n", " 2*z^3 + 3*z^2 + z + 4,\n", " 3*z^3 + 4*z^2 + 1,\n", " 4*z^3 + 2*z^2 + 4,\n", " 2*z^3 + z^2 + z + 2,\n", " z^3 + 4*z^2 + 3*z + 1,\n", " 4*z^3 + 2*z^2 + 4*z + 3,\n", " 2*z^3 + 2,\n", " 3*z^2 + 3*z + 1,\n", " 3*z^3 + 3*z^2 + z,\n", " 3*z^3 + 3*z^2 + 4*z + 4,\n", " 3*z^3 + z^2 + 3*z + 4,\n", " z^3 + 3*z + 4,\n", " 2*z^2 + 2*z + 3,\n", " 2*z^3 + 2*z^2 + 3*z,\n", " 2*z^3 + z^2 + z + 1,\n", " z^3 + 4*z^2 + 2*z + 1,\n", " 4*z^3 + z^2 + 4*z + 3,\n", " z^3 + 2,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2*z + 2,\n", " 4*z^3 + 2*z^2 + 2*z,\n", " 2*z^3 + 3*z^2 + 2*z + 2,\n", " 3*z^3 + 3*z + 1,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2*z + 2,\n", " z^3 + 2*z^2 + 2*z,\n", " 2*z^3 + z^2 + 3*z + 3,\n", " z^3 + z^2 + 4*z + 1,\n", " z^3 + 3*z^2 + 4*z + 3,\n", " 3*z^3 + 3*z^2 + z + 3,\n", " 3*z^3 + 3*z^2 + 2*z + 4,\n", " 3*z^3 + 4*z^2 + 3*z + 4,\n", " 4*z^3 + 3*z + 4,\n", " 4*z^2 + z + 2,\n", " 4*z^3 + z^2 + 2*z,\n", " z^3 + 3*z^2 + 2*z + 2,\n", " 3*z^3 + z^2 + 3,\n", " z^3 + 2*z^2 + 2*z + 4,\n", " 2*z^3 + z^2 + 2*z + 3,\n", " z^3 + 4*z + 1,\n", " 3*z^2 + 4*z + 3,\n", " 3*z^3 + 4*z^2 + 3*z,\n", " 4*z^3 + 4*z + 4,\n", " z + 2,\n", " z^2 + 2*z,\n", " z^3 + 2*z^2,\n", " 2*z^3 + 4*z^2 + 3*z + 3,\n", " 4*z^3 + z^2 + 4*z + 1,\n", " z^3 + 3*z + 2,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + z + 1,\n", " z^3 + z^2 + z,\n", " z^3 + 3*z + 3,\n", " 2*z^2 + z + 3,\n", " 2*z^3 + z^2 + 3*z,\n", " z^3 + z^2 + z + 1,\n", " z^3 + 4*z + 3,\n", " 3*z^2 + z + 3,\n", " 3*z^3 + z^2 + 3*z,\n", " z^3 + 4*z + 4,\n", " 3*z^2 + 2*z + 3,\n", " 3*z^3 + 2*z^2 + 3*z,\n", " 2*z^3 + 4*z + 4,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + z + 1,\n", " 4*z^3 + z^2 + z,\n", " z^3 + 2*z^2 + 2*z + 2,\n", " 2*z^3 + z^2 + 3,\n", " z^3 + 3*z^2 + 4*z + 1,\n", " 3*z^3 + 3*z^2 + 4*z + 3,\n", " 3*z^3 + z^2 + 2*z + 4,\n", " z^3 + 4*z^2 + 3*z + 4,\n", " 4*z^3 + 2*z^2 + 2*z + 3,\n", " 2*z^3 + 3*z^2 + 2,\n", " 3*z^3 + 3*z^2 + 3*z + 1,\n", " 3*z^3 + 4,\n", " 2*z^2 + 3*z + 4,\n", " 2*z^3 + 3*z^2 + 4*z,\n", " 3*z^3 + 2*z^2 + z + 1,\n", " 2*z^3 + 3*z^2 + 4,\n", " 3*z^3 + 3*z^2 + 1,\n", " 3*z^3 + 2*z^2 + 4,\n", " 2*z^3 + 2*z^2 + 3*z + 4,\n", " 2*z^3 + z^2 + 1,\n", " z^3 + 3*z^2 + 2*z + 1,\n", " 3*z^3 + z^2 + 4*z + 3,\n", " z^3 + z^2 + 2*z + 4,\n", " z^3 + z^2 + 2*z + 3,\n", " z^3 + z^2 + z + 3,\n", " z^3 + z + 3,\n", " z + 3,\n", " z^2 + 3*z,\n", " z^3 + 3*z^2,\n", " 3*z^3 + 4*z^2 + 3*z + 3,\n", " 4*z^3 + 2*z + 4,\n", " 3*z^2 + z + 2,\n", " 3*z^3 + z^2 + 2*z,\n", " z^3 + 4*z^2 + 4*z + 4,\n", " 4*z^3 + 3*z^2 + 2*z + 3,\n", " 3*z^3 + 3*z^2 + 2,\n", " 3*z^3 + 2*z^2 + z + 4,\n", " 2*z^3 + 3*z^2 + 3*z + 4,\n", " 3*z^3 + z^2 + 1,\n", " z^3 + 2*z^2 + 4,\n", " 2*z^3 + 4*z^2 + 2*z + 3,\n", " 4*z^3 + 4*z + 1,\n", " 3*z + 2,\n", " 3*z^2 + 2*z,\n", " 3*z^3 + 2*z^2,\n", " 2*z^3 + 2*z^2 + 4*z + 4,\n", " 2*z^3 + 2*z^2 + 1,\n", " 2*z^3 + 3*z^2 + 2*z + 1,\n", " 3*z^3 + 2*z + 1,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2*z + 2,\n", " 2*z^2 + 2*z,\n", " 2*z^3 + 2*z^2,\n", " 2*z^3 + 3*z^2 + z + 1,\n", " 3*z^3 + 4*z^2 + 2*z + 1,\n", " 4*z^3 + 4*z^2 + 4,\n", " 4*z^3 + z^2 + z + 2,\n", " z^3 + 2*z^2 + 4*z + 2,\n", " 2*z^3 + 3*z^2 + 3,\n", " 3*z^3 + 3*z^2 + 4*z + 1,\n", " 3*z^3 + z^2 + 4,\n", " z^3 + 2*z^2 + 3*z + 4,\n", " 2*z^3 + 2*z^2 + 2*z + 3,\n", " 2*z^3 + 4*z + 1,\n", " 2*z^2 + 2*z + 1,\n", " 2*z^3 + 2*z^2 + z,\n", " 2*z^3 + 4*z^2 + z + 1,\n", " 4*z^3 + 4*z^2 + 2*z + 1,\n", " 4*z^3 + 3*z^2 + 3*z + 2,\n", " 3*z^3 + 4*z^2 + 4*z + 2,\n", " 4*z^3 + z^2 + z + 4,\n", " z^3 + 2*z^2 + z + 2,\n", " 2*z^3 + 3,\n", " 3*z^2 + 4*z + 1,\n", " 3*z^3 + 4*z^2 + z,\n", " 4*z^3 + 3*z^2 + 4*z + 4,\n", " 3*z^3 + z + 2,\n", " 3*z^2 + z + 4,\n", " 3*z^3 + z^2 + 4*z,\n", " z^3 + z^2 + 4*z + 4,\n", " z^3 + 3*z^2 + 2*z + 3,\n", " 3*z^3 + z^2 + z + 3,\n", " z^3 + 3*z^2 + 2*z + 4,\n", " 3*z^3 + z^2 + 2*z + 3,\n", " z^3 + 4*z^2 + 2*z + 4,\n", " 4*z^3 + z^2 + 2*z + 3,\n", " z^3 + 3*z^2 + 2,\n", " 3*z^3 + 4*z^2 + 3,\n", " 4*z^3 + 2*z^2 + 2*z + 4,\n", " 2*z^3 + 3*z^2 + z + 2,\n", " 3*z^3 + 4*z^2 + 3*z + 1,\n", " 4*z^3 + 4,\n", " z^2 + z + 2,\n", " z^3 + z^2 + 2*z,\n", " z^3 + z^2 + 3*z + 3,\n", " z^3 + 2*z^2 + z + 3,\n", " 2*z^3 + z + 3,\n", " 4*z^2 + 4*z + 1,\n", " 4*z^3 + 4*z^2 + z,\n", " 4*z^3 + 2*z^2 + 2*z + 2,\n", " 2*z^3 + 3*z^2 + 4*z + 2,\n", " 3*z^3 + 2*z^2 + 3*z + 1,\n", " 2*z^3 + 4,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4*z + 4,\n", " 3*z^3 + 4*z^2 + 4*z,\n", " 4*z^3 + z^2 + 4*z + 4,\n", " z^3 + z + 2,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4*z + 4,\n", " 2*z^3 + 4*z^2 + 4*z,\n", " 4*z^3 + 2*z^2 + z + 1,\n", " 2*z^3 + 2*z^2 + 3*z + 2,\n", " 2*z^3 + z^2 + 3*z + 1,\n", " z^3 + z^2 + 2*z + 1,\n", " z^3 + z^2 + 4*z + 3,\n", " z^3 + 3*z^2 + z + 3,\n", " 3*z^3 + z + 3,\n", " 3*z^2 + 2*z + 4,\n", " 3*z^3 + 2*z^2 + 4*z,\n", " 2*z^3 + z^2 + 4*z + 4,\n", " z^3 + 2*z^2 + 1,\n", " 2*z^3 + 4*z^2 + 4*z + 3,\n", " 4*z^3 + 2*z^2 + 4*z + 1,\n", " 2*z^3 + 3*z + 2,\n", " z^2 + 3*z + 1,\n", " z^3 + 3*z^2 + z,\n", " 3*z^3 + 3*z + 3,\n", " 2*z + 4,\n", " 2*z^2 + 4*z,\n", " 2*z^3 + 4*z^2,\n", " 4*z^3 + 3*z^2 + z + 1,\n", " 3*z^3 + 2*z^2 + 3*z + 2,\n", " 2*z^3 + z + 4,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2*z + 2,\n", " 2*z^3 + 2*z^2 + 2*z,\n", " 2*z^3 + z + 1,\n", " 4*z^2 + 2*z + 1,\n", " 4*z^3 + 2*z^2 + z,\n", " 2*z^3 + 2*z^2 + 2*z + 2,\n", " 2*z^3 + 3*z + 1,\n", " z^2 + 2*z + 1,\n", " z^3 + 2*z^2 + z,\n", " 2*z^3 + 3*z + 3,\n", " z^2 + 4*z + 1,\n", " z^3 + 4*z^2 + z,\n", " 4*z^3 + 3*z + 3,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2*z + 2,\n", " 3*z^3 + 2*z^2 + 2*z,\n", " 2*z^3 + 4*z^2 + 4*z + 4,\n", " 4*z^3 + 2*z^2 + 1,\n", " 2*z^3 + z^2 + 3*z + 2,\n", " z^3 + z^2 + 3*z + 1,\n", " z^3 + 2*z^2 + 4*z + 3,\n", " 2*z^3 + 3*z^2 + z + 3,\n", " 3*z^3 + 4*z^2 + 4*z + 1,\n", " 4*z^3 + z^2 + 4,\n", " z^3 + z^2 + z + 2,\n", " z^3 + 3,\n", " 4*z^2 + z + 3,\n", " 4*z^3 + z^2 + 3*z,\n", " z^3 + 4*z^2 + 2*z + 2,\n", " 4*z^3 + z^2 + 3,\n", " z^3 + z^2 + 2,\n", " z^3 + 4*z^2 + 3,\n", " 4*z^3 + 4*z^2 + z + 3,\n", " 4*z^3 + 2*z^2 + 2,\n", " 2*z^3 + z^2 + 4*z + 2,\n", " z^3 + 2*z^2 + 3*z + 1,\n", " 2*z^3 + 2*z^2 + 4*z + 3,\n", " 2*z^3 + 2*z^2 + 4*z + 1,\n", " 2*z^3 + 2*z^2 + 2*z + 1,\n", " 2*z^3 + 2*z + 1,\n", " 2*z + 1,\n", " 2*z^2 + z,\n", " 2*z^3 + z^2,\n", " z^3 + 3*z^2 + z + 1,\n", " 3*z^3 + 4*z + 3,\n", " z^2 + 2*z + 4,\n", " z^3 + 2*z^2 + 4*z,\n", " 2*z^3 + 3*z^2 + 3*z + 3,\n", " 3*z^3 + z^2 + 4*z + 1,\n", " z^3 + z^2 + 4,\n", " z^3 + 4*z^2 + 2*z + 3,\n", " 4*z^3 + z^2 + z + 3,\n", " z^3 + 2*z^2 + 2,\n", " 2*z^3 + 4*z^2 + 3,\n", " 4*z^3 + 3*z^2 + 4*z + 1,\n", " 3*z^3 + 3*z + 2,\n", " z + 4,\n", " z^2 + 4*z,\n", " z^3 + 4*z^2,\n", " 4*z^3 + 4*z^2 + 3*z + 3,\n", " 4*z^3 + 4*z^2 + 2,\n", " 4*z^3 + z^2 + 4*z + 2,\n", " z^3 + 4*z + 2,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4*z + 4,\n", " 4*z^2 + 4*z,\n", " 4*z^3 + 4*z^2,\n", " 4*z^3 + z^2 + 2*z + 2,\n", " z^3 + 3*z^2 + 4*z + 2,\n", " 3*z^3 + 3*z^2 + 3,\n", " 3*z^3 + 2*z^2 + 2*z + 4,\n", " 2*z^3 + 4*z^2 + 3*z + 4,\n", " 4*z^3 + z^2 + 1,\n", " z^3 + z^2 + 3*z + 2,\n", " z^3 + 2*z^2 + 3,\n", " 2*z^3 + 4*z^2 + z + 3,\n", " 4*z^3 + 4*z^2 + 4*z + 1,\n", " 4*z^3 + 3*z + 2,\n", " 4*z^2 + 4*z + 2,\n", " 4*z^3 + 4*z^2 + 2*z,\n", " 4*z^3 + 3*z^2 + 2*z + 2,\n", " 3*z^3 + 3*z^2 + 4*z + 2,\n", " 3*z^3 + z^2 + z + 4,\n", " z^3 + 3*z^2 + 3*z + 4,\n", " 3*z^3 + 2*z^2 + 2*z + 3,\n", " 2*z^3 + 4*z^2 + 2*z + 4,\n", " 4*z^3 + 1,\n", " z^2 + 3*z + 2,\n", " z^3 + 3*z^2 + 2*z,\n", " 3*z^3 + z^2 + 3*z + 3,\n", " z^3 + 2*z + 4,\n", " z^2 + 2*z + 3,\n", " z^3 + 2*z^2 + 3*z,\n", " 2*z^3 + 2*z^2 + 3*z + 3,\n", " 2*z^3 + z^2 + 4*z + 1,\n", " z^3 + 2*z^2 + 2*z + 1,\n", " 2*z^3 + z^2 + 4*z + 3,\n", " z^3 + 2*z^2 + 4*z + 1,\n", " 2*z^3 + 3*z^2 + 4*z + 3,\n", " 3*z^3 + 2*z^2 + 4*z + 1,\n", " 2*z^3 + z^2 + 4,\n", " z^3 + 3*z^2 + 1,\n", " 3*z^3 + 4*z^2 + 4*z + 3,\n", " 4*z^3 + z^2 + 2*z + 4,\n", " z^3 + 3*z^2 + z + 2,\n", " 3*z^3 + 3,\n", " 2*z^2 + 2*z + 4,\n", " 2*z^3 + 2*z^2 + 4*z,\n", " 2*z^3 + 2*z^2 + z + 1,\n", " 2*z^3 + 4*z^2 + 2*z + 1,\n", " 4*z^3 + 2*z + 1,\n", " 3*z^2 + 3*z + 2,\n", " 3*z^3 + 3*z^2 + 2*z,\n", " 3*z^3 + 4*z^2 + 4*z + 4,\n", " 4*z^3 + z^2 + 3*z + 4,\n", " z^3 + 4*z^2 + z + 2,\n", " 4*z^3 + 3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3*z + 3,\n", " z^3 + 3*z^2 + 3*z,\n", " 3*z^3 + 2*z^2 + 3*z + 3,\n", " 2*z^3 + 2*z + 4,\n", " 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fieldElements = generateAllNonzeroFieldElements( f, n, p ) ; pretty_print( fieldElements )" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "624" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(fieldElements)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "624" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p^n-1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A non-primitive polynomial won't generate all the nonzero field elements. Note the repetitions in the polynomal list below." ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "x^4 + x^2 + 2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = x^4 + x^2 + 2 ; pretty_print( f )" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Passed step 1: p = 5 >=2 and n = 4 >= 2\n", "Passed step 2: a0 = 2 is a primitive root\n", "Passed step 3: f(x) has no linear factors\n", "Passed step 4: f(x) is either irreducible or irreducible ^ power\n", "Passed step 5: a = 2 is constant\n", "Passed step 6: a = a0 (-1)^n mod p where a0 = 2\n", "Begin step 7: Testing on prime factors pi\n", " Skip step 7 test since prime pi = 2 divides p-1 = 4\n", " Passed step 7 since x^m is not an integer for prime pi = 3\n", " Failed step 7 since x^m is an integer for prime pi = 13\n" ] }, { "data": { "text/plain": [ "False" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isPrimitivePolynomial( f, n, p )" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "[z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1,\n", " z,\n", " z^2,\n", " z^3,\n", " 4*z^2 + 3,\n", " 4*z^3 + 3*z,\n", " 4*z^2 + 2,\n", " 4*z^3 + 2*z,\n", " 3*z^2 + 2,\n", " 3*z^3 + 2*z,\n", " 4*z^2 + 4,\n", " 4*z^3 + 4*z,\n", " 2,\n", " 2*z,\n", " 2*z^2,\n", " 2*z^3,\n", " 3*z^2 + 1,\n", " 3*z^3 + z,\n", " 3*z^2 + 4,\n", " 3*z^3 + 4*z,\n", " z^2 + 4,\n", " z^3 + 4*z,\n", " 3*z^2 + 3,\n", " 3*z^3 + 3*z,\n", " 4,\n", " 4*z,\n", " 4*z^2,\n", " 4*z^3,\n", " z^2 + 2,\n", " z^3 + 2*z,\n", " z^2 + 3,\n", " z^3 + 3*z,\n", " 2*z^2 + 3,\n", " 2*z^3 + 3*z,\n", " z^2 + 1,\n", " z^3 + z,\n", " 3,\n", " 3*z,\n", " 3*z^2,\n", " 3*z^3,\n", " 2*z^2 + 4,\n", " 2*z^3 + 4*z,\n", " 2*z^2 + 1,\n", " 2*z^3 + z,\n", " 4*z^2 + 1,\n", " 4*z^3 + z,\n", " 2*z^2 + 2,\n", " 2*z^3 + 2*z,\n", " 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fieldElements = generateAllNonzeroFieldElements( f, n, p ); pretty_print( fieldElements )" ] } ], "metadata": { "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "SageMath 9.1", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 2 }