(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 7.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     48094,       1539]
NotebookOptionsPosition[     42559,       1364]
NotebookOutlinePosition[     43037,       1384]
CellTagsIndexPosition[     42994,       1381]
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Arithmetic of Large Integers", "Section"],

Cell[BoxData[
 RowBox[{"50", "!"}]], "Input"],

Cell[BoxData[
 FractionBox[
  RowBox[{"50", "!"}], 
  SuperscriptBox["2", "100"]]], "Input"],

Cell[BoxData[
 RowBox[{"GCD", "[", 
  RowBox[{
   RowBox[{"50", "!"}], ",", 
   SuperscriptBox["2", "100"]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", 
  RowBox[{"50", "!"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  SuperscriptBox["2", "256"], "+", "1"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", 
  RowBox[{
   SuperscriptBox["2", "256"], "+", "1"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"p", "=", 
  RowBox[{"Random", "[", 
   RowBox[{"Integer", ",", 
    RowBox[{"{", 
     RowBox[{"1", ",", 
      SuperscriptBox["10", "1000"]}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "p", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"PrimeQ", "[", "p", "]"}]], "Input"]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Euclidean Algorithm",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[{
 RowBox[{"Clear", "[", "gcd", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"gcd", "[", 
   RowBox[{"a_", ",", "b_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"gcd", "[", 
    RowBox[{
     RowBox[{"\[LeftBracketingBar]", "a", "\[RightBracketingBar]"}], ",", 
     RowBox[{"\[LeftBracketingBar]", "b", "\[RightBracketingBar]"}]}], "]"}], 
   "/;", 
   RowBox[{
    RowBox[{"a", "<", "0"}], " ", "||", 
    RowBox[{"b", "<", "0"}]}]}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"gcd", "[", 
   RowBox[{"a_", ",", "b_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"gcd", "[", 
    RowBox[{"b", ",", "a"}], "]"}], "/;", 
   RowBox[{"a", "<", "b"}]}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"gcd", "[", 
   RowBox[{"a_", ",", "0"}], "]"}], ":=", "a"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"gcd", "[", 
   RowBox[{"a_", ",", "b_"}], "]"}], ":=", 
  RowBox[{"gcd", "[", 
   RowBox[{"b", ",", 
    RowBox[{"Mod", "[", 
     RowBox[{"a", ",", "b"}], "]"}]}], "]"}]}]}], "Input"],

Cell[BoxData[
 RowBox[{"gcd", "[", 
  RowBox[{
   RowBox[{"50", "!"}], ",", 
   SuperscriptBox["2", "100"]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"GCD", "[", 
  RowBox[{
   RowBox[{"50", "!"}], ",", 
   SuperscriptBox["2", "100"]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"q", "=", 
  RowBox[{"Random", "[", 
   RowBox[{"Integer", ",", 
    RowBox[{"{", 
     RowBox[{"1", ",", 
      SuperscriptBox["10", "1000"]}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"Timing", "[", 
  RowBox[{"gcd", "[", 
   RowBox[{"p", ",", "q"}], "]"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"Timing", "[", 
  RowBox[{"GCD", "[", 
   RowBox[{"p", ",", "q"}], "]"}], "]"}]], "Input"]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Extended Euclidean Algorithm",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[{
 RowBox[{"Clear", "[", "extendedgcd", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"extendedgcd", "[", 
   RowBox[{"xx_", ",", "y_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"x", ",", "k", ",", "rule", ",", "r", ",", "q", ",", "X"}], 
      "}"}], ",", "\[IndentingNewLine]", 
     RowBox[{
      RowBox[{
       RowBox[{"x", "[", "0", "]"}], "=", "xx"}], ";", 
      RowBox[{
       RowBox[{"x", "[", "1", "]"}], "=", "y"}], ";", 
      RowBox[{"k", "=", "0"}], ";", 
      RowBox[{"rule", "=", 
       RowBox[{"{", "}"}]}], ";", 
      RowBox[{"gcdmatrix", "=", 
       RowBox[{"{", "}"}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"While", "[", 
       RowBox[{
        RowBox[{"Not", "[", 
         RowBox[{
          RowBox[{"x", "[", 
           RowBox[{"k", "+", "1"}], "]"}], "==", "0"}], "]"}], ",", 
        "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"k", "=", 
          RowBox[{"k", "+", "1"}]}], ";", "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"r", "[", "k", "]"}], "=", 
          RowBox[{"Mod", "[", 
           RowBox[{
            RowBox[{"x", "[", 
             RowBox[{"k", "-", "1"}], "]"}], ",", 
            RowBox[{"x", "[", "k", "]"}]}], "]"}]}], ";", 
         "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"q", "[", "k", "]"}], "=", 
          RowBox[{"Quotient", "[", 
           RowBox[{
            RowBox[{"x", "[", 
             RowBox[{"k", "-", "1"}], "]"}], ",", 
            RowBox[{"x", "[", "k", "]"}]}], "]"}]}], ";", 
         "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"x", "[", 
           RowBox[{"k", "+", "1"}], "]"}], "=", 
          RowBox[{"r", "[", "k", "]"}]}], ";", "\[IndentingNewLine]", 
         RowBox[{"AppendTo", "[", 
          RowBox[{"rule", ",", 
           RowBox[{
            RowBox[{"X", "[", 
             RowBox[{"k", "+", "1"}], "]"}], "\[Rule]", 
            RowBox[{"Collect", "[", 
             RowBox[{
              RowBox[{
               RowBox[{
                RowBox[{"X", "[", 
                 RowBox[{"k", "-", "1"}], "]"}], "-", 
                RowBox[{
                 RowBox[{"q", "[", "k", "]"}], "*", 
                 RowBox[{"X", "[", "k", "]"}]}]}], "/.", "rule"}], ",", 
              RowBox[{"{", 
               RowBox[{
                RowBox[{"X", "[", "0", "]"}], ",", 
                RowBox[{"X", "[", "1", "]"}]}], "}"}]}], "]"}]}]}], "]"}], 
         ";", "\[IndentingNewLine]", 
         RowBox[{"AppendTo", "[", 
          RowBox[{"gcdmatrix", ",", 
           RowBox[{"{", 
            RowBox[{"k", ",", "\"\<|\>\"", ",", 
             RowBox[{"x", "[", 
              RowBox[{"k", "-", "1"}], "]"}], ",", "\"\<=\>\"", ",", 
             RowBox[{"q", "[", "k", "]"}], ",", "\"\<*\>\"", ",", 
             RowBox[{"x", "[", "k", "]"}], ",", "\"\<+\>\"", ",", 
             RowBox[{"r", "[", "k", "]"}]}], "}"}]}], "]"}], ";"}]}], 
       "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{"x", "[", "k", "]"}], ",", 
        RowBox[{"Coefficient", "[", 
         RowBox[{
          RowBox[{
           RowBox[{
            RowBox[{"X", "[", 
             RowBox[{"k", "-", "2"}], "]"}], "-", 
            RowBox[{
             RowBox[{"q", "[", 
              RowBox[{"k", "-", "1"}], "]"}], "*", 
             RowBox[{"X", "[", 
              RowBox[{"k", "-", "1"}], "]"}]}]}], "/.", "rule"}], ",", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"X", "[", "0", "]"}], ",", 
            RowBox[{"X", "[", "1", "]"}]}], "}"}]}], "]"}]}], "}"}]}]}], 
    "\[IndentingNewLine]", "]"}], "/;", 
   RowBox[{
    RowBox[{"IntegerQ", "[", "xx", "]"}], "&&", 
    RowBox[{"IntegerQ", "[", "y", "]"}]}]}]}]}], "Input"],

