(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 10.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 43000, 1291] NotebookOptionsPosition[ 38703, 1151] NotebookOutlinePosition[ 39061, 1167] CellTagsIndexPosition[ 39018, 1164] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell[TextData[{ "Cryptography with ", StyleBox["Mathematica", FontSlant->"Italic"] }], "Title"], Cell[CellGroupData[{ Cell["Modular Arithmetic", "Section", CellChangeTimes->{{3.624034729568111*^9, 3.624034733494886*^9}}], Cell[TextData[{ StyleBox["Definition:", FontWeight->"Bold"], " Let m be any positive integer. We say that ", StyleBox["two integers a and b are congruent modulo m", FontVariations->{"Underline"->True}], " if b-a is divisible by m. In other words, the division of a by m gives the \ same remainder as the division of b by m. We write a=b (mod m), or a \ \[Congruent] b (mod m), or a-b \[Congruent] 0 (mod m)." }], "Text", CellChangeTimes->{{3.624035117733488*^9, 3.624035256428549*^9}, { 3.62403529169237*^9, 3.624035325684688*^9}, {3.6240362275555887`*^9, 3.624036282647273*^9}}], Cell[TextData[StyleBox["Equivalence Relation: ", FontWeight->"Bold"]], "Text", CellChangeTimes->{{3.6240355707359533`*^9, 3.624035615583908*^9}}], Cell[CellGroupData[{ Cell[TextData[{ StyleBox["reflexive:", FontWeight->"Bold"], " a \[Congruent] a (mod m)" }], "Subitem", CellChangeTimes->{{3.624035624821643*^9, 3.624035662662304*^9}, 3.624035728402268*^9}], Cell[TextData[{ StyleBox["symmetric: ", FontWeight->"Bold"], " if a \[Congruent] b (mod m) then b \[Congruent] a (mod m)" }], "Subitem", CellChangeTimes->{{3.624035624821643*^9, 3.6240357036381702`*^9}}], Cell[TextData[{ StyleBox["transitive:", FontWeight->"Bold"], " if a \[Congruent] b (mod m) and b \[Congruent] c (mod m) then a \ \[Congruent] c (mod m)" }], "Subitem", CellChangeTimes->{{3.624035624821643*^9, 3.624035745930636*^9}}] }, Open ]], Cell[TextData[{ StyleBox["Division Principle:", FontWeight->"Bold"], " Let m be any positive integer. Let b be any integer. Then there exist \ unique numbers q and r such that b=qm+r, and 0 \[LessEqual] r < m. \n", StyleBox["Smallest representative: ", FontWeight->"Bold"], "b \[Congruent] r (mod m)", StyleBox[" ", FontWeight->"Bold"], "and we think of r as the simplest representative of the equivalence class \ of b modulo m. " }], "Text", CellChangeTimes->{{3.6240353484719353`*^9, 3.6240355437800903`*^9}, { 3.624035765582368*^9, 3.624035766662245*^9}, {3.62403580601989*^9, 3.624035806652162*^9}}], Cell[TextData[{ StyleBox["The set of smallest representatives modulo m is denoted by ", FontWeight->"Bold"], Cell[BoxData[ FormBox[ SubscriptBox["\[DoubleStruckCapitalZ]", "m"], TraditionalForm]], FontWeight->"Bold", FontColor->RGBColor[0, 0, 1]], StyleBox["={0,1,2,3....,m-1}", FontWeight->"Bold", FontColor->RGBColor[0, 0, 1]], StyleBox[".", FontWeight->"Bold"] }], "Text", CellChangeTimes->{{3.624035781294599*^9, 3.6240358982946587`*^9}}], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"On", " ", SubscriptBox["\[DoubleStruckCapitalZ]", "m"], " ", "we", " ", "have", " ", "two", " ", "operations"}], " ", "+", " ", RowBox[{ RowBox[{"(", "addition", ")"}], " ", "and", " ", "*", " ", RowBox[{"(", "multiplication", ")"}]}]}], ",", " ", RowBox[{"with", " ", "the", " ", "following", " ", RowBox[{"properties", ":"}]}]}], TraditionalForm]], "Text", CellChangeTimes->{{3.6240359607034483`*^9, 3.624036103607272*^9}}], Cell[CellGroupData[{ Cell["\<\ If a, b and c are integers and a \[Congruent] b (mod m), then a + c \ \[Congruent] b + c (mod m)\ \>", "Subitem", CellChangeTimes->{{3.624036126292816*^9, 3.624036178400765*^9}}], Cell["\<\ If a, b, c, d are integers and a \[Congruent] b (mod m) and c \[Congruent] d \ (mod m) then ac \[Congruent] bd (mod m)\ \>", "Subitem", CellChangeTimes->{{3.624036126292816*^9, 3.624036221947456*^9}, { 3.624036290047223*^9, 3.624036290053232*^9}}], Cell[TextData[{ "Special case: If a and b are integers and n is a positive integer, then ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["a", RowBox[{"n", " "}]], "\[Congruent]", " ", RowBox[{ SuperscriptBox["b", "n"], " ", RowBox[{ RowBox[{"(", RowBox[{"mod", " ", "m"}], ")"}], "."}]}]}], TraditionalForm]]] }], "Subitem", CellChangeTimes->{{3.624036126292816*^9, 3.624036221947456*^9}, { 3.624036290047223*^9, 3.624036398913952*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Multiplicative inverse", "Section", CellChangeTimes->{{3.624034729568111*^9, 3.624034733494886*^9}, { 3.70166880534578*^9, 3.7016688122071123`*^9}}], Cell[TextData[{ StyleBox["Definition: ", FontWeight->"Bold"], "A ", StyleBox["multiplicative inverse", FontVariations->{"Underline"->True}], " of an integer a modulo m is an integer b such that ab \[Congruent] 1 (mod \ m). \n We write ", Cell[BoxData[ FormBox[ SuperscriptBox["a", RowBox[{"-", "1"}]], TraditionalForm]]], "\[Congruent] b (mod m)." }], "Text", CellChangeTimes->{{3.624036420665502*^9, 3.624036494160837*^9}, { 3.624036551844882*^9, 3.624036554164837*^9}, {3.624036606298398*^9, 3.624036636332901*^9}}], Cell[TextData[StyleBox["Examples : ", FontWeight->"Bold"]], "Text", CellChangeTimes->{{3.6240366454476*^9, 3.624036756765441*^9}, 3.624036811311699*^9}], Cell[CellGroupData[{ Cell[TextData[{ StyleBox["2*3 \[Congruent] 6 \[Congruent] 1 (mod 5), ", FontWeight->"Bold"], "so ", Cell[BoxData[ FormBox[ SuperscriptBox["2", RowBox[{"-", "1"}]], TraditionalForm]], FontWeight->"Bold"], StyleBox["\[Congruent] 3 (mod 5)", FontWeight->"Bold"], " and ", Cell[BoxData[ FormBox[ SuperscriptBox["3", RowBox[{"-", "1"}]], TraditionalForm]], FontWeight->"Bold"], StyleBox["\[Congruent] 2 (mod 5)", FontWeight->"Bold"] }], "Subitem", CellChangeTimes->{{3.624036807604966*^9, 3.624036814132634*^9}}], Cell[TextData[{ StyleBox["2 ", FontWeight->"Bold"], "is not invertible modulo", StyleBox[" 6. ", FontWeight->"Bold"], "Suppose, by contradiction, that there exists a number x such that 2x \ \[Congruent] 1 (mod 6), then 2x-1 is divisible by 6, so in particular 2x-1 is \ divisible by 2, which is false, because 2x-1 is odd." }], "Subitem", CellChangeTimes->{{3.624036807604966*^9, 3.624036976787937*^9}}] }, Open ]], Cell[TextData[{ StyleBox["Theorem:", FontWeight->"Bold"], " If p", "\[GreaterSlantEqual]", "2 is a prime number, then any number a in {1,2,...p-1} has a multiplicative \ inverse in ", Cell[BoxData[ FormBox[ SubscriptBox["\[DoubleStruckCapitalZ]", "p"], TraditionalForm]], CellChangeTimes->{{3.6240359607034483`*^9, 3.624036103607272*^9}}] }], "Text", CellChangeTimes->{{3.6240370045187063`*^9, 3.624037132579398*^9}}], Cell[TextData[{ StyleBox["Theorem:", FontWeight->"Bold"], " Let m\[GreaterSlantEqual]2 be any positive number, and a be a number in \ {1,2,...m-1}. Then a has a multiplicative inverse in ", Cell[BoxData[ FormBox[ SubscriptBox["\[DoubleStruckCapitalZ]", "m"], TraditionalForm]], CellChangeTimes->{{3.6240359607034483`*^9, 3.624036103607272*^9}}], " if and only if a and m are relatively prime." }], "Text", CellChangeTimes->{{3.624037101871274*^9, 3.624037213931428*^9}}], Cell[CellGroupData[{ Cell["\<\ Suppose that a and b are relatively prime, and let us consider the set of \ remainders:\ \>", "Subitem", CellChangeTimes->{{3.624037294827655*^9, 3.624037382806769*^9}, { 3.62403767117852*^9, 3.6240376772984953`*^9}}], Cell["\<\ a*0 (mod m), a*1 (mod m), a*2 (mod m), ... , a* (m-1) (mod m)\ \>", "Subitem", CellDingbat->None, CellChangeTimes->{{3.624037294827655*^9, 3.624037382801002*^9}, { 3.624037416841071*^9, 3.6240374657067966`*^9}, {3.624037686610175*^9, 3.6240376946264343`*^9}}], Cell["\<\ Notice that remainders are all distinct. Otherwise, suppose that a*i \ \[Congruent] a*j (mod m) for some i and j with 0", "Subitem", CellDingbat->None, CellChangeTimes->{{3.624037294827655*^9, 3.624037382801002*^9}, { 3.624037416841071*^9, 3.624037680445179*^9}}], Cell["\<\ In conclusion {a*0 (mod m), a*1 (mod m), a*2 (mod m), ... , a* (m-1) (mod \ m)} ={0,1,2,..., m-1}, so there exists a number k such that a*k \[Congruent] \ 1 (mod m).\ \>", "Subitem", CellDingbat->None, CellChangeTimes->{{3.624037294827655*^9, 3.624037382801002*^9}, { 3.624037416841071*^9, 3.624037757986333*^9}}], Cell["\<\ Suppose now that a*b \[Congruent] 1 (mod m) and let us show that a and m must \ be relatively prime.\ \>", "Subitem", CellChangeTimes->{{3.624037762042506*^9, 3.6240377994006443`*^9}}], Cell[TextData[{ "Suppose by contradiction, that a and m are not relatively prime and let a= ", Cell[BoxData[ FormBox[ SubscriptBox["a", "1"], TraditionalForm]]], "*c and m=", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], "*c, where 1<", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], "None, CellChangeTimes->{{3.624037762042506*^9, 3.624037855596408*^9}, { 3.65631706963475*^9, 3.6563171176690283`*^9}}], Cell[TextData[{ "a*b \[Congruent] 1 (mod m) \[DoubleLongRightArrow] ", Cell[BoxData[ FormBox[ SubscriptBox["a", "1"], TraditionalForm]]], "*c*b \[Congruent] 1 (mod m) \[DoubleLongRightArrow] ", Cell[BoxData[ FormBox[ SubscriptBox["a", "1"], TraditionalForm]]], "*c*b*", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], " \[Congruent] ", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], " (mod m) " }], "Subitem", CellDingbat->None, CellChangeTimes->{{3.624037762042506*^9, 3.624038030583232*^9}, { 3.656317122261441*^9, 3.656317145170001*^9}}], Cell[TextData[{ "\[DoubleLongRightArrow] (", Cell[BoxData[ FormBox[ SubscriptBox["a", "1"], TraditionalForm]]], "*b)*(c*", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], ") \[Congruent] ", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], " (mod m) \[DoubleLongRightArrow] 0 \[Congruent] ", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], " (mod m), which is false because ", Cell[BoxData[ FormBox[ SubscriptBox["m", "1"], TraditionalForm]]], " is not divisible by m. " }], "Subitem", CellDingbat->None, CellChangeTimes->{{3.624037762042506*^9, 3.624038056023233*^9}, { 3.656317148627433*^9, 3.656317183813908*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ "Modular Arithmetic in ", StyleBox["Mathematica", FontSlant->"Italic"] }], "Section", CellChangeTimes->{{3.62403474102289*^9, 3.6240347469666023`*^9}}], Cell[TextData[{ StyleBox["PowerMod[a,b,m]", FontWeight->"Bold"], " - gives ", Cell[BoxData[ FormBox[ SuperscriptBox["a", "b"], TraditionalForm]]], "mod m.\n", StyleBox["PowerMod[a,-1,m] ", FontWeight->"Bold"], "- finds the inverse of a modulo m; returns an error message \ \[OpenCurlyDoubleQuote]a is not invertible modulo m\[CloseCurlyDoubleQuote] \ is the integer a is not invertible modulo m.\n", StyleBox["PowerMod[a,1/r,m]", FontWeight->"Bold"], " - finds a modular r root of a." }], "Text", CellChangeTimes->{{3.624034781679995*^9, 3.624034987523432*^9}, { 3.624036562102447*^9, 3.624036581836773*^9}}], Cell[BoxData[ RowBox[{"PowerMod", "[", RowBox[{"3", ",", RowBox[{"-", "1"}], ",", "7"}], "]"}]], "Input", CellChangeTimes->{{3.624035020575572*^9, 3.624035035517601*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"PowerMod", "[", RowBox[{"3", ",", RowBox[{"-", "1"}], ",", "6"}], "]"}]], "Input", CellChangeTimes->{{3.6240350292227507`*^9, 3.624035038221874*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ "Mathematica is able to solve modular equations using \n", StyleBox["Solve[{List of Equations}, {List of Variables}, Modulus->m]", FontWeight->"Bold"] }], "Text", CellChangeTimes->{{3.6242108880291758`*^9, 3.624210939152709*^9}, { 3.6242110827697887`*^9, 3.624211083633028*^9}, 3.701668916155079*^9}], Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"3", "x"}], " ", "\[Equal]", "1"}], "}"}], ",", " ", RowBox[{"{", "x", "}"}], ",", " ", RowBox[{"Modulus", "\[Rule]", "7"}]}], " ", "]"}]], "Input", CellChangeTimes->{{3.624211096982094*^9, 3.62421114733051*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"2", "x"}], " ", "\[Equal]", " ", "1"}], "}"}], ",", RowBox[{"{", "x", "}"}], ",", " ", RowBox[{"Modulus", "\[Rule]", "26"}]}], "]"}]], "Input", CellChangeTimes->{{3.624211187935019*^9, 3.6242112083508987`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"2", "x"}], " ", "\[Equal]", " ", "2"}], "}"}], ",", RowBox[{"{", "x", "}"}], ",", " ", RowBox[{"Modulus", "\[Rule]", "26"}]}], "]"}]], "Input", CellChangeTimes->{{3.6242112301444883`*^9, 3.6242112302529917`*^9}}, Background->RGBColor[0.87, 0.94, 1]] }, Open ]], Cell[CellGroupData[{ Cell["Affine ciphers", "Section", CellChangeTimes->{{3.624033047288239*^9, 3.624033050439247*^9}}], Cell[TextData[{ "An Affine cipher is an enchipherment scheme of the form ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox["E", RowBox[{"a", ",", "b"}]], "(", "x", ")"}], "=", RowBox[{"ax", "+", RowBox[{"b", " ", RowBox[{"(", RowBox[{"mod", " ", "26"}], ")"}]}]}]}], TraditionalForm]], FontWeight->"Bold"], " and ", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ RowBox[{ SubscriptBox["D", RowBox[{"a", ",", "b"}]], "(", "x", ")"}], "=", RowBox[{ RowBox[{ SuperscriptBox["a", RowBox[{"-", "1"}]], "(", RowBox[{"x", "-", "b"}], ")"}], " ", RowBox[{"(", RowBox[{"mod", " ", "26"}], ")"}]}]}], FontWeight->"Bold"], TraditionalForm]]], ", where a and b are integer numbers between 0 and 25, and a and 26 must be \ relatively prime." }], "Text", CellChangeTimes->{{3.624033185868272*^9, 3.624033233076146*^9}, { 3.624033569106139*^9, 3.624033676196334*^9}, {3.624034024254312*^9, 3.624034059131054*^9}, {3.701672731830654*^9, 3.701672739012226*^9}}], Cell["These are the admissible values for the first key (key a):", "Text", CellChangeTimes->{{3.624034354067368*^9, 3.6240343649438963`*^9}, { 3.624034404529327*^9, 3.624034417856174*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Select", "[", RowBox[{ RowBox[{"Table", "[", RowBox[{"i", ",", RowBox[{"{", RowBox[{"i", ",", "25"}], "}"}]}], "]"}], ",", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"GCD", "[", RowBox[{"26", ",", "#"}], "]"}], "\[Equal]", "1"}], ")"}], "&"}]}], "]"}]], "Input", Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ "1", ",", "3", ",", "5", ",", "7", ",", "9", ",", "11", ",", "15", ",", "17", ",", "19", ",", "21", ",", "23", ",", "25"}], "}"}]], "Output", CellChangeTimes->{3.624034386904517*^9, 3.656317522453587*^9}] }, Open ]], Cell["An example of a good key : a = 3", "Text", CellChangeTimes->{{3.624038276593713*^9, 3.624038289384252*^9}, { 3.6241981591313334`*^9, 3.624198164641966*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Table", "[", RowBox[{ RowBox[{"Mod", "[", RowBox[{ RowBox[{"3", "*", "i"}], ",", "26"}], "]"}], ",", " ", RowBox[{"{", RowBox[{"i", ",", "0", ",", "25"}], "}"}]}], "]"}]], "Input", CellChangeTimes->{{3.624038349172082*^9, 3.6240383494016657`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ "0", ",", "3", ",", "6", ",", "9", ",", "12", ",", "15", ",", "18", ",", "21", ",", "24", ",", "1", ",", "4", ",", "7", ",", "10", ",", "13", ",", "16", ",", "19", ",", "22", ",", "25", ",", "2", ",", "5", ",", "8", ",", "11", ",", "14", ",", "17", ",", "20", ",", "23"}], "}"}]], "Output", CellChangeTimes->{3.624038351908895*^9}] }, Open ]], Cell["An example of a bad key: a = 2", "Text", CellChangeTimes->{{3.62403829489009*^9, 3.624038302112776*^9}, { 3.6241981669780073`*^9, 3.624198171658003*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Table", "[", RowBox[{ RowBox[{"Mod", "[", RowBox[{ RowBox[{"2", "*", "i"}], ",", "26"}], "]"}], ",", " ", RowBox[{"{", RowBox[{"i", ",", "0", ",", "25"}], "}"}]}], "]"}]], "Input", CellChangeTimes->{{3.6240383050805607`*^9, 3.6240383356254*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ "0", ",", "2", ",", "4", ",", "6", ",", "8", ",", "10", ",", "12", ",", "14", ",", "16", ",", "18", ",", "20", ",", "22", ",", "24", ",", "0", ",", "2", ",", "4", ",", "6", ",", "8", ",", "10", ",", "12", ",", "14", ",", "16", ",", "18", ",", "20", ",", "22", ",", "24"}], "}"}]], "Output", CellChangeTimes->{{3.624038316286405*^9, 3.624038337420867*^9}}] }, Open ]], Cell[TextData[{ StyleBox["Remark", FontWeight->"Bold"], ": Note that when a = 1, the Affine Cipher is just the Caesar Cipher \ discussed in the last lecture" }], "Text", CellChangeTimes->{{3.6563235601097727`*^9, 3.656323613278635*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Euler's totient function \[Phi](n)", "Section", CellChangeTimes->{{3.7016692567082872`*^9, 3.701669259111034*^9}, { 3.7016692904102077`*^9, 3.701669319776581*^9}}], Cell[TextData[{ StyleBox["Definition: \n", FontWeight->"Bold"], "The function", StyleBox[" \[Phi](n) ", FontWeight->"Bold"], "gives the number of positive integers less than or equal to n which are \ relatively prime to n." }], "Text", CellChangeTimes->{{3.624036420665502*^9, 3.624036494160837*^9}, { 3.624036551844882*^9, 3.624036554164837*^9}, {3.624036606298398*^9, 3.624036636332901*^9}, {3.701669401782687*^9, 3.7016694380983553`*^9}, { 3.701670477665638*^9, 3.701670497231262*^9}}], Cell[TextData[{ StyleBox["Formula: ", FontWeight->"Bold"], " ", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ StyleBox[ RowBox[{"\[Phi]", "(", "n", ")"}], FontWeight->"Bold"], StyleBox["=", FontWeight->"Bold"], RowBox[{ RowBox[{ RowBox[{ StyleBox["n", FontWeight->"Bold"], StyleBox["*", FontWeight->"Bold"], RowBox[{"(", RowBox[{"1", "-", StyleBox[ FractionBox["1", SubscriptBox["p", "1"]], FontSize->18]}], ")"}], RowBox[{"(", RowBox[{"1", "-", StyleBox[ FractionBox["1", SubscriptBox["p", "2"]], FontSize->18]}], ")"}]}], "..."}], RowBox[{"(", RowBox[{"1", "-", StyleBox[ FractionBox["1", SubscriptBox["p", "k"]], FontSize->18]}], ")"}]}]}], FontColor->GrayLevel[0], Background->RGBColor[1, 1, 0.85]], TraditionalForm]], FormatType->"TraditionalForm"], "\n where ", Cell[BoxData[ FormBox[ SubscriptBox["p", "1"], TraditionalForm]]], ",...", Cell[BoxData[ FormBox[ SubscriptBox["p", "k"], TraditionalForm]]], " are all the prime divisors of n." }], "Text", CellChangeTimes->{{3.624036420665502*^9, 3.624036494160837*^9}, { 3.624036551844882*^9, 3.624036554164837*^9}, {3.624036606298398*^9, 3.624036636332901*^9}, {3.701669401782687*^9, 3.7016694380983553`*^9}, { 3.701669499340605*^9, 3.701669500299163*^9}, 3.701670005017687*^9, { 3.701670036616474*^9, 3.7016700816278*^9}, {3.701670126481748*^9, 3.701670205945809*^9}, {3.701670271287046*^9, 3.701670328900625*^9}, { 3.701670378232889*^9, 3.7016704636412897`*^9}, {3.701671077087584*^9, 3.701671077087764*^9}}], Cell[TextData[{ StyleBox["Mathematica ", FontWeight->"Bold", FontSlant->"Italic"], StyleBox["function: \nEulerPhi[n] ", FontWeight->"Bold"], "- computes Euler\[CloseCurlyQuote]s totient function ", StyleBox["\[Phi](n)", FontWeight->"Bold"], ". " }], "Text", CellChangeTimes->{{3.624036420665502*^9, 3.624036494160837*^9}, { 3.624036551844882*^9, 3.624036554164837*^9}, {3.624036606298398*^9, 3.624036636332901*^9}, {3.701669401782687*^9, 3.7016694380983553`*^9}, { 3.701669499340605*^9, 3.701669500299163*^9}, {3.701669709927011*^9, 3.701669775176188*^9}, 3.7016704740174847`*^9, {3.701670517772366*^9, 3.7016705325891943`*^9}}], Cell[TextData[{ StyleBox["Applications: \n", FontWeight->"Bold"], "Euler\[CloseCurlyQuote]s totient function ", StyleBox["\[Phi](n)", FontWeight->"Bold"], " is widely used in Number Theory and also useful for a number of \ cryptographic protocols. For example, in the case of an Affine Cipher, we can \ use it to count the number of admissible values for the first parameter \ \[OpenCurlyDoubleQuote]a\[CloseCurlyDoubleQuote] of the key." }], "Text", CellChangeTimes->{{3.624036420665502*^9, 3.624036494160837*^9}, { 3.624036551844882*^9, 3.624036554164837*^9}, {3.624036606298398*^9, 3.624036636332901*^9}, {3.701669401782687*^9, 3.7016694380983553`*^9}, { 3.701669499340605*^9, 3.701669500299163*^9}, {3.701669709927011*^9, 3.701669775176188*^9}, 3.7016704740174847`*^9, {3.701670517772366*^9, 3.7016705325891943`*^9}, {3.701670819632317*^9, 3.7016710052927103`*^9}, { 3.701671119140725*^9, 3.701671131797016*^9}}, TextJustification->1.], Cell[BoxData[ RowBox[{"EulerPhi", "[", "26", "]"}]], "Input", CellChangeTimes->{{3.701670664012352*^9, 3.701670682623293*^9}, { 3.701670758091434*^9, 3.701670758712846*^9}}, Background->RGBColor[0.87, 0.94, 1]] }, Open ]], Cell[CellGroupData[{ Cell["Encoding and Decoding of Affine Ciphers", "Section", CellChangeTimes->{{3.6240347627587357`*^9, 3.6240347677907753`*^9}, { 3.62403810952796*^9, 3.6240381155590343`*^9}, {3.624199117497347*^9, 3.624199136920718*^9}, 3.624211353801586*^9, {3.701671155686583*^9, 3.701671159765534*^9}}], Cell[TextData[{ "Notice that each function is defined twice, on Integers and on Strings. You \ can use ", StyleBox["?AffineEncode", FontWeight->"Bold"], " to see that ", StyleBox["Mathematica", FontSlant->"Italic"], " takes in both definitions, and it decides which one to apply based on the \ type of the input. " }], "Text", CellChangeTimes->{{3.7016718932183847`*^9, 3.701672027699725*^9}}], Cell[BoxData[ RowBox[{"Clear", "[", RowBox[{"AffineEncode", ",", " ", "AffineDecode"}], "]"}]], "Input", CellChangeTimes->{{3.624038890013033*^9, 3.624038899343802*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{ RowBox[{"AffineEncode", "[", RowBox[{ RowBox[{"x_", " ", "?", "IntegerQ"}], ",", " ", "a_", ",", " ", "b_"}], "]"}], ":=", " ", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"a", "*", "x"}], "+", "b"}], ",", "26"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"AffineEncode", "[", RowBox[{ RowBox[{"x_", " ", "?", "StringQ"}], ",", " ", "a_", ",", " ", "b_"}], "]"}], ":=", " ", "\[IndentingNewLine]", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"n", ",", "numerictext"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"numerictext", "=", RowBox[{ RowBox[{"ToCharacterCode", "[", RowBox[{"ToUpperCase", "[", "x", "]"}], "]"}], "-", "65"}]}], ";", "\[IndentingNewLine]", RowBox[{"numerictext", " ", "=", " ", RowBox[{"Select", "[", RowBox[{"numerictext", ",", " ", RowBox[{ RowBox[{"(", RowBox[{"0", "<=", "#", "\[LessEqual]", "25"}], ")"}], "&"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"n", " ", "=", " ", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"a", "*", "numerictext"}], "+", "b"}], ",", "26"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"FromCharacterCode", "[", RowBox[{"n", "+", "65"}], "]"}]}]}], "\[IndentingNewLine]", "]"}]}]}], "Input", CellChangeTimes->{{3.6240257500371323`*^9, 3.6240257987200212`*^9}, { 3.624025831271524*^9, 3.624025842014024*^9}, 3.6240262221904793`*^9, { 3.624026317748263*^9, 3.6240263753323812`*^9}, {3.62403450344028*^9, 3.6240345550976458`*^9}, {3.624034679639542*^9, 3.624034696591422*^9}, { 3.6241982715951643`*^9, 3.6241982958523083`*^9}, {3.624198809385181*^9, 3.624198835769988*^9}, {3.624199059411195*^9, 3.6241990650590363`*^9}, 3.6563182096969433`*^9}, FontSize->14, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{ RowBox[{"AffineDecode", "[", RowBox[{ RowBox[{"x_", " ", "?", "IntegerQ"}], ",", " ", "a_", ",", " ", "b_"}], "]"}], ":=", " ", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"PowerMod", "[", RowBox[{"a", ",", RowBox[{"-", "1"}], ",", "26"}], "]"}], "*", RowBox[{"(", RowBox[{"x", "-", "b"}], ")"}]}], ",", "26"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"AffineDecode", "[", RowBox[{ RowBox[{"x_", " ", "?", "StringQ"}], ",", " ", "a_", ",", " ", "b_"}], "]"}], ":=", " ", "\[IndentingNewLine]", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"n", ",", "numerictext"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"numerictext", " ", "=", " ", RowBox[{ RowBox[{"ToCharacterCode", "[", "x", "]"}], "-", "65"}]}], ";", "\[IndentingNewLine]", RowBox[{"n", " ", "=", " ", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"PowerMod", "[", RowBox[{"a", ",", RowBox[{"-", "1"}], ",", "26"}], "]"}], "*", RowBox[{"(", RowBox[{"numerictext", "-", "b"}], ")"}]}], ",", "26"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"FromCharacterCode", "[", RowBox[{"n", "+", "65"}], "]"}]}]}], "\[IndentingNewLine]", "]"}]}]}], "Input", CellChangeTimes->{{3.624032008355279*^9, 3.624032090512413*^9}, { 3.6240386901368513`*^9, 3.6240387437183867`*^9}, {3.624038845063614*^9, 3.62403884847127*^9}, {3.6241982856280746`*^9, 3.6241982874110603`*^9}, { 3.624198840786376*^9, 3.624198869880609*^9}, {3.6241990332362328`*^9, 3.624199050444194*^9}, 3.656318200322913*^9}, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ "\n", StyleBox["Listable", FontWeight->"Bold"], " is an attribute that can be assigned to a function to indicate that the \ function should automatically be applied to lists that appear as its \ arguments. For example, Sin is listable, so Sin[{1, 2, 3, 4}] evaluates to \ {Sin[1], Sin[2], Sin[3], Sin[4]}" }], "Text", CellChangeTimes->{{3.656319767823564*^9, 3.6563198777460823`*^9}}, TextJustification->1.], Cell[BoxData[{ RowBox[{ RowBox[{"SetAttributes", "[", RowBox[{"AffineEncode", ",", " ", "Listable"}], "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"SetAttributes", "[", RowBox[{"AffineDecode", ",", " ", "Listable"}], "]"}], ";"}]}], "Input", CellChangeTimes->{{3.624198558855381*^9, 3.624198568967004*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{"AffineEncode", "[", RowBox[{"3", ",", "5", ",", "1"}], "]"}], "\[IndentingNewLine]", RowBox[{"AffineDecode", "[", RowBox[{"16", ",", "5", ",", "1"}], "]"}], "\[IndentingNewLine]", RowBox[{"AffineEncode", "[", RowBox[{ RowBox[{"{", RowBox[{"0", ",", "1", ",", "2", ",", "3", ",", "4", ",", "5"}], "}"}], ",", "5", ",", "1"}], "]"}], "\[IndentingNewLine]", RowBox[{"AffineEncode", "[", RowBox[{"\"\\"", ",", " ", "7", ",", " ", "11"}], "]"}], "\[IndentingNewLine]", RowBox[{"AffineDecode", "[", RowBox[{"\"\\"", ",", " ", "7", ",", " ", "11"}], "]"}]}], "Input", CellChangeTimes->{{3.624038128681815*^9, 3.6240381342805862`*^9}, { 3.624038178321445*^9, 3.624038212236616*^9}, {3.624038372147931*^9, 3.624038381401793*^9}, {3.624198576824216*^9, 3.624198587471162*^9}, { 3.6241986401336*^9, 3.624198642198125*^9}, {3.6241989142597303`*^9, 3.624198914688346*^9}, {3.62420670520072*^9, 3.624206711334469*^9}, { 3.6563195713347588`*^9, 3.6563196256473293`*^9}, {3.6563199332165537`*^9, 3.656319950903358*^9}}, Background->GrayLevel[0.85]] }, Open ]], Cell[CellGroupData[{ Cell["Simple substitution/Monoalphabetic substitutions", "Section", CellChangeTimes->{{3.6241993865117693`*^9, 3.624199409599485*^9}}], Cell[TextData[{ StyleBox["Description:", FontWeight->"Bold"], " With the method of a simple substitution one chooses a ", StyleBox["fixed permutation p", FontWeight->"Bold"], " of the alphabet letters {a, b, \[Ellipsis], z} and applies that \ permutation to all letters in the plaintext." }], "Text", CellChangeTimes->{{3.624199527908495*^9, 3.624199581619829*^9}, { 3.701671215617731*^9, 3.701671218751512*^9}}, TextJustification->1.], Cell[TextData[{ StyleBox["Encoding and Decoding functions:", FontWeight->"Bold"], "\n", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"E", "(", "x", ")"}], "="}], TraditionalForm]]], " ", Cell[BoxData[ FormBox[ RowBox[{"p", "(", "x", ")"}], TraditionalForm]]], "\n", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"D", "(", "x", ")"}], "="}], TraditionalForm]]], Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ SuperscriptBox["p", RowBox[{"-", "1"}]], "(", "x", ")"}]}], TraditionalForm]]] }], "Text", CellChangeTimes->{{3.6242014427560987`*^9, 3.624201547364739*^9}, { 3.701671282728355*^9, 3.70167129316089*^9}}], Cell[TextData[StyleBox["Example:", FontWeight->"Bold"]], "Text", CellChangeTimes->{{3.6242014427560987`*^9, 3.624201547364739*^9}, { 3.701671282728355*^9, 3.7016713148219748`*^9}}], Cell[BoxData[ RowBox[{"Cipher", " ", "=", " ", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"\"\\"", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"\"\\"", "\[Rule]", "\"\\""}]}], "}"}]}]], "Input", CellChangeTimes->{{3.624206847182817*^9, 3.62420685906186*^9}, { 3.624206902543586*^9, 3.624207133139069*^9}, {3.624207265160836*^9, 3.624207279278679*^9}, {3.6242073103293333`*^9, 3.6242073493482943`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"DecodeA", " ", "=", " ", RowBox[{ RowBox[{"(", RowBox[{"\"\\"", " ", "/.", " ", "Cipher"}], ")"}], "\[Rule]", "\"\\""}]}]], "Input", CellChangeTimes->{{3.624201574883129*^9, 3.624201617945201*^9}, { 3.6242021798980083`*^9, 3.624202189246249*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ "We can generate the English alphabet in several ways: from the ASCII codes, \ or by using the ", StyleBox["Mathematica", FontSlant->"Italic"], " function ", StyleBox["Alphabet[..]", FontWeight->"Bold"], "." }], "Text", CellChangeTimes->{{3.656330237227537*^9, 3.656330271489605*^9}, { 3.656330303021346*^9, 3.656330341155397*^9}}], Cell[BoxData[{ RowBox[{"alphabet", " ", "=", " ", RowBox[{"Table", "[", RowBox[{ RowBox[{"FromCharacterCode", "[", "i", "]"}], ",", RowBox[{"{", RowBox[{"i", ",", "65", ",", RowBox[{"65", "+", "25"}]}], "}"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{"alphabet", "=", RowBox[{"ToUpperCase", " ", "@", " ", RowBox[{"Alphabet", "[", "\"\\"", "]"}]}]}]}], "Input", CellChangeTimes->{{3.624202214339829*^9, 3.624202320375886*^9}, { 3.6242023795111227`*^9, 3.624202384902361*^9}, {3.624202417105383*^9, 3.624202417262621*^9}, 3.624202456430208*^9, {3.701671430309493*^9, 3.701671431221299*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell["\<\ Now we can display the backwards correspondence between the permuted \ (encrypted) alphabet and the original one.\ \>", "Text", CellChangeTimes->{{3.656331113772849*^9, 3.656331171236003*^9}}], Cell[BoxData[ RowBox[{"DecodeCipher", " ", "=", " ", RowBox[{"Table", "[", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"alphabet", "[", RowBox[{"[", "i", "]"}], "]"}], "/.", " ", "Cipher"}], ")"}], "\[Rule]", RowBox[{"alphabet", "[", RowBox[{"[", "i", "]"}], "]"}]}], ",", RowBox[{"{", RowBox[{"i", ",", "1", ",", "26"}], "}"}]}], "]"}]}]], "Input", CellChangeTimes->{{3.62420233197855*^9, 3.624202336820602*^9}, { 3.6242024809456577`*^9, 3.624202529743141*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell["Encoding and Decoding for Simple Substitution Ciphers", "Subsection", CellChangeTimes->{{3.624207521834441*^9, 3.624207525593336*^9}, { 3.701671348942782*^9, 3.701671365799492*^9}}], Cell[CellGroupData[{ Cell["\<\ StringReplace[\[OpenCurlyDoubleQuote]string\[CloseCurlyDoubleQuote],s\[Rule]\ sp] or StringReplace[\[OpenCurlyDoubleQuote]string\[CloseCurlyDoubleQuote],{\ s1\[Rule]sp1,s2\[Rule]sp2,\[Ellipsis]}] replaces the string expressions s by sp whenever they appear as substrings \ of string.\ \>", "Subsubsection", CellChangeTimes->{{3.624206439012788*^9, 3.6242064602405357`*^9}}], Cell[BoxData[{ RowBox[{"Clear", "[", RowBox[{"EncodeP", ",", " ", "DecodeP"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"EncodeP", "[", "x_", "]"}], ":=", RowBox[{"StringReplace", "[", RowBox[{ RowBox[{"ToUpperCase", "[", "x", "]"}], ",", " ", "Cipher"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"DecodeP", "[", "x_", "]"}], ":=", RowBox[{"StringReplace", "[", RowBox[{ RowBox[{"ToUpperCase", "[", "x", "]"}], ",", " ", "DecodeCipher"}], "]"}]}]}], "Input", CellChangeTimes->{{3.624200161199871*^9, 3.6242001862049313`*^9}, { 3.6242075430462017`*^9, 3.62420767035211*^9}, {3.624207713367834*^9, 3.6242077160155973`*^9}, {3.6242078955029993`*^9, 3.624207897629118*^9}, { 3.701671385729732*^9, 3.701671387177218*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"EncodeP", "[", "\"\\"", "]"}]], "Input", CellChangeTimes->{{3.624207677096342*^9, 3.624207691357514*^9}, 3.62420772476735*^9, 3.624207821324841*^9, {3.6242078610408773`*^9, 3.624207868092946*^9}, 3.6242079521734543`*^9}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"DecodeP", "[", "\"\\"", "]"}]], "Input", CellChangeTimes->{{3.624204298054552*^9, 3.624204316303628*^9}, { 3.6242077335306063`*^9, 3.62420774712085*^9}, {3.6242079359601307`*^9, 3.6242079552214737`*^9}}, Background->RGBColor[0.87, 0.94, 1]] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Cryptanalysis of Affine Ciphers:", "Section", CellChangeTimes->{{3.624208044692566*^9, 3.624208054556316*^9}}], Cell[CellGroupData[{ Cell["a) By the method of a known ciphertext:", "Subsubsection", CellChangeTimes->{{3.624208063172361*^9, 3.624208090268035*^9}, { 3.656325076253151*^9, 3.6563250772056293`*^9}, {3.701672672737474*^9, 3.701672672960371*^9}}], Cell[TextData[{ StyleBox["Exercise: ", FontWeight->"Bold"], "Suppose that an affine cipher E(x) = ax+b (mod 26) enciphers \ \[OpenCurlyDoubleQuote]H\[CloseCurlyDoubleQuote] as \[OpenCurlyDoubleQuote]X\ \[CloseCurlyDoubleQuote] and \[OpenCurlyDoubleQuote]Q\[CloseCurlyDoubleQuote] \ as \[OpenCurlyDoubleQuote]Y\[CloseCurlyDoubleQuote]. Find the key. Then use \ the key to decode the ciphertext \ \[OpenCurlyDoubleQuote]HXAEAEICJJOLCGPSQPVJCAPHOTHCHHCIG\ \[CloseCurlyDoubleQuote], which has been encoded using the same cipher. " }], "Text", CellChangeTimes->{{3.6242082478670588`*^9, 3.624208341271936*^9}, { 3.624208493532267*^9, 3.6242085043715477`*^9}, {3.624210781324059*^9, 3.624210791403756*^9}, {3.624211479746768*^9, 3.6242114804967012`*^9}, { 3.701672686162005*^9, 3.701672688984914*^9}}, TextJustification->1.], Cell[TextData[{ StyleBox["Hint: ", FontWeight->"Bold"], "Solve a system of two linear equations mod 26." }], "Text", CellChangeTimes->{{3.6242113834663057`*^9, 3.624211433127977*^9}, { 3.656325805915979*^9, 3.6563258064763308`*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["\<\ b) By exhaustive key search, or brute-force approach (try all possible keys):\ \ \>", "Subsubsection", CellChangeTimes->{{3.624208063172361*^9, 3.624208090268035*^9}, { 3.656319060033389*^9, 3.6563190632587147`*^9}, {3.6563194536706877`*^9, 3.656319461934849*^9}, {3.6563250726923933`*^9, 3.656325073580098*^9}, { 3.7016726756814613`*^9, 3.701672676056275*^9}}], Cell["\<\ The following text \"KJJTZKLTVFMMLSVNULAUVIZFIVAIVQQXVFZX\" has been encoded \ using an Affine Cipher. Decode the text.\ \>", "Text", CellChangeTimes->{{3.6563194864647903`*^9, 3.656319492686431*^9}, 3.701667865106997*^9}] }, Open ]], Cell[CellGroupData[{ Cell["c) By frequency analysis:", "Subsubsection", CellChangeTimes->{{3.624208081883882*^9, 3.6242080879403677`*^9}, { 3.624208930116665*^9, 3.6242089342847433`*^9}, {3.656325079334611*^9, 3.656325080294981*^9}, {3.656325114234623*^9, 3.656325124268654*^9}}], Cell[TextData[{ StyleBox["Exercise:", FontWeight->"Bold"], " Suppose that you have intercepted the following ciphertext \ \[OpenCurlyDoubleQuote]\ QNRVKVITSTIJVLVFPUTHVONVPGNWZVTGWQTWWQVPFPWVZXPPVHDIVNGWQVHNGWITIFAFPXZUSFHNDG\ WXGJWQVSVWWVICIVBDVGHXVPXGWQVHXUQVIWVYWTGOHNZUTIXGJWQVPVRXWQWQVSVWWVICIVBDVGHX\ VPNCWQVVGJSXPQTSUQTAVWNGVKVIFBDXHLSFCXGOPWQVXZTJVPDGOVIWQVUVIZDWTWXNGUNCWQVZNP\ WCIVBDVGWSVWWVIPXGWQVUSTXGWVYW\[CloseCurlyDoubleQuote]. \nYou know that it \ has been encoded using an affine cipher, but you don' t know the key. Use \ frequency analysis to break the cipher. " }], "Text", CellChangeTimes->{{3.624209715352704*^9, 3.624209789136374*^9}, { 3.6242128806216297`*^9, 3.624212893583449*^9}}] }, Open ]] }, Open ]] }, Open ]] }, WindowSize->{879, 512}, WindowMargins->{{Automatic, 38}, {Automatic, 0}}, FrontEndVersion->"11.0 for Mac OS X x86 (32-bit, 64-bit Kernel) (September \ 21, 2016)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[580, 22, 99, 4, 92, "Title"], Cell[CellGroupData[{ Cell[704, 30, 103, 1, 64, "Section"], Cell[810, 33, 593, 12, 68, "Text"], Cell[1406, 47, 147, 2, 30, "Text"], Cell[CellGroupData[{ Cell[1578, 53, 206, 6, 26, "Subitem"], Cell[1787, 61, 211, 5, 26, "Subitem"], Cell[2001, 68, 243, 6, 26, "Subitem"] }, Open ]], Cell[2259, 77, 623, 15, 87, "Text"], Cell[2885, 94, 464, 14, 32, "Text"], Cell[3352, 110, 523, 12, 32, "Text"], Cell[CellGroupData[{ Cell[3900, 126, 190, 4, 26, "Subitem"], Cell[4093, 132, 261, 5, 26, "Subitem"], Cell[4357, 139, 488, 14, 26, "Subitem"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[4894, 159, 157, 2, 64, "Section"], Cell[5054, 163, 562, 16, 50, "Text"], Cell[5619, 181, 158, 3, 30, "Text"], Cell[CellGroupData[{ Cell[5802, 188, 545, 20, 27, "Subitem"], Cell[6350, 210, 412, 10, 41, "Subitem"] }, Open ]], Cell[6777, 223, 433, 12, 34, "Text"], Cell[7213, 237, 484, 11, 51, "Text"], Cell[CellGroupData[{ Cell[7722, 252, 230, 5, 26, "Subitem"], Cell[7955, 259, 277, 6, 24, "Subitem"], Cell[8235, 267, 468, 9, 58, "Subitem"], Cell[8706, 278, 328, 7, 41, "Subitem"], Cell[9037, 287, 195, 4, 26, "Subitem"], Cell[9235, 293, 503, 17, 26, "Subitem"], Cell[9741, 312, 614, 21, 26, "Subitem"], Cell[10358, 335, 713, 25, 26, "Subitem"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[11120, 366, 172, 5, 64, "Section"], Cell[11295, 373, 630, 18, 88, "Text"], Cell[11928, 393, 217, 5, 48, "Input"], Cell[12148, 400, 219, 5, 48, "Input"], Cell[12370, 407, 324, 6, 49, "Text"], Cell[12697, 415, 351, 9, 48, "Input"], Cell[13051, 426, 350, 9, 48, "Input"], Cell[13404, 437, 352, 9, 48, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[13793, 451, 99, 1, 64, "Section"], Cell[13895, 454, 1089, 34, 54, "Text"], Cell[14987, 490, 191, 2, 30, "Text"], Cell[CellGroupData[{ Cell[15203, 496, 375, 13, 48, "Input"], Cell[15581, 511, 251, 5, 32, "Output"] }, Open ]], Cell[15847, 519, 165, 2, 30, "Text"], Cell[CellGroupData[{ Cell[16037, 525, 335, 9, 48, "Input"], Cell[16375, 536, 386, 7, 32, "Output"] }, Open ]], Cell[16776, 546, 162, 2, 30, "Text"], Cell[CellGroupData[{ Cell[16963, 552, 333, 9, 48, "Input"], Cell[17299, 563, 410, 7, 32, "Output"] }, Open ]], Cell[17724, 573, 241, 6, 30, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[18002, 584, 172, 2, 64, "Section"], Cell[18177, 588, 504, 12, 49, "Text"], Cell[18684, 602, 1807, 58, 68, "Text"], Cell[20494, 662, 660, 16, 49, "Text"], Cell[21157, 680, 970, 18, 87, "Text"], Cell[22130, 700, 215, 4, 48, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[22382, 709, 301, 4, 64, "Section"], Cell[22686, 715, 404, 11, 49, "Text"], Cell[23093, 728, 212, 4, 48, "Input"], Cell[23308, 734, 1959, 50, 207, "Input"], Cell[25270, 786, 1773, 47, 175, "Input"], Cell[27046, 835, 430, 10, 68, "Text"], Cell[27479, 847, 372, 9, 70, "Input"], Cell[27854, 858, 1159, 23, 133, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[29050, 886, 135, 1, 64, "Section"], Cell[29188, 889, 447, 11, 49, "Text"], Cell[29638, 902, 656, 25, 69, "Text"], Cell[30297, 929, 184, 3, 30, "Text"], Cell[30484, 934, 768, 14, 48, "Input"], Cell[31255, 950, 335, 8, 48, "Input"], Cell[31593, 960, 359, 11, 49, "Text"], Cell[31955, 973, 689, 15, 70, "Input"], Cell[32647, 990, 203, 4, 30, "Text"], Cell[32853, 996, 578, 16, 48, "Input"], Cell[CellGroupData[{ Cell[33456, 1016, 190, 2, 44, "Subsection"], Cell[CellGroupData[{ Cell[33671, 1022, 385, 7, 59, "Subsubsection"], Cell[34059, 1031, 818, 19, 91, "Input"], Cell[34880, 1052, 308, 5, 48, "Input"], Cell[35191, 1059, 288, 5, 48, "Input"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[35540, 1071, 117, 1, 64, "Section"], Cell[CellGroupData[{ Cell[35682, 1076, 230, 3, 35, "Subsubsection"], Cell[35915, 1081, 832, 15, 68, "Text"], Cell[36750, 1098, 239, 6, 30, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[37026, 1109, 379, 7, 35, "Subsubsection"], Cell[37408, 1118, 237, 5, 49, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[37682, 1128, 264, 3, 35, "Subsubsection"], Cell[37949, 1133, 714, 13, 144, "Text"] }, Open ]] }, Open ]] }, Open ]] } ] *)