{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "?GF" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "F3=GF(3); F9.=GF(3^2);" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(F3)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2, 1]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(F9)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$$" ], "text/plain": [ "2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}1$$" ], "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F3(1)+F3(5)); show(F3(1/2)); show(F3(2^10))" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$$" ], "text/plain": [ "2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}1$$" ], "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F9(1)+F9(5)); show(F9(1/2)); show(F9(2^10))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}a$$" ], "text/plain": [ "a" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}a + 1$$" ], "text/plain": [ "a + 1" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}a + 2$$" ], "text/plain": [ "a + 2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F9(a^9)); show(F9((1+a)^9)); show(F9(1/a))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}1$$" ], "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F9(a*(a+2)))" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}a + 1$$" ], "text/plain": [ "a + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F9(a^2));" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(F9(1+a-a^2))" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F3X.=PolynomialRing(GF(3)); P=x^4-x^3+x^2-x+1; P.is_irreducible()" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2 b^{3} + b^{2} + 2 b + 1$$" ], "text/plain": [ "2*b^3 + b^2 + 2*b + 1" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2 b^{3} + b^{2} + 2 b + 1$$" ], "text/plain": [ "2*b^3 + b^2 + 2*b + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F81.=GF(3^4,modulus=P); show(b^9); show(1/b)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x^3 + x^2 + 2*x + 1" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x^9 % P" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 2*x^3 + x^2 + 2*x + 1, 1)" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "xgcd(x,P)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 2*x^3 + x^2 + 2*x + 1" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.minpoly(x)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^2 + 2*x + 2" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a.minpoly(x)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{32} + 2 x^{24} + x^{16} + 2 x^{8} + 1$$" ], "text/plain": [ "x^32 + 2*x^24 + x^16 + 2*x^8 + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "Phi=cyclotomic_value(3^4-1,x); show(Phi)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 1) * (x + 2)^2" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1=x^3+2*x^2+2*x+1; P1.factor()" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^3 + 2*x^2 + 2*x + 2" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P2=x^3+2*x^2-x-1; P2.factor()" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P2.is_irreducible()" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "F27.=GF(3^3,modulus=P2); F27X.=PolynomialRing(F27)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^3 + 2*x^2 + 2*x + 2" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P2.factor()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 2*c) * (x + c^2 + 2*c) * (x + 2*c^2 + 2*c + 2)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F27X(P2).factor()" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 2*x^3 + 2*x^2 + x + 2" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x=F3X.gen(); P3=x^4+2*x^3+2*x^2+x+2; P3.factor()" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x^2 + x + a) * (x^2 + x + 2*a + 1)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F9X.=PolynomialRing(F9); F9X(P3).factor()" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + b^3 + b^2 + 2) * (x + b^3 + 2*b^2 + 2*b + 1) * (x + 2*b^3 + b^2 + b) * (x + 2*b^3 + 2*b^2 + 2)" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F81X.=PolynomialRing(F81); F81X(P3).factor()" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x^4 + x + 2) * (x^4 + 2*x + 2) * (x^4 + x^3 + 2) * (x^4 + x^3 + x^2 + 2*x + 2) * (x^4 + x^3 + 2*x^2 + 2*x + 2) * (x^4 + 2*x^3 + 2) * (x^4 + 2*x^3 + x^2 + x + 2) * (x^4 + 2*x^3 + 2*x^2 + x + 2)" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Phi.factor() # P3 est un facteur de la décomposition mais pas P" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x^2 + x + a) * (x^2 + x + 2*a + 1) * (x^2 + 2*x + a) * (x^2 + 2*x + 2*a + 1) * (x^2 + a*x + 2*a) * (x^2 + a*x + 2*a + 1) * (x^2 + (a + 1)*x + a + 2) * (x^2 + (a + 1)*x + 2*a) * (x^2 + (a + 2)*x + a) * (x^2 + (a + 2)*x + a + 2) * (x^2 + 2*a*x + 2*a) * (x^2 + 2*a*x + 2*a + 1) * (x^2 + (2*a + 1)*x + a) * (x^2 + (2*a + 1)*x + a + 2) * (x^2 + (2*a + 2)*x + a + 2) * (x^2 + (2*a + 2)*x + 2*a)" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F9X(Phi).factor()" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x^4 + x + 2) * (x^4 + 2*x + 2) * (x^4 + x^3 + 2) * (x^4 + x^3 + x^2 + 2*x + 2) * (x^4 + x^3 + 2*x^2 + 2*x + 2) * (x^4 + 2*x^3 + 2) * (x^4 + 2*x^3 + x^2 + x + 2) * (x^4 + 2*x^3 + 2*x^2 + x + 2)" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F27X(Phi).factor()" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + b + 1) * (x + 2*b + 2) * (x + b^2 + 2) * (x + b^2 + b) * (x + b^2 + b + 2) * (x + 2*b^2 + 1) * (x + 2*b^2 + 2*b) * (x + 2*b^2 + 2*b + 1) * (x + b^3 + 1) * (x + b^3 + 2*b) * (x + b^3 + 2*b + 2) * (x + b^3 + b^2 + 1) * (x + b^3 + b^2 + 2) * (x + b^3 + b^2 + b + 1) * (x + b^3 + b^2 + b + 2) * (x + b^3 + b^2 + 2*b) * (x + b^3 + b^2 + 2*b + 1) * (x + b^3 + 2*b^2 + b + 1) * (x + b^3 + 2*b^2 + 2*b) * (x + b^3 + 2*b^2 + 2*b + 1) * (x + 2*b^3 + 2) * (x + 2*b^3 + b) * (x + 2*b^3 + b + 1) * (x + 2*b^3 + b^2 + b) * (x + 2*b^3 + b^2 + b + 2) * (x + 2*b^3 + b^2 + 2*b + 2) * (x + 2*b^3 + 2*b^2 + 1) * (x + 2*b^3 + 2*b^2 + 2) * (x + 2*b^3 + 2*b^2 + b) * (x + 2*b^3 + 2*b^2 + b + 2) * (x + 2*b^3 + 2*b^2 + 2*b + 1) * (x + 2*b^3 + 2*b^2 + 2*b + 2)" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F81X(Phi).factor()" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}32$$" ], "text/plain": [ "32" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "[4, 2, 4, 1]" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R1=Integers(3^4-1); show(R1.unit_group_order());\n", "[R1(3^(i+1)).multiplicative_order() for i in range(4)]" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 2*x^3 + 2*x^2 + x + 2" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K.=GF(3^4,modulus=P3); x=F3X.gen(); mul(x-beta^(3^i) for i in range(4))" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}40$$" ], "text/plain": [ "40" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n=3^4-1; m=n/gcd(2,n); show(m)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}(x^{4} + x^{2} + x + 1) \\cdot (x^{4} + x^{2} + 2 x + 1) \\cdot (x^{4} + x^{3} + x^{2} + 1) \\cdot (x^{4} + 2 x^{3} + x^{2} + 1)$$" ], "text/plain": [ "(x^4 + x^2 + x + 1) * (x^4 + x^2 + 2*x + 1) * (x^4 + x^3 + x^2 + 1) * (x^4 + 2*x^3 + x^2 + 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "Phim=cyclotomic_value(m,x); facts=factor(Phim); show(facts)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, beta^2, 2*beta^3 + beta^2 + 2*beta + 2, beta^3 + beta + 1]" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[facts[i][0](beta^2) for i in range(4)]" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 6, 18, 54, 2]" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[R1(2*3^i) for i in range(5)]" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + x^2 + x + 1" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mul(x-beta^(2*3^i) for i in range(4))" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + x^2 + x + 1" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "minpoly(beta^2)" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}31$$" ], "text/plain": [ "31" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m=5; n=2^m-1; delta=7; show(n);\n" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}(x^{5} + x^{2} + 1) \\cdot (x^{5} + x^{3} + 1) \\cdot (x^{5} + x^{3} + x^{2} + x + 1) \\cdot (x^{5} + x^{4} + x^{2} + x + 1) \\cdot (x^{5} + x^{4} + x^{3} + x + 1) \\cdot (x^{5} + x^{4} + x^{3} + x^{2} + 1)$$" ], "text/plain": [ "(x^5 + x^2 + 1) * (x^5 + x^3 + 1) * (x^5 + x^3 + x^2 + x + 1) * (x^5 + x^4 + x^2 + x + 1) * (x^5 + x^4 + x^3 + x + 1) * (x^5 + x^4 + x^3 + x^2 + 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F2X.=PolynomialRing(GF(2)); show(factor(cyclotomic_value(n,x)));" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [], "source": [ "mu=x^5 + x^2 + 1; K.=GF(2^5,modulus=mu);" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^15 + x^11 + x^10 + x^9 + x^8 + x^7 + x^5 + x^3 + x^2 + x + 1" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lcm(minpoly(beta^(i+1)) for i in range(delta-1))" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{15} + x^{11} + x^{10} + x^{9} + x^{8} + x^{7} + x^{5} + x^{3} + x^{2} + x + 1$$" ], "text/plain": [ "x^15 + x^11 + x^10 + x^9 + x^8 + x^7 + x^5 + x^3 + x^2 + x + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "g3=minpoly(beta^3); g5=minpoly(beta^5); g=mu*g3*g5; show(g)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}16$$" ], "text/plain": [ "16" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "k=n-g.degree(); show(k);" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}3$$" ], "text/plain": [ "3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "t=floor((delta-1)/2); show(t);" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{15} + x^{13} + x^{12} + x^{11} + x^{7} + x^{5} + x^{4} + x^{3} + x$$" ], "text/plain": [ "x^15 + x^13 + x^12 + x^11 + x^7 + x^5 + x^4 + x^3 + x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "M=F2X.random_element(k-1); show(M);" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{30} + x^{28} + x^{27} + x^{25} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{14} + x^{12} + x^{9} + x^{7} + x^{5} + x^{4} + x^{2} + x$$" ], "text/plain": [ "x^30 + x^28 + x^27 + x^25 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^14 + x^12 + x^9 + x^7 + x^5 + x^4 + x^2 + x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "c=M*g; show(c);" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{28} + x^{27} + x^{25} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{14} + x^{12} + x^{9} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1$$" ], "text/plain": [ "x^28 + x^27 + x^25 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "e=x^(n-1)+1+x^8; R=c+e; show(R);" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\beta^{3} + \\beta + 1\\right) x^{5} + \\left(\\beta^{3} + \\beta^{2}\\right) x^{4} + \\beta^{3} x^{3} + \\left(\\beta^{3} + 1\\right) x^{2} + \\left(\\beta^{4} + \\beta + 1\\right) x + \\beta^{4} + \\beta^{3} + \\beta^{2} + \\beta$$" ], "text/plain": [ "(beta^3 + beta + 1)*x^5 + (beta^3 + beta^2)*x^4 + beta^3*x^3 + (beta^3 + 1)*x^2 + (beta^4 + beta + 1)*x + beta^4 + beta^3 + beta^2 + beta" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "S=add(R(beta^(i+1))*x^i for i in range(2*t)); show(S);" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [], "source": [ "def Berlekamp(S,t):\n", " v0=x^(2*t); v1=S; u0=0; u1=1;\n", " while v1.degree()>=t:\n", " q,v2=v0.quo_rem(v1); u2=u0-u1*q;\n", " v0=v1; v1=v2; u0=u1; u1=u2;\n", " return(u1)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\beta^{3} + \\beta^{2}\\right) x^{3} + \\left(\\beta^{4} + \\beta^{3} + \\beta\\right) x^{2} + \\left(\\beta^{3} + \\beta\\right) x + \\beta^{4} + \\beta^{3} + \\beta^{2}$$" ], "text/plain": [ "(beta^3 + beta^2)*x^3 + (beta^4 + beta^3 + beta)*x^2 + (beta^3 + beta)*x + beta^4 + beta^3 + beta^2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "L=Berlekamp(S,t); show(L);" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(1, 1), (beta, 1), (beta^3 + beta^2 + beta + 1, 1)]" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L.roots()" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "8\n", "30\n" ] } ], "source": [ "for i in range(n):\n", " if L(beta^(-i))==0:\n", " print(i)" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{30} + x^{8} + 1$$" ], "text/plain": [ "x^30 + x^8 + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(e);" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\beta^{4} + \\beta^{3} + \\beta\\right) x^{3} + \\left(\\beta^{4} + \\beta^{3} + \\beta^{2} + 1\\right) x^{2} + \\left(\\beta^{2} + \\beta + 1\\right) x + \\beta + 1$$" ], "text/plain": [ "(beta^4 + beta^3 + beta)*x^3 + (beta^4 + beta^3 + beta^2 + 1)*x^2 + (beta^2 + beta + 1)*x + beta + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "e=x^2+x^5+x^15; R=c+e; S=add(R(beta^(i+1))*x^i for i in range(2*t)); L=Berlekamp(S,t); show(L);" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n", "5\n", "15\n" ] } ], "source": [ "for i in range(n):\n", " if L(beta^(-i))==0:\n", " print(i)" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\beta^{4} + \\beta^{3} + \\beta^{2} + 1\\right) x^{3} + \\left(\\beta^{3} + \\beta^{2}\\right) x^{2} + \\left(\\beta^{3} + \\beta^{2}\\right) x + \\beta^{4} + \\beta^{3} + \\beta$$" ], "text/plain": [ "(beta^4 + beta^3 + beta^2 + 1)*x^3 + (beta^3 + beta^2)*x^2 + (beta^3 + beta^2)*x + beta^4 + beta^3 + beta" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "e=x^2+x^5+x^15+x^25; R=c+e; S=add(R(beta^(i+1))*x^i for i in range(2*t)); L=Berlekamp(S,t); show(L);" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [], "source": [ "for i in range(n):\n", " if L(beta^(-i))==0:\n", " print(i)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.6" } }, "nbformat": 4, "nbformat_minor": 2 }