Cell[BoxData[
 RowBox[{"extendedgcd", "[", 
  RowBox[{"p", ",", "q"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"g", ",", 
    RowBox[{"{", 
     RowBox[{"s", ",", "t"}], "}"}]}], "}"}], "=", 
  RowBox[{"extendedgcd", "[", 
   RowBox[{
    RowBox[{"50", "!"}], ",", 
    SuperscriptBox["2", "100"]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"s", "*", 
   RowBox[{"50", "!"}]}], "+", 
  RowBox[{"t", "*", 
   SuperscriptBox["2", "100"]}]}]], "Input"],

Cell[BoxData[
 RowBox[{"extendedgcd", "[", 
  RowBox[{
   RowBox[{"Fibonacci", "[", "20", "]"}], ",", 
   RowBox[{"Fibonacci", "[", "19", "]"}]}], "]"}]], "Input"],

Cell[BoxData["gcdmatrix"], "Input"]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Fermat Test",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[
 SuperscriptBox["2", "p"]], "Input"],

Cell[BoxData["p"], "Input"],

Cell[BoxData[
 RowBox[{"Mod", "[", 
  RowBox[{
   SuperscriptBox["2", "p"], ",", "p"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"PowerMod", "[", 
  RowBox[{"2", ",", "p", ",", "p"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"Timing", "[", 
  RowBox[{"result1", "=", 
   RowBox[{"PowerMod", "[", 
    RowBox[{"2", ",", 
     RowBox[{"p", "-", "1"}], ",", "p"}], "]"}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"PrimeQ", "[", "p", "]"}]], "Input",
 CellChangeTimes->{{3.477216300140625*^9, 3.4772163033125*^9}}]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Fast Powers",
 FontFamily->"Arial"]], "Section"],

Cell[CellGroupData[{

Cell["Recursive Approach", "Subsection"],

Cell[BoxData[{
 RowBox[{"Clear", "[", "powermod", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"powermod", "[", 
   RowBox[{"a_", ",", "0", ",", "p_"}], "]"}], ":=", 
  "1"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"powermod", "[", 
   RowBox[{"a_", ",", "n_", ",", "p_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"Mod", "[", 
    RowBox[{
     SuperscriptBox[
      RowBox[{"powermod", "[", 
       RowBox[{"a", ",", 
        FractionBox["n", "2"], ",", "p"}], "]"}], "2"], ",", "p"}], "]"}], "/;", 
   RowBox[{"EvenQ", "[", "n", "]"}]}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"powermod", "[", 
   RowBox[{"a_", ",", "n_", ",", "p_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"Mod", "[", 
    RowBox[{
     RowBox[{"a", "*", 
      RowBox[{"powermod", "[", 
       RowBox[{"a", ",", 
        RowBox[{"n", "-", "1"}], ",", "p"}], "]"}]}], ",", "p"}], "]"}], "/;", 
   RowBox[{"OddQ", "[", "n", "]"}]}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"$RecursionLimit", "=", "\[Infinity]"}], ";"}]}], "Input"],

Cell[BoxData[
 RowBox[{"Timing", "[", 
  RowBox[{"result2", "=", 
   RowBox[{"powermod", "[", 
    RowBox[{"2", ",", 
     RowBox[{"p", "-", "1"}], ",", "p"}], "]"}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"result1", "-", "result2"}]], "Input"]
}, Open  ]],

Cell[CellGroupData[{

Cell["Iterative Approach", "Subsection"],

Cell[BoxData[
 RowBox[{"digits", "=", 
  RowBox[{"IntegerDigits", "[", 
   RowBox[{
    RowBox[{"p", "-", "1"}], ",", "2"}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"Length", "[", "digits", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"iterativepowermod", "[", 
   RowBox[{"a_", ",", "n_", ",", "p_"}], "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"digits", ",", "result", ",", "power", ",", "k"}], "}"}], ",", 
    "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"digits", "=", 
      RowBox[{"IntegerDigits", "[", 
       RowBox[{"n", ",", "2"}], "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"result", "=", "1"}], ";", 
     RowBox[{"power", "=", "a"}], ";", "\[IndentingNewLine]", 
     RowBox[{"Do", "[", 
      RowBox[{
       RowBox[{
        RowBox[{"If", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"digits", "[", 
            RowBox[{"[", 
             RowBox[{
              RowBox[{"Length", "[", "digits", "]"}], "-", "k", "+", "1"}], 
             "]"}], "]"}], "\[Equal]", "1"}], ",", 
          RowBox[{"result", "=", 
           RowBox[{"Mod", "[", 
            RowBox[{
             RowBox[{"result", "*", "power"}], ",", "p"}], "]"}]}]}], "]"}], 
        ";", 
        RowBox[{"power", "=", 
         RowBox[{"Mod", "[", 
          RowBox[{
           SuperscriptBox["power", "2"], ",", "p"}], "]"}]}]}], ",", 
       RowBox[{"{", 
        RowBox[{"k", ",", 
         RowBox[{"Length", "[", "digits", "]"}]}], "}"}]}], "]"}], ";", 
     "\[IndentingNewLine]", "result"}]}], "\[IndentingNewLine]", 
   "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"Timing", "[", 
  RowBox[{"result3", "=", 
   RowBox[{"iterativepowermod", "[", 
    RowBox[{"2", ",", 
     RowBox[{"p", "-", "1"}], ",", "p"}], "]"}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"result3", "-", "result1"}]], "Input"]
}, Open  ]]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Carmichael Numbers",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[{
 RowBox[{"Clear", "[", "NextCarmichael", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"NextCarmichael", "[", "n_", "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"ready", "=", "False"}], ",", 
      RowBox[{"p", "=", "n"}], ",", "a"}], "}"}], ",", "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"While", "[", 
      RowBox[{
       RowBox[{"Not", "[", "ready", "]"}], ",", "\[IndentingNewLine]", 
       RowBox[{"If", "[", 
        RowBox[{
         RowBox[{"Not", "[", 
          RowBox[{"PrimeQ", "[", "p", "]"}], "]"}], ",", 
         "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"list", "=", 
           RowBox[{"Table", "[", 
            RowBox[{
             RowBox[{
              RowBox[{"PowerMod", "[", 
               RowBox[{"a", ",", "p", ",", "p"}], "]"}], "-", "a"}], ",", 
             RowBox[{"{", 
              RowBox[{"a", ",", 
               RowBox[{"p", "-", "1"}]}], "}"}]}], "]"}]}], ";", 
          "\[IndentingNewLine]", 
          RowBox[{"list", "=", 
           RowBox[{"Union", "[", "list", "]"}]}], ";", "\[IndentingNewLine]", 
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{"list", "\[Equal]", 
             RowBox[{"{", "0", "}"}]}], ",", 
            RowBox[{"ready", "=", "True"}], ",", 
            RowBox[{"p", "=", 
             RowBox[{"p", "+", "1"}]}]}], "]"}]}], ",", 
         RowBox[{"p", "=", 
          RowBox[{"p", "+", "1"}]}]}], "]"}]}], "]"}], ";", 
     "\[IndentingNewLine]", "p"}]}], "]"}]}]}], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"NextCarmichael", "[", "4", "]"}]}], ")"}], "//", 
  "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "c", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"NextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "c", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"NextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "c", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"NextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "c", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"NextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{"FactorInteger", "[", "c", "]"}]], "Input"],

