(*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 0, 0] NotebookDataLength[ 164312, 3473] NotebookOptionsPosition[ 150140, 3156] NotebookOutlinePosition[ 150654, 3177] CellTagsIndexPosition[ 150611, 3174] WindowFrame->Normal ContainsDynamic->False*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["\<\ Primitive Polynomial Search Example\ \>", "Title", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415650004723082*^9, 3.415650006573312*^9}, { 3.415709825153708*^9, 3.4157098289689903`*^9}, {3.458482869740264*^9, 3.458482877491879*^9}, 3.458483612622904*^9}, TextAlignment->Center], Cell["Sean E. O'Connor", "Subtitle", CellMargins->{{7, Inherited}, {Inherited, Inherited}}, CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{3.4584836126230507`*^9}, TextAlignment->Center], Cell[TextData[StyleBox["artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com",\ "Subsubtitle"]], "Subtitle", CellMargins->{{7, Inherited}, {Inherited, Inherited}}, CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{3.458483612623116*^9}, TextAlignment->Center], Cell["Abstract", "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{3.4584836126232033`*^9}], Cell[TextData[{ "We describe methods for testing whether a polynomial is primitive or \ irreducible using a ", StyleBox["Mathematica script. ", FontSlant->"Italic"], "The straightforward test to determine whether a polynomial f(x) is \ primitive over GF(p) by checking if x is a generator of the field GF(", Cell[BoxData[ FormBox[ SuperscriptBox["p", "n"], TraditionalForm]]], ") is exponentially slow. We show a much faster test, due to Alanen, Knuth \ and Sugimoto based on factoring ", Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ RowBox[{ SuperscriptBox["p", "n"], "-", "1"}], RowBox[{"p", "-", "1"}]], "."}], TraditionalForm]]] }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415709892688006*^9, 3.415710043056424*^9}, { 3.415729827066167*^9, 3.415729843930984*^9}, {3.458482886918886*^9, 3.458482927867222*^9}, 3.4584836126232767`*^9}, ParagraphIndent->0], Cell["1. Preliminaries", "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{3.415729389681034*^9, 3.458483612623403*^9}], Cell[TextData[{ "First we have to set up a series of helper functions. Let's try them out \ in GF(", Cell[BoxData[ FormBox[ SuperscriptBox["5", "4"], TraditionalForm]]], "), using the primitive polynomial," }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156329538842278`*^9, 3.4156330044771*^9}, { 3.415646222977437*^9, 3.415646223615296*^9}, {3.4156500754613657`*^9, 3.415650085835122*^9}, {3.415710412203019*^9, 3.4157104524915*^9}, 3.45848361262348*^9}], Cell[BoxData[ RowBox[{ RowBox[{"p", "=", "5"}], ";", " ", RowBox[{"n", "=", "4"}], ";", RowBox[{"f", "=", RowBox[{ SuperscriptBox["x", "4"], "+", SuperscriptBox["x", "2"], "+", RowBox[{"2", "x"}], "+", "3"}]}], ";"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633014986371*^9, 3.41563303246393*^9}, { 3.415649942258945*^9, 3.415649943288313*^9}, {3.421596850700919*^9, 3.421596865552033*^9}, {3.421599080673317*^9, 3.421599101535763*^9}, 3.4584836126235657`*^9}], Cell["\<\ The number of elements in the field, which is the total number of polynomials \ is\ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563300953085*^9, 3.4156330109049473`*^9}, { 3.4157104592348137`*^9, 3.4157104600021753`*^9}, 3.458483612623643*^9}], Cell[BoxData[ RowBox[{ RowBox[{"NumberOfPolynomials", "[", RowBox[{"p", ",", "n"}], "]"}], ":=", SuperscriptBox["p", "n"]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632921204267*^9, 3.4156329266176367`*^9}, { 3.4157107521951838`*^9, 3.415710759342532*^9}, 3.4584836126237173`*^9}], Cell[BoxData[ RowBox[{"NumberOfPolynomials", "[", RowBox[{"p", ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415710767811591*^9, 3.415710772472261*^9}, 3.458483612623796*^9}], Cell[BoxData["625"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.415710773201536*^9, 3.415712110842586*^9, 3.415712157080552*^9, 3.4157128945257597`*^9, 3.4157130830744057`*^9, {3.415713139925215*^9, 3.41571317351376*^9}, 3.415713520655067*^9, 3.415713743753936*^9, 3.415714054746379*^9, 3.415714124054571*^9, 3.4157180492549257`*^9, 3.415729381869916*^9, 3.415729436720495*^9, 3.415729859445253*^9, 3.4189068462103233`*^9, 3.421596805383183*^9, 3.42159825701836*^9, 3.421598458133984*^9, 3.4215985044535217`*^9, 3.421599108473308*^9, 3.421599159428276*^9, 3.4216078391642637`*^9, 3.421607960432249*^9, 3.4326031453735437`*^9, {3.4338988766928463`*^9, 3.433898886302394*^9}, 3.433898917287818*^9, 3.458399058560152*^9, {3.458399098048642*^9, 3.4583991219031143`*^9}, 3.4584008475797863`*^9, 3.458404365416494*^9, 3.458405358538845*^9, 3.458405492750342*^9, 3.4584058044107647`*^9, 3.458406285266108*^9, 3.458407493499922*^9, 3.458407558302174*^9, 3.458407706852957*^9, 3.4584083908027363`*^9, 3.458408495847783*^9, 3.4584090019202757`*^9, 3.458409664588375*^9, {3.458423460177009*^9, 3.458423469412881*^9}, 3.4584235317424107`*^9, 3.458423602144751*^9, 3.458424136291336*^9, 3.4584243523912573`*^9, 3.4584243856077547`*^9, 3.458424455703512*^9, 3.4584246799658813`*^9, 3.458424759714135*^9, 3.458424796127501*^9, 3.4584832749043617`*^9, 3.458483419330946*^9, 3.458483506252899*^9, 3.458483554851603*^9, {3.458483612623878*^9, 3.458483623381771*^9}, 3.4584839471853867`*^9}], Cell[TextData[{ "The number of distinct ", StyleBox["primitive", FontSlant->"Italic"], " polynomials is \[Phi](", Cell[BoxData[ FormBox[ FractionBox[ RowBox[{ SuperscriptBox["p", "n"], "-", "1"}], "n"], TraditionalForm]]], ")" }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{3.4156326048826103`*^9, 3.458483612623955*^9}], Cell[BoxData[ RowBox[{ RowBox[{"NumberOfPrimitivePolynomials", "[", " ", RowBox[{"p_", ",", " ", "n_"}], " ", "]"}], " ", ":=", " ", FractionBox[ RowBox[{"EulerPhi", "[", RowBox[{ SuperscriptBox["p", "n"], "-", "1"}], "]"}], "n"]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156325178990097`*^9, 3.415632529854072*^9}, 3.415632609685247*^9, 3.458483612624029*^9}], Cell[BoxData[ RowBox[{"NumberOfPrimitivePolynomials", "[", RowBox[{"p", ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633043441327*^9, 3.4156330498651*^9}, 3.458483612624106*^9}], Cell[BoxData["48"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633051215269*^9, 3.41563307998981*^9}, { 3.415634786636334*^9, 3.415634804031348*^9}, 3.415634838348587*^9, 3.415640641746306*^9, 3.415641784737862*^9, {3.415644491343171*^9, 3.41564450954937*^9}, 3.415646036714658*^9, 3.415646241616729*^9, 3.415647092090295*^9, 3.415647183842038*^9, 3.4156479731025*^9, 3.415649014666712*^9, 3.415650173778471*^9, 3.415650342924683*^9, 3.415651093212482*^9, {3.4157106993761797`*^9, 3.4157107129835577`*^9}, 3.415712110933598*^9, 3.415712157167227*^9, 3.4157128946247673`*^9, 3.415713083210685*^9, {3.415713140011306*^9, 3.4157131736171103`*^9}, 3.415713520727528*^9, 3.4157137438496304`*^9, 3.415714054857195*^9, 3.415714124151217*^9, 3.4157180493849688`*^9, 3.4157293819760923`*^9, 3.4157294368299503`*^9, 3.4157298595401363`*^9, 3.4189068463223248`*^9, 3.421596805460781*^9, 3.4215982571143093`*^9, 3.421598458197194*^9, 3.42159850451692*^9, 3.421599108588866*^9, 3.421599159525173*^9, 3.421607839260051*^9, 3.42160796050497*^9, 3.4326031454371357`*^9, { 3.433898876786089*^9, 3.433898886455393*^9}, 3.43389891736989*^9, 3.458399058652063*^9, {3.4583990981676807`*^9, 3.45839912195686*^9}, 3.458400847709594*^9, 3.4584043654852037`*^9, 3.458405358626931*^9, 3.458405492821931*^9, 3.458405804475238*^9, 3.458406285339292*^9, 3.458407493599523*^9, 3.458407558357746*^9, 3.458407706926565*^9, 3.458408390896377*^9, 3.458408495946474*^9, 3.45840900199832*^9, 3.458409664687674*^9, {3.458423460276428*^9, 3.458423469480651*^9}, 3.4584235318052807`*^9, 3.45842360221742*^9, 3.458424136351347*^9, 3.458424352476454*^9, 3.458424385679141*^9, 3.458424455775814*^9, 3.458424680046682*^9, 3.458424759769648*^9, 3.4584247961767263`*^9, 3.458483274991284*^9, 3.458483419430625*^9, 3.458483506307156*^9, 3.4584835549248533`*^9, {3.4584836126241827`*^9, 3.458483623450634*^9}, 3.458483947287671*^9}], Cell["The probability of a random polynomial being primitive is", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4156326048826103`*^9, {3.4157105847159452`*^9, 3.415710641702524*^9}, { 3.458483222480753*^9, 3.458483224230176*^9}, {3.458483269496166*^9, 3.458483294520718*^9}, 3.45848361262426*^9}], Cell[BoxData[ RowBox[{ RowBox[{ RowBox[{"NumberOfPrimitivePolynomials", "[", RowBox[{"p", ",", "n"}], "]"}], "/", RowBox[{"NumberOfPolynomials", "[", RowBox[{"p", ",", "n"}], "]"}]}], " ", "//", "N"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.458483264987117*^9, 3.458483265640377*^9}, 3.458483612624333*^9}], Cell[BoxData["0.0768`"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458483275043491*^9, 3.458483419479187*^9, 3.458483506344842*^9, 3.45848355497396*^9, {3.458483612624412*^9, 3.458483623500399*^9}, 3.458483947354066*^9}], Cell[TextData[{ "The number of polynomials with linear factors is ", Cell[BoxData[ RowBox[{ StyleBox[ UnderoverscriptBox["\[Sum]", RowBox[{"i", "=", "0"}], "n"], FontSize->18], RowBox[{ SuperscriptBox["p", RowBox[{"n", "-", "i"}]], SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "i"], " ", RowBox[{"(", GridBox[{ {"p"}, {"i"} }], ")"}]}]}]]] }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, 3.458483612624487*^9}], Cell[BoxData[ RowBox[{ RowBox[{"NumberOfPolynomialsWithLinearFactors", "[", " ", RowBox[{"p_", ",", "n_"}], " ", "]"}], " ", ":=", " ", RowBox[{ UnderoverscriptBox["\[Sum]", RowBox[{"i", "=", "0"}], "n"], RowBox[{ SuperscriptBox["p", RowBox[{"n", "-", "i"}]], SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "i"], " ", RowBox[{"Binomial", "[", RowBox[{"p", ",", " ", "i"}], "]"}]}]}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632756475444*^9, 3.4156327601942577`*^9}, { 3.4156330676935368`*^9, 3.415633073843191*^9}, 3.458483612624559*^9}], Cell[BoxData[ RowBox[{"NumberOfPolynomialsWithLinearFactors", "[", RowBox[{"p", ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633058811693*^9, 3.415633060936946*^9}, 3.4584836126246367`*^9}], Cell[BoxData["205"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633061733231*^9, 3.415633081695537*^9}, { 3.415634786761631*^9, 3.415634804157913*^9}, 3.415634838430029*^9, 3.4156406418384123`*^9, 3.4156417848598137`*^9, {3.415644491464267*^9, 3.415644509668805*^9}, 3.415646036855495*^9, 3.4156462450250463`*^9, 3.415647092245597*^9, 3.415647184288766*^9, 3.4156479732386513`*^9, 3.41564901474916*^9, 3.4156501738543873`*^9, 3.4156503430412703`*^9, 3.415651093328684*^9, {3.4157106994607477`*^9, 3.4157107131084223`*^9}, 3.415712111022688*^9, 3.41571215724354*^9, 3.415712894731263*^9, 3.415713083341153*^9, {3.41571314009251*^9, 3.415713173712418*^9}, 3.415713520815259*^9, 3.4157137439282093`*^9, 3.4157140549323597`*^9, 3.4157141242382717`*^9, 3.4157180495198507`*^9, 3.415729382089579*^9, 3.415729436973137*^9, 3.415729859647913*^9, 3.4189068463867893`*^9, 3.421596805593882*^9, 3.421598257214778*^9, 3.4215984582509823`*^9, 3.421598504608177*^9, 3.4215991086603613`*^9, 3.4215991595927773`*^9, 3.42160783936209*^9, 3.421607960585394*^9, 3.432603145548767*^9, { 3.433898876943317*^9, 3.433898886497159*^9}, 3.433898917426325*^9, 3.458399058717482*^9, {3.458399098267755*^9, 3.458399121996962*^9}, 3.458400847793364*^9, 3.458404365541157*^9, 3.4584053587271633`*^9, 3.458405492863064*^9, 3.4584058045287743`*^9, 3.458406285390044*^9, 3.458407493674572*^9, 3.458407558413519*^9, 3.4584077069801683`*^9, 3.458408390966445*^9, 3.458408496034349*^9, 3.4584090020687933`*^9, 3.45840966477188*^9, {3.458423460343501*^9, 3.458423469547593*^9}, 3.458423531882432*^9, 3.458423602267906*^9, 3.4584241364016113`*^9, 3.4584243525429993`*^9, 3.458424385729306*^9, 3.458424455826763*^9, 3.458424680129889*^9, 3.458424759819853*^9, 3.4584247962210083`*^9, 3.4584832751238737`*^9, 3.458483419580353*^9, 3.45848350640598*^9, 3.458483555029632*^9, {3.458483612624715*^9, 3.458483623596539*^9}, 3.458483947450109*^9}], Cell["\<\ The probability of a random polynomial having no linear factors is\ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4156326048826103`*^9, {3.4157105847159452`*^9, 3.415710641702524*^9}, { 3.458483222480753*^9, 3.458483224230176*^9}, {3.458483304308133*^9, 3.458483305217*^9}, 3.458483612624791*^9}], Cell[BoxData[ RowBox[{ RowBox[{"1", "-", RowBox[{ RowBox[{"NumberOfPolynomialsWithLinearFactors", "[", RowBox[{"p", ",", "n"}], "]"}], "/", RowBox[{"NumberOfPolynomials", "[", RowBox[{"p", ",", "n"}], "]"}]}]}], "//", "N"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415710592162369*^9, 3.415710606601947*^9}, { 3.415710654221059*^9, 3.415710727930529*^9}, {3.415710780621934*^9, 3.415710814279649*^9}, {3.458483232696302*^9, 3.458483252784148*^9}, 3.4584836126248627`*^9}], Cell[BoxData["0.672`"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4157106995314837`*^9, 3.4157107306041107`*^9}, { 3.415710777234284*^9, 3.415710815754734*^9}, 3.4157121110804*^9, 3.4157121573012447`*^9, 3.415712894798493*^9, 3.4157130834074383`*^9, { 3.415713140161476*^9, 3.41571317376884*^9}, 3.41571352088232*^9, 3.415713743998373*^9, 3.415714054988126*^9, 3.4157141242951727`*^9, 3.41571804964305*^9, 3.415729382169346*^9, 3.415729437055616*^9, 3.4157298597227497`*^9, 3.418906846447809*^9, 3.4215968056559057`*^9, 3.4215982572651587`*^9, 3.42159845831155*^9, 3.421598504656681*^9, 3.421599108711113*^9, 3.421599159648341*^9, 3.421607839412633*^9, 3.421607960659511*^9, 3.4326031455948668`*^9, {3.433898876983086*^9, 3.433898886534178*^9}, 3.433898917461718*^9, 3.458399058754393*^9, { 3.458399098314857*^9, 3.458399122040902*^9}, 3.458400847843734*^9, 3.4584043655898457`*^9, 3.4584053587934523`*^9, 3.458405492905326*^9, 3.4584058045773*^9, 3.458406285426485*^9, 3.4584074937073717`*^9, 3.458407558458104*^9, 3.458407707026134*^9, 3.458408391133236*^9, 3.458408496067931*^9, 3.458409002237196*^9, 3.458409664822208*^9, { 3.458423460380917*^9, 3.458423469615378*^9}, 3.4584235319377413`*^9, 3.4584236023177443`*^9, 3.4584241364635067`*^9, 3.4584243526103086`*^9, 3.458424385779976*^9, 3.458424455859851*^9, 3.4584246801803913`*^9, 3.458424759853088*^9, 3.458424796254155*^9, {3.458483254458556*^9, 3.458483275177066*^9}, 3.4584834196290913`*^9, 3.458483506440522*^9, 3.458483555073436*^9, {3.4584836126249437`*^9, 3.458483623636725*^9}, 3.458483947489317*^9}], Cell[TextData[{ "Is ", StyleBox["a", FontWeight->"Bold"], " a primitive root of p, i.e. does ", StyleBox["a", FontWeight->"Bold"], " generate the multiplicative group GF(p)?" }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.41563322485546*^9, 3.415633262659584*^9}, 3.45848361262502*^9}], Cell[BoxData[ RowBox[{ RowBox[{ RowBox[{"IsPrimitiveRoot", "[", " ", RowBox[{"a_", ",", " ", "p_"}], " ", "]"}], " ", ":=", " ", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"MultiplicativeOrder", "[", RowBox[{"a", ",", "p"}], "]"}], " ", "\[Equal]", " ", RowBox[{"p", "-", "1"}]}], ",", "\[IndentingNewLine]", RowBox[{"isPrimitiveRoot", " ", "=", " ", "True"}], ",", " ", RowBox[{"isPrimitiveRoot", " ", "=", " ", "False"}]}], "]"}]}], ";"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632776770362*^9, 3.415632829408029*^9}, 3.458483612625094*^9}], Cell[BoxData[ RowBox[{"IsPrimitiveRoot", "[", RowBox[{"4", ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633088255333*^9, 3.415633119251072*^9}, 3.4584836126251717`*^9}], Cell[BoxData["False"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563309506371*^9, 3.415633119671541*^9}, { 3.4156347868594112`*^9, 3.415634804265058*^9}, 3.415634838511099*^9, { 3.415635706011767*^9, 3.415635709313044*^9}, 3.415640641921805*^9, 3.415641785005921*^9, {3.415644491592021*^9, 3.4156445097506037`*^9}, 3.415646036960273*^9, 3.4156462489391727`*^9, 3.415647092395363*^9, 3.415647185026619*^9, 3.415647973402569*^9, 3.415649014871867*^9, 3.415650173981666*^9, 3.4156503431361628`*^9, 3.415651093419759*^9, { 3.4157106996367683`*^9, 3.415710713284904*^9}, 3.4157121111477203`*^9, 3.4157121573677464`*^9, 3.415712894878517*^9, 3.4157130834876432`*^9, { 3.415713140244813*^9, 3.41571317383611*^9}, 3.415713520959447*^9, 3.4157137440847797`*^9, 3.415714055048291*^9, 3.415714124376416*^9, 3.4157180497848673`*^9, 3.4157293822712297`*^9, 3.415729437133459*^9, 3.415729859869801*^9, 3.418906846510957*^9, 3.421596805738201*^9, 3.421598257367198*^9, 3.421598458384446*^9, 3.4215985047246113`*^9, 3.42159910878015*^9, 3.421599159712223*^9, 3.421607839513275*^9, 3.4216079607394*^9, 3.432603145660281*^9, {3.4338988770456743`*^9, 3.433898886601638*^9}, 3.4338989175249557`*^9, 3.4583990588404408`*^9, { 3.458399098381815*^9, 3.458399122106639*^9}, 3.458400847967926*^9, 3.4584043656745253`*^9, 3.458405358856608*^9, 3.45840549297152*^9, 3.458405804640641*^9, 3.458406285505704*^9, 3.458407493758173*^9, 3.458407558520163*^9, 3.4584077070755997`*^9, 3.458408391231431*^9, 3.458408496134705*^9, 3.458409002333046*^9, 3.4584096648882513`*^9, { 3.458423460447754*^9, 3.458423469711735*^9}, 3.458423532004939*^9, 3.4584236023658867`*^9, 3.458424136499732*^9, 3.458424352706098*^9, 3.458424385822669*^9, 3.458424455909034*^9, 3.4584246802768383`*^9, 3.45842475991903*^9, 3.458424796288192*^9, 3.458483275255485*^9, 3.458483419700121*^9, 3.4584835064892397`*^9, 3.458483555123658*^9, { 3.458483612625251*^9, 3.458483623702854*^9}, 3.458483947556477*^9}], Cell["a = 4 is not a generator of GF(p)", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563300953085*^9, 3.4156330109049473`*^9}, { 3.4157104592348137`*^9, 3.4157104600021753`*^9}, {3.458420620844285*^9, 3.458420649441957*^9}, 3.458483612625327*^9}], Cell[BoxData[ RowBox[{"Table", "[", RowBox[{ RowBox[{"Mod", "[", RowBox[{ SuperscriptBox["4", "k"], ",", "p"}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", RowBox[{"p", "-", "1"}]}], "}"}]}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633132150193*^9, 3.415633197647007*^9}, 3.458483612625442*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"4", ",", "1", ",", "4", ",", "1"}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633180065971*^9, 3.415633198700671*^9}, { 3.415634786936529*^9, 3.415634804362591*^9}, 3.415634838560453*^9, 3.4156406420073833`*^9, 3.415641785102766*^9, {3.415644491679998*^9, 3.415644509830392*^9}, 3.415646037056761*^9, 3.415646250428301*^9, 3.4156470925298367`*^9, 3.415647185116467*^9, 3.41564797350959*^9, 3.415649014934451*^9, 3.415650174081758*^9, 3.415650343216241*^9, 3.41565109350745*^9, {3.415710699696582*^9, 3.4157107133617773`*^9}, 3.415712111201256*^9, 3.415712157417041*^9, 3.415712894932252*^9, 3.415713083557501*^9, {3.415713140316297*^9, 3.4157131738891706`*^9}, 3.415713521011273*^9, 3.4157137441531773`*^9, 3.415714055103813*^9, 3.41571412444657*^9, 3.415718049851643*^9, 3.415729382337915*^9, 3.4157294372069674`*^9, 3.415729859941238*^9, 3.418906846560423*^9, 3.421596805806102*^9, 3.4215982574171352`*^9, 3.421598458439831*^9, 3.4215985047842407`*^9, 3.4215991088488903`*^9, 3.421599159764413*^9, 3.4216078395651417`*^9, 3.4216079608119183`*^9, 3.4326031456932583`*^9, { 3.4338988770966454`*^9, 3.433898886635913*^9}, 3.4338989175788803`*^9, 3.458399058887824*^9, {3.458399098414966*^9, 3.458399122141608*^9}, 3.4584008480141373`*^9, 3.458404365706551*^9, 3.458405358905528*^9, 3.4584054930050697`*^9, 3.458405804672914*^9, 3.458406285538106*^9, 3.458407493794099*^9, 3.458407558562661*^9, 3.458407707109297*^9, 3.458408391314904*^9, 3.458408496180286*^9, 3.458409002416665*^9, 3.458409664925098*^9, {3.4584234604807243`*^9, 3.4584234697643948`*^9}, 3.458423532054287*^9, 3.458423602417665*^9, 3.4584241365469427`*^9, 3.458424352776299*^9, 3.458424385879733*^9, 3.4584244559424877`*^9, 3.4584246803303223`*^9, 3.45842475995181*^9, 3.458424796317128*^9, 3.4584832753378696`*^9, 3.458483419745165*^9, 3.458483506523394*^9, 3.458483555157352*^9, {3.4584836126255198`*^9, 3.458483623740247*^9}, 3.458483947592618*^9}], Cell[BoxData[ RowBox[{"IsPrimitiveRoot", "[", RowBox[{"3", ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633088255333*^9, 3.415633127383244*^9}, 3.4584836126256027`*^9}], Cell[BoxData["True"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.415633128185506*^9, {3.415634787003109*^9, 3.415634804484405*^9}, 3.4156348386064873`*^9, 3.41564064208936*^9, 3.4156417852028112`*^9, { 3.415644491782672*^9, 3.415644509908437*^9}, 3.415646037162504*^9, 3.415646251797841*^9, 3.415647092646463*^9, 3.4156471852161627`*^9, 3.415647973608452*^9, 3.415649015018957*^9, 3.415650174146681*^9, 3.4156503433208723`*^9, 3.41565109359368*^9, {3.415710699763165*^9, 3.415710713446527*^9}, 3.415712111268203*^9, 3.415712157469997*^9, 3.415712895000389*^9, 3.415713083624954*^9, {3.4157131403831577`*^9, 3.415713173939044*^9}, 3.41571352106592*^9, 3.415713744217299*^9, 3.415714055153976*^9, 3.4157141245139313`*^9, 3.415718049923306*^9, 3.415729382397395*^9, 3.415729437267704*^9, 3.415729860020906*^9, 3.418906846609674*^9, 3.421596805875684*^9, 3.421598257466345*^9, 3.421598458489016*^9, 3.421598504847672*^9, 3.4215991088990726`*^9, 3.421599159815486*^9, 3.421607839635715*^9, 3.4216079608775187`*^9, 3.4326031457285547`*^9, {3.433898877133065*^9, 3.433898886673328*^9}, 3.4338989176146*^9, 3.458399058925394*^9, {3.458399098469041*^9, 3.45839912217754*^9}, 3.458400848060117*^9, 3.458404365756103*^9, 3.4584053589431667`*^9, 3.4584054930541277`*^9, 3.45840580472726*^9, 3.4584062855927773`*^9, 3.458407493839525*^9, 3.45840755860828*^9, 3.458407707158134*^9, 3.4584083913987217`*^9, 3.458408496218297*^9, 3.4584090024995213`*^9, 3.4584096649575567`*^9, {3.458423460526737*^9, 3.4584234698316298`*^9}, 3.4584235320873747`*^9, 3.458423602454488*^9, 3.458424136595923*^9, 3.4584243528426867`*^9, 3.458424385911805*^9, 3.458424455980823*^9, 3.4584246803963957`*^9, 3.458424759985615*^9, 3.4584247963494062`*^9, 3.458483275421712*^9, 3.458483419796618*^9, 3.458483506568342*^9, 3.458483555208776*^9, {3.458483612625679*^9, 3.458483623774193*^9}, 3.458483947639387*^9}], Cell[TextData[{ "But a = 3 ", StyleBox["is", FontWeight->"Bold"], " a generator of GF(p)" }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563300953085*^9, 3.4156330109049473`*^9}, { 3.4157104592348137`*^9, 3.4157104600021753`*^9}, {3.458420620844285*^9, 3.458420667890478*^9}, 3.458483612625763*^9}], Cell[BoxData[ RowBox[{"Table", "[", RowBox[{ RowBox[{"Mod", "[", RowBox[{ SuperscriptBox["3", "k"], ",", "p"}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", RowBox[{"p", "-", "1"}]}], "}"}]}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633132150193*^9, 3.415633212106399*^9}, 3.4584836126258373`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"3", ",", "4", ",", "2", ",", "1"}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4156332137672462`*^9, {3.415634787070405*^9, 3.415634804553694*^9}, 3.415634838686432*^9, 3.415640642159793*^9, 3.415641785290427*^9, { 3.415644491868044*^9, 3.415644509982461*^9}, 3.415646037264257*^9, 3.4156462534568777`*^9, 3.4156470927564573`*^9, 3.415647185303925*^9, 3.415647973699347*^9, 3.415649015090111*^9, 3.415650174216007*^9, 3.415650343406683*^9, 3.415651093672814*^9, {3.4157106998304653`*^9, 3.415710713529201*^9}, 3.415712111334737*^9, 3.415712157521742*^9, 3.415712895066462*^9, 3.4157130836919518`*^9, {3.415713140452003*^9, 3.415713174007275*^9}, 3.4157135211329947`*^9, 3.415713744283163*^9, 3.415714055203186*^9, 3.415714124582156*^9, 3.415718050008543*^9, 3.41572938246953*^9, 3.415729437336615*^9, 3.41572986009343*^9, 3.418906846661066*^9, 3.421596805939559*^9, 3.4215982575163183`*^9, 3.421598458539742*^9, 3.421598504914001*^9, 3.42159910894781*^9, 3.421599159867399*^9, 3.421607839704276*^9, 3.4216079609445677`*^9, 3.43260314577925*^9, {3.4338988771985207`*^9, 3.4338988867187557`*^9}, 3.43389891767955*^9, 3.4583990589581213`*^9, {3.458399098514801*^9, 3.4583991222244864`*^9}, 3.458400848110243*^9, 3.458404365807701*^9, 3.458405358989189*^9, 3.458405493108169*^9, 3.458405804773447*^9, 3.458406285643899*^9, 3.458407493893876*^9, 3.458407558662176*^9, 3.458407707203841*^9, 3.458408391481451*^9, 3.458408496263019*^9, 3.458409002585125*^9, 3.45840966500478*^9, {3.4584234605639343`*^9, 3.45842346989774*^9}, 3.458423532130995*^9, 3.458423602500182*^9, 3.4584241366464*^9, 3.458424352909099*^9, 3.4584243859655247`*^9, 3.458424456046207*^9, 3.458424680463378*^9, 3.45842476002676*^9, 3.4584247963828173`*^9, 3.4584832755048113`*^9, 3.458483419827538*^9, 3.4584835066192703`*^9, 3.458483555256925*^9, {3.458483612625914*^9, 3.458483623819821*^9}, 3.458483947692*^9}], Cell["Extract a polynomial's constant term,", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415650291105389*^9, 3.4156502944238873`*^9}, {3.415710850414256*^9, 3.415710851954792*^9}, 3.458483612625989*^9}], Cell[BoxData[ RowBox[{ RowBox[{ RowBox[{"ConstantTermOfPolynomial", "[", "f_", "]"}], ":=", RowBox[{ RowBox[{"CoefficientList", "[", RowBox[{"f", ",", "x"}], "]"}], "[", RowBox[{"[", "1", "]"}], "]"}]}], ";"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633500873073*^9, 3.4156335108394413`*^9}, 3.458483612626071*^9}], Cell[BoxData[ RowBox[{"ConstantTermOfPolynomial", "[", "f", "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415633519322632*^9, 3.41563352475846*^9}, 3.458483612626149*^9}], Cell[BoxData["3"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.415633525549226*^9, {3.415634787175434*^9, 3.4156348046523943`*^9}, 3.415634838781304*^9, 3.415635504941071*^9, 3.415640642266477*^9, 3.415641785475389*^9, {3.415644491984138*^9, 3.415644510069747*^9}, 3.41564603768685*^9, 3.415646258722986*^9, 3.415647092912888*^9, 3.415647185439789*^9, 3.415647973833756*^9, 3.415649015178849*^9, 3.4156501742945633`*^9, 3.415650343517626*^9, 3.415651093765204*^9, { 3.415710699910944*^9, 3.4157107136258163`*^9}, 3.415712111413981*^9, 3.41571215758387*^9, 3.415712895145294*^9, 3.415713083790173*^9, { 3.415713140530616*^9, 3.415713174087311*^9}, 3.41571352120993*^9, 3.415713744368298*^9, 3.4157140552682543`*^9, 3.415714124663447*^9, 3.4157180501923943`*^9, 3.415729382548308*^9, 3.415729437403702*^9, 3.415729860225095*^9, 3.418906846738098*^9, 3.421596806038989*^9, 3.4215982576168747`*^9, 3.421598458603518*^9, 3.421598504976753*^9, 3.421599109010667*^9, 3.421599159930128*^9, 3.421607839819817*^9, 3.4216079610423603`*^9, 3.432603145912444*^9, {3.433898877262764*^9, 3.433898886786178*^9}, 3.4338989177441883`*^9, 3.458399059024747*^9, { 3.458399098574136*^9, 3.458399122272892*^9}, 3.4584008482139597`*^9, 3.458404365909667*^9, 3.458405359073019*^9, 3.4584054931887503`*^9, 3.458405804860722*^9, 3.458406285748835*^9, 3.45840749397283*^9, 3.458407558735897*^9, 3.45840770727627*^9, 3.458408391614097*^9, 3.4584084963302393`*^9, 3.458409002715966*^9, 3.458409665073257*^9, { 3.4584234606604357`*^9, 3.4584234699957447`*^9}, 3.45842353220476*^9, 3.458423602566985*^9, 3.458424136713896*^9, 3.458424353023241*^9, 3.458424386012052*^9, 3.4584244561083937`*^9, 3.4584246805769176`*^9, 3.458424760102409*^9, 3.4584247964323483`*^9, 3.458483275638405*^9, 3.45848341988535*^9, 3.4584835066893682`*^9, 3.458483555323621*^9, { 3.458483612626227*^9, 3.458483623886324*^9}, 3.458483947758252*^9}], Cell["Test if a polynomial is constant,", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415650291105389*^9, 3.4156502944238873`*^9}, {3.415710850414256*^9, 3.415710851954792*^9}, { 3.415710909517223*^9, 3.415710917048912*^9}, 3.4584836126263027`*^9}], Cell[BoxData[ RowBox[{ RowBox[{"PolynomialIsConstant", "[", "f_", "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Exponent", "[", RowBox[{"f", ",", "x"}], "]"}], " ", "\[Equal]", " ", "0"}], ",", " ", "True", ",", "False"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415635300515997*^9, 3.415635308457017*^9}, { 3.4157131242503443`*^9, 3.4157131526259193`*^9}, 3.45848361262639*^9}], Cell[BoxData[ RowBox[{"PolynomialIsConstant", "[", "3", "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156353214770393`*^9, 3.4156353325512533`*^9}, 3.4584836126264687`*^9}], Cell[BoxData["True"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4156353329920588`*^9, 3.415640642659871*^9, 3.415641785923272*^9, { 3.4156444924419127`*^9, 3.41564451045094*^9}, 3.415646038265326*^9, 3.4156462744982653`*^9, 3.41564709346174*^9, 3.4156471858172894`*^9, 3.415647974333879*^9, 3.415649015502144*^9, 3.415650174616613*^9, 3.415650344075823*^9, 3.415651094090455*^9, {3.415710700181785*^9, 3.4157107140274267`*^9}, 3.415712111535612*^9, 3.415712157684106*^9, 3.4157128952659693`*^9, {3.415713079511362*^9, 3.4157130839276953`*^9}, { 3.4157131406442337`*^9, 3.4157131741497517`*^9}, 3.4157135212702103`*^9, 3.415713744443636*^9, 3.415714055334159*^9, 3.415714124745625*^9, 3.415718050342393*^9, 3.41572938264398*^9, 3.415729437482305*^9, 3.41572986033731*^9, 3.418906846810511*^9, 3.421596806118116*^9, 3.4215982577175837`*^9, 3.421598458670395*^9, 3.421598505041181*^9, 3.421599109075756*^9, 3.421599159995652*^9, 3.4216078399209557`*^9, 3.421607961126857*^9, 3.432603145970848*^9, {3.433898877323762*^9, 3.43389888683633*^9}, 3.4338989178032227`*^9, 3.458399059107025*^9, { 3.4583990986195173`*^9, 3.458399122328508*^9}, 3.458400848314032*^9, 3.458404366010458*^9, 3.4584053591400433`*^9, 3.4584054932412033`*^9, 3.4584058049105387`*^9, 3.458406285866062*^9, 3.45840749402838*^9, 3.458407558783595*^9, 3.458407707317367*^9, 3.458408391763667*^9, 3.45840849637246*^9, 3.4584090028667316`*^9, 3.458409665138995*^9, { 3.4584234607429047`*^9, 3.458423470079316*^9}, 3.4584235322411537`*^9, 3.458423602616457*^9, 3.458424136762375*^9, 3.458424353106778*^9, 3.458424386079691*^9, 3.4584244561461687`*^9, 3.4584246806606627`*^9, 3.4584247601387568`*^9, 3.4584247964829807`*^9, 3.4584832757538*^9, 3.45848341993295*^9, 3.458483506731864*^9, 3.458483555374052*^9, { 3.458483612626547*^9, 3.458483623928233*^9}, 3.458483947806383*^9}], Cell["\<\ Evaluate a polynomial at {0,...,p-1} to check if it has any zeros over GF(p),\ \ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415634307222859*^9, 3.4156343396272087`*^9}, {3.415710923543201*^9, 3.415710927864895*^9}, 3.458483612626627*^9}], Cell[BoxData[ RowBox[{ RowBox[{"PolynomialHasLinearFactor", "[", RowBox[{"f_", ",", "p_"}], "]"}], ":=", RowBox[{"MemberQ", "[", " ", RowBox[{ RowBox[{"Table", "[", RowBox[{ RowBox[{ RowBox[{"Mod", "[", RowBox[{"f", ",", "p"}], "]"}], "/.", RowBox[{"x", "\[Rule]", "i"}]}], ",", RowBox[{"{", RowBox[{"i", ",", "0", ",", RowBox[{"p", "-", "1"}]}], "}"}]}], "]"}], ",", " ", "0"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415634231154682*^9, 3.415634249306583*^9}, 3.4156342936831303`*^9, 3.4157125425591288`*^9, 3.458483612626711*^9}], Cell[BoxData[ RowBox[{"PolynomialHasLinearFactor", "[", RowBox[{ RowBox[{ SuperscriptBox["x", "4"], "+", "2"}], ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563425957725*^9, 3.4156342728642282`*^9}, 3.458483612626789*^9}], Cell[BoxData["False"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415634273895193*^9, 3.415634296529438*^9}, { 3.415634787315136*^9, 3.4156348048702793`*^9}, 3.4156348388593187`*^9, 3.415635743150779*^9, 3.4156406424152527`*^9, 3.415641785577388*^9, { 3.415644492117461*^9, 3.415644510173394*^9}, 3.415646037980056*^9, 3.415646261236525*^9, 3.415647093048315*^9, 3.415647185550112*^9, 3.4156479739739037`*^9, 3.415649015275261*^9, 3.4156501743758497`*^9, 3.41565034364432*^9, 3.415651093855545*^9, {3.41571069997363*^9, 3.415710713737164*^9}, 3.415712111616414*^9, 3.415712157751129*^9, { 3.415712546203333*^9, 3.415712555602702*^9}, 3.415712895345521*^9, 3.415713084037778*^9, {3.41571314074804*^9, 3.415713174234007*^9}, 3.4157135213417377`*^9, 3.415713744525963*^9, 3.415714055434471*^9, 3.415714124824078*^9, 3.415718050493402*^9, 3.415729382789927*^9, 3.415729437567546*^9, 3.4157298605597057`*^9, 3.418906846894576*^9, 3.42159680620052*^9, 3.4215982578186913`*^9, 3.421598458735983*^9, 3.421598505101708*^9, 3.421599109192481*^9, 3.421599160079619*^9, 3.4216078400297832`*^9, 3.4216079612079372`*^9, 3.432603146060467*^9, { 3.433898877406711*^9, 3.4338988868772783`*^9}, 3.433898917874825*^9, 3.458399059175193*^9, {3.458399098669313*^9, 3.458399122377989*^9}, 3.4584008484105864`*^9, 3.4584043661429853`*^9, 3.458405359188184*^9, 3.458405493291013*^9, 3.4584058049608727`*^9, 3.4584062859678802`*^9, 3.458407494078211*^9, 3.458407558845533*^9, 3.458407707379073*^9, 3.458408391896715*^9, 3.458408496418962*^9, 3.4584090029988813`*^9, 3.458409665205578*^9, {3.458423460826429*^9, 3.458423470178173*^9}, 3.458423532292398*^9, 3.458423602683669*^9, 3.4584241368299723`*^9, 3.4584243531906137`*^9, 3.458424386128639*^9, 3.458424456196578*^9, 3.458424680744072*^9, 3.458424760190311*^9, 3.458424796532843*^9, 3.458483275908798*^9, 3.4584834199829483`*^9, 3.458483506777227*^9, 3.4584835554229507`*^9, {3.4584836126268673`*^9, 3.4584836239742317`*^9}, 3.458483947856423*^9}], Cell[BoxData[ RowBox[{"PolynomialHasLinearFactor", "[", RowBox[{ RowBox[{"x", "+", "2"}], ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.41563425957725*^9, 3.41563428274382*^9}, { 3.4157125245982943`*^9, 3.415712552209229*^9}, 3.4584836126269493`*^9}], Cell[BoxData["True"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415634283797707*^9, 3.415634297925415*^9}, { 3.415634787389089*^9, 3.4156348050527067`*^9}, 3.415634838936866*^9, { 3.415635736595067*^9, 3.415635757056679*^9}, 3.4156406424812727`*^9, 3.41564178566704*^9, {3.415644492218564*^9, 3.415644510254394*^9}, 3.415646038067634*^9, 3.415646262480812*^9, 3.415647093187038*^9, 3.415647185614691*^9, 3.415647974070492*^9, 3.4156490153349657`*^9, 3.4156501744500723`*^9, 3.415650343824132*^9, 3.4156510939230747`*^9, { 3.415710700043401*^9, 3.415710713839307*^9}, 3.4157121116687813`*^9, 3.4157121578008537`*^9, {3.4157125327161703`*^9, 3.415712557108018*^9}, 3.415712895398634*^9, 3.41571308410688*^9, {3.415713140814704*^9, 3.4157131743043623`*^9}, 3.4157135214154177`*^9, 3.415713744596177*^9, 3.415714055523374*^9, 3.4157141248973103`*^9, 3.415718050561502*^9, 3.4157293828511667`*^9, 3.4157294376919947`*^9, 3.415729860628861*^9, 3.418906846966288*^9, 3.421596806272889*^9, 3.421598257868381*^9, 3.4215984587905416`*^9, 3.421598505161503*^9, 3.42159910924885*^9, 3.4215991601538*^9, 3.421607840081012*^9, 3.42160796127969*^9, 3.432603146094892*^9, {3.4338988774653397`*^9, 3.4338988869447403`*^9}, 3.433898917947255*^9, 3.458399059207808*^9, {3.458399098714511*^9, 3.4583991224231443`*^9}, 3.4584008484610443`*^9, 3.458404366209779*^9, 3.4584053592384768`*^9, 3.458405493336255*^9, 3.458405805005971*^9, 3.4584062860189867`*^9, 3.458407494122533*^9, 3.4584075588911858`*^9, 3.458407707425033*^9, 3.4584083919802628`*^9, 3.458408496464177*^9, 3.458409003081873*^9, 3.458409665241534*^9, {3.458423460863263*^9, 3.4584234702306337`*^9}, 3.458423532337109*^9, 3.4584236027209177`*^9, 3.458424136861664*^9, 3.458424353242219*^9, 3.458424386162216*^9, 3.458424456246546*^9, 3.458424680812595*^9, 3.458424760236112*^9, 3.4584247965654907`*^9, 3.4584832759882727`*^9, 3.458483420028*^9, 3.458483506822497*^9, 3.4584835554553337`*^9, {3.458483612627035*^9, 3.4584836240192432`*^9}, 3.458483947890081*^9}], Cell[TextData[{ "Evaluate ", Cell[BoxData[ StyleBox[ RowBox[{ RowBox[{ SuperscriptBox["x", "pk"], RowBox[{"(", RowBox[{ RowBox[{"mod", " ", "f", RowBox[{"(", "x", ")"}]}], ",", "p"}], ")"}]}], ",", RowBox[{"0", " ", "\[LessEqual]", "k", "\[LessEqual]", RowBox[{"n", "-", "1"}]}]}], "Subsection"]]] }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415634307222859*^9, 3.4156343396272087`*^9}, 3.415640546540505*^9, 3.458483612627112*^9}], Cell[BoxData[ RowBox[{ RowBox[{"PowersOfXModFP", "[", RowBox[{"f_", ",", " ", "p_", ",", " ", "n_"}], "]"}], " ", ":=", " ", RowBox[{"Table", "[", " ", RowBox[{ RowBox[{"PolynomialMod", "[", " ", RowBox[{ SuperscriptBox["x", RowBox[{"p", " ", "k"}]], " ", ",", " ", RowBox[{"{", RowBox[{"f", ",", " ", "p"}], "}"}]}], " ", "]"}], ",", " ", RowBox[{"{", RowBox[{"k", ",", " ", "0", ",", " ", RowBox[{"n", "-", "1"}]}], "}"}]}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415640561344247*^9, 3.415640627976019*^9}, 3.458483612627184*^9}], Cell[BoxData[ RowBox[{"PowersOfXModFP", "[", RowBox[{"f", ",", "p", ",", " ", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415640613243536*^9, 3.415640631235248*^9}, 3.458483612627261*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"1", ",", RowBox[{ RowBox[{"2", " ", "x"}], "+", RowBox[{"3", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"3", "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", SuperscriptBox["x", "3"]}], ",", RowBox[{ RowBox[{"4", " ", "x"}], "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "3"]}]}]}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415634788441757*^9, 3.4156348069656553`*^9}, 3.4156348399478483`*^9, {3.415640621869787*^9, 3.4156406427564077`*^9}, { 3.415640736954583*^9, 3.415640738632154*^9}, 3.4156417860860653`*^9, { 3.415644492587438*^9, 3.415644510542243*^9}, 3.415644750589613*^9, 3.415644787817424*^9, 3.415646038407667*^9, 3.415646143223974*^9, 3.4156462783693666`*^9, 3.4156470935740356`*^9, 3.415647185918185*^9, 3.415647974572494*^9, 3.4156490156168118`*^9, 3.41565017477241*^9, 3.41565034421621*^9, 3.41565109421577*^9, {3.415710700328373*^9, 3.415710714137689*^9}, 3.415712111751136*^9, 3.4157121578683577`*^9, 3.415712895507921*^9, 3.415713084197234*^9, {3.41571314095625*^9, 3.415713174391326*^9}, 3.415713521479813*^9, 3.415713744686644*^9, 3.415714055604105*^9, 3.415714124978828*^9, 3.4157180507118998`*^9, 3.415729382955022*^9, 3.415729437784665*^9, 3.415729860760243*^9, 3.418906847044623*^9, 3.4215968064194517`*^9, 3.421598258003318*^9, 3.421598458887203*^9, 3.421598505244155*^9, 3.421599109311673*^9, 3.4215991602161922`*^9, 3.421607840279904*^9, 3.4216079613837833`*^9, 3.432603146189661*^9, {3.433898877570281*^9, 3.433898887004656*^9}, 3.433898918010635*^9, 3.45839905929978*^9, {3.458399098764584*^9, 3.458399122473571*^9}, 3.4584008485803022`*^9, 3.458404366343054*^9, 3.458405359305461*^9, 3.4584054933868856`*^9, 3.458405805057682*^9, 3.4584062861193542`*^9, 3.458407494173279*^9, 3.4584075589421062`*^9, 3.458407707475428*^9, 3.4584083923614902`*^9, 3.45840849653053*^9, 3.45840900351336*^9, 3.458409665286907*^9, {3.4584234609472103`*^9, 3.458423470327437*^9}, 3.458423532387672*^9, 3.458423602771966*^9, 3.458424136928919*^9, 3.458424353339881*^9, 3.45842438622908*^9, 3.458424456292644*^9, 3.458424680927052*^9, 3.458424760285577*^9, 3.4584247966049967`*^9, 3.458483276119648*^9, 3.45848342007329*^9, 3.458483506873713*^9, 3.458483555514206*^9, {3.458483612627345*^9, 3.4584836240692043`*^9}, 3.458483947956094*^9}], Cell[TextData[{ "Form the Q matrix from the rows of coefficients of the powers ", Cell[BoxData[ StyleBox[ RowBox[{ RowBox[{ SuperscriptBox["x", "pk"], RowBox[{"(", RowBox[{ RowBox[{"mod", " ", "f", RowBox[{"(", "x", ")"}]}], ",", "p"}], ")"}]}], ",", RowBox[{"0", " ", "\[LessEqual]", "k", "\[LessEqual]", RowBox[{"n", "-", "1"}]}]}], "Subsection"]]] }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415634307222859*^9, 3.4156343396272087`*^9}, 3.415640546540505*^9, {3.4157109574951487`*^9, 3.4157109681841927`*^9}, 3.458483612627421*^9}], Cell[BoxData[ RowBox[{ RowBox[{"PadRightRows", "[", RowBox[{"L_", ",", "n_"}], "]"}], ":=", RowBox[{"Map", "[", " ", RowBox[{ RowBox[{"Function", "[", " ", RowBox[{"x", ",", " ", RowBox[{"PadRight", "[", RowBox[{"x", ",", "n"}], "]"}]}], "]"}], ",", " ", "L"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415644945212062*^9, 3.415645048938745*^9}, 3.458483612627492*^9}], Cell[BoxData[ RowBox[{"PadRightRows", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"{", "1", "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"1", ",", "0", ",", "1"}], "}"}], ",", RowBox[{"{", "1", "}"}]}], "}"}], ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415645097396462*^9, 3.4156451094650373`*^9}, 3.458483612627569*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"1", ",", "0", ",", "0", ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", "1", ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"1", ",", "0", ",", "1", ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"1", ",", "0", ",", "0", ",", "0"}], "}"}]}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.415645114837758*^9, 3.4156460385596733`*^9, 3.415646303768618*^9, 3.41564709369956*^9, 3.415647186060049*^9, 3.41564797477886*^9, 3.4156490157025337`*^9, 3.4156501748693247`*^9, 3.415650344382494*^9, 3.4156510943106127`*^9, {3.415710700407217*^9, 3.415710714212523*^9}, 3.415712111880237*^9, 3.41571215792953*^9, 3.415712895580624*^9, 3.415713084271872*^9, {3.4157131410314093`*^9, 3.4157131745552073`*^9}, 3.4157135215421467`*^9, 3.415713744796177*^9, 3.415714055719214*^9, 3.4157141251014557`*^9, 3.4157180508611813`*^9, 3.415729383056306*^9, 3.415729437875888*^9, 3.415729860890579*^9, 3.418906847113864*^9, 3.421596806486763*^9, 3.4215982581030617`*^9, 3.421598458948512*^9, 3.421598505308248*^9, 3.421599109376172*^9, 3.421599160282729*^9, 3.421607840380361*^9, 3.421607961501206*^9, 3.432603146241108*^9, { 3.4338988776556253`*^9, 3.4338988870610743`*^9}, 3.433898918054804*^9, 3.4583990594033957`*^9, {3.458399098813699*^9, 3.458399122523226*^9}, 3.458400848663872*^9, 3.4584043665055923`*^9, 3.45840535934912*^9, 3.458405493437643*^9, 3.4584058051053257`*^9, 3.458406286174774*^9, 3.4584074942233267`*^9, 3.458407558990715*^9, 3.458407707526011*^9, 3.458408392496524*^9, 3.4584084965794888`*^9, 3.45840900364885*^9, 3.458409665354047*^9, {3.458423461029634*^9, 3.4584234704287043`*^9}, 3.458423532436984*^9, 3.458423602821204*^9, 3.458424136967078*^9, 3.458424353456604*^9, 3.45842438627899*^9, 3.458424456341729*^9, 3.458424681061494*^9, 3.458424760335349*^9, 3.458424796638988*^9, 3.458483276253461*^9, 3.458483420122798*^9, 3.458483506923504*^9, 3.458483555580723*^9, {3.458483612627651*^9, 3.4584836241192627`*^9}, 3.458483948027554*^9}], Cell[BoxData[ RowBox[{ RowBox[{"QMatrix", "[", " ", RowBox[{"f_", ",", " ", "p_", ",", " ", "n_"}], " ", "]"}], " ", ":=", " ", RowBox[{"PadRightRows", "[", RowBox[{ RowBox[{"CoefficientList", "[", " ", RowBox[{ RowBox[{"PowersOfXModFP", "[", RowBox[{"f", ",", "p", ",", " ", "n"}], "]"}], ",", "x"}], " ", "]"}], ",", "n"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415640713913618*^9, 3.415640751192862*^9}, { 3.415640789921249*^9, 3.415640808688479*^9}, {3.4156447928270473`*^9, 3.415644806587051*^9}, {3.415645058581504*^9, 3.415645064340135*^9}, 3.458483612627734*^9}], Cell[BoxData[ RowBox[{ RowBox[{"QMatrix", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}], "//", " ", "MatrixForm"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415640786578743*^9, 3.4156407872094088`*^9}, { 3.4156408175690107`*^9, 3.415640826446797*^9}, 3.4584836126278133`*^9}], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0"}, {"0", "2", "3", "4"}, {"3", "0", "4", "1"}, {"0", "4", "4", "3"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4156409074042273`*^9, 3.415640966547542*^9, 3.415641486354044*^9, { 3.415641781215197*^9, 3.415641786264559*^9}, {3.4156444927082853`*^9, 3.415644510640387*^9}, {3.415644746814834*^9, 3.415644754499817*^9}, { 3.4156447961300592`*^9, 3.415644808625964*^9}, 3.415645068171023*^9, 3.415645117450719*^9, 3.415646038680664*^9, 3.4156463139031*^9, 3.415647093889565*^9, 3.4156471861712112`*^9, 3.415647974872468*^9, 3.4156490158612223`*^9, 3.4156501749600563`*^9, 3.415650344541892*^9, 3.4156510943960247`*^9, {3.415710700477817*^9, 3.415710714275341*^9}, 3.415712111947399*^9, 3.415712158002961*^9, 3.415712895648602*^9, 3.415713084335102*^9, {3.4157131410932426`*^9, 3.4157131746430693`*^9}, 3.415713521669691*^9, 3.415713744881206*^9, 3.41571405578824*^9, 3.415714125176711*^9, 3.415718050998198*^9, 3.415729383184458*^9, 3.4157294379508677`*^9, 3.4157298610585337`*^9, 3.418906847217379*^9, 3.421596806569621*^9, 3.421598258205823*^9, 3.421598459027214*^9, 3.421598505396159*^9, 3.421599109476457*^9, 3.421599160353155*^9, 3.421607840481498*^9, 3.4216079615773973`*^9, 3.4326031464007063`*^9, { 3.433898877773066*^9, 3.4338988871317453`*^9}, 3.433898918140615*^9, 3.45839905954939*^9, {3.458399098867836*^9, 3.4583991225732727`*^9}, 3.4584008487624273`*^9, 3.4584043666065817`*^9, 3.458405359434587*^9, 3.458405493492696*^9, 3.458405805160882*^9, 3.458406286226345*^9, 3.458407494273799*^9, 3.4584075590466423`*^9, 3.458407707575782*^9, 3.45840839266858*^9, 3.458408496647435*^9, 3.458409003781274*^9, 3.458409665396496*^9, {3.458423461113743*^9, 3.458423470527274*^9}, 3.458423532487852*^9, 3.458423602871592*^9, 3.458424137017709*^9, 3.458424353556314*^9, 3.458424386328692*^9, 3.458424456392449*^9, 3.458424681164431*^9, 3.458424760385865*^9, 3.4584247966719513`*^9, 3.458483276394261*^9, 3.458483420174795*^9, 3.458483506972816*^9, 3.4584835556445847`*^9, {3.4584836126278973`*^9, 3.458483624169477*^9}, 3.4584839480774813`*^9}], Cell[BoxData[ RowBox[{ RowBox[{"QIMatrix", "[", RowBox[{"f_", ",", "p_", ",", "n_"}], "]"}], " ", ":=", " ", RowBox[{"Mod", "[", " ", RowBox[{ RowBox[{ RowBox[{"QMatrix", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}], " ", "-", RowBox[{"IdentityMatrix", "[", "n", "]"}]}], ",", " ", "p"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156408474964933`*^9, 3.415640899517598*^9}, { 3.415640950943687*^9, 3.4156409628932037`*^9}, 3.4584836126279793`*^9}], Cell[BoxData[ RowBox[{"QI", "=", RowBox[{"QIMatrix", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415640911370661*^9, 3.4156409335006943`*^9}, { 3.4156409701589937`*^9, 3.415640980659607*^9}, {3.41564102991735*^9, 3.415641058064372*^9}, 3.458483612628057*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"0", ",", "0", ",", "0", ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "1", ",", "3", ",", "4"}], "}"}], ",", RowBox[{"{", RowBox[{"3", ",", "0", ",", "3", ",", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "4", ",", "4", ",", "2"}], "}"}]}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415641464573585*^9, 3.415641488820204*^9}, { 3.4156417765803013`*^9, 3.415641786429284*^9}, {3.415644474732114*^9, 3.4156445107456617`*^9}, 3.415644758896563*^9, 3.415645962793188*^9, 3.415646038804926*^9, 3.415646322985177*^9, {3.415647088137452*^9, 3.415647094101804*^9}, 3.415647186274701*^9, 3.415647974944543*^9, 3.415649016042816*^9, 3.415650175051079*^9, 3.415650344683717*^9, 3.4156510946427727`*^9, {3.415710700561501*^9, 3.415710714354821*^9}, 3.415712112025731*^9, 3.415712158129425*^9, 3.4157128957255907`*^9, 3.4157130844157677`*^9, {3.41571314119453*^9, 3.415713174723836*^9}, 3.415713521745892*^9, 3.41571374497668*^9, 3.4157140558500423`*^9, 3.415714125276332*^9, 3.415718051128848*^9, 3.415729383288794*^9, 3.4157294380221786`*^9, 3.415729861192603*^9, 3.418906847297782*^9, 3.4215968066557713`*^9, 3.421598258306201*^9, 3.4215984591123543`*^9, 3.4215985055376787`*^9, 3.4215991095493193`*^9, 3.4215991604549303`*^9, 3.421607840580751*^9, 3.421607961656962*^9, 3.4326031464673223`*^9, { 3.433898877825657*^9, 3.433898887178738*^9}, 3.433898918209228*^9, 3.458399059620082*^9, {3.45839909893438*^9, 3.458399122623473*^9}, 3.458400848860724*^9, 3.458404366700411*^9, 3.458405359506761*^9, 3.45840549355523*^9, 3.4584058052102337`*^9, 3.458406286297781*^9, 3.458407494339699*^9, 3.458407559103243*^9, 3.4584077076253443`*^9, 3.458408392839635*^9, 3.458408496688574*^9, 3.458409003930655*^9, 3.458409665442196*^9, {3.4584234612422457`*^9, 3.4584234706273603`*^9}, 3.458423532537003*^9, 3.458423602920974*^9, 3.4584241370671997`*^9, 3.458424353655142*^9, 3.458424386379096*^9, 3.4584244564412117`*^9, 3.4584246812599497`*^9, 3.458424760435804*^9, 3.4584247967059307`*^9, 3.458483276520486*^9, 3.458483420238542*^9, 3.458483507040064*^9, 3.458483555694147*^9, {3.4584836126281347`*^9, 3.458483624219325*^9}, 3.458483948149839*^9}], Cell["Determine the left nullspace of Q-I and its nullity.", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632631906171*^9, 3.41563269105234*^9}, { 3.415633485828392*^9, 3.415633496929037*^9}, {3.415634307222859*^9, 3.4156343396272087`*^9}, 3.415640546540505*^9, {3.4157109574951487`*^9, 3.415710996599331*^9}, 3.4584836126282187`*^9}], Cell[BoxData[ RowBox[{ RowBox[{"LeftNullspace", "[", RowBox[{"QI_", ",", "p_"}], "]"}], " ", ":=", " ", RowBox[{"NullSpace", "[", " ", RowBox[{ RowBox[{"Transpose", "[", " ", "QI", "]"}], ",", " ", RowBox[{"Modulus", "\[Rule]", "p"}]}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156409888138943`*^9, 3.415641023930561*^9}, { 3.4156418525698137`*^9, 3.415641854328496*^9}, 3.458483612628292*^9}], Cell[BoxData[ RowBox[{"LeftNullspace", "[", RowBox[{"QI", ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156410373450823`*^9, 3.415641042569655*^9}, { 3.415641350547996*^9, 3.4156413706861687`*^9}, {3.41564185902497*^9, 3.415641859344002*^9}, {3.4156470810055933`*^9, 3.415647081157256*^9}, 3.4584836126283693`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"{", RowBox[{"1", ",", "0", ",", "0", ",", "0"}], "}"}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156410431143427`*^9, 3.415641060330245*^9}, { 3.415641353303741*^9, 3.415641371616976*^9}, 3.415641494882234*^9, 3.415641602186145*^9, 3.415641786582992*^9, 3.415641860213785*^9, { 3.415644493014001*^9, 3.415644510844892*^9}, 3.41564603894179*^9, 3.415646329277279*^9, {3.415647085157929*^9, 3.4156470942136*^9}, 3.415647186379323*^9, 3.415647975052496*^9, 3.4156490161290607`*^9, 3.4156501751730843`*^9, 3.4156503448652554`*^9, 3.415651095095223*^9, { 3.415710700642837*^9, 3.415710714442453*^9}, 3.41571211209171*^9, 3.4157121582053013`*^9, 3.415712895795334*^9, 3.415713084502878*^9, { 3.415713141294442*^9, 3.4157131747816057`*^9}, 3.415713521824904*^9, 3.415713745061573*^9, 3.415714055933669*^9, 3.415714125360112*^9, 3.415718051344843*^9, 3.415729383368202*^9, 3.4157294381029787`*^9, 3.415729861342002*^9, 3.4189068473579206`*^9, 3.421596806716337*^9, 3.421598258419931*^9, 3.4215984592535477`*^9, 3.421598505608388*^9, 3.421599109612164*^9, 3.421599160516341*^9, 3.4216078406811647`*^9, 3.421607961739387*^9, 3.432603146525613*^9, {3.433898877919952*^9, 3.433898887264092*^9}, 3.4338989183289633`*^9, 3.458399059685635*^9, { 3.458399099008556*^9, 3.458399122673633*^9}, 3.458400848960248*^9, 3.458404366800753*^9, 3.458405359560133*^9, 3.458405493602667*^9, 3.458405805260857*^9, 3.458406286372607*^9, 3.4584074943807077`*^9, 3.4584075591588173`*^9, 3.458407707675785*^9, 3.458408392962678*^9, 3.458408496734803*^9, 3.458409004064829*^9, 3.4584096655010147`*^9, { 3.458423461312766*^9, 3.458423470727539*^9}, 3.458423532587376*^9, 3.458423602982696*^9, 3.458424137117373*^9, 3.458424353757105*^9, 3.458424386445565*^9, 3.45842445649612*^9, 3.458424681359514*^9, 3.4584247604858217`*^9, 3.458424796738867*^9, 3.458483276653137*^9, 3.458483420306085*^9, 3.458483507088813*^9, 3.458483555753249*^9, { 3.4584836126284523`*^9, 3.45848362426928*^9}, 3.4584839482222557`*^9}], Cell[BoxData[ RowBox[{ RowBox[{"LeftNullity", "[", RowBox[{"QI_", ",", "p_"}], "]"}], " ", ":=", RowBox[{"Length", "[", RowBox[{"LeftNullspace", "[", RowBox[{"QI", ",", "p"}], "]"}], "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415641319500445*^9, 3.415641347667507*^9}, { 3.4156414534583893`*^9, 3.415641456521351*^9}, {3.4156418630273438`*^9, 3.415641866976225*^9}, {3.415641900444448*^9, 3.415641912041986*^9}, 3.458483612628533*^9}], Cell[BoxData[ RowBox[{"LeftNullity", "[", RowBox[{"QI", ",", "p"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415641358189129*^9, 3.415641373918119*^9}, { 3.4156414605695047`*^9, 3.415641461001101*^9}, {3.415641904791945*^9, 3.415641905069908*^9}, 3.458483612628612*^9}], Cell[BoxData["1"], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415641364285284*^9, 3.415641374911542*^9}, 3.4156414976077433`*^9, 3.415641606128606*^9, 3.415641786740321*^9, 3.4156418689773817`*^9, {3.41564190593196*^9, 3.415641913811371*^9}, { 3.4156444931622467`*^9, 3.415644510928884*^9}, 3.4156460391063232`*^9, 3.4156463324613028`*^9, 3.415647094307858*^9, 3.415647186490663*^9, 3.415647975171966*^9, 3.415649016198534*^9, 3.41565017526344*^9, 3.415650344996147*^9, 3.415651095338586*^9, {3.4157107007313957`*^9, 3.4157107145212097`*^9}, 3.41571211216332*^9, 3.4157121582613783`*^9, 3.415712895896801*^9, 3.415713084582263*^9, {3.415713141374052*^9, 3.41571317485215*^9}, 3.4157135219100523`*^9, 3.415713745171618*^9, 3.415714056017434*^9, 3.4157141254431458`*^9, 3.415718051458729*^9, 3.415729383474062*^9, 3.41572943821211*^9, 3.415729861542198*^9, 3.4189068474850082`*^9, 3.421596806805965*^9, 3.4215982585192633`*^9, 3.4215984593249187`*^9, 3.421598505671373*^9, 3.421599109681204*^9, 3.4215991606008387`*^9, 3.421607840781047*^9, 3.421607961828597*^9, 3.432603146610012*^9, {3.433898877985361*^9, 3.433898887339101*^9}, 3.433898918389282*^9, 3.458399059757312*^9, {3.458399099080415*^9, 3.458399122723164*^9}, 3.458400849075362*^9, 3.458404366932963*^9, 3.458405359617702*^9, 3.458405493658284*^9, 3.458405805310803*^9, 3.4584062864100027`*^9, 3.458407494427054*^9, 3.4584075592066927`*^9, 3.458407707724435*^9, 3.458408393095581*^9, 3.458408496806633*^9, 3.4584090041975307`*^9, 3.4584096655987453`*^9, {3.458423461396044*^9, 3.4584234708268337`*^9}, 3.4584235326370373`*^9, 3.458423603046545*^9, 3.458424137176087*^9, 3.458424353855772*^9, 3.458424386487527*^9, 3.458424456546451*^9, 3.4584246814589*^9, 3.458424760535467*^9, 3.45842479677151*^9, 3.458483276965633*^9, 3.458483420353149*^9, 3.458483507138644*^9, 3.458483555848496*^9, {3.458483612628689*^9, 3.458483624319436*^9}, 3.458483948276967*^9}], Cell["2. Fast Algorithm for Finding a Primitive Polynomial", "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415712646450121*^9, 3.4157126468940573`*^9}, 3.415729393998034*^9, 3.4584836126287737`*^9}], Cell["\<\ Here's a reasonably fast method for testing a polynomial modulo p for \ primitivity.\ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156329538842278`*^9, 3.4156330044771*^9}, { 3.415646222977437*^9, 3.415646223615296*^9}, {3.4156500754613657`*^9, 3.415650133154221*^9}, {3.4157115412780657`*^9, 3.415711551468334*^9}, 3.458483612628847*^9}], Cell[BoxData[ RowBox[{ RowBox[{"IsPrimitive", "[", RowBox[{"f_", ",", " ", "p_", ",", "n_"}], "]"}], " ", ":=", " ", RowBox[{"Module", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"{", RowBox[{"r", ",", " ", "factors", ",", " ", RowBox[{"isPrimitiveRoot", " ", "=", " ", "False"}], ",", "a0", ",", "a"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"Print", "[", RowBox[{"Catch", "[", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{ RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "f", ",", " ", "\"\\"", ",", " ", "n", ",", " ", "\"\< modulo p = \>\"", ",", " ", "p", ",", " ", "\"\< for primitivity\>\""}], " ", "]"}], " ", ";", "\[IndentingNewLine]", "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{ "Factor", " ", "r", " ", "into", " ", "distinct", " ", "primes", " ", "with", " ", "their", " ", RowBox[{"powers", "."}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", RowBox[{"r", " ", "=", " ", FractionBox[ RowBox[{ SuperscriptBox["p", "n"], "-", "1"}], RowBox[{"p", "-", "1"}]]}], ";", "\[IndentingNewLine]", RowBox[{"factors", "=", RowBox[{"FactorInteger", "[", "r", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"numPrimeFactors", " ", "=", " ", RowBox[{"Length", "[", " ", "factors", " ", "]"}]}], " ", ";", "\[IndentingNewLine]", RowBox[{"For", "[", " ", RowBox[{ RowBox[{ RowBox[{"i", " ", "=", " ", "1"}], ";", " ", RowBox[{"s", " ", "=", " ", "\"\\""}]}], " ", ",", " ", RowBox[{"i", " ", "\[LessEqual]", " ", "numPrimeFactors"}], ",", " ", RowBox[{"++", "i"}], ",", "\[IndentingNewLine]", " ", RowBox[{ RowBox[{"distinctPrime", " ", "=", " ", RowBox[{ RowBox[{"factors", "[", RowBox[{"[", "i", "]"}], "]"}], "[", RowBox[{"[", "1", "]"}], "]"}]}], ";", " ", RowBox[{"powerOfPrime", "=", RowBox[{ RowBox[{"factors", "[", RowBox[{"[", "i", "]"}], "]"}], "[", RowBox[{"[", "2", "]"}], "]"}]}], ";", "\[IndentingNewLine]", " ", RowBox[{"s", "=", RowBox[{"StringJoin", "[", " ", RowBox[{"s", ",", RowBox[{"ToString", "[", "distinctPrime", "]"}], ",", " ", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"powerOfPrime", " ", ">", " ", "1"}], ",", RowBox[{"StringJoin", "[", RowBox[{"\"\<^\>\"", ",", RowBox[{"ToString", "[", "powerOfPrime", "]"}]}], "]"}], ",", " ", "\"\<\>\""}], "]"}], ",", " ", "\"\< \>\""}], "]"}]}]}]}], "\[IndentingNewLine]", " ", "]"}], ";", "\[IndentingNewLine]", RowBox[{"Print", "[", "s", "]"}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{ RowBox[{"Check", " ", "if", " ", FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "n"], TraditionalForm], FormBox[ SubscriptBox["a", RowBox[{"0", " "}]], TraditionalForm], " ", "is", " ", "a", " ", "primitive", " ", "root", " ", "of", " ", "p"}], ",", " ", RowBox[{"where", " ", SubscriptBox["a", RowBox[{"0", " "}]], "is", " ", "the", " ", "constant", " ", "term", " ", "of", " ", "f", RowBox[{ RowBox[{"(", "x", ")"}], "."}]}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"a0", "=", RowBox[{"ConstantTermOfPolynomial", "[", "f", "]"}]}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"IsPrimitiveRoot", "[", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "n"], "a0"}], ",", " ", "p"}], "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "a0", ",", " ", "\"\< passes primitive root test\>\""}], " ", "]"}], ",", " ", "\[IndentingNewLine]", " ", RowBox[{"Throw", "[", RowBox[{ "\"\<>>>Not primitive: fails the \>\"", ",", " ", "a0", ",", " ", "\"\< primitive root test.\>\""}], "]"}]}], "]"}], ";", "\[IndentingNewLine]", StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{"Check", " ", "that", " ", "f", RowBox[{"(", "x", ")"}], " ", "has", " ", "no", " ", "linear", " ", RowBox[{"factors", "."}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"PolynomialHasLinearFactor", "[", RowBox[{"f", ",", "p"}], "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Throw", "[", "\"\<>>>Not primitive: contains one or more linear factors.\>\"", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", "\"\\"", " ", "]"}]}], "\[IndentingNewLine]", " ", "]"}], ";", "\[IndentingNewLine]", StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{"Check", " ", "that", " ", "f", RowBox[{"(", "x", ")"}], " ", "is", " ", "irreducible", " ", "or", " ", "a", " ", "power", " ", "of", " ", "an", " ", RowBox[{"irreducible", "."}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{"\"\\"", ",", RowBox[{"PowersOfXModFP", "[", RowBox[{"f", ",", "p", ",", " ", "n"}], "]"}]}], "]"}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", " ", RowBox[{"QI", "=", RowBox[{"QIMatrix", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}]}], ";", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{"\"\\"", ",", " ", RowBox[{"QI", " ", "//", "MatrixForm"}]}], "]"}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", " ", RowBox[{"null", " ", "=", " ", RowBox[{"LeftNullity", "[", RowBox[{"QI", ",", "p"}], "]"}]}], ";", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{"\"\\"", ",", " ", "null"}], " ", "]"}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"null", " ", "\[LessEqual]", " ", "1"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Print", "[", " ", "\"\\"", " ", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Throw", "[", "\"\<>>>Not primitive: two or more distinct irreducible factors.\>\ \"", "]"}]}], " ", "]"}], ";", "\[IndentingNewLine]", StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", RowBox[{ StyleBox["(*", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], RowBox[{ RowBox[{ StyleBox["Check", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["that", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], SuperscriptBox["x", "r"], " ", RowBox[{"(", RowBox[{ RowBox[{ StyleBox["mod", FontWeight->"Plain"], " ", StyleBox["f", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[ RowBox[{"(", "x", ")"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"]}], StyleBox[",", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["p", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"]}], StyleBox[")", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"]}]}], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["=", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox[ RowBox[{"a", " ", "is", " ", "an", " ", RowBox[{"integer", "."}]}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"]}], StyleBox[" ", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["*)", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"]}], "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"a", " ", "=", RowBox[{"PolynomialMod", "[", RowBox[{ SuperscriptBox["x", "r"], ",", RowBox[{"{", RowBox[{"f", ",", "p"}], "}"}]}], "]"}]}], " ", ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"PolynomialIsConstant", "[", "a", "]"}], ",", " ", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "a"}], " ", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Throw", "[", " ", "\"\<>>>Not primitive: fails the \!\(\*SuperscriptBox[\(x\), \ \(r\)]\) = a = integer test\>\"", "]"}]}], "]"}], ";", "\[IndentingNewLine]", StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{ RowBox[{"Check", " ", "if", " ", "a"}], "=", RowBox[{ FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "n"], TraditionalForm], FormBox[ SubscriptBox["a", RowBox[{"0", " "}]], TraditionalForm], RowBox[{"(", RowBox[{"mod", " ", "p"}], ")"}]}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], "\[IndentingNewLine]", "\[IndentingNewLine]", " ", RowBox[{"If", "[", " ", RowBox[{ RowBox[{ RowBox[{"Mod", "[", " ", RowBox[{ RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{"-", "1"}], ")"}], "n"], " ", "a0"}], " ", "-", " ", "a"}], ",", " ", "p"}], "]"}], "\[Equal]", " ", "0"}], ",", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", "\"\\"", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Throw", "[", "\"\<>>>Not primitive: fails the const coefficient test\>\"", "]"}]}], "]"}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", "\[IndentingNewLine]", StyleBox[ RowBox[{"(*", " ", RowBox[{ RowBox[{ RowBox[{"Check", " ", RowBox[{ FormBox[ SuperscriptBox["x", "m"], TraditionalForm], "\[NotEqual]", RowBox[{"integer", " ", RowBox[{"(", RowBox[{ RowBox[{"mod", " ", "f", RowBox[{"(", "x", ")"}]}], ",", "p"}], ")"}], " ", "for", " ", "m"}]}]}], "\[Element]", RowBox[{"{", FormBox[ FractionBox["r", SubscriptBox["p", "i"]], TraditionalForm], "}"}]}], ",", " ", RowBox[{ RowBox[{ "but", " ", "skip", " ", "the", " ", "test", " ", "for", " ", "m"}], " ", "=", RowBox[{ RowBox[{ FractionBox["r", RowBox[{ SubscriptBox["p", "i"], " "}]], " ", "if", " ", FormBox[ SubscriptBox["p", "i"], TraditionalForm]}], " ", "|", " ", RowBox[{"(", RowBox[{"p", "-", "1"}], ")"}]}]}]}], " ", "*)"}], FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], StyleBox["\[IndentingNewLine]", FontFamily->"Chalkboard", FontSize->11, FontWeight->"Plain"], RowBox[{ RowBox[{"For", "[", " ", RowBox[{ RowBox[{"i", " ", "=", " ", "1"}], " ", ",", " ", RowBox[{"i", " ", "\[LessEqual]", " ", "numPrimeFactors"}], ",", " ", RowBox[{"++", "i"}], ",", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{ RowBox[{"prime", " ", "=", " ", RowBox[{ RowBox[{"factors", "[", RowBox[{"[", "i", "]"}], "]"}], "[", RowBox[{"[", "1", "]"}], "]"}]}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"m", " ", "=", " ", FractionBox["r", "prime"]}], ";", "\[IndentingNewLine]", "\[IndentingNewLine]", RowBox[{"If", "[", " ", RowBox[{ RowBox[{ RowBox[{"Mod", "[", RowBox[{ RowBox[{"p", "-", "1"}], ",", FormBox["prime", TraditionalForm]}], "]"}], " ", "\[Equal]", " ", "0"}], ",", "\[IndentingNewLine]", " ", RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "m", ",", " ", "\"\< since \!\(\*SubscriptBox[\(p\), \(i\)]\) = \>\"", ",", " ", "prime", ",", " ", "\"\< | p-1 = \>\"", ",", " ", RowBox[{"p", "-", "1"}]}], " ", "]"}], ",", "\[IndentingNewLine]", "\[IndentingNewLine]", " ", RowBox[{ RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "m", ",", " ", "\"\< prime factor = \>\"", ",", " ", "prime"}], " ", "]"}], ";", "\[IndentingNewLine]", " ", RowBox[{"a", " ", "=", RowBox[{"PolynomialMod", "[", RowBox[{ SuperscriptBox["x", "m"], ",", RowBox[{"{", RowBox[{"f", ",", "p"}], "}"}]}], "]"}]}], " ", ";", " ", "\[IndentingNewLine]", " ", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"PolynomialIsConstant", "[", "a", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Throw", "[", " ", "\"\<>>>Not primitive: failed the a = integer test\>\"", "]"}], ",", "\[IndentingNewLine]", " ", RowBox[{ RowBox[{"Print", "[", " ", RowBox[{ "\"\\"", ",", " ", "a", ",", " ", "\"\< \[NotEqual] integer for m = \>\"", ",", " ", "m", ",", " ", "\"\< \!\(\*SubscriptBox[\(p\), \(i\)]\) = \>\"", ",", " ", "prime"}], "]"}], ";"}]}], "\[IndentingNewLine]", " ", "]"}]}]}], "\[IndentingNewLine]", " ", "]"}]}]}], "\[IndentingNewLine]", " ", "]"}], "\[IndentingNewLine]", RowBox[{ "Throw", "[", "\"\<>>>Polynomial is primitive!\>\"", " ", "]"}]}], ";"}], "\[IndentingNewLine]", "]"}], " ", StyleBox[ RowBox[{"(*", " ", RowBox[{"end", " ", "of", " ", "catch", " ", "block"}], " ", "*)"}], FontWeight->"Plain"], "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}]}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415632805135297*^9, 3.415632871254759*^9}, { 3.415633327949883*^9, 3.415633383754052*^9}, {3.415633532553911*^9, 3.4156335380169373`*^9}, {3.415634220098701*^9, 3.4156342202406683`*^9}, { 3.415634353129039*^9, 3.415634372446854*^9}, {3.415635409971546*^9, 3.415635486815139*^9}, {3.415635527988963*^9, 3.415635609647072*^9}, { 3.415635652620492*^9, 3.41563569225158*^9}, {3.415635722343903*^9, 3.415635727596592*^9}, {3.4156357646176653`*^9, 3.415635782093054*^9}, { 3.4156359201939383`*^9, 3.415635958699271*^9}, {3.415641507403556*^9, 3.415641556540681*^9}, {3.415641641949259*^9, 3.415641706108436*^9}, { 3.415641820566573*^9, 3.415641836112331*^9}, {3.4156418727403812`*^9, 3.4156418831537647`*^9}, {3.415641938999935*^9, 3.415642091285924*^9}, { 3.4156422053059177`*^9, 3.415642206176425*^9}, {3.415642256907422*^9, 3.4156422695509453`*^9}, {3.4156423078718433`*^9, 3.4156424323728447`*^9}, 3.415642475443755*^9, {3.41564277451048*^9, 3.415642951806993*^9}, { 3.415643444802539*^9, 3.415643703199647*^9}, {3.41564375282541*^9, 3.4156439189290667`*^9}, {3.415644111063333*^9, 3.415644202860955*^9}, { 3.415644238657819*^9, 3.415644257863415*^9}, {3.415644628251315*^9, 3.415644658252647*^9}, {3.415645146378117*^9, 3.415645231356732*^9}, { 3.4156453099326468`*^9, 3.415645328775977*^9}, {3.415645420596882*^9, 3.415645431792807*^9}, {3.4156454770673*^9, 3.4156454779450703`*^9}, { 3.415645511284429*^9, 3.415645527076276*^9}, {3.415646494004738*^9, 3.415646527145769*^9}, {3.415646719169685*^9, 3.415646885632266*^9}, { 3.415646928955227*^9, 3.415647048321115*^9}, {3.41564903364152*^9, 3.415649037456915*^9}, {3.415649877723939*^9, 3.415649924586747*^9}, { 3.415650553308078*^9, 3.415650594762691*^9}, {3.415650627616259*^9, 3.415650830583742*^9}, {3.415651043181239*^9, 3.415651044632341*^9}, { 3.415711536524712*^9, 3.4157117782859497`*^9}, {3.415711965356038*^9, 3.415712105018536*^9}, {3.415712136071122*^9, 3.415712151580799*^9}, { 3.41571218458785*^9, 3.415712197671681*^9}, {3.415713044745064*^9, 3.4157130562195263`*^9}, {3.415713164755204*^9, 3.415713164922975*^9}, { 3.415713380983205*^9, 3.4157133951922073`*^9}, {3.415713436686281*^9, 3.41571345612696*^9}, {3.4157134899805307`*^9, 3.4157135046626043`*^9}, { 3.421598153540642*^9, 3.421598173841982*^9}, {3.4215982041187468`*^9, 3.4215982296494617`*^9}, {3.4215984186876802`*^9, 3.421598454083496*^9}, 3.421598501658718*^9, {3.4215986933840837`*^9, 3.4215988187326927`*^9}, { 3.421598866496674*^9, 3.421598873695447*^9}, {3.4215989239491177`*^9, 3.421598959920191*^9}, 3.4215990078250647`*^9, {3.421599451307147*^9, 3.421599451988037*^9}, {3.421604542731165*^9, 3.421604647972404*^9}, { 3.4216064472225447`*^9, 3.421606461987335*^9}, {3.421606546513283*^9, 3.421606573564622*^9}, {3.458398891515388*^9, 3.458398989020945*^9}, { 3.458399048592922*^9, 3.458399117170351*^9}, {3.458400777777853*^9, 3.45840082741967*^9}, {3.458400873327458*^9, 3.45840089852607*^9}, { 3.458400931532053*^9, 3.458400940811591*^9}, {3.45840440375826*^9, 3.4584044474390907`*^9}, {3.4584044819450703`*^9, 3.4584044844553843`*^9}, {3.4584045952612886`*^9, 3.458404622719172*^9}, { 3.458405244945937*^9, 3.458405251826632*^9}, {3.4584052845453243`*^9, 3.458405355119339*^9}, {3.458405390131791*^9, 3.4584055186315613`*^9}, { 3.458405558090477*^9, 3.458405678000844*^9}, {3.458405726583164*^9, 3.458405732956612*^9}, {3.458405774480152*^9, 3.458405797768998*^9}, { 3.4584058317457113`*^9, 3.458405833152878*^9}, {3.4584058707275333`*^9, 3.4584058765431128`*^9}, {3.4584059712981586`*^9, 3.4584059981304417`*^9}, {3.458406067529755*^9, 3.458406078633706*^9}, { 3.458406272141276*^9, 3.4584062810829763`*^9}, 3.458406878009544*^9, { 3.458407470966456*^9, 3.458407488582456*^9}, {3.458407544160725*^9, 3.458407701613521*^9}, {3.458407843526928*^9, 3.4584081046367197`*^9}, { 3.4584084449981003`*^9, 3.458408488320897*^9}, {3.458409595976684*^9, 3.458409649988937*^9}, {3.458423388300716*^9, 3.458423423826988*^9}, 3.45842352404783*^9, {3.458424113189314*^9, 3.458424155794003*^9}, { 3.458483343955859*^9, 3.458483362248691*^9}, {3.458483397599334*^9, 3.458483398619707*^9}, {3.458483501386325*^9, 3.458483502431384*^9}, { 3.458483538646451*^9, 3.4584835517562027`*^9}, 3.458483612628921*^9}], Cell["\<\ Test the method on several polynomials. First, our example polynomial.\ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156329538842278`*^9, 3.4156330044771*^9}, { 3.415646222977437*^9, 3.415646223615296*^9}, {3.4156500754613657`*^9, 3.415650133154221*^9}, {3.4157115412780657`*^9, 3.415711551468334*^9}, { 3.458424283094145*^9, 3.4584242932369833`*^9}, {3.45848352203524*^9, 3.458483528120059*^9}, 3.4584836126290007`*^9}], Cell[BoxData[ RowBox[{"IsPrimitive", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415644343681767*^9, 3.4156443485131483`*^9}, { 3.415645552578573*^9, 3.415645563256778*^9}, 3.415645934242545*^9, { 3.458424158373489*^9, 3.4584241678304996`*^9}, 3.458483612629084*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing polynomial \"\>", "\[InvisibleSpace]", RowBox[{"3", "+", RowBox[{"2", " ", "x"}], "+", SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "4"]}], "\[InvisibleSpace]", "\<\"of degree n = \"\>", "\[InvisibleSpace]", "4", "\[InvisibleSpace]", "\<\" modulo p = \"\>", "\[InvisibleSpace]", "5", "\[InvisibleSpace]", "\<\" for primitivity\"\>"}], SequenceForm[ "Testing polynomial ", 3 + 2 $CellContext`x + $CellContext`x^2 + $CellContext`x^4, "of degree n = ", 4, " modulo p = ", 5, " for primitivity"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948327867*^9}], Cell[BoxData["\<\"Prime factorization: 2^2 3 13 \"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948330929*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Const coeff a0 = \"\>", "\[InvisibleSpace]", "3", "\[InvisibleSpace]", "\<\" passes primitive root test\"\>"}], SequenceForm["Const coeff a0 = ", 3, " passes primitive root test"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.4584839483336477`*^9}], Cell[BoxData["\<\"No linear factors\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948336248*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Powers of x in Q matrix rows =\"\>", "\[InvisibleSpace]", RowBox[{"{", RowBox[{"1", ",", RowBox[{ RowBox[{"2", " ", "x"}], "+", RowBox[{"3", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"3", "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", SuperscriptBox["x", "3"]}], ",", RowBox[{ RowBox[{"4", " ", "x"}], "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "3"]}]}]}], "}"}]}], SequenceForm[ "Powers of x in Q matrix rows =", { 1, 2 $CellContext`x + 3 $CellContext`x^2 + 4 $CellContext`x^3, 3 + 4 $CellContext`x^2 + $CellContext`x^3, 4 $CellContext`x + 4 $CellContext`x^2 + 3 $CellContext`x^3}], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.4584839483392763`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Q - I = \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "0", "0"}, {"0", "1", "3", "4"}, {"3", "0", "3", "1"}, {"0", "4", "4", "2"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]}], SequenceForm["Q - I = ", MatrixForm[{{0, 0, 0, 0}, {0, 1, 3, 4}, {3, 0, 3, 1}, {0, 4, 4, 2}}]], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948342347*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Nullity = \"\>", "\[InvisibleSpace]", "1"}], SequenceForm["Nullity = ", 1], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948345133*^9}], Cell[BoxData["\<\"One (possibly repeated) distinct irreducible factor\"\>"], \ "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948347698*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(r\\)]\\) = a \ = integer \"\>", "\[InvisibleSpace]", "3"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(r\)]\) = a = integer ", 3], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.4584839483504047`*^9}], Cell[BoxData["\<\"Const coeff test passes\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.4584839483531322`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Skipping test for m = \"\>", "\[InvisibleSpace]", "78", "\[InvisibleSpace]", "\<\" since \\!\\(\\*SubscriptBox[\\(p\\), \ \\(i\\)]\\) = \"\>", "\[InvisibleSpace]", "2", "\[InvisibleSpace]", "\<\" | p-1 = \"\>", "\[InvisibleSpace]", "4"}], SequenceForm[ "Skipping test for m = ", 78, " since \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 2, " | p-1 = ", 4], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948355772*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing m = \"\>", "\[InvisibleSpace]", "52", "\[InvisibleSpace]", "\<\" prime factor = \"\>", "\[InvisibleSpace]", "3"}], SequenceForm["Testing m = ", 52, " prime factor = ", 3], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948358585*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(m\\)]\\) = a \ = \"\>", "\[InvisibleSpace]", RowBox[{ RowBox[{"4", " ", "x"}], "+", SuperscriptBox["x", "2"], "+", RowBox[{"2", " ", SuperscriptBox["x", "3"]}]}], "\[InvisibleSpace]", "\<\" \[NotEqual] integer for m = \"\>", "\[InvisibleSpace]", "52", "\[InvisibleSpace]", "\<\" \\!\\(\\*SubscriptBox[\\(p\\), \\(i\\)]\\) = \"\ \>", "\[InvisibleSpace]", "3"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(m\)]\) = a = ", 4 $CellContext`x + $CellContext`x^2 + 2 $CellContext`x^3, " \[NotEqual] integer for m = ", 52, " \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 3], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948361388*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing m = \"\>", "\[InvisibleSpace]", "12", "\[InvisibleSpace]", "\<\" prime factor = \"\>", "\[InvisibleSpace]", "13"}], SequenceForm["Testing m = ", 12, " prime factor = ", 13], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948364357*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(m\\)]\\) = a \ = \"\>", "\[InvisibleSpace]", RowBox[{"3", "+", RowBox[{"4", " ", "x"}], "+", RowBox[{"2", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], "\[InvisibleSpace]", "\<\" \[NotEqual] integer for m = \"\>", "\[InvisibleSpace]", "12", "\[InvisibleSpace]", "\<\" \\!\\(\\*SubscriptBox[\\(p\\), \\(i\\)]\\) = \"\ \>", "\[InvisibleSpace]", "13"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(m\)]\) = a = ", 3 + 4 $CellContext`x + 2 $CellContext`x^2 + 4 $CellContext`x^3, " \[NotEqual] integer for m = ", 12, " \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 13], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948367144*^9}], Cell[BoxData["\<\">>>Polynomial is primitive!\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.458408496892601*^9, 3.458409004321385*^9, 3.458409665665195*^9, { 3.458423461488804*^9, 3.458423470926498*^9}, 3.458423532692902*^9, 3.458423603111043*^9, {3.458424137249609*^9, 3.4584241688650837`*^9}, 3.458424353972074*^9, 3.458424386533923*^9, 3.458424456597706*^9, 3.458424681558714*^9, 3.458424760601397*^9, 3.458424796804678*^9, 3.4584832772679367`*^9, 3.458483420406878*^9, 3.458483507184435*^9, 3.458483555900861*^9, {3.458483612629163*^9, 3.458483624397739*^9}, 3.458483948370034*^9}], Cell["Now test the method on several polynomials.", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156329538842278`*^9, 3.4156330044771*^9}, { 3.415646222977437*^9, 3.415646223615296*^9}, {3.4156500754613657`*^9, 3.415650133154221*^9}, {3.4157115412780657`*^9, 3.415711551468334*^9}, { 3.458424283094145*^9, 3.4584242932369833`*^9}, {3.45848352203524*^9, 3.458483528120059*^9}, {3.45848357687742*^9, 3.458483612630395*^9}}], Cell[BoxData[ RowBox[{"IsPrimitive", "[", RowBox[{ RowBox[{ SuperscriptBox["x", "8"], "+", " ", "1"}], ",", "2", ",", "8"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.458406095774911*^9, 3.458406118282383*^9}, { 3.4584061947575912`*^9, 3.458406246064266*^9}, {3.458407743283431*^9, 3.458407799733412*^9}, {3.4584241978911324`*^9, 3.45842419957701*^9}, { 3.458424256155292*^9, 3.4584242574978113`*^9}, 3.458483612630475*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing polynomial \"\>", "\[InvisibleSpace]", RowBox[{"1", "+", SuperscriptBox["x", "8"]}], "\[InvisibleSpace]", "\<\"of degree n = \"\>", "\[InvisibleSpace]", "8", "\[InvisibleSpace]", "\<\" modulo p = \"\>", "\[InvisibleSpace]", "2", "\[InvisibleSpace]", "\<\" for primitivity\"\>"}], SequenceForm[ "Testing polynomial ", 1 + $CellContext`x^8, "of degree n = ", 8, " modulo p = ", 2, " for primitivity"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584242005487823`*^9, 3.45842425829062*^9, 3.4584243540280724`*^9, 3.4584243866994534`*^9, 3.458424456675055*^9, 3.458424681613461*^9, 3.4584247606898823`*^9, 3.4584247968870363`*^9, 3.4584832773266706`*^9, 3.458483420461054*^9, 3.458483507243376*^9, 3.458483555955317*^9, { 3.4584836126305532`*^9, 3.4584836244863167`*^9}, 3.458483948405946*^9}], Cell[BoxData["\<\"Prime factorization: 3 5 17 \"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584242005487823`*^9, 3.45842425829062*^9, 3.4584243540280724`*^9, 3.4584243866994534`*^9, 3.458424456675055*^9, 3.458424681613461*^9, 3.4584247606898823`*^9, 3.4584247968870363`*^9, 3.4584832773266706`*^9, 3.458483420461054*^9, 3.458483507243376*^9, 3.458483555955317*^9, { 3.4584836126305532`*^9, 3.4584836244863167`*^9}, 3.45848394840898*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Const coeff a0 = \"\>", "\[InvisibleSpace]", "1", "\[InvisibleSpace]", "\<\" passes primitive root test\"\>"}], SequenceForm["Const coeff a0 = ", 1, " passes primitive root test"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584242005487823`*^9, 3.45842425829062*^9, 3.4584243540280724`*^9, 3.4584243866994534`*^9, 3.458424456675055*^9, 3.458424681613461*^9, 3.4584247606898823`*^9, 3.4584247968870363`*^9, 3.4584832773266706`*^9, 3.458483420461054*^9, 3.458483507243376*^9, 3.458483555955317*^9, { 3.4584836126305532`*^9, 3.4584836244863167`*^9}, 3.458483948411655*^9}], Cell[BoxData["\<\">>>Not primitive: contains one or more linear \ factors.\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584242005487823`*^9, 3.45842425829062*^9, 3.4584243540280724`*^9, 3.4584243866994534`*^9, 3.458424456675055*^9, 3.458424681613461*^9, 3.4584247606898823`*^9, 3.4584247968870363`*^9, 3.4584832773266706`*^9, 3.458483420461054*^9, 3.458483507243376*^9, 3.458483555955317*^9, { 3.4584836126305532`*^9, 3.4584836244863167`*^9}, 3.458483948414548*^9}], Cell[BoxData[ RowBox[{"IsPrimitive", "[", RowBox[{ RowBox[{ SuperscriptBox["x", "8"], "+", " ", "x", "+", " ", "1"}], ",", "2", ",", "8"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.458406095774911*^9, 3.458406118282383*^9}, { 3.4584061947575912`*^9, 3.458406246064266*^9}, {3.458407743283431*^9, 3.458407799733412*^9}, {3.458424432036209*^9, 3.458424432922529*^9}, 3.4584836126308823`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing polynomial \"\>", "\[InvisibleSpace]", RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "8"]}], "\[InvisibleSpace]", "\<\"of degree n = \"\>", "\[InvisibleSpace]", "8", "\[InvisibleSpace]", "\<\" modulo p = \"\>", "\[InvisibleSpace]", "2", "\[InvisibleSpace]", "\<\" for primitivity\"\>"}], SequenceForm[ "Testing polynomial ", 1 + $CellContext`x + $CellContext`x^8, "of degree n = ", 8, " modulo p = ", 2, " for primitivity"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948455707*^9}], Cell[BoxData["\<\"Prime factorization: 3 5 17 \"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948458686*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Const coeff a0 = \"\>", "\[InvisibleSpace]", "1", "\[InvisibleSpace]", "\<\" passes primitive root test\"\>"}], SequenceForm["Const coeff a0 = ", 1, " passes primitive root test"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948461381*^9}], Cell[BoxData["\<\"No linear factors\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948464058*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Powers of x in Q matrix rows =\"\>", "\[InvisibleSpace]", RowBox[{"{", RowBox[{"1", ",", SuperscriptBox["x", "2"], ",", SuperscriptBox["x", "4"], ",", SuperscriptBox["x", "6"], ",", RowBox[{"1", "+", "x"}], ",", RowBox[{ SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "3"]}], ",", RowBox[{ SuperscriptBox["x", "4"], "+", SuperscriptBox["x", "5"]}], ",", RowBox[{ SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"]}]}], "}"}]}], SequenceForm[ "Powers of x in Q matrix rows =", { 1, $CellContext`x^2, $CellContext`x^4, $CellContext`x^6, 1 + $CellContext`x, $CellContext`x^2 + $CellContext`x^3, $CellContext`x^4 + \ $CellContext`x^5, $CellContext`x^6 + $CellContext`x^7}], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948467013*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Q - I = \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "0", "0", "0", "0", "0", "0"}, {"0", "1", "1", "0", "0", "0", "0", "0"}, {"0", "0", "1", "0", "1", "0", "0", "0"}, {"0", "0", "0", "1", "0", "0", "1", "0"}, {"1", "1", "0", "0", "1", "0", "0", "0"}, {"0", "0", "1", "1", "0", "1", "0", "0"}, {"0", "0", "0", "0", "1", "1", "1", "0"}, {"0", "0", "0", "0", "0", "0", "1", "0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]}], SequenceForm["Q - I = ", MatrixForm[{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0, 1, 0}}]], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.4584839484703283`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Nullity = \"\>", "\[InvisibleSpace]", "2"}], SequenceForm["Nullity = ", 2], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.4584839484732924`*^9}], Cell[BoxData["\<\">>>Not primitive: two or more distinct irreducible \ factors.\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.4584084969633303`*^9, 3.458409004422769*^9, 3.4584096657208843`*^9, { 3.458423462003353*^9, 3.458423470982101*^9}, 3.4584235327858343`*^9, 3.4584236031843147`*^9, 3.458424137340013*^9, 3.4584241767739*^9, { 3.458424433886155*^9, 3.458424456748371*^9}, 3.458424681664452*^9, 3.4584247608663683`*^9, 3.458424796932528*^9, 3.458483277380096*^9, 3.458483420511251*^9, 3.45848350731596*^9, 3.45848355599323*^9, { 3.458483612630967*^9, 3.458483624536332*^9}, 3.458483948475893*^9}], Cell[BoxData[ RowBox[{"IsPrimitive", "[", RowBox[{ RowBox[{ SuperscriptBox["x", "8"], "+", " ", SuperscriptBox["x", "4"], "+", " ", "1"}], ",", "2", ",", "8"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.458406095774911*^9, 3.458406118282383*^9}, { 3.4584061947575912`*^9, 3.458406246064266*^9}, {3.458407743283431*^9, 3.458407799733412*^9}, {3.4584241978911324`*^9, 3.458424238002162*^9}, 3.458483612631592*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing polynomial \"\>", "\[InvisibleSpace]", RowBox[{"1", "+", SuperscriptBox["x", "4"], "+", SuperscriptBox["x", "8"]}], "\[InvisibleSpace]", "\<\"of degree n = \"\>", "\[InvisibleSpace]", "8", "\[InvisibleSpace]", "\<\" modulo p = \"\>", "\[InvisibleSpace]", "2", "\[InvisibleSpace]", "\<\" for primitivity\"\>"}], SequenceForm[ "Testing polynomial ", 1 + $CellContext`x^4 + $CellContext`x^8, "of degree n = ", 8, " modulo p = ", 2, " for primitivity"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948509963*^9}], Cell[BoxData["\<\"Prime factorization: 3 5 17 \"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.4584839485129147`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Const coeff a0 = \"\>", "\[InvisibleSpace]", "1", "\[InvisibleSpace]", "\<\" passes primitive root test\"\>"}], SequenceForm["Const coeff a0 = ", 1, " passes primitive root test"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.4584839485158243`*^9}], Cell[BoxData["\<\"No linear factors\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948518467*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Powers of x in Q matrix rows =\"\>", "\[InvisibleSpace]", RowBox[{"{", RowBox[{"1", ",", SuperscriptBox["x", "2"], ",", SuperscriptBox["x", "4"], ",", SuperscriptBox["x", "6"], ",", RowBox[{"1", "+", SuperscriptBox["x", "4"]}], ",", RowBox[{ SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "6"]}], ",", "1", ",", SuperscriptBox["x", "2"]}], "}"}]}], SequenceForm[ "Powers of x in Q matrix rows =", { 1, $CellContext`x^2, $CellContext`x^4, $CellContext`x^6, 1 + $CellContext`x^4, $CellContext`x^2 + $CellContext`x^6, 1, $CellContext`x^2}], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948521243*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Q - I = \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "0", "0", "0", "0", "0", "0"}, {"0", "1", "1", "0", "0", "0", "0", "0"}, {"0", "0", "1", "0", "1", "0", "0", "0"}, {"0", "0", "0", "1", "0", "0", "1", "0"}, {"1", "0", "0", "0", "0", "0", "0", "0"}, {"0", "0", "1", "0", "0", "1", "1", "0"}, {"1", "0", "0", "0", "0", "0", "1", "0"}, {"0", "0", "1", "0", "0", "0", "0", "1"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]}], SequenceForm["Q - I = ", MatrixForm[{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 1}}]], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948524431*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Nullity = \"\>", "\[InvisibleSpace]", "1"}], SequenceForm["Nullity = ", 1], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948527521*^9}], Cell[BoxData["\<\"One (possibly repeated) distinct irreducible factor\"\>"], \ "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.4584839485300713`*^9}], Cell[BoxData["\<\">>>Not primitive: fails the \ \\!\\(\\*SuperscriptBox[\\(x\\), \\(r\\)]\\) = a = integer test\"\>"], "Print",\ CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584242283383427`*^9, 3.458424238694477*^9}, 3.4584243540778847`*^9, 3.4584243868761387`*^9, 3.458424456796075*^9, 3.458424681714428*^9, 3.458424761222002*^9, 3.458424797262706*^9, 3.458483277429554*^9, 3.458483420561594*^9, 3.4584835073550053`*^9, 3.458483556039627*^9, {3.458483612631671*^9, 3.458483624589213*^9}, 3.458483948532723*^9}], Cell[BoxData[ RowBox[{"IsPrimitive", "[", RowBox[{ RowBox[{ SuperscriptBox["x", "8"], "+", " ", SuperscriptBox["x", "6"], "+", " ", SuperscriptBox["x", "5"], "+", "x", "+", "1"}], ",", "2", ",", "8"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.458406095774911*^9, 3.458406118282383*^9}, { 3.4584061947575912`*^9, 3.458406246064266*^9}, {3.458407743283431*^9, 3.458407799733412*^9}, {3.458408540828259*^9, 3.458408574644999*^9}, { 3.4584087644381104`*^9, 3.4584087857528257`*^9}, {3.458409291522283*^9, 3.458409318255706*^9}, 3.458483612632362*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing polynomial \"\>", "\[InvisibleSpace]", RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "5"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "8"]}], "\[InvisibleSpace]", "\<\"of degree n = \"\>", "\[InvisibleSpace]", "8", "\[InvisibleSpace]", "\<\" modulo p = \"\>", "\[InvisibleSpace]", "2", "\[InvisibleSpace]", "\<\" for primitivity\"\>"}], SequenceForm[ "Testing polynomial ", 1 + $CellContext`x + $CellContext`x^5 + $CellContext`x^6 + \ $CellContext`x^8, "of degree n = ", 8, " modulo p = ", 2, " for primitivity"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.4584839486281433`*^9}], Cell[BoxData["\<\"Prime factorization: 3 5 17 \"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948631361*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Const coeff a0 = \"\>", "\[InvisibleSpace]", "1", "\[InvisibleSpace]", "\<\" passes primitive root test\"\>"}], SequenceForm["Const coeff a0 = ", 1, " passes primitive root test"], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948634141*^9}], Cell[BoxData["\<\"No linear factors\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948636857*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Powers of x in Q matrix rows =\"\>", "\[InvisibleSpace]", RowBox[{"{", RowBox[{"1", ",", SuperscriptBox["x", "2"], ",", SuperscriptBox["x", "4"], ",", SuperscriptBox["x", "6"], ",", RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "5"], "+", SuperscriptBox["x", "6"]}], ",", RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "3"], "+", SuperscriptBox["x", "5"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"]}], ",", RowBox[{"1", "+", SuperscriptBox["x", "3"], "+", SuperscriptBox["x", "4"]}], ",", RowBox[{ SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "5"], "+", SuperscriptBox["x", "6"]}]}], "}"}]}], SequenceForm[ "Powers of x in Q matrix rows =", { 1, $CellContext`x^2, $CellContext`x^4, $CellContext`x^6, 1 + $CellContext`x + $CellContext`x^5 + $CellContext`x^6, 1 + $CellContext`x + $CellContext`x^2 + $CellContext`x^3 + \ $CellContext`x^5 + $CellContext`x^6 + $CellContext`x^7, 1 + $CellContext`x^3 + $CellContext`x^4, $CellContext`x^2 + \ $CellContext`x^5 + $CellContext`x^6}], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.45848394864011*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Q - I = \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "0", "0", "0", "0", "0", "0"}, {"0", "1", "1", "0", "0", "0", "0", "0"}, {"0", "0", "1", "0", "1", "0", "0", "0"}, {"0", "0", "0", "1", "0", "0", "1", "0"}, {"1", "1", "0", "0", "1", "1", "1", "0"}, {"1", "1", "1", "1", "0", "0", "1", "1"}, {"1", "0", "0", "1", "1", "0", "1", "0"}, {"0", "0", "1", "0", "0", "1", "1", "1"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]}], SequenceForm["Q - I = ", MatrixForm[{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 1, 1, 0}, {1, 1, 1, 1, 0, 0, 1, 1}, {1, 0, 0, 1, 1, 0, 1, 0}, {0, 0, 1, 0, 0, 1, 1, 1}}]], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.45848394864345*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Nullity = \"\>", "\[InvisibleSpace]", "1"}], SequenceForm["Nullity = ", 1], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.4584839486464987`*^9}], Cell[BoxData["\<\"One (possibly repeated) distinct irreducible factor\"\>"], \ "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948649178*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(r\\)]\\) = a \ = integer \"\>", "\[InvisibleSpace]", "1"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(r\)]\) = a = integer ", 1], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948652028*^9}], Cell[BoxData["\<\"Const coeff test passes\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.4584839486548567`*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing m = \"\>", "\[InvisibleSpace]", "85", "\[InvisibleSpace]", "\<\" prime factor = \"\>", "\[InvisibleSpace]", "3"}], SequenceForm["Testing m = ", 85, " prime factor = ", 3], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948657618*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(m\\)]\\) = a \ = \"\>", "\[InvisibleSpace]", RowBox[{ SuperscriptBox["x", "4"], "+", SuperscriptBox["x", "5"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"]}], "\[InvisibleSpace]", "\<\" \[NotEqual] integer for m = \"\>", "\[InvisibleSpace]", "85", "\[InvisibleSpace]", "\<\" \\!\\(\\*SubscriptBox[\\(p\\), \\(i\\)]\\) = \"\ \>", "\[InvisibleSpace]", "3"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(m\)]\) = a = ", \ $CellContext`x^4 + $CellContext`x^5 + $CellContext`x^6 + $CellContext`x^7, " \[NotEqual] integer for m = ", 85, " \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 3], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948660481*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing m = \"\>", "\[InvisibleSpace]", "51", "\[InvisibleSpace]", "\<\" prime factor = \"\>", "\[InvisibleSpace]", "5"}], SequenceForm["Testing m = ", 51, " prime factor = ", 5], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948663628*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(m\\)]\\) = a \ = \"\>", "\[InvisibleSpace]", RowBox[{"x", "+", SuperscriptBox["x", "4"]}], "\[InvisibleSpace]", "\<\" \[NotEqual] integer for m = \"\>", "\[InvisibleSpace]", "51", "\[InvisibleSpace]", "\<\" \\!\\(\\*SubscriptBox[\\(p\\), \\(i\\)]\\) = \"\ \>", "\[InvisibleSpace]", "5"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(m\)]\) = a = ", $CellContext`x + \ $CellContext`x^4, " \[NotEqual] integer for m = ", 51, " \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 5], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948666581*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Testing m = \"\>", "\[InvisibleSpace]", "15", "\[InvisibleSpace]", "\<\" prime factor = \"\>", "\[InvisibleSpace]", "17"}], SequenceForm["Testing m = ", 15, " prime factor = ", 17], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948669587*^9}], Cell[BoxData[ InterpretationBox[ RowBox[{"\<\"Pass test for \\!\\(\\*SuperscriptBox[\\(x\\), \\(m\\)]\\) = a \ = \"\>", "\[InvisibleSpace]", RowBox[{ SuperscriptBox["x", "3"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"]}], "\[InvisibleSpace]", "\<\" \[NotEqual] integer for m = \"\>", "\[InvisibleSpace]", "15", "\[InvisibleSpace]", "\<\" \\!\\(\\*SubscriptBox[\\(p\\), \\(i\\)]\\) = \"\ \>", "\[InvisibleSpace]", "17"}], SequenceForm[ "Pass test for \!\(\*SuperscriptBox[\(x\), \(m\)]\) = a = ", \ $CellContext`x^3 + $CellContext`x^6 + $CellContext`x^7, " \[NotEqual] integer for m = ", 15, " \!\(\*SubscriptBox[\(p\), \(i\)]\) = ", 17], Editable->False]], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.458483948672429*^9}], Cell[BoxData["\<\">>>Polynomial is primitive!\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4584085414650507`*^9, 3.458408556003044*^9}, { 3.458408770836102*^9, 3.458408786674348*^9}, 3.458409004486886*^9, { 3.45840930333427*^9, 3.4584093193009453`*^9}, 3.458409665770967*^9, { 3.458423462420104*^9, 3.458423471032593*^9}, 3.4584235331076193`*^9, 3.4584236032337017`*^9, 3.458424137394985*^9, 3.458424178987855*^9, 3.458424354178083*^9, 3.458424387565043*^9, 3.458424457128751*^9, 3.4584246817652493`*^9, 3.458424761521799*^9, 3.458424797635482*^9, 3.458483277484302*^9, 3.458483420610952*^9, 3.458483507405861*^9, 3.4584835560903187`*^9, {3.4584836126324472`*^9, 3.458483624653117*^9}, 3.4584839486754417`*^9}], Cell["3. Slow Algorithm for Finding a Primitive Polynomial", "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415712646450121*^9, 3.415712657751089*^9}, 3.4157293990538588`*^9, 3.458483612633834*^9}], Cell[TextData[{ "The exponentially slow (brute force) method is to try ", Cell[BoxData[ FormBox[ SuperscriptBox["x", "k"], TraditionalForm]]], " (mod f(x), p) and check we don't get 1 until k = ", Cell[BoxData[ FormBox[ SuperscriptBox["p", "n"], TraditionalForm]]], "-1.\nHere are the first few powers," }], "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156496838948803`*^9, 3.41564971734724*^9}, { 3.415650162794191*^9, 3.415650166121984*^9}, {3.415712388881093*^9, 3.4157123894234467`*^9}, {3.4157124355481997`*^9, 3.415712440594768*^9}, 3.4584836126339083`*^9}], Cell[BoxData[ RowBox[{"Table", "[", " ", RowBox[{ RowBox[{"PolynomialMod", "[", RowBox[{ SuperscriptBox["x", "k"], ",", RowBox[{"{", RowBox[{"f", ",", "p"}], "}"}]}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", "10"}], "}"}]}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415649474036326*^9, 3.415649480346051*^9}, { 3.415712365018589*^9, 3.415712371374052*^9}, 3.458483612634251*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"x", ",", SuperscriptBox["x", "2"], ",", SuperscriptBox["x", "3"], ",", RowBox[{"2", "+", RowBox[{"3", " ", "x"}], "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}]}], ",", RowBox[{ RowBox[{"2", " ", "x"}], "+", RowBox[{"3", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"3", "+", RowBox[{"2", " ", "x"}], "+", RowBox[{"3", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"1", "+", RowBox[{"2", " ", "x"}], "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"1", "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"3", "+", RowBox[{"3", " ", "x"}], "+", SuperscriptBox["x", "2"], "+", RowBox[{"4", " ", SuperscriptBox["x", "3"]}]}], ",", RowBox[{"3", "+", RowBox[{"4", " ", SuperscriptBox["x", "2"]}], "+", SuperscriptBox["x", "3"]}]}], "}"}]], "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.415712372950135*^9, 3.4157128967131987`*^9, 3.415713084846528*^9, { 3.415713141620961*^9, 3.415713175395248*^9}, 3.415713522400344*^9, { 3.415713737161072*^9, 3.415713760090885*^9}, 3.41571405631056*^9, 3.415714125783993*^9, 3.4157180526059113`*^9, 3.415729383758984*^9, 3.415729438608391*^9, 3.41572986211226*^9, 3.418906848037168*^9, 3.421596808075615*^9, 3.421598259272838*^9, 3.4215984602090387`*^9, 3.4215985064030743`*^9, 3.421599109969833*^9, 3.421599160868929*^9, 3.421607841099957*^9, 3.421607962119152*^9, 3.43260314730937*^9, { 3.433898878533299*^9, 3.43389888764583*^9}, 3.4338989189148397`*^9, 3.458399060591415*^9, {3.4583990997011023`*^9, 3.458399123510049*^9}, 3.458400849296101*^9, 3.4584043672396717`*^9, 3.458405359805294*^9, 3.458405494106048*^9, 3.458405805522728*^9, 3.458406287521378*^9, 3.4584074953356667`*^9, 3.4584075593935823`*^9, 3.4584077086706038`*^9, 3.45840839339648*^9, 3.45840849701297*^9, 3.458409004554571*^9, 3.458409665824032*^9, {3.458423463034491*^9, 3.4584234710921173`*^9}, 3.458423533816554*^9, 3.45842360328685*^9, 3.4584241374489183`*^9, 3.4584243542371798`*^9, 3.458424388198049*^9, 3.458424457750485*^9, 3.45842468182672*^9, 3.458424762205865*^9, 3.458424798291655*^9, 3.458483277542655*^9, 3.4584834206652193`*^9, 3.458483507454842*^9, 3.4584835561439867`*^9, {3.45848361263433*^9, 3.458483624735939*^9}, 3.45848394882664*^9}], Cell["\<\ Scan through all the powers, and make sure 1 is the last one!\ \>", "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.4156496838948803`*^9, 3.41564971734724*^9}, { 3.415650162794191*^9, 3.415650166121984*^9}, {3.415711887873*^9, 3.415711914566701*^9}, 3.458483612634404*^9}], Cell[BoxData[{ RowBox[{ RowBox[{"IsPrimitiveSlow", "[", RowBox[{"f_", ",", "p_", ",", "n_"}], "]"}], " ", ":=", " ", "\[IndentingNewLine]", RowBox[{"Module", "[", " ", RowBox[{ RowBox[{"{", "allPowers", "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"allPowers", "=", RowBox[{"Table", "[", " ", RowBox[{ RowBox[{"PolynomialMod", "[", RowBox[{ SuperscriptBox["x", "k"], ",", RowBox[{"{", RowBox[{"f", ",", "p"}], "}"}]}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", RowBox[{ SuperscriptBox["p", "n"], "-", "1"}]}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"For", "[", " ", RowBox[{ RowBox[{"k", " ", "=", " ", "1"}], ",", " ", RowBox[{"k", " ", "\[LessEqual]", " ", RowBox[{ SuperscriptBox["p", "n"], "-", "1"}]}], ",", " ", RowBox[{"++", "k"}], ",", "\[IndentingNewLine]", " ", RowBox[{"If", "[", " ", RowBox[{ RowBox[{ RowBox[{"allPowers", "[", RowBox[{"[", "k", "]"}], "]"}], " ", "\[Equal]", " ", "1"}], ",", "\[IndentingNewLine]", " ", RowBox[{"If", "[", " ", RowBox[{ RowBox[{"k", " ", "<", " ", RowBox[{ SuperscriptBox["p", "n"], "-", "1"}]}], ",", " ", "\[IndentingNewLine]", " ", RowBox[{ RowBox[{"Print", "[", " ", RowBox[{ "\"\<>>>Polynomial is NOT primitive \!\(\*SuperscriptBox[\(x\), \ \(k\)]\)=1 for k = \>\"", ",", "k"}], " ", "]"}], ";", " ", RowBox[{"Return", "[", "]"}]}], ",", "\[IndentingNewLine]", " ", RowBox[{ "Print", "[", " ", "\"\<>>>Polynomial is primitive!\>\"", " ", "]"}]}], "]"}]}], "]"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{" "}]}], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415649501179551*^9, 3.415649564977016*^9}, { 3.415711921282351*^9, 3.415711927739768*^9}, {3.415712278794251*^9, 3.415712332468902*^9}, {3.415712401020297*^9, 3.415712403116811*^9}, 3.4157124741170073`*^9, {3.415713705538864*^9, 3.415713719094226*^9}, { 3.415713771604417*^9, 3.415713809585268*^9}, {3.415713850919409*^9, 3.415713932509047*^9}, {3.415714014898362*^9, 3.415714018657844*^9}, 3.458483612634495*^9}], Cell[BoxData[ RowBox[{"IsPrimitiveSlow", "[", RowBox[{"f", ",", "p", ",", "n"}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{{3.415644343681767*^9, 3.4156443485131483`*^9}, { 3.415645552578573*^9, 3.415645563256778*^9}, 3.415645934242545*^9, { 3.4157123377612133`*^9, 3.415712348285486*^9}, {3.415712405429071*^9, 3.415712413049953*^9}, 3.4157124769161263`*^9, 3.458483612634597*^9}], Cell[BoxData["\<\">>>Polynomial is primitive!\"\>"], "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}, CellChangeTimes->{ 3.42159911238074*^9, 3.421599162601603*^9, 3.421607842870283*^9, 3.421607965722872*^9, 3.432603148360752*^9, {3.433898879554319*^9, 3.433898888485461*^9}, 3.433898919737054*^9, 3.458399061551559*^9, { 3.4583991006656017`*^9, 3.458399124365011*^9}, 3.4584008501324377`*^9, 3.4584043686168957`*^9, 3.45840536070776*^9, 3.4584054950343533`*^9, 3.458405806458354*^9, 3.4584062883832197`*^9, 3.4584074962066708`*^9, 3.45840756025387*^9, 3.458407709535892*^9, 3.458408394319415*^9, 3.458408497873082*^9, 3.458409005636243*^9, 3.458409666679488*^9, { 3.458423463943159*^9, 3.458423471975636*^9}, 3.458423534673753*^9, 3.458423604138172*^9, 3.458424138299231*^9, 3.458424355119397*^9, 3.458424389041258*^9, 3.458424458604332*^9, 3.458424682679071*^9, 3.4584247630504923`*^9, 3.4584247991541033`*^9, 3.458483278469737*^9, 3.458483421514572*^9, 3.458483508356536*^9, 3.458483557007987*^9, { 3.458483612634687*^9, 3.458483625623967*^9}, 3.4584839497318563`*^9}] }, Open ]] }, ScreenStyleEnvironment->"Working", PrintingStyleEnvironment->"ColorPrintout", WindowSize->{1252, 1057}, WindowMargins->{{295, Automatic}, {Automatic, 6}}, PrintingCopies->1, PrintingPageRange->{1, Automatic}, CellLabelAutoDelete->True, Magnification->1.25, FrontEndVersion->"6.0 for Mac OS X x86 (32-bit) (May 21, 2008)", StyleDefinitions->"Sean.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[445, 16, 328, 8, 159, "Title", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[776, 26, 213, 4, 45, "Subtitle", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[992, 32, 284, 5, 33, "Subtitle", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[1279, 39, 124, 2, 57, "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[1406, 43, 949, 24, 65, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[2358, 69, 152, 2, 57, "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[2513, 73, 517, 12, 29, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[3033, 87, 546, 13, 59, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[3582, 102, 302, 6, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[3887, 110, 341, 7, 57, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[4231, 119, 240, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[4474, 126, 1596, 23, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[6073, 151, 378, 13, 40, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[6454, 166, 434, 10, 77, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[6891, 178, 247, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[7141, 185, 2036, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[9180, 216, 342, 5, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[9525, 223, 376, 9, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[9904, 234, 273, 5, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[10180, 241, 583, 21, 45, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[10766, 264, 659, 17, 88, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[11428, 283, 259, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[11690, 290, 2053, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[13746, 321, 357, 7, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[14106, 330, 555, 12, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[14664, 344, 1692, 24, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[16359, 370, 383, 11, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[16745, 383, 686, 17, 93, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[17434, 402, 238, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[17675, 409, 2094, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[19772, 440, 295, 4, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[20070, 446, 394, 11, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[20467, 459, 2116, 31, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[22586, 492, 238, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[22827, 499, 2019, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[24849, 530, 352, 9, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[25204, 541, 396, 11, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[25603, 554, 2070, 31, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[27676, 587, 345, 5, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[28024, 594, 392, 10, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[28419, 606, 221, 4, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[28643, 612, 2033, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[30679, 643, 389, 5, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[31071, 650, 479, 11, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[31553, 663, 224, 4, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[31780, 669, 1977, 28, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[33760, 699, 395, 8, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[34158, 709, 673, 18, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[34834, 729, 297, 7, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[35134, 738, 2125, 30, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[37262, 770, 318, 6, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[37583, 778, 2155, 30, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[39741, 810, 629, 17, 29, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[40373, 829, 661, 17, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[41037, 848, 250, 5, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[41290, 855, 2637, 48, 63, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[43930, 905, 736, 18, 29, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[44669, 925, 468, 13, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[45140, 940, 482, 13, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[45625, 955, 2191, 37, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[47819, 994, 683, 16, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[48505, 1012, 332, 7, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[48840, 1021, 2776, 50, 109, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[51619, 1073, 545, 13, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[52167, 1088, 363, 7, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[52533, 1097, 2392, 39, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[54928, 1138, 386, 5, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[55317, 1145, 473, 10, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[55793, 1157, 388, 7, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[56184, 1166, 2172, 32, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[58359, 1200, 515, 11, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[58877, 1213, 331, 6, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[59211, 1221, 2063, 29, 54, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[61277, 1252, 242, 3, 57, "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[61522, 1257, 403, 8, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[61928, 1267, 22961, 527, 1974, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[84892, 1796, 489, 8, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[85384, 1806, 364, 6, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[85751, 1814, 1226, 24, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[86980, 1840, 662, 10, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[87645, 1852, 865, 15, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[88513, 1869, 649, 10, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[89165, 1881, 1517, 36, 51, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[90685, 1919, 1490, 34, 97, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[92178, 1955, 754, 14, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[92935, 1971, 685, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[93623, 1984, 879, 16, 45, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[94505, 2002, 657, 10, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[95165, 2014, 1043, 19, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[96211, 2035, 866, 16, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[97080, 2053, 1355, 28, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[98438, 2083, 868, 16, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[99309, 2101, 1399, 29, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[100711, 2132, 659, 10, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[101373, 2144, 470, 6, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[101846, 2152, 497, 10, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[102346, 2164, 954, 18, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[103303, 2184, 500, 7, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[103806, 2193, 704, 12, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[104513, 2207, 530, 8, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[105046, 2217, 466, 10, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[105515, 2229, 1116, 20, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[106634, 2251, 636, 9, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[107273, 2262, 839, 14, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[108115, 2278, 625, 9, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[108743, 2289, 1433, 32, 51, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[110179, 2323, 1909, 40, 169, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[112091, 2365, 732, 13, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[112826, 2380, 670, 10, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[113499, 2392, 491, 11, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[113993, 2405, 1005, 19, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[115001, 2426, 499, 7, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[115503, 2435, 702, 12, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[116208, 2449, 486, 7, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[116697, 2458, 1137, 26, 51, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[117837, 2486, 1768, 38, 169, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[119608, 2526, 591, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[120202, 2539, 524, 8, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[120729, 2549, 565, 9, 45, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[121297, 2560, 635, 13, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[121935, 2575, 1385, 26, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[123323, 2603, 788, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[124114, 2616, 991, 16, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[125108, 2634, 777, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[125888, 2647, 1993, 43, 51, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[127884, 2692, 2058, 42, 169, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[129945, 2736, 884, 15, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[130832, 2753, 813, 12, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[131648, 2767, 1005, 17, 45, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[132656, 2786, 785, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[133444, 2799, 994, 17, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[134441, 2818, 1509, 29, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[135953, 2849, 994, 17, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[136950, 2868, 1367, 25, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[138320, 2895, 996, 17, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[139319, 2914, 1456, 28, 47, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[140778, 2944, 789, 11, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[141570, 2957, 240, 3, 57, "Section", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[141813, 2962, 628, 15, 52, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[142444, 2979, 483, 12, 63, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[142930, 2993, 2750, 63, 63, "Output", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[145683, 3058, 324, 6, 25, "Text", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[146010, 3066, 2530, 60, 247, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[148543, 3128, 442, 7, 54, "Input", CellGroupingRules->{GroupTogetherGrouping, 10000.}], Cell[148988, 3137, 1136, 16, 42, "Print", CellGroupingRules->{GroupTogetherGrouping, 10000.}] }, Open ]] } ] *)