Cell[CellGroupData[{

Cell["Structure of Carmichael Numbers", "Subsection"],

Cell[BoxData[{
 RowBox[{"Clear", "[", "FastNextCarmichael", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"FastNextCarmichael", "[", "n_", "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"ready", "=", "False"}], ",", 
      RowBox[{"p", "=", "n"}]}], "}"}], ",", "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"While", "[", 
      RowBox[{
       RowBox[{"Not", "[", "ready", "]"}], ",", "\[IndentingNewLine]", 
       RowBox[{"If", "[", 
        RowBox[{
         RowBox[{"PrimeQ", "[", "p", "]"}], ",", 
         RowBox[{"p", "=", 
          RowBox[{"p", "+", "1"}]}], ",", "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"factors", "=", 
           RowBox[{"Transpose", "[", 
            RowBox[{"FactorInteger", "[", "p", "]"}], "]"}]}], ";", 
          "\[IndentingNewLine]", 
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"Not", "[", 
              RowBox[{
               RowBox[{"Union", "[", 
                RowBox[{"factors", "[", 
                 RowBox[{"[", "2", "]"}], "]"}], "]"}], "\[Equal]", 
               RowBox[{"{", "1", "}"}]}], "]"}], "||", "\[IndentingNewLine]", 
             RowBox[{"Not", "[", 
              RowBox[{"IntegerQ", "[", 
               RowBox[{
                RowBox[{"(", 
                 RowBox[{"p", "-", "1"}], ")"}], "/", 
                RowBox[{"Apply", "[", 
                 RowBox[{"LCM", ",", 
                  RowBox[{
                   RowBox[{"factors", "[", 
                    RowBox[{"[", "1", "]"}], "]"}], "-", "1"}]}], "]"}]}], 
               "]"}], "]"}]}], ",", 
            RowBox[{"p", "=", 
             RowBox[{"p", "+", "1"}]}], ",", 
            RowBox[{"ready", "=", "True"}]}], "]"}]}]}], "]"}]}], 
      "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", "p"}]}], 
   "\[IndentingNewLine]", "]"}]}]}], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"FastNextCarmichael", "[", "4", "]"}]}], ")"}], "//", 
  "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"FastNextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"FastNextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"c", "=", 
    RowBox[{"FastNextCarmichael", "[", 
     RowBox[{"c", "+", "1"}], "]"}]}], ")"}], "//", "Timing"}]], "Input"]
}, Open  ]]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Diffie-Hellman Key Exchange",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[
 RowBox[{"Plot", "[", 
  RowBox[{
   SuperscriptBox["2", "x"], ",", 
   RowBox[{"{", 
    RowBox[{"x", ",", "0", ",", "10"}], "}"}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"ListPlot", "[", 
  RowBox[{
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"x", ",", 
       SuperscriptBox["2", "x"]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"x", ",", "0", ",", "10"}], "}"}]}], "]"}], ",", 
   RowBox[{"PlotStyle", "\[Rule]", 
    RowBox[{"PointSize", "[", "0.01", "]"}]}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"NextPrime", "[", "1000", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"ListPlot", "[", 
  RowBox[{
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"x", ",", 
       RowBox[{"PowerMod", "[", 
        RowBox[{"2", ",", "x", ",", "1009"}], "]"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"x", ",", "0", ",", "1009"}], "}"}]}], "]"}], ",", 
   RowBox[{"PlotStyle", "\[Rule]", 
    RowBox[{"PointSize", "[", "0.01", "]"}]}]}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"NextPrime", "[", "10000", "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"ListPlot", "[", 
  RowBox[{
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"x", ",", 
       RowBox[{"PowerMod", "[", 
        RowBox[{"2", ",", "x", ",", "10007"}], "]"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"x", ",", "0", ",", "10007"}], "}"}]}], "]"}], ",", 
   RowBox[{"PlotStyle", "\[Rule]", 
    RowBox[{"PointSize", "[", "0.01", "]"}]}]}], "]"}]], "Input"]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Modular Inverse",
 FontFamily->"Arial"]], "Section"],

Cell[BoxData[
 RowBox[{"\[CurlyPhi]", "=", 
  RowBox[{"NextPrime", "[", 
   SuperscriptBox["10", "10"], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"e", "=", 
  RowBox[{"NextPrime", "[", 
   SuperscriptBox["10", "5"], "]"}]}]], "Input"],

Cell[CellGroupData[{

Cell["\<\
We search for the Inverse of e modulo \[CurlyPhi]\
\>", "Subsection"],

Cell[BoxData[
 RowBox[{"d", "=", 
  RowBox[{"PowerMod", "[", 
   RowBox[{"e", ",", 
    RowBox[{"-", "1"}], ",", "\[CurlyPhi]"}], "]"}]}]], "Input"]
}, Open  ]],

Cell[CellGroupData[{

Cell["Test:", "Subsection"],

Cell[BoxData[
 RowBox[{"Mod", "[", 
  RowBox[{
   RowBox[{"e", "*", "d"}], ",", "\[CurlyPhi]"}], "]"}]], "Input"]
}, Open  ]],

Cell[CellGroupData[{

Cell["The Extended Euclidiean Algorithm yields", "Subsection"],

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"g", ",", 
    RowBox[{"{", 
     RowBox[{"s", ",", "t"}], "}"}]}], "}"}], "=", 
  RowBox[{"extendedgcd", "[", 
   RowBox[{"e", ",", "\[CurlyPhi]"}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"d", "==", 
  RowBox[{"Mod", "[", 
   RowBox[{"s", ",", "\[CurlyPhi]"}], "]"}]}]], "Input"]
}, Open  ]]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["The RSA Crypto System",
 FontFamily->"Arial"]], "Section"],

Cell[CellGroupData[{

Cell["Loading auxiliary functions...", "Subsection",
 InitializationCell->True,
 CellChangeTimes->{3.47780854390625*^9}],

Cell[BoxData[{
 RowBox[{
  RowBox[{
   RowBox[{"Combine", "[", "liste_", "]"}], ":=", 
   RowBox[{
    RowBox[{"First", "[", "liste", "]"}], " ", "/;", " ", 
    RowBox[{
     RowBox[{"Length", "[", "liste", "]"}], "==", "1"}]}]}], "\n"}], "\n", 
 RowBox[{
  RowBox[{
   RowBox[{"Combine", "[", "liste_", "]"}], ":=", 
   RowBox[{
    RowBox[{"1000", "*", 
     RowBox[{"Combine", "[", 
      RowBox[{"Reverse", "[", 
       RowBox[{"Rest", "[", 
        RowBox[{"Reverse", "[", "liste", "]"}], "]"}], "]"}], "]"}]}], "+", 
    RowBox[{"Last", "[", "liste", "]"}]}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"Convert", "[", "string_", "]"}], ":=", "  ", 
   RowBox[{"Combine", "[", 
    RowBox[{"ToCharacterCode", "[", "string", "]"}], "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"makelist", "[", "zahl_", "]"}], ":=", 
   RowBox[{
    RowBox[{"{", "zahl", "}"}], " ", "/;", " ", 
    RowBox[{"zahl", "<", "1000"}]}]}], "\n"}], "\n", 
 RowBox[{
  RowBox[{
   RowBox[{"makelist", "[", "zahl_", "]"}], ":=", 
   RowBox[{"Append", "[", 
    RowBox[{
     RowBox[{"makelist", "[", 
      RowBox[{
       RowBox[{"(", 
        RowBox[{"zahl", "-", 
         RowBox[{"Mod", "[", 
          RowBox[{"zahl", ",", "1000"}], "]"}]}], ")"}], "/", "1000"}], "]"}],
      ",", 
     RowBox[{"Mod", "[", 
      RowBox[{"zahl", ",", "1000"}], "]"}]}], "\n", "\t\t", "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"ConvertBack", "[", "zahl_", "]"}], ":=", 
   RowBox[{"FromCharacterCode", "[", 
    RowBox[{"makelist", "[", "zahl", "]"}], "]"}]}], "\[IndentingNewLine]", 
  "\[IndentingNewLine]", 
  RowBox[{"(*", "\[IndentingNewLine]", 
   RowBox[{
    RowBox[{"NextPrime", "[", "n_", "]"}], ":=", 
    RowBox[{
     RowBox[{
      RowBox[{"n", "+", "1"}], "/;", 
      RowBox[{
       RowBox[{"PrimeQ", "[", 
        RowBox[{"n", "+", "1"}], "]"}], "\[IndentingNewLine]", 
       RowBox[{"NextPrime", "[", "n_", "]"}]}]}], ":=", 
     RowBox[{"NextPrime", "[", 
      RowBox[{"n", "+", "1"}], "]"}]}]}], "\[IndentingNewLine]", "*)"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"EncodeRSA", "[", "nachricht_", "]"}], ":=", 
   RowBox[{"PowerMod", "[", 
    RowBox[{
     RowBox[{"Convert", "[", "nachricht", "]"}], ",", "e", ",", "m"}], 
    "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"DecodeRSA", "[", "zahl_", "]"}], ":=", 
   RowBox[{"ConvertBack", "[", 
    RowBox[{"PowerMod", "[", 
     RowBox[{"zahl", ",", "d", ",", "m"}], "]"}], "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"InitializeRSA", ":=", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", "}"}], ",", "\[IndentingNewLine]", 
     RowBox[{
      RowBox[{"p", "=", 
       RowBox[{"NextPrime", "[", 
        RowBox[{"Random", "[", 
         RowBox[{"Integer", ",", 
          RowBox[{"{", 
           RowBox[{
            SuperscriptBox["10", "199"], ",", 
            SuperscriptBox["10", "200"]}], "}"}]}], "]"}], "]"}]}], ";", 
      "\[IndentingNewLine]", 
      RowBox[{"q", "=", 
       RowBox[{"NextPrime", "[", 
        RowBox[{"Random", "[", 
         RowBox[{"Integer", ",", 
          RowBox[{"{", 
           RowBox[{
            SuperscriptBox["10", "199"], ",", 
            SuperscriptBox["10", "200"]}], "}"}]}], "]"}], "]"}]}], ";", 
      "\[IndentingNewLine]", 
      RowBox[{"m", "=", 
       RowBox[{"p", "*", "q"}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"\[CurlyPhi]", "=", 
       RowBox[{
        RowBox[{"(", 
         RowBox[{"p", "-", "1"}], ")"}], "*", 
        RowBox[{"(", 
         RowBox[{"q", "-", "1"}], ")"}]}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"e", "=", "\[CurlyPhi]"}], ";", "\[IndentingNewLine]", 
      RowBox[{"While", "[", 
       RowBox[{
        RowBox[{"Not", "[", 
         RowBox[{
          RowBox[{"GCD", "[", 
           RowBox[{"\[CurlyPhi]", ",", "e"}], "]"}], "===", "1"}], "]"}], ",",
         "\[IndentingNewLine]", 
        RowBox[{"e", "=", 
         RowBox[{"NextPrime", "[", 
          RowBox[{"Random", "[", 
           RowBox[{"Integer", ",", 
            RowBox[{"{", 
             RowBox[{
              SuperscriptBox["10", "39"], ",", 
              SuperscriptBox["10", "40"]}], "}"}]}], "]"}], "]"}]}]}], "]"}], 
      ";", "\[IndentingNewLine]", 
      RowBox[{"d", "=", 
       RowBox[{"PowerMod", "[", 
        RowBox[{"e", ",", 
         RowBox[{"-", "1"}], ",", "\[CurlyPhi]"}], "]"}]}], ";"}]}], 
    "\[IndentingNewLine]", "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"Clear", "[", 
    RowBox[{
    "ErzeugeISBNPr\[UDoubleDot]fziffer", ",", 
     "CheckISBNPr\[UDoubleDot]fziffer"}], "]"}], ";"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"ErzeugeISBNPr\[UDoubleDot]fziffer", "[", "n_", "]"}], ":=", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", "liste", "}"}], ",", 
     RowBox[{
      RowBox[{"liste", "=", 
       RowBox[{"IntegerDigits", "[", 
        RowBox[{"n", ",", "10"}], "]"}]}], ";", 
      RowBox[{"While", "[", 
       RowBox[{
        RowBox[{
         RowBox[{"Length", "[", "liste", "]"}], "<", "9"}], ",", 
        RowBox[{"PrependTo", "[", 
         RowBox[{"liste", ",", "0"}], "]"}]}], "]"}], ";", "\n", "\t\t", 
      RowBox[{"Mod", "[", 
       RowBox[{
        RowBox[{"Sum", "[", 
         RowBox[{
          RowBox[{"k", "*", 
           RowBox[{"liste", "[", 
            RowBox[{"[", "k", "]"}], "]"}]}], ",", 
          RowBox[{"{", 
           RowBox[{"k", ",", "9"}], "}"}]}], "]"}], ",", "11"}], "]"}]}]}], 
    "]"}]}], "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"CheckISBNPr\[UDoubleDot]fziffer", "[", "n_", "]"}], ":=", 
   RowBox[{
    RowBox[{"Module", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"zahl", ",", "rest"}], "}"}], ",", "\n", "\t\t", 
      RowBox[{
       RowBox[{"zahl", "=", 
        RowBox[{"Mod", "[", 
         RowBox[{"n", ",", "10"}], "]"}]}], ";", 
       RowBox[{"rest", "=", 
        RowBox[{
         RowBox[{"(", 
          RowBox[{"n", "-", "zahl"}], ")"}], "/", "10"}]}], ";", 
       RowBox[{"If", "[", 
        RowBox[{
         RowBox[{"SameQ", "[", 
          RowBox[{
           RowBox[{"ErzeugeISBNPr\[UDoubleDot]fziffer", "[", "rest", "]"}], 
           ",", "zahl"}], "]"}], ",", "\"\<Die ISBN ist o.k.\>\"", ",", 
         "\"\<Die ISBN ist nicht o.k.\>\""}], "]"}]}]}], "]"}], "/;", 
    RowBox[{"NumberQ", "[", "n", "]"}]}]}], "\n", "\t"}], "\n", 
 RowBox[{
  RowBox[{
   RowBox[{"CheckISBNPr\[UDoubleDot]fziffer", "[", 
    RowBox[{"n_", "*", "X"}], "]"}], ":=", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"zahl", ",", "rest"}], "}"}], ",", "\n", "\t\t", 
     RowBox[{
      RowBox[{"zahl", "=", "10"}], ";", 
      RowBox[{"rest", "=", "n"}], ";", 
      RowBox[{"If", "[", 
       RowBox[{
        RowBox[{"SameQ", "[", 
         RowBox[{
          RowBox[{"ErzeugeISBNPr\[UDoubleDot]fziffer", "[", "rest", "]"}], 
          ",", "zahl"}], "]"}], ",", "\"\<Die ISBN ist o.k.\>\"", ",", 
        "\"\<Die ISBN ist nicht o.k.\>\""}], "]"}]}]}], "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Clear", "[", 
   RowBox[{
   "Digitalisiere", ",", "Verbalisiere", ",", "ReedSolomon", ",", 
    "InverseReedSolomon"}], "]"}], "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"Digitalisiere", "[", "wort_", "]"}], ":=", 
   RowBox[{
    RowBox[{"ToCharacterCode", "[", "wort", "]"}], "-", "64"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"Verbalisiere", "[", "liste_", "]"}], ":=", 
   RowBox[{"FromCharacterCode", "[", 
    RowBox[{"liste", "+", "64"}], "]"}]}], "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Clear", "[", "ReedSolomon", "]"}], ";"}], "\n", 
 RowBox[{
  RowBox[{
   RowBox[{"ReedSolomon", "[", 
    RowBox[{"wort_", ",", "p_"}], "]"}], ":=", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
      "liste", ",", "n", ",", "a0", ",", "a1", ",", "a2", ",", "a3", ",", "k",
        ",", "sol"}], "}"}], ",", "\[IndentingNewLine]", 
     RowBox[{
      RowBox[{"liste", "=", 
       RowBox[{"Digitalisiere", "[", "wort", "]"}]}], ";", 
      "\[IndentingNewLine]", 
      RowBox[{"n", "=", 
       RowBox[{"Length", "[", "liste", "]"}]}], ";", 
      RowBox[{"sol", "=", 
       RowBox[{"Solve", "[", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{
           RowBox[{
            RowBox[{"a0", "+", "a1", "+", "a2", "+", "a3", "+", 
             RowBox[{"Apply", "[", 
              RowBox[{"Plus", ",", "liste"}], "]"}]}], "==", "0"}], ",", 
           "\[IndentingNewLine]", 
           RowBox[{
            RowBox[{"a1", "+", 
             RowBox[{"2", "a2"}], "+", 
             RowBox[{"3", "a3"}], "+", 
             RowBox[{"Sum", "[", 
              RowBox[{
               RowBox[{
                RowBox[{"(", 
                 RowBox[{"k", "+", "3"}], ")"}], "*", 
                RowBox[{"liste", "[", 
                 RowBox[{"[", "k", "]"}], "]"}]}], ",", 
               RowBox[{"{", 
                RowBox[{"k", ",", "n"}], "}"}]}], "]"}]}], "==", "0"}], ",", 
           "\[IndentingNewLine]", 
           RowBox[{
            RowBox[{"a1", "+", 
             RowBox[{"4", "a2"}], "+", 
             RowBox[{"9", "a3"}], "+", 
             RowBox[{"Sum", "[", 
              RowBox[{
               RowBox[{
                RowBox[{
                 RowBox[{"(", 
                  RowBox[{"k", "+", "3"}], ")"}], "^", "2"}], "*", 
                RowBox[{"liste", "[", 
                 RowBox[{"[", "k", "]"}], "]"}]}], ",", 
               RowBox[{"{", 
                RowBox[{"k", ",", "n"}], "}"}]}], "]"}]}], "==", "0"}], ",", 
           "\[IndentingNewLine]", 
           RowBox[{
            RowBox[{"a1", "+", 
             RowBox[{"8", "a2"}], "+", 
             RowBox[{"27", "a3"}], "+", 
             RowBox[{"Sum", "[", 
              RowBox[{
               RowBox[{
                RowBox[{
                 RowBox[{"(", 
                  RowBox[{"k", "+", "3"}], ")"}], "^", "3"}], "*", 
                RowBox[{"liste", "[", 
                 RowBox[{"[", "k", "]"}], "]"}]}], ",", 
               RowBox[{"{", 
                RowBox[{"k", ",", "n"}], "}"}]}], "]"}]}], "==", "0"}], ",", 
           "\[IndentingNewLine]", 
           RowBox[{"Modulus", "\[Equal]", "p"}]}], "}"}], ",", 
         RowBox[{"{", 
          RowBox[{"a0", ",", "a1", ",", "a2", ",", "a3"}], "}"}]}], "]"}]}], 
      ";", "\[IndentingNewLine]", 
      RowBox[{"liste", "=", 
       RowBox[{
        RowBox[{"Flatten", "[", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"a0", ",", "a1", ",", "a2", ",", "a3"}], "}"}], ",", 
           "liste"}], "}"}], "]"}], "/.", 
        RowBox[{"sol", "[", 
         RowBox[{"[", "1", "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"Verbalisiere", "[", "liste", "]"}]}]}], "\n", "\t", "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{"Clear", "[", "InverseReedSolomon", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"InverseReedSolomon", "[", 
   RowBox[{"wort_", ",", "p_"}], "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
     "liste", ",", "n", ",", "e", ",", "s", ",", "x", ",", "k", ",", "i", ",",
       "j", ",", "ii", ",", "jj", ",", "aalpha", ",", "bbeta", ",", "alpha", 
      ",", "beta"}], "}"}], ",", "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"liste", "=", 
      RowBox[{"Digitalisiere", "[", "wort", "]"}]}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"n", "=", 
      RowBox[{"Length", "[", "liste", "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"s", "=", 
      RowBox[{"Mod", "[", 
       RowBox[{
        RowBox[{"Apply", "[", 
         RowBox[{"Plus", ",", "liste"}], "]"}], ",", "p"}], "]"}]}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"t", "=", 
      RowBox[{"Mod", "[", 
       RowBox[{
        RowBox[{"Sum", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"(", 
            RowBox[{"k", "-", "1"}], ")"}], "*", 
           RowBox[{"liste", "[", 
            RowBox[{"[", "k", "]"}], "]"}]}], ",", 
          RowBox[{"{", 
           RowBox[{"k", ",", "1", ",", "n"}], "}"}]}], "]"}], ",", "p"}], 
       "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"u", "=", 
      RowBox[{"Mod", "[", 
       RowBox[{
        RowBox[{"Sum", "[", 
         RowBox[{
          RowBox[{
           RowBox[{
            RowBox[{"(", 
             RowBox[{"k", "-", "1"}], ")"}], "^", "2"}], "*", 
           RowBox[{"liste", "[", 
            RowBox[{"[", "k", "]"}], "]"}]}], ",", 
          RowBox[{"{", 
           RowBox[{"k", ",", "1", ",", "n"}], "}"}]}], "]"}], ",", "p"}], 
       "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"v", "=", 
      RowBox[{"Mod", "[", 
       RowBox[{
        RowBox[{"Sum", "[", 
         RowBox[{
          RowBox[{
           RowBox[{
            RowBox[{"(", 
             RowBox[{"k", "-", "1"}], ")"}], "^", "3"}], "*", 
           RowBox[{"liste", "[", 
            RowBox[{"[", "k", "]"}], "]"}]}], ",", 
          RowBox[{"{", 
           RowBox[{"k", ",", "1", ",", "n"}], "}"}]}], "]"}], ",", "p"}], 
       "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{
        RowBox[{"Union", "[", 
         RowBox[{"{", 
          RowBox[{"s", ",", "t", ",", "u", ",", "v"}], "}"}], "]"}], 
        "\[Equal]", " ", 
        RowBox[{"{", "0", "}"}]}], ",", "\[IndentingNewLine]", 
       RowBox[{"Return", "[", 
        RowBox[{"StringTake", "[", 
         RowBox[{"wort", ",", 
          RowBox[{"{", 
           RowBox[{"5", ",", 
            RowBox[{"-", "1"}]}], "}"}]}], "]"}], "]"}], ",", 
       "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"sol", "=", 
         RowBox[{"Solve", "[", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{
             RowBox[{"s", "\[Equal]", " ", 
              RowBox[{"alpha", "+", "beta"}]}], ",", 
             RowBox[{"t", "\[Equal]", 
              RowBox[{
               RowBox[{"i", " ", "alpha"}], "+", 
               RowBox[{"j", " ", "beta"}]}]}], ",", 
             RowBox[{"u", "\[Equal]", " ", 
              RowBox[{
               RowBox[{
                RowBox[{"i", "^", "2"}], " ", "alpha"}], "+", 
               RowBox[{
                RowBox[{"j", "^", "2"}], " ", "beta"}]}]}], ",", 
             RowBox[{"v", "\[Equal]", " ", 
              RowBox[{
               RowBox[{
                RowBox[{"i", "^", "3"}], " ", "alpha"}], "+", 
               RowBox[{
                RowBox[{"j", "^", "3"}], " ", "beta"}]}]}], ",", 
             RowBox[{"Modulus", "\[Equal]", "p"}]}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{"alpha", ",", "beta", ",", "i", ",", "j"}], "}"}]}], 
          "]"}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"ii", "=", 
         RowBox[{"i", "/.", 
          RowBox[{"sol", "[", 
           RowBox[{"[", 
            RowBox[{"-", "1"}], "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"jj", "=", 
         RowBox[{"j", "/.", 
          RowBox[{"sol", "[", 
           RowBox[{"[", 
            RowBox[{"-", "1"}], "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"aalpha", "=", 
         RowBox[{"alpha", "/.", 
          RowBox[{"sol", "[", 
           RowBox[{"[", 
            RowBox[{"-", "1"}], "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"bbeta", "=", 
         RowBox[{"beta", "/.", 
          RowBox[{"sol", "[", 
           RowBox[{"[", 
            RowBox[{"-", "1"}], "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"If", "[", 
         RowBox[{
          RowBox[{"IntegerQ", "[", "ii", "]"}], ",", 
          RowBox[{
           RowBox[{"liste", "[", 
            RowBox[{"[", 
             RowBox[{"ii", "+", "1"}], "]"}], "]"}], "=", 
           RowBox[{"Mod", "[", 
            RowBox[{
             RowBox[{
              RowBox[{"liste", "[", 
               RowBox[{"[", 
                RowBox[{"ii", "+", "1"}], "]"}], "]"}], "-", "aalpha"}], ",", 
             "p"}], "]"}]}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{"If", "[", 
         RowBox[{
          RowBox[{"IntegerQ", "[", "jj", "]"}], ",", 
          RowBox[{
           RowBox[{"liste", "[", 
            RowBox[{"[", 
             RowBox[{"jj", "+", "1"}], "]"}], "]"}], "=", 
           RowBox[{"Mod", "[", 
            RowBox[{
             RowBox[{
              RowBox[{"liste", "[", 
               RowBox[{"[", 
                RowBox[{"jj", "+", "1"}], "]"}], "]"}], "-", "bbeta"}], ",", 
             "p"}], "]"}]}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{"liste", "=", 
         RowBox[{"Nest", "[", 
          RowBox[{"Rest", ",", "liste", ",", "4"}], "]"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"Verbalisiere", "[", "liste", "]"}]}]}], 
      "\[IndentingNewLine]", "]"}]}]}], "\[IndentingNewLine]", 
   "]"}]}]}], "Input",
 InitializationCell->True,
 CellChangeTimes->{{3.41114455134375*^9, 3.411144562390625*^9}, {
  3.47780855346875*^9, 3.477808567390625*^9}, {3.477808668*^9, 
  3.477808676390625*^9}}]
}, Closed]],

Cell[CellGroupData[{

Cell["Generation of keys...", "Subsection",
 CellChangeTimes->{{3.477808882015625*^9, 3.477808887359375*^9}}],

Cell[BoxData["InitializeRSA"], "Input",
 CellChangeTimes->{{3.4778088908125*^9, 3.47780889203125*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["public key", "Subsection",
 CellChangeTimes->{{3.47780889709375*^9, 3.477808898734375*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"e", ",", "m"}], "}"}]], "Input"]
}, Open  ]],

Cell[CellGroupData[{

Cell["private key", "Subsection",
 CellChangeTimes->{{3.477808903875*^9, 3.477808904375*^9}}],

Cell[BoxData["d"], "Input"]
}, Open  ]],

Cell[CellGroupData[{

Cell["encoding with RSA", "Subsection",
 CellChangeTimes->{{3.477808916921875*^9, 3.47780891946875*^9}}],

Cell[BoxData[
 RowBox[{"message", "=", "\"\<This is my message\>\""}]], "Input",
 CellChangeTimes->{{3.477808925578125*^9, 3.477808932765625*^9}}],

Cell[BoxData[
 RowBox[{"result", "=", 
  RowBox[{"EncodeRSA", "[", "message", "]"}]}]], "Input",
 CellChangeTimes->{{3.47780893665625*^9, 3.47780894528125*^9}}],

Cell[BoxData[
 RowBox[{"DecodeRSA", "[", "result", "]"}]], "Input",
 CellChangeTimes->{{3.47780894884375*^9, 3.4778089521875*^9}}],

Cell[BoxData[
 RowBox[{"DecodeRSA", "[", 
  RowBox[{"result", "+", "1"}], "]"}]], "Input",
 CellChangeTimes->{{3.477808958515625*^9, 3.477808960546875*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["another message", "Subsection",
 CellChangeTimes->{{3.47780896675*^9, 3.47780896925*^9}}],

Cell[BoxData[
 RowBox[{"result", "=", 
  RowBox[{
  "EncodeRSA", "[", "\"\<What about this message?\>\"", "]"}]}]], "Input",
 CellChangeTimes->{{3.477808973265625*^9, 3.477808985359375*^9}}],

Cell[BoxData[
 RowBox[{"DecodeRSA", "[", "result", "]"}]], "Input",
 CellChangeTimes->{{3.477808994015625*^9, 3.477809000859375*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["Finally a really message:", "Subsection",
 CellChangeTimes->{{3.4778090045625*^9, 3.47780901065625*^9}}],

Cell[BoxData[
 RowBox[{"<<", 
  "\"\<C:\\\\Dokumente und Einstellungen\\\\koepf\\\\Eigene \
Dateien\\\\Koepf\\\\Vortr\[ADoubleDot]ge\\\\Kamerun2010\\\\message\>\""}]], \
"Input",
 CellChangeTimes->{{3.411144634984375*^9, 3.411144638171875*^9}, {
  3.4765282107599945`*^9, 3.4765282252913375`*^9}, {3.47780903309375*^9, 
  3.47780904471875*^9}}],

Cell[BoxData[
 RowBox[{"result", "=", 
  RowBox[{"EncodeRSA", "[", "message", "]"}]}]], "Input",
 CellChangeTimes->{{3.47780904821875*^9, 3.4778090600625*^9}}],

Cell[BoxData[
 RowBox[{"DecodeRSA", "[", "result", "]"}]], "Input",
 CellChangeTimes->{{3.47780904990625*^9, 3.477809064359375*^9}}]
}, Open  ]]
}, Closed]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["A two-correcting Reed-Solomon Code",
 FontFamily->"Arial"]], "Section",
 CellChangeTimes->{{3.477806491109375*^9, 3.4778065034375*^9}}],

Cell[CellGroupData[{

Cell["\<\
These functions generate the necessary redundancy and are able to correct up \
to two errors.\
\>", "Subsection",
 CellChangeTimes->{{3.477806621359375*^9, 3.47780665875*^9}, {
  3.477806716703125*^9, 3.47780671690625*^9}}],

Cell[BoxData[
 RowBox[{"code", "=", 
  RowBox[{"ReedSolomon", "[", 
   RowBox[{"\"\<MATHEMATICS\>\"", ",", "31"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.477806850734375*^9, 3.4778068519375*^9}}],

Cell[BoxData[
 RowBox[{"InverseReedSolomon", "[", 
  RowBox[{"code", ",", "31"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"code1", "=", 
  RowBox[{"StringReplace", "[", 
   RowBox[{"code", ",", 
    RowBox[{"\"\<H\>\"", "->", "\"\<J\>\""}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"InverseReedSolomon", "[", 
  RowBox[{"code1", ",", "31"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"code2", "=", 
  RowBox[{"StringReplace", "[", 
   RowBox[{"code1", ",", 
    RowBox[{"\"\<D\>\"", "->", "\"\<Z\>\""}]}], "]"}]}]], "Input",
 CellChangeTimes->{3.477806875859375*^9}],

Cell[BoxData[
 RowBox[{"InverseReedSolomon", "[", 
  RowBox[{"code2", ",", "31"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"code3", "=", 
  RowBox[{"StringReplace", "[", 
   RowBox[{"code2", ",", 
    RowBox[{"\"\<E\>\"", "->", "\"\<F\>\""}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"InverseReedSolomon", "[", 
  RowBox[{"code3", ",", "31"}], "]"}]], "Input"]
}, Open  ]]
}, Closed]]
},
AutoGeneratedPackage->Automatic,
WindowSize->{1015, 666},
WindowMargins->{{0, Automatic}, {Automatic, 0}},
PrintingCopies->1,
PrintingPageRange->{Automatic, Automatic},
ShowSelection->True,
Magnification->2,
FrontEndVersion->"7.0 for Microsoft Windows (32-bit) (February 18, 2009)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[567, 22, 47, 0, 140, "Section"],
Cell[617, 24, 45, 1, 57, "Input"],
Cell[665, 27, 92, 3, 89, "Input"],
Cell[760, 32, 126, 4, 64, "Input"],
Cell[889, 38, 85, 2, 57, "Input"],
Cell[977, 42, 75, 2, 60, "Input"],
Cell[1055, 46, 116, 3, 64, "Input"],
Cell[1174, 51, 195, 6, 64, "Input"],
Cell[1372, 59, 66, 1, 57, "Input"],
Cell[1441, 62, 59, 1, 57, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[1537, 68, 80, 1, 76, "Section"],
Cell[1620, 71, 999, 30, 3104, "Input"],
Cell[2622, 103, 126, 4, 1024, "Input"],
Cell[2751, 109, 126, 4, 1024, "Input"],
Cell[2880, 115, 195, 6, 1024, "Input"],
Cell[3078, 123, 113, 3, 912, "Input"],
Cell[3194, 128, 113, 3, 912, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[3344, 136, 89, 1, 76, "Section"],
Cell[3436, 139, 3835, 101, 9632, "Input"],
Cell[7274, 242, 87, 2, 912, "Input"],
Cell[7364, 246, 258, 9, 1024, "Input"],
Cell[7625, 257, 142, 5, 960, "Input"],
Cell[7770, 264, 163, 4, 912, "Input"],
Cell[7936, 270, 35, 0, 912, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[8008, 275, 72, 1, 76, "Section"],
Cell[8083, 278, 50, 1, 912, "Input"],
Cell[8136, 281, 27, 0, 912, "Input"],
Cell[8166, 283, 104, 3, 912, "Input"],
Cell[8273, 288, 94, 2, 912, "Input"],
Cell[8370, 292, 185, 5, 912, "Input"],
Cell[8558, 299, 123, 2, 912, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[8718, 306, 72, 1, 76, "Section"],
Cell[CellGroupData[{
Cell[8815, 311, 40, 0, 1168, "Subsection"],
Cell[8858, 313, 1018, 29, 4752, "Input"],
Cell[9879, 344, 185, 5, 912, "Input"],
Cell[10067, 351, 61, 1, 912, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[10165, 357, 40, 0, 1168, "Subsection"],
Cell[10208, 359, 143, 4, 912, "Input"],
Cell[10354, 365, 64, 1, 912, "Input"],
Cell[10421, 368, 1400, 39, 5728, "Input"],
Cell[11824, 409, 194, 5, 912, "Input"],
Cell[12021, 416, 61, 1, 912, "Input"]
}, Open  ]]
}, Closed]],
Cell[CellGroupData[{
Cell[12131, 423, 79, 1, 76, "Section"],
Cell[12213, 426, 1570, 41, 2368, "Input"],
Cell[13786, 469, 148, 5, 456, "Input"],
Cell[13937, 476, 66, 1, 456, "Input"],
Cell[14006, 479, 171, 5, 456, "Input"],
Cell[14180, 486, 66, 1, 456, "Input"],
Cell[14249, 489, 171, 5, 456, "Input"],
Cell[14423, 496, 66, 1, 456, "Input"],
Cell[14492, 499, 171, 5, 456, "Input"],
Cell[14666, 506, 66, 1, 456, "Input"],
Cell[14735, 509, 171, 5, 456, "Input"],
Cell[14909, 516, 66, 1, 456, "Input"],
Cell[CellGroupData[{
Cell[15000, 521, 53, 0, 584, "Subsection"],
Cell[15056, 523, 1914, 48, 3184, "Input"],
Cell[16973, 573, 152, 5, 456, "Input"],
Cell[17128, 580, 175, 5, 456, "Input"],
Cell[17306, 587, 175, 5, 456, "Input"],
Cell[17484, 594, 175, 5, 456, "Input"]
}, Open  ]]
}, Closed]],
Cell[CellGroupData[{
Cell[17708, 605, 88, 1, 76, "Section"],
Cell[17799, 608, 165, 5, 912, "Input"],
Cell[17967, 615, 367, 11, 1472, "Input"],
Cell[18337, 628, 65, 1, 912, "Input"],
Cell[18405, 631, 422, 12, 1472, "Input"],
Cell[18830, 645, 66, 1, 912, "Input"],
Cell[18899, 648, 424, 12, 1472, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[19360, 665, 76, 1, 76, "Section"],
Cell[19439, 668, 122, 3, 1024, "Input"],
Cell[19564, 673, 111, 3, 1024, "Input"],
Cell[CellGroupData[{
Cell[19700, 680, 79, 2, 1168, "Subsection"],
Cell[19782, 684, 148, 4, 912, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[19967, 693, 27, 0, 1168, "Subsection"],
Cell[19997, 695, 113, 3, 1312, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[20147, 703, 62, 0, 1168, "Subsection"],
Cell[20212, 705, 219, 7, 1312, "Input"],
Cell[20434, 714, 114, 3, 1312, "Input"]
}, Open  ]]
}, Closed]],
Cell[CellGroupData[{
Cell[20597, 723, 82, 1, 76, "Section"],
Cell[CellGroupData[{
Cell[20704, 728, 120, 2, 73, "Subsection",
 InitializationCell->True],
Cell[20827, 732, 17475, 479, 3528, "Input",
 InitializationCell->True]
}, Closed]],
Cell[CellGroupData[{
Cell[38339, 1216, 109, 1, 53, "Subsection"],
Cell[38451, 1219, 102, 1, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[38590, 1225, 97, 1, 73, "Subsection"],
Cell[38690, 1228, 72, 2, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[38799, 1235, 93, 1, 73, "Subsection"],
Cell[38895, 1238, 27, 0, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[38959, 1243, 104, 1, 73, "Subsection"],
Cell[39066, 1246, 146, 2, 57, "Input"],
Cell[39215, 1250, 160, 3, 57, "Input"],
Cell[39378, 1255, 130, 2, 57, "Input"],
Cell[39511, 1259, 156, 3, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[39704, 1267, 95, 1, 73, "Subsection"],
Cell[39802, 1270, 190, 4, 57, "Input"],
Cell[39995, 1276, 133, 2, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[40165, 1283, 110, 1, 73, "Subsection"],
Cell[40278, 1286, 344, 7, 126, "Input"],
Cell[40625, 1295, 159, 3, 57, "Input"],
Cell[40787, 1300, 132, 2, 57, "Input"]
}, Open  ]]
}, Closed]],
Cell[CellGroupData[{
Cell[40968, 1308, 159, 2, 76, "Section"],
Cell[CellGroupData[{
Cell[41152, 1314, 233, 5, 108, "Subsection"],
Cell[41388, 1321, 197, 4, 57, "Input"],
Cell[41588, 1327, 98, 2, 57, "Input"],
Cell[41689, 1331, 162, 4, 57, "Input"],
Cell[41854, 1337, 99, 2, 57, "Input"],
Cell[41956, 1341, 205, 5, 57, "Input"],
Cell[42164, 1348, 99, 2, 57, "Input"],
Cell[42266, 1352, 163, 4, 57, "Input"],
Cell[42432, 1358, 99, 2, 57, "Input"]
}, Open  ]]
}, Closed]]
}
]
*)

(* End of internal cache information *)