(************** Content-type: application/mathematica **************
CreatedBy='Mathematica 5.2'
Mathematica-Compatible Notebook
This notebook can be used with any Mathematica-compatible
application, such as Mathematica, MathReader or Publicon. The data
for the notebook starts with the line containing stars above.
To get the notebook into a Mathematica-compatible application, do
one of the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the
application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing
the word CacheID, otherwise Mathematica-compatible applications may
try to use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
*******************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 267778, 7728]*)
(*NotebookOutlinePosition[ 268455, 7751]*)
(* CellTagsIndexPosition[ 268411, 7747]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell[TextData[StyleBox["Nevezetes pr\[IAcute]mtesztel\[ODoubleAcute] \
algoritmusok ",
FontFamily->"Times New Roman"]], "Title"],
Cell[TextData[StyleBox["Szerz\[ODoubleAcute]: N\[EAcute]medy Varga Andr\
\[AAcute]s (CC2A7Q) \n m\[AAcute]sod\[EAcute]ves matematikus \
hallgat\[OAcute]",
FontSize->24]], "Text"],
Cell[BoxData[
\(\(\(\[IndentingNewLine]\)\(<<
NumberTheory`NumberTheoryFunctions`\)\)\)], "Input",
InitializationCell->True],
Cell[CellGroupData[{
Cell[TextData[StyleBox["\nBevezet\[EAcute]s:",
FontFamily->"Times New Roman",
FontSize->18]], "Subsubtitle"],
Cell["\<\
A matematika egyik leg\[ODoubleAcute]sibb \[AAcute]ga a sz\[AAcute]melm\
\[EAcute]let. Ez a tudom\[AAcute]ny \[EAcute]vsz\[AAcute]zadok \[OAcute]ta \
szolg\[AAcute]ltat sz\[EAcute]p eredm\[EAcute]nyeket, \[EAcute]s \
neh\[EAcute]z probl\[EAcute]m\[AAcute]kat, sejt\[EAcute]seket a matematikusok \
sz\[AAcute]m\[AAcute]ra. Fontos gyakorlati alkalmaz\[AAcute]sai is \
ismeretesek, f\[ODoubleAcute]leg a kriptogr\[AAcute]fia ter\[UDoubleDot]let\
\[EAcute]n. Kiemelked\[ODoubleAcute] szerepe van benne a pr\[IAcute]msz\
\[AAcute]moknak, ezekkel fogunk foglalkozni ebben a notebookban.\
\>", "Text",
FontSize->14],
Cell[TextData[StyleBox["A tov\[AAcute]bbiakban k\[ODoubleDot]z\[ODoubleDot]lj\
\[UDoubleDot]k a meg\[EAcute]rt\[EAcute]s\[EAcute]hez sz\[UDoubleDot]ks\
\[EAcute]ges elm\[EAcute]leti anyagot, majd n\[EAcute]gy pr\[IAcute]mtesztel\
\[EAcute]si elj\[AAcute]r\[AAcute]st.",
FontSize->14]], "Text"],
Cell[CellGroupData[{
Cell[TextData[{
StyleBox["1. Pr\[IAcute]msz\[AAcute]mok",
FontSize->18],
StyleBox[":",
FontSize->18,
FontWeight->"Plain"]
}], "Section",
FontFamily->"Times New Roman"],
Cell["\<\
El\[ODoubleAcute]sz\[ODoubleDot]r az eg\[EAcute]sz sz\[AAcute]mok gy\
\[UDoubleAcute]r\[UDoubleAcute]j\[EAcute]ben defini\[AAcute]lunk k\[EAcute]t \
fontos tulajdons\[AAcute]got:\
\>", "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Legyen ",
Cell[BoxData[
\(TraditionalForm\`p \[Element] \[DoubleStruckCapitalZ]\\{\(-1\), 0,
1}\)]],
". A ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" sz\[AAcute]m felbonthatatlan (irreducibilis), ha ",
Cell[BoxData[
\(TraditionalForm\`p = \ a\ b\)]],
"-b\[ODoubleAcute]l k\[ODoubleDot]vetkezik, hogy ",
Cell[BoxData[
\(TraditionalForm\`a = {1, \(-1\)}\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`b = {1, \(-1\)}\)]],
" valamelyik\[EAcute]vel."
}], "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Legyen ",
Cell[BoxData[
\(TraditionalForm\`p \[Element] \[DoubleStruckCapitalZ]\\{\(-1\), 0,
1}\)]],
". A ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" sz\[AAcute]m pr\[IAcute]m, ha ",
Cell[BoxData[
\(TraditionalForm\`p | a\ b\)]],
"-b\[ODoubleAcute]l k\[ODoubleDot]vetkezik, hogy ",
Cell[BoxData[
\(TraditionalForm\`p | a\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`p | b\)]],
". \n- ",
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"],
": ez t\[ODoubleDot]bbt\[EAcute]nyez\[ODoubleAcute]s szorzatra is igaz."
}], "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["\[CapitalAAcute]ll\[IAcute]t\[AAcute]s",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`\[DoubleStruckCapitalZ]\)]],
"-ben ha ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" felbonthatatlan \[DoubleLeftRightArrow] ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" pr\[IAcute]m."
}], "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"],
": \n El\[ODoubleAcute]sz\[ODoubleDot]r \[DoubleRightArrow] \
ir\[AAcute]nyt:\n ",
Cell[BoxData[
\(TraditionalForm\`p | a\ b\)]],
", de tegy\[UDoubleDot]k fel, hogy ",
Cell[BoxData[
\(TraditionalForm\`p \[NotVerticalBar] a\)]],
". Be kell l\[AAcute]tni, hogy ekkor ",
Cell[BoxData[
\(TraditionalForm\`p | b\)]],
" teljes\[UDoubleDot]l.\n ",
Cell[BoxData[
\(TraditionalForm\`\((p, a)\) | p\)]],
", vagyis ",
Cell[BoxData[
\(TraditionalForm\`\((p, a)\)\ = 1\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
", de ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" nem lehet, mert ",
Cell[BoxData[
\(TraditionalForm\`p\ \[NotVerticalBar] \ a\)]],
", vagyis ",
Cell[BoxData[
\(TraditionalForm\`\((p, a)\) = 1\)]],
". De ",
Cell[BoxData[
\(TraditionalForm\`p | a\ b\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`\((p, a)\) = 1\)]],
"-b\[ODoubleAcute]l k\[ODoubleDot]vetkezik, hogy ",
Cell[BoxData[
\(TraditionalForm\`p | b\)]],
", \[EAcute]s \[IAcute]gy ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" pr\[IAcute]m.\n Most \[DoubleLeftArrow] ir\[AAcute]nyban:\n \
",
Cell[BoxData[
\(TraditionalForm\`p = a\ b\)]],
", akkor persze ",
Cell[BoxData[
\(TraditionalForm\`p | a\ b\)]],
". Mivel ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" pr\[IAcute]m a feltev\[EAcute]s szerint, ez\[EAcute]rt ",
Cell[BoxData[
\(TraditionalForm\`p | a\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`p | b\)]],
" \[EAcute]s \[IAcute]gy ",
Cell[BoxData[
\(TraditionalForm\`a\ b | a\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`a\ b | b\)]],
", ami viszont csak \[UAcute]gy lehet, ha ",
Cell[BoxData[
\(TraditionalForm\`b = {1, \(-1\)}\)]],
" vagy ",
Cell[BoxData[
\(TraditionalForm\`a = {1, \(-1\)}\)]],
" valamelyik\[EAcute]vel. Ez azt jelenti, hogy ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" irreducibilis."
}], "Text",
FontSize->14],
Cell["\<\
A pr\[IAcute]msz\[AAcute]moknak rengeteg alkalmaz\[AAcute]sa van a matematik\
\[AAcute]ban, f\[ODoubleAcute]leg a sz\[AAcute]melm\[EAcute]letben \
j\[AAcute]tszanak fontos szerepet.\
\>", "Text",
FontSize->14],
Cell[TextData[{
"Ezt mutatja p\[EAcute]ld\[AAcute]ul a sz\[AAcute]melm\[EAcute]let alapt\
\[EAcute]tele is, melyet most bizony\[IAcute]t\[AAcute]s n\[EAcute]lk\
\[UDoubleDot]l mondunk ki:\n ",
Cell[BoxData[
\(TraditionalForm\`\[ForAll] \
a \[Element] \[DoubleStruckCapitalZ]\ \\{\(-1\), 0, 1}\)]],
", sz\[AAcute]m felbonthat\[OAcute] v\[EAcute]ges sok irreducibilis (vagyis \
pr\[IAcute]m) sz\[AAcute]m szorzat\[AAcute]ra. A felbont\[AAcute]s ",
Cell[BoxData[
\(TraditionalForm\`{1, \(-1\)}\)]],
"szorz\[OAcute]kt\[OAcute]l \[EAcute]s a sorrendt\[ODoubleAcute]l \
eltekintve egy\[EAcute]rtelm\[UDoubleAcute].\n Megjegyz\[EAcute]s: Ha ",
Cell[BoxData[
\(TraditionalForm\`a > 0\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`a \[NotEqual] 1\)]],
", akkor pozit\[IAcute]v pr\[IAcute]mek szorzat\[AAcute]ra bontva \
\[EAcute]s azokat nagys\[AAcute]g szerinti sorrendbe rendezve, a felbont\
\[AAcute]s egys\[EAcute]g szorz\[OAcute]t\[OAcute]l eltekintve \
egy\[EAcute]rtelm\[UDoubleAcute]."
}], "Text",
FontSize->14],
Cell["\<\
Tov\[AAcute]bbi fontos alkalmaz\[AAcute]sokat tal\[AAcute]lunk a kriptogr\
\[AAcute]fi\[AAcute]ban. Ezekr\[ODoubleAcute]l k\[EAcute]s\[ODoubleAcute]bb \
esik majd sz\[OAcute].\
\>", "Text",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[{
StyleBox["2. Kongruenci\[AAcute]k, marad\[EAcute]koszt\[AAcute]lyok",
FontSize->18],
StyleBox[":",
FontSize->18,
FontWeight->"Plain"]
}], "Section",
FontFamily->"Times New Roman"],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`a \[Element] \[DoubleStruckCapitalZ]\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`m \[Element] \[DoubleStruckCapitalZ]\\{0}\)]],
" eset\[EAcute]n ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
" mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" jelenti ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
"-nak ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
"-mel vett legkisebb nemnegat\[IAcute]v oszt\[AAcute]si marad\[EAcute]k\
\[AAcute]t.\n (Ez j\[OAcute]l defini\[AAcute]lt ",
StyleBox["\[DoubleStruckCapitalN]",
FontSize->16],
" j\[OAcute]lrendezetts\[EAcute]ge miatt)"
}], "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`m \[Element] \[DoubleStruckCapitalZ]\\{0}\)]],
"eset\[EAcute]n azt mondjuk, hogy ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
" kongruens ",
Cell[BoxData[
\(TraditionalForm\`b\)]],
"-vel modulo ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
", ha ",
Cell[BoxData[
\(TraditionalForm\`a\ \ mod\ m\ = \ b\ \ mod\ m\)]],
". Jele: ",
Cell[BoxData[
\(TraditionalForm\`a \[Congruent] b\ \ \((m)\)\)]],
" \n(",
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"],
": ha ",
Cell[BoxData[
\(TraditionalForm\`a\ \ mod\ m \[NotEqual] \ b\ \ mod\ m\)]],
", akkor inkongruensek. Jele: ",
Cell[BoxData[
\(TraditionalForm\`a \[NotCongruent] b\ \ \((m)\)\)]],
")"
}], "Text",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["A kongruencia tulajdons\[AAcute]gai",
FontWeight->"Bold"],
": \n ",
StyleBox["1.",
FontWeight->"Bold"],
" ",
Cell[BoxData[
\(TraditionalForm\`a \[Congruent] b\ \ \((m)\)\)]],
" \[DoubleLeftRightArrow] ",
Cell[BoxData[
\(TraditionalForm\`b \[Congruent] a\ \ \((m)\)\)]],
" \[DoubleLeftRightArrow] ",
Cell[BoxData[
\(TraditionalForm\`a - b \[Congruent] 0\ \ \((m)\)\)]],
" \[DoubleLeftRightArrow] ",
Cell[BoxData[
\(TraditionalForm\`m | a - b\)]],
" \n ",
StyleBox["2.",
FontWeight->"Bold"],
" A kongruencia ekvivalencia rel\[AAcute]ci\[OAcute], azaz \
reflex\[IAcute]v, szimmetrikus \[EAcute]s tranzit\[IAcute]v.\n ",
StyleBox["3.",
FontWeight->"Bold"],
" Ha ",
Cell[BoxData[
\(TraditionalForm\`f\ \((x)\)\)]],
" egy eg\[EAcute]sz egy\[UDoubleDot]tthat\[OAcute]s polinom \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`a \[Congruent] b\ \ \((m)\)\)]],
", akkor ",
Cell[BoxData[
\(TraditionalForm\`f\ \((a)\)\ \[Congruent] \
f\ \((b)\)\ \ \((m)\)\)]]
}], "Text",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{"-", " ",
StyleBox["Kongruenci\[AAcute]k",
FontFamily->"Times New Roman",
FontWeight->"Bold"]}],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
RowBox[{
StyleBox["kapcsolata",
FontFamily->"Times New Roman",
FontWeight->"Bold"], ":", " ", "\[IndentingNewLine]",
RowBox[{
RowBox[{
StyleBox["1.",
FontWeight->"Bold"], " ", Cell[TextData[{
StyleBox["a x \[Congruent] a y",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" (",
FontFamily->"Times New Roman",
FontVariations->{"CompatibilityType"->0}],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontVariations->{"CompatibilityType"->0}]
}]]}], " ",
StyleBox["\[DoubleLeftRightArrow]",
FontFamily->"Times New Roman",
FontSize->16],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
RowBox[{
StyleBox["x",
FontFamily->"Times New Roman",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox["\[Congruent]",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
RowBox[{
StyleBox["y",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
StyleBox[
RowBox[{"(",
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
RowBox[{
StyleBox["(",
FontSlant->"Italic"],
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[",",
FontWeight->"Plain",
FontSlant->"Italic",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
StyleBox["m",
FontSlant->"Italic"]}],
StyleBox[")",
FontSlant->"Italic"]}]], ")"}],
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}]}]}]}]}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
RowBox[{
RowBox[{
StyleBox["2.",
FontWeight->"Bold"],
StyleBox[" ",
FontSlant->"Italic"],
StyleBox["x",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{
StyleBox["y",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontSlant->"Italic"],
RowBox[{
StyleBox["(",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[\(m\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontWeight->"Plain"]}],
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Plain"]}]],
StyleBox["i",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}]}], "=",
RowBox[{
RowBox[{\(1\ ... \), " ",
StyleBox["r",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}], " ",
StyleBox["\[DoubleLeftRightArrow]",
FontFamily->"Times New Roman",
FontSize->16],
StyleBox[" ",
FontSlant->"Italic"],
RowBox[{
StyleBox["x",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["\[Congruent]",
FontWeight->"Plain"],
RowBox[{
StyleBox["y",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontFamily->"Times New Roman"], " "}]],
RowBox[{"(",
RowBox[{"[",
RowBox[{
StyleBox[\(m\_1\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[",",
FontFamily->"Times New Roman",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox[\(m\_2\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[",",
FontFamily->"Times New Roman",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["...",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox[",",
FontFamily->"Times New Roman",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox[\(m\_r\),
FontFamily->"Times New Roman",
FontSlant->"Italic"]}], "]"}], ")"}]}]}]}]}]}]}], "Text",\
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Marad\[EAcute]koszt\[AAcute]lyok",
FontWeight->"Bold"],
":\n - ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Az ",
Cell[BoxData[
\(TraditionalForm\`x\)]],
"-szel kongruens mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" sz\[AAcute]mokat az ",
Cell[BoxData[
\(TraditionalForm\`x\)]],
" \[AAcute]ltal reprezent\[AAcute]lt mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" marad\[EAcute]koszt\[AAcute]lynak nevezz\[UDoubleDot]k. \n - ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Ha minden marad\[EAcute]koszt\[AAcute]lyb\[OAcute]l \
kivesz\[UDoubleDot]nk egy reprezent\[AAcute]nst, akkor a kapott \
sz\[AAcute]mhalmaz egy mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" teljes marad\[EAcute]krendszer."
}], "Text",
FontSize->14],
Cell[TextData[{
"Standard teljes marad\[EAcute]krendszer mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
":"
}], "Text",
FontSize->14],
Cell[BoxData[
\(stm[m_] := Range[m - 1]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(stm[28]\)], "Input"],
Cell[BoxData[
\({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27}\)], "Output"]
}, Open ]],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Az ",
Cell[BoxData[
\(TraditionalForm\`x\)]],
"-szel reprezent\[AAcute]lt mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" marad\[EAcute]koszt\[AAcute]lyt reduk\[AAcute]lt marad\[EAcute]koszt\
\[AAcute]lynak nevezz\[UDoubleDot]k, ha ",
Cell[BoxData[
\(TraditionalForm\`\((x, m)\) = 1\)]],
".\n- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": Ha minden reduk\[AAcute]lt marad\[EAcute]koszt\[AAcute]lyb\[OAcute]l \
kivesz\[UDoubleDot]nk egy reprezent\[AAcute]nst, akkor a kapott \
sz\[AAcute]mhalmaz egy mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" reduk\[AAcute]lt marad\[EAcute]krendszer."
}], "Text",
FontSize->14],
Cell[TextData[{
"Standard reduk\[AAcute]lt marad\[EAcute]krendszer mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
":"
}], "Text",
FontSize->14],
Cell[BoxData[
\(srm[m_] := Select[Range[m], \((GCD[#, m] \[Equal] 1)\) &]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(srm[28]\)], "Input"],
Cell[BoxData[
\({1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27}\)], "Output"]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[{
StyleBox["3. Az Euler-f\[EAcute]le \[CurlyPhi] \
f\[UDoubleDot]ggv\[EAcute]ny",
FontSize->18],
StyleBox[":",
FontSize->18,
FontWeight->"Plain"]
}], "Section"],
Cell[TextData[{
"- ",
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"],
": A mod ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" reduk\[AAcute]lt marad\[EAcute]krendszer elemeinek sz\[AAcute]m\[AAcute]t \
",
Cell[BoxData[
\(TraditionalForm\`\[CurlyPhi]\ \((m)\)\)]],
" jel\[ODoubleDot]li. Ezt a f\[UDoubleDot]ggv\[EAcute]nyt \
Euler-f\[EAcute]le ",
Cell[BoxData[
\(TraditionalForm\`\[CurlyPhi]\)]],
" f\[UDoubleDot]ggv\[EAcute]nynek nevezik. \n ",
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`\[CurlyPhi]\ \((m)\)\)]],
" teh\[AAcute]t az ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
"-n\[EAcute]l nem nagyobb, ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
"-hez relat\[IAcute]v pr\[IAcute]mek sz\[AAcute]ma."
}], "Text",
FontSize->14],
Cell[BoxData[
RowBox[{
StyleBox[\(Ez\ azt\ jelenti\),
FontFamily->"Times New Roman"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["hogy",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["ha",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["p",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["pr\[IAcute]m",
FontFamily->"Times New Roman"]}],
StyleBox[",",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["akkor",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[CurlyPhi]",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["p",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}]}],
StyleBox["=",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["p",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["-",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
RowBox[{
StyleBox["1",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontSlant->"Italic"],
StyleBox["\[EAcute]s",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False,
"StrikeThrough"->False,
"Masked"->False,
"CompatibilityType"->0,
"RotationAngle"->0}],
StyleBox["\[CurlyPhi]",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[\((p\^r)\),
FontFamily->"Times New Roman",
FontSlant->"Italic"]}]}],
StyleBox["=",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(p\^r\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["-",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
RowBox[{
StyleBox[\(p\^\(r - 1\)\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[".",
FontFamily->"Times New Roman"]}]}]}]}]}]], "Text",
FontSize->14],
Cell[CellGroupData[{
Cell[BoxData[
\(ra = Random[Integer, {1, 50}]\)], "Input"],
Cell[BoxData[
\(34\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(EulerPhi[ra] \[Equal] Length[srm[ra]]\)], "Input"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{"-", " ",
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{"(",
RowBox[{
StyleBox["\[CurlyPhi]",
FontFamily->"Times New Roman"], " ",
StyleBox["kisz\[AAcute]m\[IAcute]t\[AAcute]sa",
"Input",
FontFamily->"Times New Roman"]}],
StyleBox[" ",
"Input"],
StyleBox[")",
"Input"]}]}],
StyleBox[":",
"Input"], Cell[TextData[{
" ",
StyleBox["\[CurlyPhi](",
FontFamily->"Times New Roman"],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"]
}]]}],
StyleBox["=",
"Input"],
StyleBox[" ",
"Input"],
RowBox[{
RowBox[{
StyleBox["\[CurlyPhi]",
FontFamily->"Times New Roman"],
RowBox[{"(",
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
StyleBox[
SuperscriptBox[
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"], \(\[Alpha]\_i\)],
FontSlant->"Italic"]}], ")"}]}], " ", "=", " ",
RowBox[{
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
StyleBox[
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"], \(\[Alpha]\_i\)], "-",
SuperscriptBox[
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"], \(\[Alpha]\_i - 1\)]}], ")"}],
FontFamily->"Times New Roman"]}], " ", "=", " ",
RowBox[{
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"], " ",
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
RowBox[{"(",
RowBox[{
StyleBox["1",
FontFamily->"Times New Roman"],
StyleBox["-",
FontFamily->"Times New Roman"],
FractionBox[
StyleBox["1",
FontFamily->"Times New Roman"],
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"]]}], ")"}]}]}]}]}]}], " ", ",",
" ",
RowBox[{
RowBox[{
StyleBox["ahol",
FontFamily->"Times New Roman"], " ",
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}], "=",
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
RowBox[{
SuperscriptBox[
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"], \(\[Alpha]\_i\)], " ",
"."}]}]}]}]], "Text",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
StyleBox["-",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
StyleBox[":",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
RowBox[{
RowBox[{
StyleBox["Logikai",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["szita",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["formul\[AAcute]val",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["bizony\[IAcute]tjuk",
FontFamily->"Times New Roman"],
StyleBox[".",
FontFamily->"Times New Roman"],
StyleBox[Cell[""],
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"]}],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}],
StyleBox["-",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["ben",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["a",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[
"t\[ODoubleDot]bbsz\[ODoubleDot]r\[ODoubleDot]seinek",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["sz\[AAcute]ma",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[
RowBox[{
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
StyleBox[\(p\_i\),
FontSlant->"Italic"]], ".", " ", "Ezeket"}],
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["levonjuk",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[Cell[""],
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"]}],
StyleBox["-",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(b\[ODoubleAcute]l . \ Ekkor\),
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["azonban",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["k\[EAcute]tszer",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["vontuk",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["le",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(p\_i\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[\(p\_j\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["t\[ODoubleDot]bbsz\[ODoubleDot]r\[ODoubleDot]seit",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["teh\[AAcute]t",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["ezeket",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["hozz\[AAcute]adjuk",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[EAcute]s",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[IAcute]gy",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["tov\[AAcute]bb",
FontFamily->"Times New Roman"],
StyleBox[":",
FontFamily->"Times New Roman"],
StyleBox["\[IndentingNewLine]",
FontFamily->"Times New Roman"], Cell[TextData[{
StyleBox["\[CurlyPhi](",
FontFamily->"Times New Roman"],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"]
}]]}]}]}]}]}],
StyleBox["=",
"Input",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["-",
"Input",
FontFamily->"Times New Roman"],
StyleBox[
FractionBox[
StyleBox["m",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[\(p\_1\),
FontWeight->"Plain",
FontSlant->"Italic"]],
FontFamily->"Times New Roman",
FontWeight->"Bold"],
StyleBox["-",
FontFamily->"Times New Roman"],
StyleBox[
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
StyleBox[\(p\_2\),
FontSlant->"Italic"]],
FontFamily->"Times New Roman"],
StyleBox["-",
FontFamily->"Times New Roman"]}],
StyleBox["...",
FontFamily->"Times New Roman"]}],
StyleBox["-",
FontFamily->"Times New Roman"],
StyleBox[
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
StyleBox[\(p\_r\),
FontSlant->"Italic"]],
FontFamily->"Times New Roman"],
StyleBox["+",
FontFamily->"Times New Roman"],
StyleBox[
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
RowBox[{
StyleBox[\(p\_1\),
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox[\(p\_2\),
FontSlant->"Italic"]}]],
FontFamily->"Times New Roman"],
StyleBox["+",
FontFamily->"Times New Roman"]}],
StyleBox["...",
FontFamily->"Times New Roman"]}],
StyleBox["+",
FontFamily->"Times New Roman"],
StyleBox[
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
RowBox[{
StyleBox[\(p\_\(r - 1\)\),
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(p\_r\),
FontSlant->"Italic"]}]],
FontFamily->"Times New Roman"],
StyleBox["-",
FontFamily->"Times New Roman"]}],
StyleBox["...",
FontFamily->"Times New Roman"]}],
StyleBox["+",
FontFamily->"Times New Roman"],
StyleBox[
RowBox[{\(\((\(-1\))\)\^r\), " ",
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
RowBox[{
RowBox[{
RowBox[{
StyleBox[\(p\_1\),
FontSlant->"Italic"],
StyleBox[" "],
StyleBox[\(p\_2\),
FontSlant->"Italic"]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["...",
FontFamily->"Times New Roman"]}],
StyleBox[\(p\_r\),
FontSlant->"Italic"]}]]}],
FontFamily->"Times New Roman"]}],
StyleBox["=",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
RowBox[{"(",
RowBox[{"1", "-",
FractionBox["1",
StyleBox[\(p\_i\),
FontSlant->"Italic"]]}], ")"}]}],
FontFamily->"Times New Roman"]}]}]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["ahol",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}],
StyleBox["=",
FontFamily->"Times New Roman"],
StyleBox[
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
SuperscriptBox[
StyleBox[
SubscriptBox[
StyleBox["p",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["i",
FontWeight->"Plain"]],
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"], \(\[Alpha]\_i\)]}],
FontFamily->"Times New Roman"]}]}]], "Text",
FontSize->14],
Cell[TextData[{
"-",
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"],
": Ha ",
Cell[BoxData[
\(TraditionalForm\`\((a, b)\) = 1\)]],
", akkor ",
Cell[BoxData[
\(TraditionalForm\`\[CurlyPhi](
a\ b) = \(\[CurlyPhi](a)\)\ \ \(\[CurlyPhi](b)\)\)]]
}], "Text",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
StyleBox["Marad\[EAcute]krendszerek",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
RowBox[{
StyleBox["tulajdons\[AAcute]gai",
FontFamily->"Times New Roman",
FontWeight->"Bold"], ":", "\[IndentingNewLine]",
RowBox[{
RowBox[{
RowBox[{
"1.", " ", Cell[TextData[StyleBox[
"T\[Subset]\[DoubleStruckCapitalZ]",
FontSize->16]]],
StyleBox[" ",
"Section"],
StyleBox["teljes",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["marad\[EAcute]krendszer",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["mod",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input"],
StyleBox["m",
FontSlant->"Italic"],
StyleBox[Cell[""],
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input"],
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Subsection"],
StyleBox[\(\(a\)\(.\)\),
"Input"]}],
StyleBox[" ",
"Input"],
StyleBox["|",
"Input",
FontWeight->"Bold"],
StyleBox["T",
"Input"],
StyleBox["|",
"Input"]}]}]}],
StyleBox["=",
"Input"],
RowBox[{
StyleBox[Cell[""],
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["m",
FontWeight->"Plain",
FontSlant->"Italic"]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
" \
",
"Input"],
RowBox[{
RowBox[{
StyleBox["b",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[",",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_j\),
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[Element]",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["T",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
StyleBox["-",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["re",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}]}], "\[NotCongruent]",
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_j\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["m",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["ha",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"], "i"}], "\[NotEqual]",
"j"}]}]}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
RowBox[{
RowBox[{
RowBox[{
"2.", " ", Cell[TextData[StyleBox[
"R\[Subset]\[DoubleStruckCapitalZ]",
FontSize->16]]],
StyleBox[" ",
"Input"],
StyleBox["reduk\[AAcute]lt",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["marad\[EAcute]krendszer",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["mod",
"Input",
FontFamily->"Times New Roman"],
StyleBox[" ",
"Input"],
StyleBox["m",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input"],
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Subsection"],
StyleBox[\(\(a\)\(.\)\),
"Input"]}],
StyleBox[" ",
"Input"],
StyleBox["|",
"Input"],
StyleBox["R",
"Input"],
StyleBox["|",
"Input"]}],
StyleBox["=",
"Input"], Cell["\[CurlyPhi](m)",
FontFamily->"Times New Roman"]}]}], "\[IndentingNewLine]",
RowBox[{"\t\t\t\t\t\t ",
RowBox[{
RowBox[{
StyleBox["b",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_j\),
FontSlant->"Italic"], " ",
StyleBox["\[Element]",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["R",
FontFamily->"Times New Roman",
FontWeight->"Bold"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["eset\[EAcute]n",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}],
StyleBox["\[NotCongruent]",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_j\),
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["m",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"]}],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["ha",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["i",
FontFamily->"Times New Roman"]}],
StyleBox["\[NotEqual]",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["j",
FontFamily->"Times New Roman"]}]}]}]}], "\[IndentingNewLine]",
RowBox[{"\t\t\t\t\t\t\t",
RowBox[{
RowBox[{
StyleBox["c",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"], " ",
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_i\),
FontFamily->"Trebuchet MS",
FontSlant->"Italic"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox["m",
FontSlant->"Italic"]}],
StyleBox[")",
FontFamily->"Times New Roman"]}]}], "=", "1"}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-",
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"], ":", " ",
RowBox[{"Ha", " ", Cell[TextData[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["a",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
",",
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")=1",
FontFamily->"Times New Roman"]
}]], " ", "\[EAcute]s", " ",
RowBox[{
StyleBox["{",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox[\(r\_1\),
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox["...",
FontFamily->"Times New Roman"],
StyleBox[",",
FontFamily->"Times New Roman"],
StyleBox[\(r\_k\),
FontSlant->"Italic"]}],
StyleBox["}",
FontFamily->"Times New Roman"]}], " ", "teljes",
" ", \((vagy\ reduk\[AAcute]lt)\), " ", "marad\[EAcute]krendszer",
" ", "mod",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["m",
FontSlant->"Italic"]}]}]}], ",",
RowBox[{"akkor", " ",
RowBox[{"{",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox[\(r\_1\),
FontSlant->"Italic"]}], ",", "...", ",",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_k\),
FontSlant->"Italic"]}]}], "}"}], " ", "is", " ", "teljes",
" ", \((vagy\ reduk\[AAcute]lt)\), " ", "marad\[EAcute]krendszer",
" ", "mod", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{
"Egyszer\[UDoubleAcute]en", " ", "ellen\[ODoubleAcute]rizni", " ",
"kell", " ",
RowBox[{"{",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_1\),
FontSlant->"Italic"]}], ",", "...", ",",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_k\),
FontSlant->"Italic"]}]}], "}"}]}],
"-", \(ra\ a\ fenti\ tulajdons\[AAcute]gokat\)}]}]}],
",", \(melyek\ trivi\[AAcute]lisan\ \
\(\(teljes\[UDoubleDot]lnek\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"], ":", " ",
RowBox[{"Ha", " ",
StyleBox["T",
FontWeight->"Bold"]}]}]}], "=",
RowBox[{
RowBox[{"{",
RowBox[{
StyleBox[\(r\_1\),
FontSlant->"Italic"], ",", "...", ",",
StyleBox[\(r\_k\),
FontSlant->"Italic"]}], "}"}], " ", "teljes", " ",
"marad\[EAcute]krendszer", " ", "mod", " ",
StyleBox["m",
FontSlant->"Italic"]}]}], ",", " ",
RowBox[{"akkor", " ",
RowBox[{"{",
RowBox[{
RowBox[{
StyleBox[\(r\_1\),
FontSlant->"Italic"], "+",
StyleBox["a",
FontSlant->"Italic"]}], ",", "...", ",",
RowBox[{
StyleBox[\(r\_k\),
FontSlant->"Italic"],
StyleBox["+",
FontFamily->"Times New Roman"],
StyleBox["a",
FontSlant->"Italic"]}]}], "}"}], " ", "is", " ", "az", " ",
"mod", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"],
": Megint ellen\[ODoubleAcute]rizni kell az el\[ODoubleAcute]bbi tulajdons\
\[AAcute]gokat, melyek egyszer\[UDoubleAcute]en l\[AAcute]tszanak."
}], "Text",
FontSize->14],
Cell[TextData[{
StyleBox["Invert\[AAcute]l\[AAcute]s",
FontWeight->"Bold"],
":"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
StyleBox[
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], \(-1\)],
FontFamily->"Times New Roman"], " ", "az",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["a",
FontSlant->"Italic"], " ", "elem", " ", "inverze", " ",
"modulo", " ",
StyleBox["m",
FontSlant->"Italic"]}]}]}], ",",
RowBox[{
RowBox[{"ha", " ",
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold",
FontSlant->"Italic"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], \(-1\)]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], ".", " ", "Az"}], " ",
StyleBox["a",
FontSlant->"Italic"], " ", "elem", " ",
"invert\[AAcute]lhat\[OAcute]", " ", "modulo", " ",
StyleBox["m",
FontSlant->"Italic"]}]}],
",", \(ha\ l\[EAcute]tezik\ \(\(inverze\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
StyleBox["-T\[EAcute]tel",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
" invert\[AAcute]lhat\[OAcute] modulo ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" \[DoubleLeftRightArrow] ",
Cell[BoxData[
\(TraditionalForm\`\((a, m)\) = 1\)]],
". Ha ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
"-nak l\[EAcute]tezik inverze modulo ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
", akkor az egy\[EAcute]rtelm\[UDoubleAcute] modulo ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
"."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
StyleBox["Euler \[EAcute]s Fermat t\[EAcute]telei",
FontWeight->"Bold"],
":"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
RowBox[{"-", " ",
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox[\((Euler)\),
FontWeight->"Bold"]}], ":", " ",
RowBox[{"Ha", " ", Cell[TextData[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["a",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
",",
StyleBox["m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")=1",
FontFamily->"Times New Roman"]
}]]}]}], " ", ",",
RowBox[{
RowBox[{"akkor", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], " ", "."}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{"Legyen", " ",
RowBox[{"{",
RowBox[{
StyleBox[\(r\_1\),
FontSlant->"Italic"], ",", "...", ",",
StyleBox[
SubscriptBox[
StyleBox["r",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
FontFamily->"Times New Roman"]}], "}"}], " ",
"reduk\[AAcute]lt", " ", "marad\[EAcute]krendszer", " ", "mod",
" ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], ".", " ", "M\[AAcute]r"}], " ",
"bel\[AAcute]ttuk"}]}]}], ",",
RowBox[{"hogy", " ", "ekkor", " ",
RowBox[{"{",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_1\),
FontSlant->"Italic"]}], ",", "...", ",",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
SubscriptBox[
StyleBox["r",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]]}]}], "}"}], " ", "is",
" ", "reduk\[AAcute]lt", " ", "marad\[EAcute]krendszer", " ", "mod",
" ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], ".", " ", "Most"}], " ", "ezen", " ",
"k\[EAcute]t", " ", "halmaz", " ", "elemeit", " ", "p\[AAcute]rokba",
" ", "rendezz\[UDoubleDot]k", " ", "\[UAcute]gy"}], ",",
RowBox[{"hogy", " ",
StyleBox[\(r\_i\),
FontSlant->"Italic"], " ", "p\[AAcute]rja", " ", "az", " ", "az",
" ",
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_j\),
FontSlant->"Italic"]}], ",",
RowBox[{
RowBox[{
RowBox[{"amire",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox[\(r\_j\),
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], " ", "\[EAcute]s",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["i",
FontFamily->"Times New Roman"]}]}], "=",
RowBox[{
RowBox[{\(1. .. \),
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
RowBox[{
StyleBox["(",
"Input"],
StyleBox["m",
FontSlant->"Italic"],
StyleBox[")",
"Input",
FontWeight->"Bold"]}],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["\[CapitalIAcute]gy",
"Input"]}],
StyleBox[" ",
"Input"],
RowBox[{
UnderoverscriptBox["\[Product]", \(i = 1\),
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}]}], "\[Congruent]",
RowBox[{
UnderoverscriptBox["\[Product]", \(j = 1\),
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox[\(r\_j\),
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Bold"], " "}]],
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], ".", " ",
"Ebb\[ODoubleAcute]l"}], " ",
"k\[ODoubleDot]vetkezik"}]}]}]}], ",",
RowBox[{
RowBox[{"hogy", " ",
RowBox[{
UnderoverscriptBox["\[Product]", \(i = 1\),
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
StyleBox[\(r\_i\),
FontSlant->"Italic"]}]}], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
RowBox[{
UnderoverscriptBox["\[Product]", \(j = 1\),
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]],
RowBox[{
StyleBox[\(r\_j\),
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontFamily->"Times New Roman"], " "}]],
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], ".", " ", "A"}], " ",
"produktumok", " ", "mindk\[EAcute]t", " ", "oldalon", " ",
"egy", " ", "reduk\[AAcute]lt", " ", "marad\[EAcute]krendszer",
" ", "\[ODoubleDot]sszes", " ", "elem\[EAcute]nek", " ",
"szorzat\[AAcute]t", " ", "adj\[AAcute]k"}]}]}]}], ",",
RowBox[{
RowBox[{
"teh\[AAcute]t", " ", "kongruensek", " ", "egym\[AAcute]ssal", " ",
"mod", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], ".", " ", "\[CapitalIAcute]gy"}], " ",
"viszont", " ", "1"}], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
FontWeight->"Bold"],
RowBox[{"(",
StyleBox["m",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"], ")"}]}]], " ",
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], "."}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{"-",
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox[\((kis\ Fermat)\),
FontWeight->"Bold"]}], ":", " ",
StyleBox["a",
FontWeight->"Bold"]}], ",", " ",
RowBox[{
StyleBox["p",
FontSlant->"Italic"],
StyleBox["\[NotVerticalBar]",
"Section"],
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["\[EAcute]s",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["p",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["pr\[IAcute]m",
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["akkor",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
StyleBox["b",
FontWeight->"Bold"], ",", " ",
RowBox[{"Ha", " ",
StyleBox["p",
FontSlant->"Italic"], " ", "pr\[IAcute]m", " ", "\[EAcute]s", " ",
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Plain"], "tetsz\[ODoubleAcute]leges", " ",
"eg\[EAcute]sz"}], " ", ",",
RowBox[{
RowBox[{"akkor", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]]}], "\[Congruent]",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontFamily->"Times New Roman"], " "}]],
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}]}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
StyleBox["a",
FontWeight->"Bold"]}]}], ",", " ",
RowBox[{\(K\[ODoubleDot]vetkezik\ az\ Euler\), "-",
RowBox[{
"t\[EAcute]telb\[ODoubleAcute]l", ".", "\[IndentingNewLine]",
" ",
StyleBox["b",
FontWeight->"Bold"]}]}], ",", " ",
RowBox[{
RowBox[{"Ha", " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{"0", " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{
"akkor", " ", "trivi\[AAcute]lisan", " ", "teljes\[UDoubleDot]l", " ",
"az", " ", \(\[AAcute]ll\[IAcute]t\[AAcute]s . \ Ha\), " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[NotCongruent]",
RowBox[{
StyleBox["0",
FontFamily->"Times New Roman"], " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
StyleBox["p",
FontSlant->"Italic"]}],
StyleBox["\[NotVerticalBar]",
"Section"],
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["Az",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["el\[ODoubleAcute]z\[ODoubleAcute]ek",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["miatt",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["p",
FontSlant->"Italic"],
StyleBox["-",
FontFamily->"Times New Roman"],
StyleBox["1",
FontFamily->"Times New Roman"]}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}], " ", "\[EAcute]s", " ",
"\[IAcute]gy",
StyleBox[" ",
FontFamily->"Times New Roman"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]]}], "\[Congruent]",
RowBox[{
StyleBox["a",
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Plain"], " "}]],
RowBox[{
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}], "."}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[{
StyleBox["4. Egy elem rendje mod ",
FontSize->18],
StyleBox["m",
FontFamily->"Times New Roman",
FontSize->18,
FontSlant->"Italic"],
StyleBox[":",
FontSize->18]
}], "Section"],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"],
StyleBox[">",
FontFamily->"Times New Roman"],
StyleBox["0",
FontFamily->"Times New Roman"]}]}]}], ",",
RowBox[{
RowBox[{
StyleBox["m",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[EAcute]s",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["a",
FontSlant->"Italic"]}], "\[Element]",
StyleBox["\[DoubleStruckCapitalZ]",
"Section"]}],
StyleBox[" ",
"Input"],
StyleBox[",",
"Input"], Cell[TextData[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["a,m",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"],
StyleBox["=",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox["1",
FontFamily->"Times New Roman"]
}]],
StyleBox[",",
"Input"],
RowBox[{
RowBox[{
StyleBox["valamint",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["k",
FontSlant->"Italic"]]}], "\[Congruent]",
RowBox[{
StyleBox["1",
FontFamily->"Times New Roman"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"de", " ",
StyleBox[
SuperscriptBox[
StyleBox["a",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["l",
FontWeight->"Plain",
FontSlant->"Italic"]],
FontWeight->"Bold"]}], "\[NotCongruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}]}], ",", " ",
RowBox[{
RowBox[{
RowBox[{"ha", " ",
StyleBox["0",
FontFamily->"Times New Roman"]}],
StyleBox["<",
FontFamily->"Times New Roman"],
StyleBox["l",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["<",
FontFamily->"Times New Roman"],
RowBox[{
RowBox[{
StyleBox["k",
FontSlant->"Italic"], " ", ".", " ", "Ekkor"}], " ",
StyleBox["k",
FontSlant->"Italic"], " ", "az", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "elem", " ", "rendje", " ", "mod",
" ",
StyleBox["m",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
RowBox[{"jele", ":", " ",
RowBox[{
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]}]}]}], "=",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["\[CapitalAAcute]ll\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]}]}],
StyleBox["=",
FontFamily->"Times New Roman"],
StyleBox["g",
FontSlant->"Italic"]}], " ", ",", " ",
RowBox[{
RowBox[{
RowBox[{
StyleBox[
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["k",
FontSlant->"Italic"]],
FontFamily->"Times New Roman"], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}]}], " ",
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Subsection"],
StyleBox["g",
FontSlant->"Italic"]}],
StyleBox["|",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"],
RowBox[{
StyleBox["k",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", "\[IndentingNewLine]",
RowBox[{"El\[ODoubleAcute]sz\[ODoubleDot]r", " ",
StyleBox["\[Implies]",
"Subsection"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["ir\[AAcute]nyban",
"Input"],
StyleBox[":",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["k",
FontSlant->"Italic"]}]}]}]}],
StyleBox["=",
"Input"],
RowBox[{
RowBox[{
RowBox[{
StyleBox["g",
FontSlant->"Italic"],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["b",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input",
FontFamily->"Times New Roman"],
StyleBox["+",
"Input",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["r",
"Input",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox[\((marad\[EAcute]kos\ oszt\[AAcute]s)\),
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["k",
FontSlant->"Italic"]]}]}]}], "=",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
RowBox[{
StyleBox["g",
FontSlant->"Italic"], " ",
StyleBox["b",
FontSlant->"Italic"]}], "+",
StyleBox["r",
"Input",
FontSlant->"Italic"]}]], "=",
RowBox[{
RowBox[{
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["k",
FontSlant->"Italic"]], ")"}],
StyleBox["b",
FontSlant->"Italic"]],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["r",
"Input",
FontSlant->"Italic"]]}], "\[Congruent]",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["r",
"Input",
FontSlant->"Italic"]], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], ".", " ", "Mivel"}],
" ",
StyleBox["r",
FontSlant->"Italic"]}],
StyleBox["<",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["g",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]}], "=",
StyleBox["g",
FontSlant->"Italic"]}]}]}]}],
",", \(ez\[EAcute]rt\ ez\ csak\ \[UAcute]gy\ lehets\[EAcute]ges\),
",",
RowBox[{
RowBox[{"ha", " ",
StyleBox["r",
FontSlant->"Italic"]}], "=", "0."}]}],
"\[IndentingNewLine]"}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
RowBox[{
StyleBox["\[DoubleLeftArrow]",
"Subsection"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["ir\[AAcute]nyban",
"Input"],
StyleBox[":",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["k",
FontSlant->"Italic"]}]}],
StyleBox[":=",
"Input"],
RowBox[{
RowBox[{
StyleBox["g",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["b",
FontSlant->"Italic"],
StyleBox[".",
FontSlant->"Italic"],
StyleBox[" ",
FontSlant->"Italic"],
StyleBox["Ekkor",
FontSlant->"Plain"]}],
StyleBox[" ",
"Input"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["k",
FontSlant->"Italic"]]}], "=",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["g",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["b",
FontSlant->"Italic"]}]], "=",
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["g",
FontSlant->"Italic"]], ")"}],
StyleBox["b",
FontSlant->"Italic"]], "\[Congruent]",
SuperscriptBox["1",
StyleBox["b",
FontSlant->"Italic"]], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], "."}]}]}]}]}]}]}]}], "Text",\
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"], ":", " ",
RowBox[{
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]}]}], "=",
RowBox[{
RowBox[{
StyleBox["k",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[Implies]",
"Subsection"],
StyleBox[
RowBox[{
StyleBox[" ",
"Input"], " "}]],
RowBox[{
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["g",
FontSlant->"Italic"]]}]}], "=",
RowBox[{
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]], " ", "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"],
StyleBox[":",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
RowBox[{
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["g",
FontSlant->"Italic"]], ")"}],
StyleBox["j",
FontSlant->"Italic"]], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}]}], " ",
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Input"],
StyleBox["k",
FontSlant->"Italic"]}],
StyleBox["|",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"],
RowBox[{
RowBox[{
StyleBox["g",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["j",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input"],
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Input"],
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]]}], "|",
RowBox[{
FractionBox[
StyleBox["g",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]],
StyleBox["j",
FontSlant->"Italic"]}]}]}]}], ",",
RowBox[{"de", " ",
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]], " ", "\[EAcute]s", " ",
FractionBox[
StyleBox["g",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]], " ", "nyilv\[AAcute]n", " ",
"relat\[IAcute]v", " ", "pr\[IAcute]mek"}], ",", " ",
RowBox[{
RowBox[{
"ez\[EAcute]rt", " ", "a", " ", "fenti", " ",
"oszthat\[OAcute]s\[AAcute]gban", " ",
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]]}], "|",
RowBox[{
RowBox[{
StyleBox["j",
FontSlant->"Italic"], ".", " ", "Ez"}], " ", "pedig", " ", "az",
" ", "el\[ODoubleAcute]bb", " ", "bel\[AAcute]tott", " ",
"\[AAcute]ll\[IAcute]t\[AAcute]s", " ", "alapj\[AAcute]n", " ",
"igazolja"}]}], ",",
RowBox[{
RowBox[{"hogy", " ",
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["g",
FontSlant->"Italic"]]}], "=",
RowBox[{
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
RowBox[{"(",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ",",
StyleBox["g",
FontSlant->"Italic"]}], ")"}]], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{"Egy", " ",
StyleBox["g",
FontSlant->"Italic"], " ", "elemet", " ", "primit\[IAcute]v",
" ", "gy\[ODoubleDot]knek", " ", "nevez\[UDoubleDot]nk", " ",
"mod", " ",
StyleBox["m",
FontSlant->"Italic"]}]}]}], ",",
RowBox[{
RowBox[{"ha", " ",
SubscriptBox["ord",
StyleBox["m",
FontSlant->"Italic"]],
StyleBox["g",
FontSlant->"Italic"]}], "=",
RowBox[{
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
RowBox[{
StyleBox["(",
"Input"],
StyleBox["m",
FontSlant->"Italic"],
StyleBox[")",
"Input"]}],
StyleBox[".",
"Input"],
StyleBox["\[IndentingNewLine]",
"Input"],
StyleBox["Primit\[IAcute]v",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["gy\[ODoubleDot]k",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["nem",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["felt\[EAcute]tlen\[UDoubleDot]l",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["l\[EAcute]tezik",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["egy",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["m",
FontSlant->"Italic"]}], "\[Element]",
RowBox[{
StyleBox["\[DoubleStruckCapitalN]",
"Section"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["sz\[AAcute]mra",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox[".",
"Input"]}]}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
"Bizony\[IAcute]t\[AAcute]s", " ", "n\[EAcute]lk\[UDoubleDot]l", " ",
"k\[ODoubleDot]zl\[UDoubleDot]nk", " ", "egy", " ", "t\[EAcute]telt",
" ", "a", " ", "primit\[IAcute]v", " ", "gy\[ODoubleDot]k", " ",
"l\[EAcute]tez\[EAcute]s\[EAcute]re", " ",
RowBox[{"vonatkoz\[OAcute]an", ":", "\[IndentingNewLine]",
RowBox[{"-",
RowBox[{"T\[EAcute]tel", ":", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"],
StyleBox[">",
FontFamily->"Times New Roman"],
StyleBox["1",
FontFamily->"Times New Roman"]}]}]}]}]}], ",",
RowBox[{
RowBox[{
RowBox[{
"akkor", " ", "l\[EAcute]tezik", " ", "primit\[IAcute]v", " ",
"gy\[ODoubleDot]k", " ", "mod",
StyleBox[
RowBox[{" ",
StyleBox[" ",
"Input"]}]],
StyleBox["m",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input"],
StyleBox["\[DoubleLeftRightArrow]",
"Subsection"],
StyleBox[" ",
"Subsection"],
StyleBox["m",
FontSlant->"Italic"]}],
StyleBox["=",
"Input"],
StyleBox["2",
"Input",
FontWeight->"Plain"]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox["4",
"Input",
FontWeight->"Plain"],
StyleBox[",",
"Input",
FontWeight->"Plain"],
SuperscriptBox[
StyleBox["p",
FontSlant->"Italic"], "\[Alpha]"], ",",
RowBox[{"2", " ",
SuperscriptBox[
StyleBox["p",
FontSlant->"Italic"], "\[Alpha]"], " ", "valamelyike"}], ",",
RowBox[{
RowBox[{"ahol", " ",
StyleBox["\[Alpha]",
FontFamily->"Times New Roman"]}],
StyleBox[">",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["0",
FontFamily->"Times New Roman"], " ", "\[EAcute]s", " ",
StyleBox["p",
FontSlant->"Italic"]}],
StyleBox[">",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["2",
FontFamily->"Times New Roman"],
" ", \(\(pr\[IAcute]m\)\(.\)\)}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["5. Mire j\[OAcute]k a nagy pr\[IAcute]mek? ",
FontSize->18]], "Section"],
Cell["\<\
Mint m\[AAcute]r kor\[AAcute]bban eml\[IAcute]tett\[UDoubleDot]k a nagy pr\
\[IAcute]meknek a kriptogr\[AAcute]fi\[AAcute]ban van fontos szerep\
\[UDoubleDot]k t\[ODoubleDot]bbek k\[ODoubleDot]z\[ODoubleDot]tt. Ez azzal \
hozhat\[OAcute] kapcsolatba, hogy a titkos\[IAcute]t\[AAcute]sokban olyan sz\
\[AAcute]melm\[EAcute]leti f\[UDoubleDot]ggv\[EAcute]nyeket \
haszn\[AAcute]lnak, melyek egyir\[AAcute]ny\[UAcute]ak, azaz egy \
sz\[AAcute]mnak neh\[EAcute]z visszakeresni az \[ODoubleAcute]sk\[EAcute]p\
\[EAcute]t. \[CapitalIAcute]me egy-k\[EAcute]t p\[EAcute]lda ilyen f\
\[UDoubleDot]ggv\[EAcute]nyre:\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
StyleBox["1. Pr\[IAcute]mfaktoriz\[AAcute]ci\[OAcute]",
FontWeight->"Bold"],
": ",
Cell[BoxData[
\(TraditionalForm\`n = p\ q\)]],
", ahol ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`q\)]],
" nagy pr\[IAcute]mek. Ekkor ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" kisz\[AAcute]mol\[AAcute]sa egy egyszer\[UDoubleAcute] szorz\[AAcute]s, \
azonban csup\[AAcute]n ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" ismeret\[EAcute]ben ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`q\)]],
" meghat\[AAcute]roz\[AAcute]sa mai ismereteink szerint rem\[EAcute]nytelen\
\[UDoubleDot]l neh\[EAcute]z."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
StyleBox["2.",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["Diszkr\[EAcute]t",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["logaritmus",
FontWeight->"Bold"], ":", " ",
RowBox[{
StyleBox["p",
FontSlant->"Italic"], " ", "egy", " ", "nagy", " ",
"pr\[IAcute]m", " ", "\[EAcute]s", " ", "egy", " ",
StyleBox["g",
FontSlant->"Italic"], " ", "elemnek", " ", "sok", " ",
"k\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute]",
" ", "hatv\[AAcute]nya", " ", "van", " ", "mod", " ",
RowBox[{
StyleBox["p",
FontSlant->"Italic"], ".", " ", "Ekkor"}], " ", "egy", " ",
StyleBox["a",
FontSlant->"Italic"]}]}]}], "=",
RowBox[{
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"],
StyleBox["i",
FontSlant->"Italic"]], " ", "mod", " ",
StyleBox["p",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ",
"kisz\[AAcute]mol\[AAcute]sa", " ", "gyorsan", " ", "megy"}]}],
",", \(az\ \[UAcute]gynevezett\ gyorshatv\[AAcute]nyoz\[AAcute]ssal\),
",", " ", \(ami\ azt\ jelenti\), ",", " ",
RowBox[{
RowBox[{"hogy", " ", "tekintj\[UDoubleDot]k",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["i",
FontSlant->"Italic"]}],
"-", \(nek\ a\ kettes\ sz\[AAcute]mrendszerbeli\ alakj\[AAcute]t\ \
\[EAcute]s\ \[UAcute]gy\ hatv\[AAcute]nyozunk\)}], ",",
RowBox[{
RowBox[{"hogy", " ",
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], \(\(2\)\(\ \)\)], "ut\[AAcute]n", " ",
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], \(\(4\)\(\ \)\)]}], "=", " ",
SuperscriptBox[
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], "2"], " ", "mod", " ",
StyleBox["p",
FontSlant->"Italic"]}], ")"}], "2"]}], ",", " ",
RowBox[{
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], "8"], "=",
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], "4"], ")"}], "2"], "=",
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"], "2"], " ", "mod", " ",
StyleBox["p",
FontSlant->"Italic"]}], ")"}], "2"], ")"}], "2"], " ",
"\[EAcute]s", " ", "\[IAcute]gy", " ", "tov\[AAcute]bb"}]}]}],
",", " ",
RowBox[{
RowBox[{
"majd", " ", "ezekb\[ODoubleAcute]l", " ", "felhaszn\[AAcute]lva",
" ", "a", " ", "kettes", " ", "sz\[AAcute]mrendszerbeli", " ",
"alakot", " ", "\[ODoubleDot]sszerakjuk", " ",
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"],
StyleBox["i",
FontSlant->"Italic"]]}], "-",
RowBox[{\(t\ . \ Azonban\), " ", "ha", " ", "csak", " ",
StyleBox["p",
FontSlant->"Italic"]}], "-",
RowBox[{"t", " ", "\[EAcute]s", " ",
SuperscriptBox[
StyleBox["g",
FontSlant->"Italic"],
StyleBox["i",
FontSlant->"Italic"]]}], "-", \(t\ ismerj\[UDoubleDot]k\)}],
",",
RowBox[{
"akkor", " ", "ezek", " ", "alapj\[AAcute]n", " ", "megmondani", " ",
StyleBox["i",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"], "\[EAcute]rt\[EAcute]k\[EAcute]t",
" ", "nagyon", " ", \(\(neh\[EAcute]z\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
"Ez", " ", "a", " ", "gyorshatv\[AAcute]nyoz\[AAcute]s", " ",
"megtal\[AAcute]lhat\[OAcute]", " ", "a", " ", "Mathematic\[AAcute]ban",
" ",
RowBox[{"is", ":", "\[IndentingNewLine]", " ",
RowBox[{
"Els\[ODoubleAcute]", " ", "esetben", " ", "el\[ODoubleAcute]bb", " ",
"hatv\[AAcute]nyozunk", " ", "majd", " ", "az", " ",
"eredm\[EAcute]nyt", " ", "tekintj\[UDoubleDot]k", " ", "mod", " ",
RowBox[{
StyleBox["n",
FontSlant->"Italic"], ":", "\[IndentingNewLine]",
RowBox[{"(",
RowBox[{
RowBox[{"Megjegyz\[EAcute]s", ":", " ",
StyleBox["a",
FontSlant->"Italic"]}], ",",
RowBox[{
StyleBox["b",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[EAcute]rt\[EAcute]kei", " ",
"megv\[AAcute]ltoztathat\[OAcute]ak"}], " ",
",", \(itt\ p\[EAcute]ldak\[EAcute]nt\ 3\^10000000 -
et\ sz\[AAcute]moljuk\ ki\ modulo\ 7. \)}],
")"}]}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(Simahatv\[AAcute]ny[a_, b_, n_] := Mod[a\^b, n]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(Timing[
Simahatv\[AAcute]ny[a, b, n] /. {a \[Rule] 3, b \[Rule] 100000000,
n \[Rule] 7}]\)], "Input"],
Cell[BoxData[
\({19.519000000000002`\ Second, 4}\)], "Output"]
}, Open ]],
Cell[TextData[{
"Most pedig a fent le\[IAcute]rt m\[OAcute]don gyors\[IAcute]tva \
sz\[AAcute]mol a program:\n (Megjegyz\[EAcute]s: ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`b\)]],
" \[EAcute]s ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" \[EAcute]rt\[EAcute]keivel itt is lehet k\[IAcute]s\[EAcute]rletezni, p\
\[EAcute]ldak\[EAcute]nt ugyanaz szerepel mint az el\[ODoubleAcute]bb, hogy a \
m\[OAcute]dszerek sebess\[EAcute]g\[EAcute]t \[ODoubleDot]ssze lehessen \
hasonl\[IAcute]tani) "
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(Gyorshatv\[AAcute]ny[a_, b_, n_] := PowerMod[a, b, n]\)], "Input"],
Cell[BoxData[
\(Timing[
Gyorshatv\[AAcute]ny[a, b, n] /. {a \[Rule] 3, b \[Rule] 100000000,
n \[Rule] 7}]\)], "Input"],
Cell[BoxData[
RowBox[{
RowBox[{
StyleBox["3.",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["N\[EAcute]gyzetre",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["emel\[EAcute]s",
FontWeight->"Bold"], ":", " ",
StyleBox["p",
FontSlant->"Italic"]}]}], ",",
RowBox[{
RowBox[{
StyleBox["q",
FontSlant->"Italic"], " ", "nagy", " ", "pr\[IAcute]mek", " ",
"\[EAcute]s", " ",
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["=",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["p",
FontSlant->"Italic"],
StyleBox[" "],
StyleBox["q",
FontSlant->"Italic"]}]}], " ", ",",
RowBox[{
RowBox[{"akkor", " ",
StyleBox["y",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"], "2"], " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "az", " ",
StyleBox["x",
FontSlant->"Italic"], " ", "megad\[AAcute]sa", " ",
"ut\[AAcute]n", " ", "gyorsan", " ",
"sz\[AAcute]molhat\[OAcute]"}]}], ",",
RowBox[{
RowBox[{"de", " ", "puszt\[AAcute]n", " ",
StyleBox["y",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "ismeret\[EAcute]ben", " ",
StyleBox["x",
FontSlant->"Italic"]}],
"-", \(et\ kisz\[AAcute]molni\ \
\(\(rem\[EAcute]nytelen\)\(.\)\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
StyleBox["4.",
FontWeight->"Bold"], " ", "V\[EAcute]g\[UDoubleDot]l", " ", "az",
" ", "egyik", " ", "legismertebb", " ", "\[EAcute]s", " ",
"legfontosabb", " ", "titkos\[IAcute]t\[AAcute]si", " ",
"alkalmaz\[AAcute]sa", " ", "a", " ", "pr\[IAcute]meknek", " ",
"az", " ",
StyleBox["RSA",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["-",
FontWeight->"Bold"],
RowBox[{
RowBox[{
StyleBox["m\[OAcute]dszer",
FontWeight->"Bold"], ".", "\[IndentingNewLine]",
"Nev\[EAcute]t"}], " ", "a", " ", "kital\[AAcute]l\[OAcute]inak",
" ", "kezd\[ODoubleAcute]bet\[UDoubleAcute]ib\[ODoubleAcute]l", " ",
"kapta",
" ", \(\((Rives - Shamir - Adlemann)\) . \[IndentingNewLine]A\),
" ", "m\[OAcute]dszer", " ",
"k\[UDoubleDot]l\[ODoubleDot]nlegess\[EAcute]ge"}]}],
",", \(hogy\ a\ titkos\[IAcute]t\[AAcute]s\ nyilv\[AAcute]nos\ kulcs\
\[UAcute]\),
",", \(azaz\ k\[ODoubleDot]zz\[EAcute]\ lehet\ tenni\ a\ \
titkos\[IAcute]t\[OAcute]\ f\[UDoubleDot]ggv\[EAcute]nyt\), ",",
RowBox[{
RowBox[{
"mert", " ", "annak", " ", "seg\[IAcute]ts\[EAcute]g\[EAcute]vel",
" ", "m\[EAcute]g", " ", "nem", " ", "lehet", " ",
"dek\[OAcute]dolni", " ", "az",
" ", \(\[UDoubleDot]zenetet . \[IndentingNewLine]Az\), " ",
"elj\[AAcute]r\[AAcute]s", " ", "a", " ",
RowBox[{"k\[ODoubleDot]vetkez\[ODoubleAcute]", ":", " ",
RowBox[{
"V\[AAcute]lasztunk", " ", "k\[EAcute]t", " ", "nagyon", " ",
"nagy", " ", \(pr\[IAcute]met . \ Legyenek\), " ", "ezek", " ",
StyleBox["p",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
RowBox[{
StyleBox["q",
FontSlant->"Italic"], ".", " ",
"K\[EAcute]pezz\[UDoubleDot]k"}], " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"]}]}]}], "=",
RowBox[{
StyleBox["p",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["q",
FontSlant->"Italic"], " ", \(sz\[AAcute]mot . \ Ekkor\), " ",
"tudjuk"}]}], ",",
RowBox[{
RowBox[{"hogy", " ",
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}],
StyleBox[" ",
"Input"],
StyleBox["=",
"Input"],
RowBox[{
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
RowBox[{
StyleBox["p",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["-",
"Input"],
StyleBox["1",
"Input",
FontWeight->"Plain"]}],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}],
RowBox[{
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
RowBox[{
StyleBox["q",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["-",
"Input"],
StyleBox["1",
"Input",
FontWeight->"Plain"]}],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["Most",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["m\[EAcute]g",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["v\[AAcute]lasztunk",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["egy",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["olyan",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["e",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["sz\[AAcute]mot",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["is",
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
RowBox[{
StyleBox["amire",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["1",
"Input",
FontWeight->"Plain"]}],
StyleBox["\[LessEqual]",
"Input"],
StyleBox["e",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["\[LessEqual]",
"Input"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["\[EAcute]s",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["amelyre",
"Input",
FontWeight->"Plain"],
StyleBox[
RowBox[{
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"]}]],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
RowBox[{
StyleBox["e",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[",",
"Input"],
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}]}],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}]}],
StyleBox["=",
"Input"],
RowBox[{
RowBox[{
RowBox[{
StyleBox["1",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["V\[EAcute]g\[UDoubleDot]l",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["megoldjuk",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["az",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["e",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["d",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]}],
StyleBox[" ",
"Input"],
StyleBox["\[Congruent]",
"Input"],
RowBox[{
StyleBox["1",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}],
StyleBox[" ",
"Input"],
RowBox[{
StyleBox["kongruenci\[AAcute]t",
"Input",
FontWeight->"Plain"],
StyleBox[".",
"Input"],
StyleBox["\[IndentingNewLine]",
"Input"],
StyleBox["Ezut\[AAcute]n",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["a",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"], "C",
RowBox[{"(",
StyleBox["x",
FontSlant->"Italic"], ")"}], " ",
"k\[OAcute]dol\[OAcute]f\[UDoubleDot]ggv\[EAcute]ny\[UDoubleDot]\
nk", " ", "legyen", " ", "a", " ",
RowBox[{"C", " ", ":",
RowBox[{
StyleBox["x",
FontSlant->"Italic"], "\[RightArrow]", " ",
RowBox[{
StyleBox["y",
FontSlant->"Italic"], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"],
StyleBox["e",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]], " ",
RowBox[{
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], ".",
"\[IndentingNewLine]", "A"}], " ",
"dek\[OAcute]dol\[OAcute]f\[UDoubleDot]ggv\[EAcute]ny",
" ", "D",
RowBox[{"(",
StyleBox["y",
FontSlant->"Italic"], ")"}], " ", "amire", " ",
RowBox[{"D", ":",
RowBox[{
StyleBox["y",
FontSlant->"Italic"], "\[RightArrow]",
RowBox[{
RowBox[{
SuperscriptBox[
StyleBox["y",
FontSlant->"Italic"],
StyleBox["d",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]], ".", " ", "Ezt"}], " ",
"\[UAcute]gy", " ",
"bizony\[IAcute]tjuk"}]}]}]}]}]}]}]}]}]}], ",",
RowBox[{
RowBox[{
RowBox[{"hogy", " ", "bel\[AAcute]tjuk", " ", "az", " ",
SuperscriptBox[
StyleBox["y",
FontSlant->"Italic"],
StyleBox["d",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]]}], "\[Congruent]",
RowBox[{
StyleBox["x",
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontFamily->"Times New Roman"], " "}]],
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "kongruencia", " ", "igaz",
" ",
RowBox[{"volt\[AAcute]t", ".", "\[IndentingNewLine]",
SuperscriptBox[
StyleBox["y",
FontSlant->"Italic"],
StyleBox["d",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]]}]}], "\[Congruent]",
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"],
StyleBox["e",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]], ")"}],
StyleBox["d",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]]}], "=",
RowBox[{
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"],
RowBox[{
RowBox[{
StyleBox["h",
FontFamily->"Times New Roman"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["\[CurlyPhi]",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman"],
StyleBox["n",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman"]}]}],
StyleBox["+",
FontFamily->"Times New Roman"],
StyleBox["1",
FontFamily->"Times New Roman"]}]], "=",
RowBox[{
RowBox[{
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"],
RowBox[{"\[CurlyPhi]",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]], ")"}],
StyleBox["h",
FontFamily->"Times New Roman"]], " ",
StyleBox["x",
FontSlant->"Italic"]}], " ", "\[Congruent]",
RowBox[{
RowBox[{
StyleBox["x",
FontSlant->"Italic"],
StyleBox[
RowBox[{
StyleBox[" ",
FontFamily->"Times New Roman"], " "}]],
RowBox[{
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], ".", " ", "Vagyis"}], " ",
"D",
RowBox[{"(",
StyleBox["y",
FontSlant->"Italic"], ")"}], " ", "t\[EAcute]nyleg", " ",
"a", " ", \
\(dek\[OAcute]dol\[OAcute]f\[UDoubleDot]ggv\[EAcute]ny . \[IndentingNewLine]C\
\),
RowBox[{"(",
StyleBox["x",
FontSlant->"Italic"], ")"}]}],
"-", \(et\ nyilv\[AAcute]noss\[AAcute]gra\ hozva\ b\[AAcute]rki\
\ tud\ nek\[UDoubleDot]nk\ k\[OAcute]dolt\ \[UDoubleDot]zenetet\ k\
\[UDoubleDot]ldeni\)}]}]}]}],
",", \(\[AAcute]m\ dek\[OAcute]dolni\ csak\ mi\ tudjuk\ azt\),
",", \(mivel\ a\ dek\[OAcute]dol\[OAcute]f\[UDoubleDot]ggv\[EAcute]ny\ \
param\[EAcute]tereit\ m\[AAcute]sok\ nem\ tudj\[AAcute]k\ \
kisz\[AAcute]molni\), ",",
RowBox[{
RowBox[{
"ahhoz", " ", "ugyanis", " ", "faktoriz\[AAcute]lni", " ",
"k\[EAcute]ne", " ",
StyleBox["n",
FontSlant->"Italic"]}],
"-", \(et . \ V\[EAcute]g\[UDoubleDot]l\ egy\ megjegyz\[EAcute]s\)}],
",", " ", \(hogy\ ez\ csak\ \[UAcute]gy\ haszn\[AAcute]lhat\[OAcute]\),
",", " ",
RowBox[{
RowBox[{
"ha", " ", "az", " ", "elk\[UDoubleDot]ldeni", " ",
"k\[IAcute]v\[AAcute]nt", " ",
StyleBox["x",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "relat\[IAcute]v",
" ", "pr\[IAcute]m", " ",
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["-",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"], \(hez . \
Ezt\ megtehetj\[UDoubleDot]k\ pl . \ \[UAcute]gy\)}], ",", " ",
RowBox[{
RowBox[{"hogy", " ",
StyleBox["x",
FontSlant->"Italic"]}],
"-", \(hez\ hozz\[AAcute]vesz\[UDoubleDot]nk\ egy\ utols\[OAcute]\ sz\
\[AAcute]mjegyet\ \[UAcute]gy\)}], ",", " ",
RowBox[{
RowBox[{"hogy", " ", "a", " ", "kapott", " ",
RowBox[{
StyleBox["x",
FontSlant->"Italic"], "'"}], " ", "sz\[AAcute]mra", " ",
RowBox[{"(",
RowBox[{
RowBox[{
StyleBox["x",
FontSlant->"Italic"], "'"}], ",",
StyleBox["n",
FontSlant->"Italic"]}], ")"}]}],
"=", \(1\ \(\(teljes\[UDoubleDot]lj\[ODoubleDot]n\)\(.\)\)\)}]}]], \
"Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["6. Mik azok a pr\[IAcute]mtesztek \[EAcute]s mi\
\[EAcute]rt van sz\[UDoubleDot]ks\[EAcute]g r\[AAcute]juk?",
FontSize->18]], "Section",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
A pr\[IAcute]mtesztek olyan algoritmusok, melyekkel nagyon nagy \
sz\[AAcute]mokr\[OAcute]l is gyorsan el lehet d\[ODoubleDot]nteni, hogy pr\
\[IAcute]mek-e vagy sem. Ezekre az\[EAcute]rt kell k\[UDoubleDot]l\
\[ODoubleDot]n m\[OAcute]dszereket kidolgozni, mert jelen ismereteink szerint \
egy nagyon nagy sz\[AAcute]m pr\[IAcute]mt\[EAcute]nyez\[ODoubleAcute]s \
felbont\[AAcute]s\[AAcute]t (kanonikus alak) nem lehet r\[ODoubleDot]vid id\
\[ODoubleAcute] alatt meg\[AAcute]llap\[IAcute]tani, \[EAcute]s mint l\
\[AAcute]ttuk a nagy pr\[IAcute]mekre sz\[UDoubleDot]ks\[EAcute]g van a \
titkos\[IAcute]t\[AAcute]si m\[OAcute]dszerekn\[EAcute]l.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
Pr\[IAcute]mtesztek: Mind a n\[EAcute]gy esetben a pr\[IAcute]mek valamely \
tulajdons\[AAcute]g\[AAcute]t felhaszn\[AAcute]lva pr\[OAcute]b\[AAcute]lunk \
meg elj\[AAcute]r\[AAcute]st adni egy sz\[AAcute]m pr\[IAcute]m \
volt\[AAcute]nak ellen\[ODoubleAcute]rz\[EAcute]s\[EAcute]re. Ehhez el\
\[ODoubleAcute]sz\[ODoubleDot]r az elm\[EAcute]leti h\[AAcute]tteret \
ismertetj\[UDoubleDot]k, majd fel\[EAcute]p\[IAcute]tj\[UDoubleDot]k az \
algoritmust l\[EAcute]p\[EAcute]senk\[EAcute]nt \[EAcute]s v\[EAcute]g\
\[UDoubleDot]l elemezz\[UDoubleDot]k annak eredm\[EAcute]ny\[EAcute]t.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["1. A Lucas-Lehmer teszt:",
FontWeight->"Bold"]], "Subtitle"],
Cell[BoxData[
RowBox[{
RowBox[{"-",
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["\[CapitalAAcute]ll\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":",
RowBox[{
RowBox[{"Ha", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox["-",
FontFamily->"Times New Roman"],
StyleBox["1",
FontFamily->"Times New Roman"]}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}]}]}], ",",
RowBox[{
RowBox[{
RowBox[{"de", " ",
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["-",
FontWeight->"Plain"],
RowBox[{
StyleBox["1",
FontWeight->"Plain"], " ", "minden", " ",
StyleBox["q",
FontSlant->"Italic"], " ",
"pr\[IAcute]moszt\[OAcute]j\[AAcute]ra", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
FractionBox[
RowBox[{"(",
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}], ")"}],
StyleBox["q",
FontSlant->"Italic"]]]}]}], "\[NotCongruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{"akkor",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["n",
FontSlant->"Italic"], " ", \(\(pr\[IAcute]m\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{"Ha", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}]}]}], ",",
RowBox[{
RowBox[{
RowBox[{"akkor", " ",
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}], "|",
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox["-",
"Input"],
RowBox[{
StyleBox["1.",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["Legyen",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
FractionBox[
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}],
RowBox[{
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]]}]}]}], "=",
RowBox[{
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ".", " ", "Ha"}], " ",
StyleBox["q",
FontSlant->"Italic"], " ", "a", " ",
StyleBox["k",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "egy", " ",
"pr\[IAcute]moszt\[OAcute]ja"}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
FractionBox[
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}],
StyleBox["q",
FontSlant->"Italic"]]]}], "\[Congruent]",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
FractionBox[
RowBox[{
StyleBox["k",
FontSlant->"Italic"], " ",
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontFamily->"Terminal",
FontSlant->"Italic"]}],
StyleBox["q",
FontSlant->"Italic"]]], "\[Congruent]",
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}]], ")"}],
FractionBox[
StyleBox["k",
FontSlant->"Italic"],
StyleBox["q",
FontSlant->"Italic"]]], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], ".", " ", "Ez"}], " ",
"ellentmond", " ", "az", " ", "\[AAcute]ll\[IAcute]t\[AAcute]s",
" ", "felt\[EAcute]teleinek"}]}], ",",
RowBox[{"azaz", " ",
StyleBox["k",
FontSlant->"Italic"], " ", "csak", " ", "1", " ", "lehet"}], ",",
RowBox[{
RowBox[{"\[EAcute]s", " ", "\[IAcute]gy", " ",
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}], "=",
RowBox[{
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", \(1. Az\ Euler\), "-",
RowBox[{"t\[EAcute]tel", " ", "szerint", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{"\[CurlyPhi]",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]]}]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "\[EAcute]s", " ", "azt",
" ", "is", " ", "l\[AAcute]ttuk", " ", "kor\[AAcute]bban"}]}]}],
",",
RowBox[{
RowBox[{"hogy", " ", "ekkor", " ",
SubscriptBox["ord",
StyleBox["n",
FontSlant->"Italic"]],
StyleBox["a",
FontSlant->"Italic"]}],
StyleBox["|",
FontSlant->"Italic"],
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"]}]}]}],
StyleBox[",",
"Input"],
RowBox[{
RowBox[{
StyleBox["ez\[EAcute]rt",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["jelen",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["esetben",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"]}]}],
StyleBox["\[GreaterEqual]",
"Input"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox["-",
"Input"],
RowBox[{
StyleBox["1",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox[\(ad\[OAcute]dik . \ De\),
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["a",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["defin\[IAcute]ci\[OAcute]ja",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["szerint",
"Input",
FontWeight->"Plain"],
StyleBox[
RowBox[{
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"]}]],
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"]}]}]}],
StyleBox["\[LessEqual]",
"Input"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox["-",
FontSlant->"Italic"],
StyleBox["1",
FontSlant->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["vagyis",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[")",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Italic"]}]}],
StyleBox["=",
"Input"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"],
StyleBox["-",
"Input"],
StyleBox["1",
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["azaz",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"],
StyleBox[\(\(pr\[IAcute]msz\[AAcute]m\)\(.\)\),
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
StyleBox["Az algoritmus",
FontWeight->"Bold"],
":"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"El\[ODoubleAcute]sz\[ODoubleDot]r k\[EAcute]sz\[IAcute]t\[UDoubleDot]nk \
egy list\[AAcute]t ",
StyleBox["n",
FontSlant->"Italic"],
"-1 pr\[IAcute]moszt\[OAcute]ib\[OAcute]l, ahol az input az ",
StyleBox["n",
FontSlant->"Italic"],
" (!!!) sz\[AAcute]m:"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(Pr\[IAcute]moszt\[OAcute]k[n_] :=
First[Transpose[FactorInteger[n - 1]]]\)], "Input"],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"A", " ", "f\[UDoubleDot]ggv\[EAcute]ny", " ", "megkapja",
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["n",
FontSlant->"Italic"]}], "-",
RowBox[{\(et\ . \ El\[ODoubleAcute]sz\[ODoubleDot]r\), " ",
"k\[EAcute]pezi", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-",
RowBox[{
"1", " ", \(pr\[IAcute]mfelbont\[AAcute]s\[AAcute]t . \ Ez\), " ",
RowBox[{"{",
RowBox[{
RowBox[{"{",
RowBox[{
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "1"], ",", \(\[Alpha]\_1\)}],
"}"}], ",", "...", ",",
RowBox[{"{",
RowBox[{
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "r"], ",", \(\[Alpha]\_r\)}],
"}"}]}], "}"}], " ", "alak\[UAcute]", " ", "lesz"}]}], ",",
RowBox[{
RowBox[{
RowBox[{"ahol", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "1"}], "=",
RowBox[{
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
RowBox[{
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "i"], \(\[Alpha]\_i\)], ".", " ",
"Ebb\[ODoubleAcute]l"}], " ", "azt\[AAcute]n", " ",
"kiv\[AAcute]logatja", " ",
StyleBox["n",
FontSlant->"Italic"]}]}],
"-", \(1\ \(\(pr\[IAcute]moszt\[OAcute]it\)\(.\)\)\)}]}]}]], "Text",\
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(Pr\[IAcute]moszt\[OAcute]k[\((2*5*5*7*43*43*53)\) + 1]\)], "Input"],
Cell[BoxData[
RowBox[{\(Ezek\ ut\[AAcute]n\ csak\ annyi\ kell\ m\[EAcute]g\), ",",
RowBox[{
"hogy", " ", "az", " ", "\[IAcute]gy", " ", "kapott", " ", "lista", " ",
"minden", " ",
StyleBox[
SubscriptBox[
StyleBox["q",
FontWeight->"Plain",
FontSlant->"Italic"], "i"],
FontWeight->"Bold",
FontSlant->"Italic"], " ", "elem\[EAcute]re", " ",
"megn\[EAcute]zz\[UDoubleDot]k", " ", "az", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
FractionBox[
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}],
StyleBox[
SubscriptBox[
StyleBox["q",
FontWeight->"Plain",
FontSlant->"Italic"], "i"],
FontWeight->"Bold",
FontSlant->"Italic"]]], " ", "sz\[AAcute]mot", " ", "modulo",
" ",
StyleBox["n",
FontSlant->"Italic"]}],
",", \(gyorshatv\[AAcute]nyoz\[AAcute]ssal . \
Ha\ ezeket\ az\ eredm\[EAcute]nyeket\ t\[AAcute]roljuk\ egy\ list\
\[AAcute]ban\), ",", \(akkor\ az\ \[AAcute]ll\[IAcute]t\[AAcute]s\ szerint\),
",", " ", \(ha\ ebben\ nem\ szerepel\ az\ 1 -
es\ \[EAcute]s\ teljes\[UDoubleDot]l\), ",",
RowBox[{
RowBox[{"hogy", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
StyleBox["n",
FontSlant->"Italic"], " ", \(pr\[IAcute]m . \ Az\), " ",
StyleBox["a",
FontSlant->"Italic"], " ", "sz\[AAcute]mot", " ",
"v\[EAcute]letlen\[UDoubleDot]l", " ", "v\[AAcute]lasztjuk", " ",
"2", " ", "\[EAcute]s", " ",
StyleBox["n",
FontSlant->"Italic"]}],
"-", \(1\ \(\(k\[ODoubleDot]z\[ODoubleDot]tt\)\(.\)\(\ \)\)\)}]}]], \
"Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(LucasLehmer1[n_] :=
Module[\[IndentingNewLine]{Pr\[IAcute]moszt\[OAcute]k, a,
eredmenyek}, \[IndentingNewLine]Pr\[IAcute]moszt\[OAcute]k[n] :=
First[Transpose[FactorInteger[n - 1]]]; \[IndentingNewLine]a =
Random[Integer, {2,
n - 1}]; \[IndentingNewLine]eredmenyek := \(PowerMod[
a, \(n - 1\)\/#, n] &\) /@
Pr\[IAcute]moszt\[OAcute]k[n]; \[IndentingNewLine]If[
PowerMod[a, n - 1, n] \[Equal] 1 &&
MemberQ[eredmenyek, 1] \[Equal] False,
Print[n, "\< pr\[IAcute]msz\[AAcute]m\>"],
Print[n, "\<-r\[ODoubleAcute]l nem bizonyosodott be,hogy \
pr\[IAcute]m\>"]]\[IndentingNewLine]]\)], "Input"],
Cell[BoxData[
\(LucasLehmer1[1000003]\)], "Input"],
Cell[BoxData[
\(Timing[LucasLehmer1[1000003]]\)], "Input"],
Cell[BoxData[
RowBox[{\(Az\ \[IAcute]gy\ kapott\ algoritmus\ h\[AAcute]tr\[AAcute]nya\),
",", \(hogy\ az\ az\ \[AAcute]ll\[IAcute]t\[AAcute]s\),
",", \(mely\ az\ elm\[EAcute]leti\ alapj\[AAcute]t\ adja\ \
ford\[IAcute]tva\ nem\ igaz\), ",",
RowBox[{"vagyis", " ", "ha", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]m"}],
",", \(abb\[OAcute]l\ m\[EAcute]g\ nem\ k\[ODoubleDot]vetkezik\), ",",
RowBox[{
RowBox[{
"hogy", " ", "az", " ", "eredm\[EAcute]nylist\[AAcute]ban", " ",
"nincs", " ", \(egyes . \ P\[EAcute]ld\[AAcute]ul\), " ",
StyleBox["n",
FontSlant->"Italic"]}], "=",
RowBox[{
RowBox[{"7", "-",
RowBox[{"re", " ", "ha", " ",
StyleBox["a",
FontSlant->"Italic"]}]}], "=", "2"}]}], ",",
RowBox[{
RowBox[{
RowBox[{"akkor", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "1"}],
"=", \(6 = \(2*3\ \[EAcute]s\ 2\^\(6\/2\) =
8 \[Congruent] 1\ \ \((7)\)\)\)}],
",", \(teh\[AAcute]t\ lesz\ 1 -
es\ a\ \(\(list\[AAcute]ban\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
\[CapitalUAcute]gy tehetj\[UDoubleDot]k hat\[EAcute]konyabb\[AAcute] a \
tesztet ha t\[ODoubleDot]bb a sz\[AAcute]mmal is \
elv\[EAcute]gezz\[UDoubleDot]k:\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"Az algoritmus ezen jav\[IAcute]t\[AAcute]s\[AAcute]ban k\[EAcute]t input \
van: ",
StyleBox["n",
FontSlant->"Italic"],
" a sz\[AAcute]m amir\[ODoubleAcute]l meg akarjuk tudni, hogy \
pr\[IAcute]m-e, ",
StyleBox["k",
FontSlant->"Italic"],
" pedig az a sz\[AAcute]m ah\[AAcute]nyszor elv\[EAcute]gezz\[UDoubleDot]k \
a tesztet. Minthogy modulo ",
StyleBox["n",
FontSlant->"Italic"],
" csak ",
StyleBox["n",
FontSlant->"Italic"],
"-1 sz\[AAcute]m van, ez\[EAcute]rt ",
StyleBox["k",
FontSlant->"Italic"],
"\[LessEqual]",
StyleBox["n",
FontSlant->"Italic"],
"-1 v\[AAcute]laszt\[AAcute]ssal el\[EAcute]g dolgozni. Min\[EAcute]l \
nagyobb ",
StyleBox["k",
FontSlant->"Italic"],
" \[EAcute]rt\[EAcute]ke ann\[AAcute]l val\[OAcute]sz\[IAcute]n\
\[UDoubleAcute]bb, hogy ha ",
StyleBox["n",
FontSlant->"Italic"],
" pr\[IAcute]m, akkor az algoritmus ezt igazolja. Azt, hogy mely ",
StyleBox["k",
FontSlant->"Italic"],
" darab sz\[AAcute]mra fogja kisz\[AAcute]molni a hatv\[AAcute]nyokat egy k\
\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute] elemekb\
\[ODoubleAcute]l \[AAcute]ll\[OAcute], ",
StyleBox["k",
FontSlant->"Italic"],
" hossz\[UAcute], v\[EAcute]letlen lista hat\[AAcute]rozza majd meg. Ennek \
minden egyes elem\[EAcute]re elv\[EAcute]gzi az el\[ODoubleAcute]z\
\[ODoubleAcute] elj\[AAcute]r\[AAcute]st \[EAcute]s a v\[EAcute]g\[EAcute]n \
egy indik\[AAcute]tor list\[AAcute]ban t\[AAcute]rolja, hogy az egyes lefut\
\[AAcute]soknak mi lett az eredm\[EAcute]nye. \[CapitalIAcute]gy a \
v\[EAcute]g\[EAcute]n el\[EAcute]g megn\[EAcute]zni, hogy az \
indik\[AAcute]tor list\[AAcute]ban van-e 1-es, amely ",
StyleBox["n",
FontSlant->"Italic"],
" pr\[IAcute]ms\[EAcute]g\[EAcute]t igazolja. Ha nincs, akkor ez \
m\[EAcute]g nem jelenti azt, hogy ",
StyleBox["n",
FontSlant->"Italic"],
" \[ODoubleDot]sszetett, csup\[AAcute]n azt, hogy az algoritmus nem bizony\
\[IAcute]totta ",
StyleBox["n",
FontSlant->"Italic"],
" pr\[IAcute]m volt\[AAcute]t. "
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(LucasLehmer2[n_, k_] :=
Module[\[IndentingNewLine]{pr\[IAcute]moszt\[OAcute]k, a, listak,
indikator,
randomlist}, \[IndentingNewLine]indikator = {}; \
\[IndentingNewLine]randomlist[m_, j_] :=
Module[\[IndentingNewLine]{A}, \[IndentingNewLine]If[j < m - 1,
A = {Random[Integer, {2, m - 1}]}; \[IndentingNewLine]While[\
Length[A] < j, \[IndentingNewLine]A =
Union[A, {\
Random[Integer, {2,
m - 1}]\ }]]; \[IndentingNewLine]Return[
A], \(Print[j, "\< nem kisebb,mint \>",
m - 1];\)]\[IndentingNewLine]]; \[IndentingNewLine]a =
randomlist[n, k]; \[IndentingNewLine]pr\[IAcute]moszt\[OAcute]k :=
First[Transpose[
FactorInteger[
n - 1]]]; \[IndentingNewLine]listak = \(PowerMod[#, \(n - 1\)\
\/pr\[IAcute]moszt\[OAcute]k, n] &\) /@ a; \[IndentingNewLine]For[l = 1,
l < Length[listak] + 1, \(l++\),
If[PowerMod[a[\([l]\)], n - 1, n] \[Equal] 1 &&
MemberQ[listak[\([l]\)], 1] \[Equal] False,
AppendTo[indikator, 1],
AppendTo[indikator, 0]]]; \[IndentingNewLine]If[
MemberQ[indikator, 1], Print[n, "\< pr\[IAcute]msz\[AAcute]m\>"],
Print[n, "\<-r\[ODoubleAcute]l nem bizonyosodott be,hogy \
pr\[IAcute]m\>"]]\[IndentingNewLine]]\)], "Input"],
Cell[BoxData[
\(LucasLehmer2[100000007, 20]\)], "Input"],
Cell[TextData[{
"Ennek a tesztnek azonban van egy \[OAcute]ri\[AAcute]si h\[AAcute]tr\
\[AAcute]nya: ahhoz hogy ",
StyleBox["n",
FontSlant->"Italic"],
"-r\[ODoubleAcute]l eld\[ODoubleDot]nts\[UDoubleDot]k, hogy pr\[IAcute]m-e, \
",
StyleBox["n",
FontSlant->"Italic"],
"-1",
"-et faktoriz\[AAcute]lnunk kell. Ezt a be\[EAcute]p\[IAcute]tett f\
\[UDoubleDot]ggv\[EAcute]ny gyorsan elv\[EAcute]gzi ugyan, de csak nem t\
\[UAcute]l nagy sz\[AAcute]mokra. A c\[EAcute]l pedig pont az lenne, hogy \
nagyon nagy sz\[AAcute]mokra is jegyen j\[OAcute] algoritmusunk."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["2. A Solovay-Strassen teszt:",
FontWeight->"Bold"]], "Subtitle"],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{"Legyen", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["m",
FontSlant->"Italic"]}], ")"}]}]}]}], "=",
RowBox[{"1.", "Az", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "kvadratikus",
" ", "marad\[EAcute]k", " ", "modulo", " ",
StyleBox["m",
FontSlant->"Italic"]}]}], ",",
RowBox[{
RowBox[{"ha", " ",
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"], "2"]}], "\[Congruent]",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}],
"-", \(nek\ l\[EAcute]tezik\ \
\(\(megold\[AAcute]sa\)\(.\)\)\)}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{"Ha", " ",
StyleBox["p",
FontSlant->"Italic"]}], ">", \(2\ pr\[IAcute]m\)}]}]}], ",",
RowBox[{
RowBox[{
"akkor", " ", "a", " ", "Legendre", " ", "szimb\[OAcute]lumot", " ",
"defin\[AAcute]juk", " ", "az", " ", "al\[AAcute]bbi", " ",
RowBox[{"m\[OAcute]don", ":", "\[IndentingNewLine]",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}]}], "=",
TagBox[
RowBox[{
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
StyleBox[GridBox[{
{
RowBox[{"1", " ", "ha", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "kvadratikus", " ",
"marad\[EAcute]k"}]},
{GridBox[{
{
RowBox[{\(-1\), " ", "ha", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "nem", " ",
"kvadratikus", " ", "marad\[EAcute]k"}]},
{
RowBox[{
RowBox[{"0", " ", "ha", " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{"0", " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}]}
}]}
}],
ShowAutoStyles->True]}],
(#&)]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{"-", " ",
StyleBox["A",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["Legendre",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["szimb\[OAcute]lum",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["tulajdons\[AAcute]gai",
FontWeight->"Bold"], ":", "\[IndentingNewLine]",
RowBox[{
RowBox[{
StyleBox["a",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
FractionBox[
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}], "2"]], " ",
RowBox[{"(",
StyleBox["p",
FontFamily->"Times New Roman",
FontSlant->"Italic"], ")"}]}]}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
RowBox[{
StyleBox["b",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"], " ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}],
RowBox[{"(",
FractionBox[
StyleBox["b",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
RowBox[{"(",
FractionBox[
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ",
StyleBox["b",
FontSlant->"Italic"]}],
StyleBox["p",
FontSlant->"Italic"]], ")"}],
" ", \((Megjegyz\[EAcute]s : \
ez\ t\[ODoubleDot]bbt\[EAcute]nyez\[ODoubleAcute]s\ szorzatra\ \
is\ igaz)\)}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
RowBox[{
RowBox[{
StyleBox["c",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"], " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{
StyleBox["b",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}], " ",
StyleBox["\[Implies]",
"Subsection"],
StyleBox[" ",
"Input"],
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{"(",
FractionBox[
StyleBox["b",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
StyleBox["d",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Bold"], " "}]],
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["p",
FontSlant->"Italic"]}], ")"}]}], "=",
RowBox[{
RowBox[{"1", " ",
StyleBox["\[Implies]",
"Subsection"],
StyleBox[" ",
"Input"],
RowBox[{"(",
FractionBox[
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "2"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
RowBox[{"1", " ", "\[EAcute]s", " ",
RowBox[{"(",
FractionBox[
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "2"], " ",
StyleBox["b",
FontSlant->"Italic"]}],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{"(",
FractionBox[
StyleBox["b",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}]}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
RowBox[{
StyleBox["e",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Bold"], " "}]],
RowBox[{"(",
FractionBox["1",
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
RowBox[{"1", " ", "\[EAcute]s", " ",
RowBox[{"(",
FractionBox[\(-1\),
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
RowBox[{"(",
FractionBox[
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}],
StyleBox["p",
FontSlant->"Italic"]], ")"}], "=",
RowBox[{
SuperscriptBox[\((\(-1\))\),
FractionBox[
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}], "2"]], "=",
TagBox[
RowBox[{
TagBox[
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
(#&)],
StyleBox[GridBox[{
{
RowBox[{
RowBox[{"1", " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"]}], "=",
RowBox[{
RowBox[{"4", " ",
StyleBox["k",
FontFamily->"Times New Roman",
FontSlant->"Italic"]}], " ", "+", "1"}]}]},
{
RowBox[{
RowBox[{\(-1\), " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"]}], "=",
RowBox[{
RowBox[{"4", " ",
StyleBox["k",
FontSlant->"Italic"]}], "-", "1"}]}]}
}],
ShowAutoStyles->True]}],
(#&)]}]}]}]}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
RowBox[{
StyleBox["f",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Bold"], " "}]],
RowBox[{"(",
FractionBox["2",
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
SuperscriptBox[\((\(-1\))\),
FractionBox[
RowBox[{
SuperscriptBox[
StyleBox["p",
FontSlant->"Italic"], "2"], "-", "1"}], "8"]], "=",
TagBox[
RowBox[{
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
StyleBox[GridBox[{
{
RowBox[{
RowBox[{"1", " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"]}],
"\[Congruent]", \(\(\[PlusMinus]1\)\ \ \((8)\)\)}]},
{
RowBox[{
RowBox[{\(-1\), " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"]}],
"\[Congruent]", \(\(\[PlusMinus]3\)\ \ \((8)\)\)}]}
}],
ShowAutoStyles->True]}],
(#&)]}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
RowBox[{
StyleBox["g",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[
RowBox[{
StyleBox[" ",
FontWeight->"Bold"],
" "}]], \((Gauss\ kvadratikus\ reciprocit\[AAcute]si\ t\
\[EAcute]tele)\)}], ":", " ",
RowBox[{"Ha", " ",
StyleBox["p",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
StyleBox["q",
FontSlant->"Italic"], " ",
"k\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute]",
" ", "p\[AAcute]ratlan", " ", "pr\[IAcute]mek"}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
RowBox[{"(",
FractionBox[
StyleBox["p",
FontSlant->"Italic"],
StyleBox["q",
FontSlant->"Italic"]], ")"}],
RowBox[{"(",
FractionBox[
StyleBox["q",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], "=",
SuperscriptBox[\((\(-1\))\),
RowBox[{
FractionBox[
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}], "2"],
FractionBox[
RowBox[{
StyleBox["q",
FontSlant->"Italic"], "-", "1"}], "2"]}]]}], ",", " ",
RowBox[{
RowBox[{"vagy", " ", "m\[AAcute]sk\[EAcute]pp", " ",
RowBox[{"(",
FractionBox[
StyleBox["p",
FontSlant->"Italic"],
StyleBox["q",
FontSlant->"Italic"]], ")"}]}], "=",
TagBox[
RowBox[{
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
StyleBox[GridBox[{
{
RowBox[{
RowBox[{
RowBox[{"-",
RowBox[{"(",
FractionBox[
StyleBox["q",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}]}], " ", "ha",
" ",
StyleBox["p",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
StyleBox["q",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Plain"], "is", " ", "4",
StyleBox["k",
FontSlant->"Italic"]}],
"-", \(1\ alak\[UAcute]\)}]},
{
RowBox[{
RowBox[{
RowBox[{"(",
FractionBox[
StyleBox["q",
FontSlant->"Italic"],
StyleBox["p",
FontSlant->"Italic"]], ")"}], " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"],
StyleBox[" ",
FontSlant->"Italic"], "\[EAcute]s", " ",
StyleBox["q",
FontSlant->"Italic"], " ", "legal\[AAcute]bb",
" ", "egyike", " ", "4",
StyleBox["k",
FontSlant->"Italic"]}],
"+", \(1\ alak\[UAcute]\)}]}
}],
ShowAutoStyles->True]}],
(#&)]}]}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"Az", " ",
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"], "2"]}], "\[Congruent]",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}], " ", "konguencia", " ",
"megoldhat\[OAcute]s\[AAcute]g\[AAcute]t", " ", "jellemzi", " ", "a",
" ", "Legendre", " ", "szimb\[OAcute]lum",
" ", \(\(\[EAcute]rt\[EAcute]ke\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], "\[Element]",
StyleBox["\[DoubleStruckCapitalN]",
"Section"]}]}]}],
StyleBox[",",
"Input"],
StyleBox[" ",
FontFamily->"Times New Roman"],
RowBox[{
StyleBox["m",
FontSlant->"Italic"], ">", \(1\ p\[AAcute]ratlan\)}], ",",
RowBox[{
StyleBox["m",
FontSlant->"Italic"], "=",
RowBox[{
RowBox[{
RowBox[{
RowBox[{
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "1"],
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "2"]}], "..."}],
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "r"], " ", "nem", " ",
"felt\[EAcute]tlen\[UDoubleDot]l", " ",
"k\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute]",
" ", "pozit\[IAcute]v", " ", "pr\[IAcute]mek", " ", "szorzata",
" ", "\[EAcute]s", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["m",
FontSlant->"Italic"]}], ")"}]}], "=",
RowBox[{
RowBox[{
"1.", "Ekkor", " ", "a", " ", "Jacobi", " ", "szimb\[OAcute]lum",
" ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{\(\[Product]\+\(i = 1\)\%r\),
RowBox[{
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
SubscriptBox[
StyleBox["p",
FontSlant->"Italic"], "i"]], ")"}], " ",
"."}]}]}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"], "2"], "\[Congruent]",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}], " ",
"megoldhat\[OAcute]s\[AAcute]ga", " ", "nem", " ",
"jellemezhet\[ODoubleAcute]", " ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}],
" ", \(\(seg\[IAcute]ts\[EAcute]g\[EAcute]vel!!\)!\)}]}]}]}], "\
\[IndentingNewLine]",
RowBox[{
RowBox[{
RowBox[{"Ha", " ",
SuperscriptBox[
StyleBox["x",
FontSlant->"Italic"], "2"]}], "\[Congruent]",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}],
"-", \(nek\ van\ megold\[AAcute]sa\)}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "=", "1"}],
",", \(de\ ford\[IAcute]tva\ nem\ felt\[EAcute]tlen\[UDoubleDot]l\ igaz \
. \ Azokat\ a\ sz\[AAcute]mokat\), ",",
RowBox[{
RowBox[{"melyekre", " ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "=", "1"}], ",",
RowBox[{"de",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["a",
FontSlant->"Italic"], " ", "nem", " ", "kvadratikus", " ",
"marad\[EAcute]k"}], ",",
" ", \(\[AAcute]ln\[EAcute]gyzetnek\ \
\(\(nevezz\[UDoubleDot]k\)\(.\)\)\)}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{"-",
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["A",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["Jacobi",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["szimb\[OAcute]lum",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["tulajdons\[AAcute]gai",
FontWeight->"Bold"], ":", "\[IndentingNewLine]", " ",
RowBox[{
RowBox[{
RowBox[{
StyleBox["a",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"], " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[Congruent]",
RowBox[{
StyleBox["b",
FontSlant->"Italic"], " ",
RowBox[{"(",
StyleBox["m",
FontSlant->"Italic"], ")"}]}]}], " ",
StyleBox["\[Implies]",
"Subsection"],
StyleBox[" ",
"Input"],
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}]}]}], "=",
RowBox[{"(",
FractionBox[
StyleBox["b",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
StyleBox["b",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{"(",
FractionBox[
RowBox[{
StyleBox["a",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["b",
FontSlant->"Italic"]}],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "=",
RowBox[{
RowBox[{
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}],
RowBox[{"(",
FractionBox[
StyleBox["b",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}], " ", "\[EAcute]s", " ",
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["m",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["n",
FontSlant->"Italic"]}]], ")"}]}], "=",
RowBox[{
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}],
RowBox[{"(",
FractionBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["n",
FontSlant->"Italic"]], ")"}],
" ", \((Megjegyz\[EAcute]s : \
ez\ t\[ODoubleDot]bbt\[EAcute]nyez\[ODoubleAcute]s\ szorzatra\
\ is\ igaz)\)}]}]}]}], "\[IndentingNewLine]",
RowBox[{
StyleBox[
RowBox[{" ",
StyleBox[" ",
FontWeight->"Bold"]}]],
RowBox[{
RowBox[{
StyleBox["c",
FontWeight->"Bold"],
StyleBox[".",
FontWeight->"Bold"], " ",
RowBox[{"(",
FractionBox[\(-1\),
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], "=",
TagBox[
RowBox[{
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
RowBox[{
RowBox[{
StyleBox[GridBox[{
{
RowBox[{
RowBox[{"1", " ", "ha",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["m",
FontSlant->"Italic"]}],
"\[Congruent]", \(1\ \ \((4)\)\)}]},
{
RowBox[{
RowBox[{\(-1\), " ", "ha", " ",
StyleBox["m",
FontSlant->"Italic"]}],
"\[Congruent]", \(\(-1\)\ \ \((4)\)\)}]}
}],
ShowAutoStyles->True],
StyleBox["\[IndentingNewLine]",
ShowAutoStyles->True],
StyleBox[" ",
ShowAutoStyles->True],
RowBox[{
StyleBox["d",
ShowAutoStyles->True,
FontWeight->"Bold"],
StyleBox[".",
ShowAutoStyles->True,
FontWeight->"Bold"],
StyleBox[" ",
ShowAutoStyles->True,
FontWeight->"Bold"],
RowBox[{"(",
FractionBox["2",
StyleBox["m",
FontSlant->"Italic"]], ")"}]}]}], "=",
TagBox[
RowBox[{
StyleBox["{",
"Subtitle",
ShowAutoStyles->False],
RowBox[{
RowBox[{
StyleBox[GridBox[{
{
RowBox[{
RowBox[{"1", " ", "ha", " ",
StyleBox["m",
FontSlant->"Italic"]}],
"\[Congruent]", \
\(\(\[PlusMinus]1\)\ \ \((8)\)\)}]},
{
RowBox[{
RowBox[{\(-1\), " ", "ha", " ",
StyleBox["m",
FontSlant->"Italic"]}],
"\[Congruent]", \
\(\(\[PlusMinus]3\)\ \ \((8)\)\)}]}
}],
ShowAutoStyles->True],
StyleBox[" ",
ShowAutoStyles->True],
StyleBox["\[IndentingNewLine]",
ShowAutoStyles->True],
RowBox[{
StyleBox["e",
ShowAutoStyles->True,
FontWeight->"Bold"],
StyleBox[".",
ShowAutoStyles->True,
FontWeight->"Bold"],
StyleBox[" ",
ShowAutoStyles->True],
RowBox[{"(",
FractionBox[
StyleBox["m",
FontSlant->"Italic"],
StyleBox["n",
FontSlant->"Italic"]], ")"}]}]}], "=",
TagBox[
StyleBox[
RowBox[{"{",
StyleBox[GridBox[{
{
RowBox[{
RowBox[{
RowBox[{"-",
RowBox[{"(",
FractionBox[
StyleBox["n",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}]}], " ",
"ha", " ",
StyleBox["n",
FontSlant->"Italic"]}],
"\[Congruent]",
StyleBox["m",
FontSlant->"Italic"],
"\[Congruent]", \(\(-1\)\ \ \((4)\)\)}]},
{
RowBox[{
RowBox[{"(",
FractionBox[
StyleBox["n",
FontSlant->"Italic"],
StyleBox["m",
FontSlant->"Italic"]], ")"}], " ",
"egy\[EAcute]bk\[EAcute]nt"}]}
}],
ShowAutoStyles->True]}],
ShowAutoStyles->False],
(#&)]}]}],
(#&)]}]}],
(#&)]}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[StyleBox["- Az algoritmus:",
FontWeight->"Bold"]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{\(Az\ elj\[AAcute]r\[AAcute]s\ a\ Legendre\ szimb\[OAcute]lumra\
\ \[EAcute]p\[UDoubleDot]l\),
",", \(pontosabban\ annak\ els\[ODoubleAcute]\ tulajdons\[AAcute]g\
\[AAcute]ra . \
Ez\[UAcute]ttal\ r\[ODoubleDot]gt\[ODoubleDot]n\ \[UAcute]gy\ \
\[IAcute]rjuk\ meg\), ",",
RowBox[{
"hogy", " ", "az", " ", "input", " ", "tartalmazza", " ", "a", " ",
"teszt", " ", "lefut\[AAcute]sainak", " ", "sz\[AAcute]m\[AAcute]t",
" ", \(is . \ Legyen\), " ",
StyleBox["n",
FontSlant->"Italic"], " ", "a", " ", "sz\[AAcute]m", " ", "amit",
" ", "tesztel\[UDoubleDot]nk", " ", "\[EAcute]s", " ", "legyenek",
" ",
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "1"]}], ",",
RowBox[{
RowBox[{"...",
StyleBox[
SubscriptBox[
StyleBox["a",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox["k",
FontFamily->"Trebuchet MS",
FontWeight->"Plain",
FontSlant->"Italic"]],
FontWeight->"Bold"], " ",
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["-",
FontSlant->"Italic"],
RowBox[{
"n\[EAcute]l", " ", "kisebb", " ", "pozit\[IAcute]v",
" ", \(eg\[EAcute]szek . \ Ezeket\), " ", "megint", " ", "egy",
" ", "v\[EAcute]letlen", " ", "lista", " ", "fogja", " ",
"tartalmazni", " ", "\[EAcute]s", " ",
StyleBox["k",
FontSlant->"Italic"]}]}], ",",
RowBox[{
"azaz", " ", "a", " ", "lista", " ", "hossza", " ", "lesz", " ", "a",
" ", "m\[AAcute]sik", " ", "input", " ",
StyleBox["n",
FontSlant->"Italic"], " ", \(mellett . \ Az\), " ", "algoritmus",
" ", "ellen\[ODoubleAcute]rzi", " ", "az"}]}],
" "}], "\[IndentingNewLine]",
RowBox[{
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"],
FractionBox[
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}], "2"]], "\[Congruent]",
RowBox[{
RowBox[{"(",
FractionBox[
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"],
StyleBox["n",
FontSlant->"Italic"]], ")"}], " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}],
" ", \(kongruenci\[AAcute]kat . \ Ha\), " ", "ezek", " ",
"k\[ODoubleDot]z\[UDoubleDot]l", " ", "b\[AAcute]rmelyik", " ",
"nem", " ", "teljes\[UDoubleDot]l", " ", "az", " ", "ellentmond",
" ", "a", " ", "Legendre", " ", "szimb\[OAcute]lum", " ",
"els\[ODoubleAcute]", " ", "tulajdons\[AAcute]g\[AAcute]nak", " ",
"\[EAcute]s", " ", "\[IAcute]gy", " ",
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Times New Roman"], "\[ODoubleDot]sszetett"}]}], ",",
RowBox[{
"ekkor", " ", "a", " ", "program", " ", "ki\[IAcute]rja", " ", "ezt",
" ", "\[EAcute]s", " ", \(kil\[EAcute]p . \ Ha\), " ",
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]m"}],
",", \(akkor\ nyilv\[AAcute]n\ mindegyik\ teljes\[UDoubleDot]l . \
Nem\ tudunk\ azonban\ biztos\ eredm\[EAcute]nyt\ garant\[AAcute]lni\
\), ",", \(ugyanis\ att\[OAcute]l\), ",",
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
FontSlant->"Italic"], "\[ODoubleDot]sszetett"}],
",", \(m\[EAcute]g\ teljes\[UDoubleDot]lhet\ mindegyik\ kongruencia . \
Azonban\ bizony\[IAcute]t\[AAcute]s\ n\[EAcute]lk\[UDoubleDot]l\ \
megjegyezz\[UDoubleDot]k\),
",", \(hogy\ ennek\ a\ \
val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ge\ kisebb\), ",",
RowBox[{"mint", " ",
SuperscriptBox[\((1\/2)\),
StyleBox["k",
FontSlant->"Italic"]]}], ",",
RowBox[{"ahol", " ", "teh\[AAcute]t", " ",
StyleBox["k",
FontSlant->"Italic"], " ", "a", " ", "lefut\[AAcute]sok",
" ", \(\(sz\[AAcute]ma\)\(.\)\)}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"Az", " ",
RowBox[{"(",
FractionBox[
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"],
StyleBox["n",
FontSlant->"Italic"]], ")"}], " ", "Jacobi", " ",
"szimb\[OAcute]lumokat", " ", "a", " ", "program", " ",
"be\[EAcute]p\[IAcute]tett", " ",
"f\[UDoubleDot]ggv\[EAcute]ny\[EAcute]vel"}], ",",
RowBox[{
RowBox[{"JacobiSymbol", "[",
RowBox[{
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"], ",",
StyleBox["n",
FontSlant->"Italic"]}], "]"}], "-",
RowBox[{
"nel", " ", "fogjuk", " ", \(kisz\[AAcute]molni . \ Mivel\), " ",
"ez", " ", "p\[AAcute]ratlan", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", \(ekre\ van\ \[EAcute]rtelmezve\)}],
",",
RowBox[{
RowBox[{
"ez\[EAcute]rt", " ", "a", " ", "p\[AAcute]ros", " ", "inputot",
" ", \(kisz\[UDoubleAcute]rj\[UDoubleDot]k . \ Ha\), " ", "nem",
" ", "bizonyosodott", " ", "be", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "r\[ODoubleAcute]l"}],
",", \(hogy\ \[ODoubleDot]sszetett\), ",",
RowBox[{
"akkor", " ", "a", " ", "v\[EAcute]g\[EAcute]n", " ", "25", " ",
"tizedesjegy", " ", "pontoss\[AAcute]gig", " ", "megadjuk",
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]ms\[EAcute]g\[EAcute]nek",
" ", \(\(val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]g\[EAcute]t\
\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(SolovayStrassen[n_, k_] :=
Module[\[IndentingNewLine]{a, val, randomlist}, \[IndentingNewLine]If[
OddQ[n],
randomlist[m_, j_] :=
Module[\[IndentingNewLine]{A}, \[IndentingNewLine]If[j < m - 1,
A = {Random[Integer, {2, m - 1}]}; \[IndentingNewLine]While[\
Length[A] < j, \[IndentingNewLine]A =
Union[A, {\
Random[
Integer, {2,
m - 1}]\ }]]; \[IndentingNewLine]Return[
A], \(Print[j, "\< nem kisebb,mint \>",
m - 1];\)]\[IndentingNewLine]]; \[IndentingNewLine]a =
randomlist[n, k]; \[IndentingNewLine]val =
N[1 - \((1\/2)\)\^k, 25]; \[IndentingNewLine]If[
PowerMod[a, \(n - 1\)\/2, n] \[Equal] Mod[JacobiSymbol[a, n], n],
Print["\", n, "\< legal\[AAcute]bb \>",
val, "\< val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m\>"],
Print[n, "\< \[ODoubleDot]sszetett\>"]], \[IndentingNewLine]Print[
n, "\< p\[AAcute]ros sz\[AAcute]m.Ha 2,akkor pr\[IAcute]m,egy\
\[EAcute]bk\[EAcute]nt \[ODoubleDot]sszetett\>"]]\[IndentingNewLine]]\)], \
"Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(SolovayStrassen[100000007, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) "\[InvisibleSpace]100000007\[InvisibleSpace]" \
legal\[AAcute]bb "\[InvisibleSpace]0.99999904632568359375`25. \
\[InvisibleSpace]" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\
\[IAcute]m"\),
SequenceForm[
"A(z) ", 100000007, " legal\[AAcute]bb ", 0.99999904632568359375`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(SolovayStrassen[
447927122303800151530042525716766391990642642424582049439333041773759332\
341245372994435424019212130238123186301407332323797071155811246428305724873407\
90521257344442028966696868302096598442754894011, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) \
"\[InvisibleSpace]\
447927122303800151530042525716766391990642642424582049439333041773759332341245\
372994435424019212130238123186301407332323797071155811246428305724873407905212\
57344442028966696868302096598442754894011\[InvisibleSpace]" legal\[AAcute]bb \
"\[InvisibleSpace]0.99999904632568359375`25. \[InvisibleSpace]" \
val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\[IAcute]m"\),
SequenceForm[
"A(z) ", 447927122303800151530042525716766391990642642424582049439333041\
773759332341245372994435424019212130238123186301407332323797071155811246428305\
72487340790521257344442028966696868302096598442754894011,
" legal\[AAcute]bb ", 0.99999904632568359375`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell["\<\
Ez az algoritmus nem faktoriz\[AAcute]l, ez\[EAcute]rt nagy sz\[AAcute]mokra \
is lefuttathat\[OAcute], viszont nem garant\[AAcute]l \
t\[ODoubleDot]k\[EAcute]letes v\[EAcute]geredm\[EAcute]nyt csak nagy val\
\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]g\[UDoubleAcute]t.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["3. A Fermat-teszt:",
FontWeight->"Bold"]], "Subtitle"],
Cell[BoxData[
RowBox[{" ",
RowBox[{\(Kor\[AAcute]bban\ l\[AAcute]ttuk\), ",",
RowBox[{"hogy", " ", "ha", " ",
StyleBox["p",
FontSlant->"Italic"], " ", "pr\[IAcute]m"}], ",",
RowBox[{\(akkor\ minden\ 0\), "<",
StyleBox["a",
FontSlant->"Italic"], "<",
RowBox[{
StyleBox["p",
FontSlant->"Italic"], " ", "eg\[EAcute]szre", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["p",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["p",
FontSlant->"Italic"], ")"}]}]}],
",", \(vagyis\ ha\ ez\ nem\ teljes\[UDoubleDot]l\), ",",
RowBox[{
RowBox[{"akkor", " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m",
" ", \(\[ODoubleDot]sszetett . \ A\), " ", "Fermat"}], "-",
RowBox[{
"teszt", " ", "egyszer\[UDoubleAcute]en", " ", "a", " ", "fenti",
" ", "kongruencia", " ",
"\[EAcute]rv\[EAcute]nyess\[EAcute]g\[EAcute]t", " ",
"ellen\[ODoubleAcute]rzi", " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ",
"pr\[IAcute]ms\[EAcute]g\[EAcute]nek",
" ", \(tesztel\[EAcute]s\[EAcute]re . \ Azonban\), " ", "itt",
" ", "is", " ", "meg", " ", "kell", " ",
"jegyezn\[UDoubleDot]nk"}]}], ",", \(hogy\ abb\[OAcute]l\), ",",
RowBox[{
RowBox[{"hogy", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "teljes\[UDoubleDot]l"}]}],
",", \(m\[EAcute]g\ nem\ k\[ODoubleDot]vetkezik\), ",",
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]m"}], ",",
RowBox[{
"\[IAcute]gy", " ", "ekkor", " ", "a", " ", "teszt", " ", "nem", " ",
"hoz", " ", \(eredm\[EAcute]nyt . \ Ilyenkor\), " ",
"\[UAcute]jabb", " ",
StyleBox["a",
FontSlant->"Italic"], " ",
"v\[AAcute]laszt\[AAcute]s\[AAcute]val",
" ", \(\(pr\[OAcute]b\[AAcute]lkozunk\)\(.\)\)}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{"Legyen", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[ODoubleDot]sszetett", " ",
"\[EAcute]s", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["n",
FontSlant->"Italic"]}], ")"}]}]}]}],
"=", \(1. Ekkor\ azt\ mondjuk\)}], ",",
RowBox[{
RowBox[{"hogy",
StyleBox[" ",
FontFamily->"Times New Roman"],
StyleBox["a",
FontSlant->"Italic"], " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ",
"\[ODoubleDot]sszetetts\[EAcute]g\[EAcute]nek", " ", "Fermat"}],
"-", "tan\[UAcute]ja"}], ",",
RowBox[{
RowBox[{"ha", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[NotCongruent]",
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], ".", " ", "Ha"}], " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"akkor", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "Fermat"}], "-",
"cinkosa"}], ",",
RowBox[{
RowBox[{"\[EAcute]s", " ", "ilyenkor", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-",
RowBox[{"et", " ",
StyleBox["a",
FontSlant->"Italic"]}],
"-", \(alap\[UAcute]\ \[AAcute]lpr\[IAcute]mnek\ \(\(nevezz\
\[UDoubleDot]k\)\(.\)\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"],
": Bizony\[IAcute]tott t\[EAcute]ny, hogy minden ",
StyleBox["a",
FontSlant->"Italic"],
"-ra, ahol ",
"(",
StyleBox["a",
FontSlant->"Italic"],
",",
StyleBox["n",
FontSlant->"Italic"],
")",
"=1, v\[EAcute]gtelen sok ",
StyleBox["a",
FontSlant->"Italic"],
"-alap\[UAcute] pszeudopr\[IAcute]m (\[AAcute]lpr\[IAcute]m) \
l\[EAcute]tezik. \n 341 a legkisebb 2-, 91 a legkisebb 3-, \[EAcute]s 15 \
a legkisebb 5-\[AAcute]lpr\[IAcute]m."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"Ha elv\[EAcute]gezz\[UDoubleDot]k a tesztet egy sz\[AAcute]mmal, amely \
\[ODoubleDot]sszetett, akkor a c\[EAcute]l az, hogy nem t\[UAcute]l sok ",
StyleBox["a",
FontSlant->"Italic"],
" v\[AAcute]laszt\[AAcute]s\[AAcute]val tal\[AAcute]ljunk egy \
tan\[UAcute]t, amely ezt bizony\[IAcute]tja. Sajnos azonban nem minden \
\[ODoubleDot]sszetet sz\[AAcute]mhoz l\[EAcute]tezik ilyen tan\[UAcute]."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{"Egy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[ODoubleDot]sszetett", " ",
"sz\[AAcute]mot", " ", "Carmichael"}],
"-", \(sz\[AAcute]mnak\ vagy\ univerz\[AAcute]lis\ \[AAcute]lpr\
\[IAcute]mnek\ nevez\[UDoubleDot]nk\)}]}]}], ",",
RowBox[{
RowBox[{"ha", " ", "minden", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["n",
FontSlant->"Italic"]}], ")"}]}], "=",
RowBox[{
RowBox[{"1", " ", "eset\[EAcute]n", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{
RowBox[{"1", " ",
RowBox[{
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], ".", " ", "Ekkor"}], " ",
StyleBox["n",
FontSlant->"Italic"], " ",
"\[ODoubleDot]sszetetts\[EAcute]g\[EAcute]nek", " ", "egyetlen",
" ", "Fermat"}],
"-", \(tan\[UAcute]ja\ \(\(sincs\)\(.\)\)\)}]}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"],
": A pr\[IAcute]mtesztel\[EAcute]si elj\[AAcute]r\[AAcute]s szempontj\
\[AAcute]b\[OAcute]l rossz h\[IAcute]r, hogy 1992-ben Alford, Granville \
\[EAcute]s Pomerance bebizony\[IAcute]tott\[AAcute]k, hogy v\[EAcute]gtelen \
sok Carmichael-sz\[AAcute]m l\[EAcute]tezik."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{"-", " ",
StyleBox["P\[EAcute]lda",
FontWeight->"Bold"]}],
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["univerz\[AAcute]lis",
FontWeight->"Bold"],
StyleBox[" ",
FontWeight->"Bold"],
RowBox[{
StyleBox["\[AAcute]lpr\[IAcute]mre",
FontWeight->"Bold"], ":", "\[IndentingNewLine]",
RowBox[{"-",
RowBox[{
StyleBox["\[CapitalAAcute]ll\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":",
" ", \(Az\ 561\ Carmichael -
sz\[AAcute]m . \ \((Ez\ a\ legkisebb)\)\)}]}]}]}],
" "}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{"-",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "2"], "\[Congruent]",
RowBox[{"1", " ", \((3)\),
StyleBox[" ",
FontWeight->"Bold"],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "560"]}], "\[Congruent]",
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "2"], ")"}], "280"],
"\[Congruent]", \(1\ \ \((3)\)\)}]}]}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "10"], "\[Congruent]",
RowBox[{"1", " ", \((11)\), " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "560"]}], "\[Congruent]",
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "10"], ")"}], "56"],
"\[Congruent]", \(1\ \ \((11)\)\)}]}], "\[IndentingNewLine]",
RowBox[{" ",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "16"], "\[Congruent]",
RowBox[{"1", " ", \((17)\), " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "560"]}], "\[Congruent]",
SuperscriptBox[
RowBox[{"(",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "16"], ")"}], "35"],
"\[Congruent]", \(1\ \ \((17)\)\)}]}], "\[IndentingNewLine]",
RowBox[{
RowBox[{
RowBox[{"Ezek", " ", "alapj\[AAcute]n", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"], "560"]}], "\[Congruent]",
RowBox[{
RowBox[{"1", " ", \((561)\), " ", "minden", " ",
StyleBox["a",
FontSlant->"Italic"]}], "-", "ra"}]}], ",",
RowBox[{
RowBox[{"amire", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",", "561"}], ")"}]}], "=", "1"}],
",", \(vagyis\ az\ 561\ univerz\[AAcute]lis\ \(\(\[AAcute]lpr\[IAcute]m\
\)\(.\)\)\)}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"A Fermat-teszt azonban ezen sz\[AAcute]mokt\[OAcute]l eltekintve hat\
\[EAcute]kony. Bel\[AAcute]tjuk, hogy ha ",
StyleBox["n",
FontSlant->"Italic"],
" \[ODoubleDot]sszetett, de nem Carmichael-sz\[AAcute]m, akkor a teszt \
\"nagy val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel\" lebuktatja."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["T\[EAcute]tel",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{"Ha", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", \(hez\ van\ Fermat\), "-",
"tan\[UAcute]"}]}]}], ",",
RowBox[{"akkor", " ", "van", " ", "legal\[AAcute]bb", " ",
RowBox[{
FractionBox[
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
RowBox[{
StyleBox["(",
"Input",
FontWeight->"Plain"],
StyleBox["n",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[")",
"Input",
FontWeight->"Plain"]}]}], "2"], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ",
RowBox[{"Legyen", " ",
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"]}]}]}], "=",
RowBox[{"{",
RowBox[{
RowBox[{
StyleBox["a",
FontSlant->"Italic"], " ", "\[Element]",
RowBox[{
StyleBox["\[DoubleStruckCapitalZ]",
"Section"],
StyleBox[":",
"Input"],
RowBox[{
StyleBox["(",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["a",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox["n",
"Input",
FontWeight->"Plain",
FontSlant->"Italic"]}],
StyleBox[")",
"Input",
FontWeight->"Plain"]}]}]}],
StyleBox["=",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox[\(1 \[EAcute]s\ 0\),
"Input",
FontWeight->"Plain"],
StyleBox["\[LessEqual]",
"Input"],
StyleBox["a",
FontSlant->"Italic"],
StyleBox["<",
"Input"],
StyleBox["n",
FontSlant->"Italic"]}]}],
StyleBox["}",
FontFamily->"Times New Roman",
FontWeight->"Plain",
FontSlant->"Plain"]}]}], ",",
RowBox[{
RowBox[{
StyleBox["tov\[AAcute]bb\[AAcute]",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["legyen",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["C",
"Subsection"]}],
StyleBox["=",
"Input"],
RowBox[{
RowBox[{
RowBox[{
RowBox[{
StyleBox["{",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["a",
FontSlant->"Italic"], "\[Element]",
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], " ", ":", " ",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}]}]}], " ", "}"}],
".", " ", "Vagyis"}], " ",
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], " ", "a", " ", "standard", " ",
"reduk\[AAcute]lt", " ", "marad\[EAcute]krendszer", " ",
"modulo", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
StyleBox["C",
"Subsection"],
StyleBox[" ",
"Input"],
StyleBox["az",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["sz\[AAcute]m",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["Fermat",
"Input",
FontWeight->"Plain"]}],
StyleBox["-",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["cinkosainak",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["halmaza",
"Input",
FontWeight->"Plain"],
StyleBox[".",
"Input"],
StyleBox[" ",
"Input"],
StyleBox["A",
"Input",
FontWeight->"Plain"]}],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["feltev\[EAcute]s",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["szerint",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["l\[EAcute]tezik",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["tan\[UAcute]",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["-",
"Input"],
StyleBox["hez",
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["vagyis",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["C",
"Subsection"]}],
StyleBox["\[Subset]",
"Subsection"],
StyleBox[" ",
"Subsection"],
RowBox[{
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], " ", "\[EAcute]s", " ",
StyleBox["C",
"Subsection"]}],
StyleBox["\[NotEqual]",
"Input"],
RowBox[{
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], ".", " ", "Legyen"}], " ",
StyleBox["t",
FontSlant->"Italic"]}]}], "\[Element]",
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], " ", "egy",
" ", \(tan\[UAcute] . \ Ekkor\), " ", "minden", " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[Element]",
RowBox[{
StyleBox["C",
"Subsection"],
StyleBox[" ",
"Input"],
StyleBox["eset\[EAcute]n",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["t",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["a",
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox["is",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["tan\[UAcute]",
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["ugyanis",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
SuperscriptBox[
RowBox[{
StyleBox["(",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
RowBox[{
StyleBox["t",
FontFamily->"Times New Roman",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["a",
FontSlant->"Italic"]}],
StyleBox[")",
FontSlant->"Italic"]}],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{
SuperscriptBox[
StyleBox["t",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]],
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
SuperscriptBox[
StyleBox["t",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]], "\[NotCongruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"hiszen", " ",
StyleBox["t",
FontSlant->"Italic"],
" ", \(tan\[UAcute] . \ Tov\[AAcute]bb\[AAcute]\), " ", "ha", " ",
StyleBox["a",
FontSlant->"Italic"]}], "\[NotEqual]",
RowBox[{
RowBox[{
StyleBox[\(a'\),
FontSlant->"Italic"], " ", "k\[EAcute]t", " ",
StyleBox["C",
"Subsection"]}],
StyleBox["-",
"Input"],
StyleBox[\(beli\ elem\),
"Input",
FontWeight->"Plain"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["akkor",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["t",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["a",
FontSlant->"Italic"]}],
StyleBox["\[NotCongruent]",
"Input"],
RowBox[{
StyleBox["t",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox[\(a'\),
FontSlant->"Italic"],
StyleBox[" ",
"Input"],
StyleBox[\((n)\),
FontSlant->"Italic"]}]}],
StyleBox[",",
FontSlant->"Italic"],
RowBox[{
RowBox[{
RowBox[{
StyleBox["hiszen",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["t",
FontSlant->"Italic"]}], "\[Element]",
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"],
" ", \(invert\[AAcute]lhat\[OAcute] . \ Ezek\), " ", "szerint",
" ", "a", " ",
StyleBox["t",
FontSlant->"Italic"],
StyleBox[" ",
FontWeight->"Bold",
FontSlant->"Italic"],
StyleBox["a",
FontSlant->"Italic"], " ", "alak\[UAcute]", " ", "elemek", " ",
"adnak", " ", "legal\[AAcute]bb"}]}], " ", "|",
StyleBox["C",
"Subsection"],
StyleBox["|",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[\(Fermat - tan\[UAcute]t\),
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"]}],
StyleBox[",",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox["teh\[AAcute]t",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["az",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
StyleBox["n",
FontSlant->"Italic"]}],
StyleBox["-",
"Input"],
StyleBox[\(hez\ relat\[IAcute]v\ pr\[IAcute]m\ marad\[EAcute]koszt\
\[AAcute]lyok\ k\[ODoubleDot]z\[UDoubleDot]l\ legal\[AAcute]bb\ annyi\ tan\
\[UAcute]\ van\),
"Input",
FontWeight->"Plain"]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
RowBox[{
StyleBox[\(mint\ \(\(cinkos\)\(.\)\)\),
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["|",
"Input",
FontWeight->"Plain"],
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], "|"}], "=",
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
StyleBox[\((n)\),
FontSlant->"Italic"]}]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox["vagyis",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["legal\[AAcute]bb",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input"],
FractionBox[
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
StyleBox[\((n)\),
FontSlant->"Italic"]}], "2"], " ", "tan\[UAcute]",
" ", \(\(van\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Megjegyz\[EAcute]s",
FontWeight->"Bold"], ":",
" ", \(M\[EAcute]g\ egyszer\[UDoubleAcute]bb\ a\ bizony\[IAcute]t\
\[AAcute]st\ az\ algebra\ eszk\[ODoubleDot]zeivel\ megfogalmazni . \
K\[ODoubleDot]nny\[UDoubleAcute]\ l\[AAcute]tni\)}]}], ",",
RowBox[{"hogy", " ",
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], " ", "a", " ", "modulo", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "szorz\[AAcute]sra", " ",
"n\[EAcute]zve", " ", "csoport"}], ",", " ",
RowBox[{"aminek", " ",
StyleBox["C",
"Subsection"],
StyleBox[" ",
"Input"],
StyleBox[\(r\[EAcute]szcsoportja . \ Lagrange\),
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["t\[EAcute]tele",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["szerint",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["egy",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["csoport",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["r\[EAcute]szcsoportj\[AAcute]nak",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["elemsz\[AAcute]ma",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["oszt\[OAcute]ja",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["a",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["csoport",
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["elemsz\[AAcute]m\[AAcute]nak",
"Input",
FontWeight->"Plain"]}],
StyleBox[",",
"Input",
FontWeight->"Plain"],
RowBox[{
StyleBox[\(azaz\ jelen\ esetben\),
"Input",
FontWeight->"Plain"],
StyleBox[" ",
"Input",
FontWeight->"Plain"],
StyleBox["|",
"Input",
FontWeight->"Plain"],
StyleBox["C",
"Subsection"],
StyleBox["|",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["osztja",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox[" ",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
StyleBox["|",
"Subsection",
FontFamily->"Times New Roman",
FontWeight->"Plain"],
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"], "|", " ",
RowBox[{
RowBox[{\(-ot . \ Mivel\), " ",
StyleBox["C",
"Subsection"]}],
StyleBox["\[NotEqual]",
"Input"],
SuperscriptBox[
SubscriptBox[
StyleBox["Z",
"Subsection"],
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"]], "*"]}]}],
",", \(az\ \[AAcute]ll\[IAcute]t\[AAcute]s\ ebb\[ODoubleAcute]l\ m\
\[AAcute]r\ \(\(l\[AAcute]tszik\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"Legyen", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[ODoubleDot]sszetett"}], ",",
RowBox[{\(de\ nem\ Carmichael\), "-",
RowBox[{\(sz\[AAcute]m . \ V\[AAcute]lasszunk\), " ", "egy", " ",
StyleBox["n",
FontSlant->"Italic"]}],
"-", \(n\[EAcute]l\ kisebb\ a\ sz\[AAcute]mot . \
Az\ el\[ODoubleAcute]bbi\ t\[EAcute]tel\ alapj\[AAcute]n\ annak\ \
a\ val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ge\)}], ",",
RowBox[{
RowBox[{
"hogy", " ", "cinkost", " ", "v\[AAcute]lasztottunk", " ",
"legfeljebb", " ",
FractionBox[
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
StyleBox[\((n)\),
FontSlant->"Italic"]}],
RowBox[{"2",
StyleBox["n",
FontSlant->"Italic"]}]]}], "<",
RowBox[{
RowBox[{\(\(1\/2\) . \ Ism\[EAcute]telj\[UDoubleDot]k\), " ", "meg",
" ", "ezt", " ", "az", " ", "elj\[AAcute]r\[AAcute]st", " ",
StyleBox["k",
FontSlant->"Italic"]}], "-", "szor"}]}],
",", \(\[IAcute]gy\ annak\ a\ val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\
\[EAcute]ge\), ",", \(hogy\ mindig\ cinkost\ v\[AAcute]lasztunk\ kisebb\),
",",
RowBox[{"mint", " ",
FractionBox["1",
SuperscriptBox["2",
StyleBox["k",
FontSlant->"Italic"]]]}], ",",
RowBox[{
RowBox[{"vagyis", " ", "viszonylag", " ", "kev\[EAcute]s", " ",
StyleBox["a",
FontSlant->"Italic"], " ",
"kipr\[OAcute]b\[AAcute]l\[AAcute]s\[AAcute]val", " ", "igen", " ",
"nagy", " ", "es\[EAcute]llyel", " ", "tal\[AAcute]lunk", " ",
"tan\[UAcute]t", " ",
StyleBox["n",
FontSlant->"Italic"],
" ", \(\[ODoubleDot]sszetetts\[EAcute]g\[EAcute]re . \ Az\), " ",
"egyetlen", " ", "probl\[EAcute]m\[AAcute]t", " ", "a", " ",
"kor\[AAcute]bban", " ", "eml\[IAcute]tett", " ", "Carmichael"}],
"-", \(sz\[AAcute]mok\ jelentik\)}],
",", \(hiszen\ ezekre\ a\ teszt\ ugyanazt\ az\ eredm\[EAcute]nyt\ \
adja\), ",", \(mint\ \(\(pr\[IAcute]mekre\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"- ",
StyleBox["Az algoritmus",
FontWeight->"Bold"],
": "
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"K\[EAcute]t", " ", "input", " ", "lesz", " ",
RowBox[{"ism\[EAcute]t", ":", " ",
RowBox[{
StyleBox["n",
FontSlant->"Italic"], " ", "\[EAcute]s", " ",
RowBox[{
StyleBox["k",
FontSlant->"Italic"], ".",
StyleBox[" ",
FontWeight->"Bold"],
StyleBox["n",
FontSlant->"Italic"]}], " ", "a", " ", "sz\[AAcute]m", " ",
"amit", " ", "tesztel\[UDoubleDot]nk", " ", "\[EAcute]s", " ",
StyleBox["k",
FontSlant->"Italic"], " ", "jelenti", " ", "azt"}]}]}],
",", \(hogy\ h\[AAcute]nyszor\), ",", "azaz", ",",
RowBox[{
RowBox[{"hogy", " ", "h\[AAcute]ny", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "sz\[AAcute]mra", " ", "fogjuk", " ",
"megn\[EAcute]zni", " ", "az", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontWeight->"Bold",
FontSlant->"Italic"], "-", "1"}]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "kongruencia",
" ", \(teljes\[UDoubleDot]l\[EAcute]s\[EAcute]t . \ Ezeket\), " ",
"a", " ", "sz\[AAcute]mokat", " ", "ism\[EAcute]t", " ", "egy", " ",
"v\[EAcute]letlen", " ", "lista", " ", "fogja",
" ", \(gener\[AAcute]lni . \ Ha\), " ", "valamelyik", " ",
"sz\[AAcute]mra", " ", "nem", " ", "teljes\[UDoubleDot]l", " ", "a",
" ", "kongruencia"}]}],
",", \(akkor\ az\ algoritmus\ le\[AAcute]ll\ \[EAcute]s\ ki\[IAcute]rja\
\), ",",
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", \(\[ODoubleDot]sszetett . \ Ha\), " ",
"v\[EAcute]gig", " ", "fut"}],
",", \(akkor\ ezt\ egy\ indik\[AAcute]tor\ jelzi\ \[EAcute]s\ az\ elj\
\[AAcute]r\[AAcute]s\ ki\[IAcute]rja\), ",",
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "mekkora", " ",
"val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel", " ",
"pr\[IAcute]m"}], ",", "illetve", ",",
RowBox[{
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "lehet", " ", "Carmichael"}],
"-", \(\(sz\[AAcute]m\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(Fermattest[n_, k_] :=
Module[\[IndentingNewLine]{randomlist, a,
val}, \[IndentingNewLine]randomlist[m_, j_] :=
Module[\[IndentingNewLine]{A}, \[IndentingNewLine]If[j < m - 1,
A = {Random[Integer, {2, m - 1}]}; \[IndentingNewLine]While[\
Length[A] < j, \[IndentingNewLine]A =
Union[A, {\
Random[Integer, {2,
m - 1}]\ }]]; \[IndentingNewLine]Return[
A], \(Print[j, "\< nem kisebb,mint \>",
m - 1];\)]\[IndentingNewLine]]; \[IndentingNewLine]a =
randomlist[n, k]; \[IndentingNewLine]val =
N[1 - \((1\/2)\)\^k, 25]; \[IndentingNewLine]If[
PowerMod[a, n - 1, n] \[Equal] Table[1, {k}],
Print["\", n, "\< legal\[AAcute]bb \>",
val, "\< val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\
\[IAcute]m ,vagy Carmichael-sz\[AAcute]m\>"],
Print[n, "\< \[ODoubleDot]sszetett\>"]];\[IndentingNewLine]]\)], \
"Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(Fermattest[100000007, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) "\[InvisibleSpace]100000007\[InvisibleSpace]" \
legal\[AAcute]bb "\[InvisibleSpace]0.99999904632568359375`25. \
\[InvisibleSpace]" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\
\[IAcute]m ,vagy Carmichael-sz\[AAcute]m"\),
SequenceForm[
"A(z) ", 100000007, " legal\[AAcute]bb ", 0.99999904632568359375`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\[IAcute]m \
,vagy Carmichael-sz\[AAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(Fermattest[
447927122303800151530042525716766391990642642424582049439333041773759332\
341245372994435424019212130238123186301407332323797071155811246428305724873407\
90521257344442028966696868302096598442754894011, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) \
"\[InvisibleSpace]\
447927122303800151530042525716766391990642642424582049439333041773759332341245\
372994435424019212130238123186301407332323797071155811246428305724873407905212\
57344442028966696868302096598442754894011\[InvisibleSpace]" legal\[AAcute]bb \
"\[InvisibleSpace]0.99999904632568359375`25. \[InvisibleSpace]" \
val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\[IAcute]m ,vagy \
Carmichael-sz\[AAcute]m"\),
SequenceForm[
"A(z) ", 447927122303800151530042525716766391990642642424582049439333041\
773759332341245372994435424019212130238123186301407332323797071155811246428305\
72487340790521257344442028966696868302096598442754894011,
" legal\[AAcute]bb ", 0.99999904632568359375`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\[IAcute]m \
,vagy Carmichael-sz\[AAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell[TextData[{
"Az algoritmus gyors nagyon nagy sz\[AAcute]mokra is, viszont nem ad biztos \
eredm\[EAcute]nyt ",
StyleBox["n",
FontSlant->"Italic"],
" pr\[IAcute]ms\[EAcute]g\[EAcute]re \[EAcute]s a \
Carmichael-sz\[AAcute]mokat sem tudja kisz\[UDoubleAcute]rni."
}], "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["4. A Rabin-Miller-teszt:",
FontWeight->"Bold"]], "Subtitle"],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{"Legyen", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "p\[AAcute]ratlan", " ",
"eg\[EAcute]sz"}], ",", " ",
RowBox[{
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}], " ", "=", " ",
RowBox[{
SuperscriptBox["2",
StyleBox["r",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]}], ",",
RowBox[{
RowBox[{"ahol", " ",
StyleBox["s",
FontSlant->"Italic"], " ", "szint\[EAcute]n", " ",
"p\[AAcute]ratlan", " ", "\[EAcute]s", " ", "legyen", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["n",
FontSlant->"Italic"]}], ")"}]}], "=", \(1. \ Ekkor\)}]}],
" "}], "\[IndentingNewLine]",
RowBox[{
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]], "-", "1"}], "=",
RowBox[{
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
StyleBox["r",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]], "-", "1"}], "=",
RowBox[{
RowBox[{
RowBox[{
RowBox[{
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
RowBox[{
StyleBox["r",
FontSlant->"Italic"], "-", "1"}]],
StyleBox["s",
FontSlant->"Italic"]}]], "-", "1"}], ")"}],
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
RowBox[{
StyleBox["r",
FontSlant->"Italic"], "-", "1"}]],
StyleBox["s",
FontSlant->"Italic"]}]], "+", "1"}], ")"}]}],
"=."}], ".."}], "=",
RowBox[{
RowBox[{
RowBox[{
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["s",
FontSlant->"Italic"]], "-", "1"}], ")"}],
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["s",
FontSlant->"Italic"]], "+", "1"}], ")"}],
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{"2",
StyleBox["s",
FontSlant->"Italic"]}]], "+", "1"}], ")"}],
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{\(2\^2\),
StyleBox["s",
FontSlant->"Italic"]}]], "+", "1"}], ")"}]}],
"..."}],
RowBox[{"(",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
RowBox[{
StyleBox["r",
FontSlant->"Italic"],
StyleBox["-",
FontWeight->"Bold"], "1"}]],
StyleBox["s",
FontSlant->"Italic"]}]], "+", "1"}],
")"}]}]}]}]}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"Ha", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]m"}], ",",
RowBox[{
RowBox[{
RowBox[{"akkor", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}]]}], "-", "1"}],
"\[Congruent]",
RowBox[{
RowBox[{"0", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "\[EAcute]s", " ",
"\[IAcute]gy", " ", "az", " ", "el\[ODoubleAcute]bbi", " ",
"szorzat", " ", "valamelyik", " ",
"t\[EAcute]nyez\[ODoubleAcute]je", " ", "oszthat\[OAcute]", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "nel"}]}], ",",
RowBox[{
RowBox[{"azaz", " ", "ha", " ", "az", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["s",
FontSlant->"Italic"]]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",", " ",
RowBox[{
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
StyleBox["i",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]], "\[Congruent]",
RowBox[{\(-1\), " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ",
RowBox[{"(",
RowBox[{
RowBox[{
StyleBox["i",
FontSlant->"Italic"], "=", "0"}], ",", "1", ",", "...", ",",
RowBox[{
StyleBox["r",
FontSlant->"Italic"], "-", "1"}]}], ")"}], " ",
"kongruenci\[AAcute]k", " ", "k\[ODoubleDot]z\[UDoubleDot]l", " ",
"egyik", " ", "sem", " ", "teljes\[UDoubleDot]l"}]}], ",",
RowBox[{"akkor", " ",
StyleBox["n",
FontSlant->"Italic"], " ", \(\[ODoubleDot]sszetett . \ Ha\), " ",
"teljes\[UDoubleDot]lnek"}], ",", \(akkor\ m\[EAcute]g\ nem\ biztos\),
",",
RowBox[{
RowBox[{"hogy", " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "pr\[IAcute]m",
" ", "ez\[EAcute]rt", " ", "\[UAcute]j", " ",
StyleBox["a",
FontSlant->"Italic"]}],
"-", \(val\ kell\ \(\(pr\[OAcute]b\[AAcute]lkozni\)\(.\)\)\)}]}]], \
"Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Defin\[IAcute]ci\[OAcute]",
FontWeight->"Bold"], ":", " ",
RowBox[{
RowBox[{"Legyen", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "p\[AAcute]ratlan", " ",
"\[ODoubleDot]sszetett", " ", "sz\[AAcute]m", " ",
"\[EAcute]s", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "1"}]}]}], "=",
RowBox[{
SuperscriptBox["2",
StyleBox["r",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]}], ",", " ",
RowBox[{
RowBox[{"ahol", " ",
StyleBox["s",
FontSlant->"Italic"], " ", "p\[AAcute]ratlan", " ", "\[EAcute]s",
" ", "legyen", " ",
RowBox[{"(",
RowBox[{
StyleBox["a",
FontSlant->"Italic"], ",",
StyleBox["n",
FontSlant->"Italic"]}], ")"}]}], "=",
RowBox[{"1.", "Az", " ",
StyleBox["a",
FontSlant->"Italic"], " ", "sz\[AAcute]m"}]}], ",", " ",
RowBox[{
RowBox[{
StyleBox["n",
FontSlant->"Italic"], " ",
"\[ODoubleDot]sszetetts\[EAcute]g\[EAcute]nek", " ", "Rabin"}], "-",
"Miller", "-", "tan\[UAcute]ja"}], ",",
RowBox[{
RowBox[{"ha", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
StyleBox["s",
FontSlant->"Italic"]]}], "\[NotCongruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",",
RowBox[{
RowBox[{"tov\[AAcute]bb\[AAcute]", " ",
SuperscriptBox[
StyleBox["a",
FontSlant->"Italic"],
RowBox[{
SuperscriptBox["2",
StyleBox["i",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]]}], "\[NotCongruent]",
RowBox[{\(-1\), " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ", "egyetlen", " ", "0"}],
"\[LessEqual]",
StyleBox["i",
FontSlant->"Italic"], "<",
RowBox[{
RowBox[{
StyleBox["r",
FontSlant->"Italic"], " ", "eset\[EAcute]n",
" ", \(sem . \ Egy\[EAcute]bk\[EAcute]nt\), " ",
StyleBox["a",
FontSlant->"Italic"], " ", "Rabin"}], "-", "Miller", "-",
"cinkos"}]}], ",",
RowBox[{
RowBox[{"\[EAcute]s", " ", "ekkor", " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"],
StyleBox[" ",
FontFamily->"Trebuchet MS",
FontWeight->"Bold",
FontSlant->"Italic"], "\[ODoubleDot]sszetett", " ",
"sz\[AAcute]mot", " ", "er\[ODoubleAcute]s", " ",
StyleBox["a",
FontSlant->"Italic"]}],
"-", \(\[AAcute]lpr\[IAcute]mnek\ \
\(\(nevezz\[UDoubleDot]k\)\(.\)\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
"- P\[EAcute]lda: Az 561 nem er\[ODoubleAcute]s 2-\[AAcute]lpr\[IAcute]m. \
(Azaz hi\[AAcute]ba Carmichael-sz\[AAcute]m, a teszt kisz\[UDoubleAcute]ri ",
StyleBox["a",
FontSlant->"Italic"],
"=2 eset\[EAcute]n)"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[{
RowBox[{
RowBox[{
RowBox[{"-", " ",
RowBox[{
StyleBox["Bizony\[IAcute]t\[AAcute]s",
FontWeight->"Bold"], ":", " ", "560"}]}], "=", \(35*2\^4\)}],
",",
RowBox[{
RowBox[{"azaz", " ",
StyleBox["r",
FontSlant->"Italic"]}], "=", "4"}], ",",
RowBox[{
StyleBox["s",
FontSlant->"Italic"], "=", "35."}]}], "\[IndentingNewLine]",
RowBox[{\(2\^35 \[Congruent] 263\ \ \((561)\)\), ",",
" ", \(2\^70 \[Congruent] 166\ \ \((561)\)\), ",",
" ", \(2\^140 \[Congruent] 67\ \ \((561)\)\), ",",
" ", \(2\^280 \[Congruent] 1\ \ \ \((561)\)\), ",", " ",
RowBox[{
RowBox[{"vagyis", " ", "az", " ",
StyleBox["a",
FontFamily->"Trebuchet MS",
FontSlant->"Italic"]}],
"=", \(2\ v\[AAcute]laszt\[AAcute]s\ bizony\[IAcute]totta\)}],
",", \(hogy\ 561\ nem\ er\[ODoubleAcute]s\ 2 - \
\(\(\[AAcute]lpr\[IAcute]m\)\(.\)\)\)}]}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
Ez az algoritmus teh\[AAcute]t kisz\[UDoubleAcute]ri az univerz\[AAcute]lis \
\[AAcute]lpr\[IAcute]meket is, \[EAcute]s a hat\[EAcute]konys\[AAcute]ga is \
jobb, mint a Fermat-teszt\[EAcute].\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{\(Bizony\[IAcute]t\[AAcute]s\ n\[EAcute]lk\[UDoubleDot]l\ k\
\[ODoubleDot]z\[ODoubleDot]lj\[UDoubleDot]k\), ",",
RowBox[{"hogy", " ", "ha", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "p\[AAcute]ratlan", " ",
"\[ODoubleDot]sszetett", " ", "sz\[AAcute]m"}], ",",
RowBox[{
RowBox[{"akkor", " ", "legfeljebb", " ",
FractionBox[
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}], "4"], " ", "Rabin"}], "-",
"Miller",
"-", \(cinkosa\ van . \
Annak\ a\ val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ge\)}],
",",
RowBox[{"hogy", " ",
StyleBox["k",
FontSlant->"Italic"], " ",
"k\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute]"}], ",",
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-",
RowBox[{
"n\[EAcute]l", " ", "kisebb", " ", "pozit\[IAcute]v", " ",
"sz\[AAcute]m", " ", "mindegyik\[EAcute]re", " ", "n\[EAcute]zve",
" ",
StyleBox["n",
FontSlant->"Italic"], " ", "er\[ODoubleAcute]s", " ",
"\[AAcute]lpr\[IAcute]m", " ", "legyen", " ", "kisebb"}]}], ",",
RowBox[{"mint", " ",
RowBox[{
FractionBox["1",
SuperscriptBox["4",
StyleBox["k",
FontSlant->"Italic"]]], "."}]}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{\(Ezen\ \[AAcute]ll\[IAcute]t\[AAcute]st\ \(1\/4\) helyett
1\/2 - re\ k\[ODoubleDot]nnyen\ biziny\[IAcute]thatn\[AAcute]nk . \
\ Ehhez\ azt\ k\[EAcute]ne\ bel\[AAcute]tni\),
",", \(hogy\ minden\ p\[AAcute]ratlan\ \[ODoubleDot]sszetett\ sz\
\[AAcute]mhoz\ l\[EAcute]tezik\ Rabin - Miller -
tan\[UAcute] . \ Ezut\[AAcute]n\ azt\), ",",
" ", \(hogy\ ha\ egy\ van\), ",", " ",
RowBox[{"akkor", " ", "van", " ", "legal\[AAcute]bb", " ",
FractionBox[
RowBox[{
StyleBox["\[CurlyPhi]",
"Subsection"],
StyleBox[\((n)\),
FontSlant->"Italic"]}], "2"], " ", "is"}],
",", \(a\ Fermat -
tesztre\ vonatkoz\[OAcute]\ t\[EAcute]telhez\ hasonl\[OAcute]an\ \
\(\(bizony\[IAcute]thatn\[AAcute]nk\)\(.\)\)\)}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{"Legyen", " ", "teh\[AAcute]t", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "p\[AAcute]ratlan", " ", "eg\[EAcute]sz",
" ", \(sz\[AAcute]m . \ Ha\), " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[ODoubleDot]sszetett"}], ",",
" ", \(akkor\ t\[ODoubleDot]bb\ mint\ 3\/4\ val\[OAcute]sz\[IAcute]n\
\[UDoubleAcute]s\[EAcute]ggel\ tal\[AAcute]lunk\ hozz\[AAcute]\ egy\ Rabin -
Miller - tan\[UAcute]t\), ",", " ",
RowBox[{
RowBox[{
"teh\[AAcute]t", " ", "az", " ", "elj\[AAcute]r\[AAcute]st", " ",
StyleBox["k",
FontSlant->"Italic"]}],
"-", \(szor\ ism\[EAcute]telve\ kevesebb\)}], ",", " ",
RowBox[{"mint", " ",
FractionBox["1",
SuperscriptBox["4",
StyleBox["k",
FontSlant->"Italic"]]], "a", " ",
"val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ge"}],
",", \(hogy\ csupa\ cinkost\ \(\(v\[AAcute]lasztottunk\)\(.\)\)\)}]], \
"Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[StyleBox["- Az algoritmus:",
FontWeight->"Bold"]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{
RowBox[{"Input", " ", "az", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "sz\[AAcute]m", " ", "amit", " ",
"tesztel\[UDoubleDot]nk", " ", "\[EAcute]s", " ",
StyleBox["k",
FontSlant->"Italic"], " ", "a", " ", "tesztek",
" ", \(sz\[AAcute]ma . \ El\[ODoubleAcute]sz\[ODoubleDot]r\), " ",
"kisz\[UDoubleAcute]rj\[UDoubleDot]k", " ", "a", " ",
"p\[AAcute]ros", " ",
StyleBox["n",
FontSlant->"Italic"], " ", \(inputot . \ Ezut\[AAcute]n\), " ",
"felbontjuk", " ",
RowBox[{"(",
RowBox[{
StyleBox["n",
FontSlant->"Italic"], "-", "1"}], ")"}]}], "-",
RowBox[{"et", " ",
SuperscriptBox["2",
StyleBox["r",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"], " ", "alakra", " ", "ahol", " ",
StyleBox["s",
FontSlant->"Italic"],
" ", \(p\[AAcute]ratlan . \ Gener\[AAcute]lunk\), " ", "egy", " ",
StyleBox["k",
FontSlant->"Italic"], " ",
"k\[UDoubleDot]l\[ODoubleDot]nb\[ODoubleDot]z\[ODoubleAcute]",
" ", "elem\[UDoubleAcute]", " ", "v\[EAcute]letlen", " ",
"list\[AAcute]t", " ", "\[EAcute]s", " ", "ennek", " ", "minden",
" ",
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"], " ", "elem\[EAcute]re", " ",
"ellen\[ODoubleAcute]rizz\[UDoubleDot]k", " ", "az", " ",
SuperscriptBox[
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"],
StyleBox["s",
FontSlant->"Italic"]]}]}], "\[Congruent]",
RowBox[{"1", " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}]}]}], ",", " ",
RowBox[{
SuperscriptBox[
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"],
RowBox[{
SuperscriptBox["2",
StyleBox["i",
FontSlant->"Italic"]],
StyleBox["s",
FontSlant->"Italic"]}]], "\[Congruent]",
RowBox[{\(-1\), " ",
RowBox[{"(",
StyleBox["n",
FontSlant->"Italic"], ")"}], " ",
RowBox[{"(",
RowBox[{
RowBox[{
StyleBox["i",
FontSlant->"Italic"], "=", "0"}], ",", "1", ",", "...", ",",
RowBox[{
StyleBox["r",
FontSlant->"Italic"], "-", "1"}]}], ")"}],
" ", \(kongruenci\[AAcute]kat . \ Ha\), " ", "valamely", " ",
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"], " ", "eset\[EAcute]n", " ", "egyik",
" ", "sem", " ", "teljes\[UDoubleDot]l"}]}], ",",
" ", \(akkor\ az\ algoritmus\ ki\[IAcute]rja\), ",", " ",
RowBox[{
RowBox[{"hogy", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "\[ODoubleDot]sszetett", " ",
"\[EAcute]s", " ", \(kil\[EAcute]p . \ Ha\), " ", "egyik", " ",
SubscriptBox[
StyleBox["a",
FontSlant->"Italic"], "j"], " ", "sem", " ", "buktatja", " ",
"le", " ",
StyleBox["n",
FontSlant->"Italic"]}], "-", "et"}], ",", " ",
RowBox[{
"akkor", " ", "az", " ", "elj\[AAcute]r\[AAcute]s", " ", "megadja", " ",
StyleBox["n",
FontSlant->"Italic"], " ", "pr\[IAcute]ms\[EAcute]g\[EAcute]nek",
" ", \(\(val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]g\[EAcute]t\
\)\(.\)\)}]}]], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[BoxData[
\(RabinMiller[n_, k_] :=
Module[\[IndentingNewLine]{randomlist, val, ind, a, b,
bont}, \[IndentingNewLine]listak = {}; \[IndentingNewLine]ind = {}; \
\[IndentingNewLine]If[OddQ[n],
randomlist[m_, j_] :=
Module[\[IndentingNewLine]{A}, \[IndentingNewLine]If[j < m - 1,
A = {Random[Integer, {2, m - 1}]}; \[IndentingNewLine]While[\
Length[A] < j, \[IndentingNewLine]A =
Union[A, {\
Random[
Integer, {2,
m - 1}]\ }]]; \[IndentingNewLine]Return[
A], \(Print[j, "\< nem kisebb,mint \>",
m - 1];\)]\[IndentingNewLine]]; \[IndentingNewLine]a =
randomlist[n, k]; \[IndentingNewLine]bont[l_] :=
Module[\[IndentingNewLine]{s, r, b}, \[IndentingNewLine]s =
l - 1; \[IndentingNewLine]r = 0; \[IndentingNewLine]While[
EvenQ[s], s = s/2;
r = r + 1;]; \[IndentingNewLine]b = {r,
s}\[IndentingNewLine]]; \[IndentingNewLine]b =
bont[n]; \[IndentingNewLine]For[v = 1,
v < Length[a] + 1, \(v++\), \[IndentingNewLine]For[i = 0,
i < b[\([1]\)], \(i++\), \[IndentingNewLine]\(If[
PowerMod[a[\([v]\)], 2\^i*b[\([2]\)], n] \[Equal] n - 1,
AppendTo[ind, 1],
AppendTo[ind, 0]];\)]\[IndentingNewLine]If[
PowerMod[a[\([v]\)], b[\([2]\)], n] \[Equal] 1,
AppendTo[ind, 1],
AppendTo[ind, 0]]; \[IndentingNewLine]AppendTo[listak, ind];
ind = {};]; \[IndentingNewLine]val =
N[1 - \((1\/4)\)\^k, 25]; \[IndentingNewLine]If[
MemberQ[listak, Table[0, {w, 1, b[\([1]\)] + 1}]],
Print[n, "\< \[ODoubleDot]sszetett\>"],
Print["\", n, "\< sz\[AAcute]m \>",
val, "\< val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m\>"]]\[IndentingNewLine],
Print[n, "\< p\[AAcute]ros sz\[AAcute]m. Ha nem 2, akkor \
\[ODoubleDot]sszetett\>"]]\[IndentingNewLine]]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(RabinMiller[100000007, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) "\[InvisibleSpace]100000007\[InvisibleSpace]" \
sz\[AAcute]m "\[InvisibleSpace]0.99999999999909050529822707176208496094`25. \
\[InvisibleSpace]" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\
\[IAcute]m"\),
SequenceForm[
"A(z) ", 100000007, " sz\[AAcute]m ",
0.99999999999909050529822707176208496094`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(RabinMiller[
447927122303800151530042525716766391990642642424582049439333041773759332\
341245372994435424019212130238123186301407332323797071155811246428305724873407\
90521257344442028966696868302096598442754894011, 20]\)], "Input"],
Cell[BoxData[
InterpretationBox[\("A(z) \
"\[InvisibleSpace]\
447927122303800151530042525716766391990642642424582049439333041773759332341245\
372994435424019212130238123186301407332323797071155811246428305724873407905212\
57344442028966696868302096598442754894011\[InvisibleSpace]" sz\[AAcute]m "\
\[InvisibleSpace]0.99999999999909050529822707176208496094`25. \
\[InvisibleSpace]" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel pr\
\[IAcute]m"\),
SequenceForm[
"A(z) ", 447927122303800151530042525716766391990642642424582049439333041\
773759332341245372994435424019212130238123186301407332323797071155811246428305\
72487340790521257344442028966696868302096598442754894011, " sz\[AAcute]m ",
0.99999999999909050529822707176208496094`25.,
" val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]ggel \
pr\[IAcute]m"],
Editable->False]], "Print"]
}, Open ]],
Cell["\<\
Ennek az algoritmusnak h\[AAcute]rom roppant hasznos tulajdons\[AAcute]ga is \
van. El\[ODoubleAcute]sz\[ODoubleDot]r is gyors nagyon nagy sz\[AAcute]mokra \
is, m\[AAcute]sodszor, kisz\[UDoubleAcute]ri a Carmichael-sz\[AAcute]mokat, \
harmadszor pedig ugyanannyi lefut\[AAcute]ssal nagyobb \
val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]get ad az \
eredm\[EAcute]nyre, mint az el\[ODoubleAcute]z\[ODoubleAcute] k\[EAcute]t \
teszt.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]],
Cell[CellGroupData[{
Cell[TextData[StyleBox["\[CapitalODoubleDot]sszegz\[EAcute]s:",
FontWeight->"Bold"]], "Subtitle"],
Cell["\<\
A notebookban defini\[AAcute]ltuk a pr\[IAcute]msz\[AAcute]mokat \[EAcute]s \
a vel\[UDoubleDot]k kapcsolatos fontosabb fogalmakat, melyek az \
elm\[EAcute]leti h\[AAcute]tt\[EAcute]r meg\[EAcute]rt\[EAcute]s\[EAcute]hez \
sz\[UDoubleDot]ks\[EAcute]gesek voltak. Ezut\[AAcute]n \
p\[EAcute]ld\[AAcute]kat hoztunk a pr\[IAcute]mek fontos gyakorlati alkalmaz\
\[AAcute]saira, f\[ODoubleAcute]leg a kriptogr\[AAcute]fia ter\[EAcute]n, \
\[EAcute]s megmutattuk, hogy mi\[EAcute]rt is van sz\[UDoubleDot]ks\[EAcute]g \
pr\[IAcute]mtesztekre. Az elm\[EAcute]leti r\[EAcute]szt n\[EAcute]gy pr\
\[IAcute]mteszt gyakorlati megval\[OAcute]s\[IAcute]t\[AAcute]sa k\
\[ODoubleDot]vette. Mind a n\[EAcute]gy esetben el\[ODoubleAcute]sz\
\[ODoubleDot]r az adott teszt elm\[EAcute]leti h\[AAcute]tter\[EAcute]t \
\[IAcute]rtuk le \[EAcute]s egy r\[EAcute]sz\[EAcute]t bizony\[IAcute]tottuk \
is, majd ezt k\[ODoubleDot]vette az algoritmus \
programoz\[AAcute]s\[AAcute]nak magyar\[AAcute]zata \[EAcute]s v\[EAcute]g\
\[UDoubleDot]l maga a teszt.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[CellGroupData[{
Cell[TextData[StyleBox["Tov\[AAcute]bbi eredm\[EAcute]nyek",
FontWeight->"Bold"]], "Subsection",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
L\[AAcute]ttuk, hogy minden tesztnek volt valami h\[AAcute]tr\[AAcute]nya, \
legt\[ODoubleDot]bbsz\[ODoubleDot]r az, hogy nem garant\[AAcute]lt t\
\[ODoubleDot]k\[EAcute]letes eredm\[EAcute]nyt egy sz\[AAcute]m pr\[IAcute]m \
volt\[AAcute]ra csak nagy val\[OAcute]sz\[IAcute]n\[UDoubleAcute]s\[EAcute]g\
\[UDoubleAcute]t. Ismert azonban m\[AAcute]r olyan, szint\[EAcute]n gyors \
algoritmus, amely teljesen biztos eredm\[EAcute]nyt ad.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell["\<\
Fontos megjegyezni, hogy a fent l\[AAcute]tott titkos\[IAcute]t\[AAcute]si \
m\[OAcute]dszerek nagy m\[EAcute]rt\[EAcute]kben arra \
\[EAcute]p\[UDoubleDot]lnek, hogy nem tudunk nagy sz\[AAcute]mokat gyorsan \
faktoriz\[AAcute]lni, azaz pr\[IAcute]mek szorzat\[AAcute]ra bontani. Azonban \
nincs olyan matematikai eredm\[EAcute]ny, amely azt mutatn\[AAcute], hogy \
erre nem is l\[EAcute]tezik algoritmus, s\[ODoubleAcute]t egy n\[EAcute]mik\
\[EAcute]pp hasonl\[OAcute] probl\[EAcute]m\[AAcute]ra (eg\[EAcute]sz egy\
\[UDoubleDot]tthat\[OAcute]s polinomok irreducibilis t\[EAcute]nyez\
\[ODoubleAcute]k szorzat\[AAcute]ra bont\[AAcute]sa) A. Lenstra, H. Lenstra \
\[EAcute]s Lov\[AAcute]sz L\[AAcute]szl\[OAcute] m\[AAcute]r tal\[AAcute]ltak \
gyors megold\[AAcute]st.\
\>", "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
" ",
StyleBox["\[CapitalEAcute]rdekess\[EAcute]gek",
FontWeight->"Bold"],
": \n ",
StyleBox[" 1",
FontWeight->"Bold"],
".Ha valaki kital\[AAcute]ln\[AAcute] a pr\[IAcute]mfaktoriz\[AAcute]l\
\[OAcute] algoritmust, akkor a legt\[ODoubleDot]bb titkos\[IAcute]t\[AAcute]s \
ezzel haszn\[AAcute]lhatatlann\[AAcute] v\[AAcute]lna. M\[AAcute]rpedig, mint \
ahogy az el\[ODoubleAcute]bb eml\[IAcute]tett\[UDoubleDot]k hasonl\[OAcute] \
probl\[EAcute]m\[AAcute]ra m\[AAcute]r van algoritmus \[EAcute]s egyes \
matematikusok szerint p\[AAcute]r \[EAcute]vtizeden bel\[UDoubleDot]l a sz\
\[AAcute]mok kanonikus alakra hoz\[AAcute]sa is megoldott lesz.\n ",
StyleBox[" 2",
FontWeight->"Bold"],
".Az al\[AAcute]bbi honlapon az igaz\[AAcute]n nagy pr\[IAcute]mek vannak \
csoportos\[IAcute]tva rengeteg tulajdons\[AAcute]guk szerint. A teljess\
\[EAcute]g ig\[EAcute]nye n\[EAcute]lk\[UDoubleDot]l csak p\[AAcute]rat eml\
\[IAcute]tve: Mersenne-pr\[IAcute]mek, ikerpr\[IAcute]mek, \
faktori\[AAcute]lis pr\[IAcute]mek. ",
ButtonBox["http://primes.utm.edu/largest.html",
ButtonData:>{
URL[ "http://primes.utm.edu/largest.html"], None},
ButtonStyle->"Hyperlink"]
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[{
" ",
StyleBox["Irodalomjegyz\[EAcute]k",
FontWeight->"Bold"],
":\n Katona Gyula Y., Recski Andr\[AAcute]s, \
Szab\[OAcute] Csaba: ",
StyleBox["A sz\[AAcute]m\[IAcute]t\[AAcute]studom\[AAcute]ny alapjai.",
FontSlant->"Italic"],
" Typotex Kiad\[OAcute], Budapest 2002.\n \
Freud R\[OAcute]bert, Gyarmati Edit: ",
StyleBox["Sz\[AAcute]melm\[EAcute]let.",
FontSlant->"Italic"],
" Universitas-Nemzeti Tank\[ODoubleDot]nyvkiad\[OAcute], Budapest 2000.\n"
}], "Text",
FontFamily->"Times New Roman",
FontSize->14],
Cell[TextData[StyleBox["Budapest 2006.12.10.",
FontWeight->"Bold"]], "Text",
FontFamily->"Times New Roman",
FontSize->14]
}, Open ]]
}, Open ]]
}, Open ]]
},
FrontEndVersion->"5.2 for Microsoft Windows",
ScreenRectangle->{{0, 1280}, {0, 877}},
AutoGeneratedPackage->Automatic,
WindowSize->{1272, 843},
WindowMargins->{{0, Automatic}, {Automatic, 0}}
]
(*******************************************************************
Cached data follows. If you edit this Notebook file directly, not
using Mathematica, you must remove the line containing CacheID at
the top of the file. The cache data will then be recreated when
you save this file from within Mathematica.
*******************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1776, 53, 130, 2, 93, "Title"],
Cell[1909, 57, 197, 3, 76, "Text"],
Cell[2109, 62, 137, 3, 50, "Input",
InitializationCell->True],
Cell[CellGroupData[{
Cell[2271, 69, 112, 2, 54, "Subsubtitle"],
Cell[2386, 73, 622, 10, 54, "Text"],
Cell[3011, 85, 295, 4, 34, "Text"],
Cell[CellGroupData[{
Cell[3331, 93, 185, 7, 69, "Section"],
Cell[3519, 102, 221, 5, 34, "Text"],
Cell[3743, 109, 633, 22, 35, "Text"],
Cell[4379, 133, 708, 25, 56, "Text"],
Cell[5090, 160, 383, 15, 35, "Text"],
Cell[5476, 177, 2168, 77, 155, "Text"],
Cell[7647, 256, 221, 5, 34, "Text"],
Cell[7871, 263, 1079, 23, 74, "Text"],
Cell[8953, 288, 215, 5, 34, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[9205, 298, 213, 7, 69, "Section"],
Cell[9421, 307, 803, 28, 58, "Text"],
Cell[10227, 337, 886, 33, 56, "Text"],
Cell[11116, 372, 1128, 37, 98, "Text"],
Cell[12247, 411, 7865, 210, 97, "Text"],
Cell[20115, 623, 881, 29, 77, "Text"],
Cell[20999, 654, 147, 6, 34, "Text"],
Cell[21149, 662, 56, 1, 30, "Input"],
Cell[CellGroupData[{
Cell[21230, 667, 40, 1, 30, "Input"],
Cell[21273, 670, 140, 2, 29, "Output"]
}, Open ]],
Cell[21428, 675, 781, 24, 56, "Text"],
Cell[22212, 701, 157, 6, 34, "Text"],
Cell[22372, 709, 90, 1, 30, "Input"],
Cell[CellGroupData[{
Cell[22487, 714, 40, 1, 30, "Input"],
Cell[22530, 717, 78, 1, 29, "Output"]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell[22657, 724, 190, 7, 70, "Section"],
Cell[22850, 733, 870, 29, 56, "Text"],
Cell[23723, 764, 3664, 105, 34, "Text"],
Cell[CellGroupData[{
Cell[27412, 873, 62, 1, 30, "Input"],
Cell[27477, 876, 36, 1, 29, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[27550, 882, 70, 1, 30, "Input"],
Cell[27623, 885, 38, 1, 29, "Output"]
}, Open ]],
Cell[27676, 889, 3448, 94, 57, "Text"],
Cell[31127, 985, 12729, 315, 120, "Text"],
Cell[43859, 1302, 308, 12, 35, "Text"],
Cell[44170, 1316, 9167, 271, 158, "Text"],
Cell[53340, 1589, 2432, 67, 39, "Text"],
Cell[55775, 1658, 1163, 30, 32, "Text"],
Cell[56941, 1690, 1355, 40, 32, "Text"],
Cell[58299, 1732, 263, 7, 35, "Text"],
Cell[58565, 1741, 148, 6, 35, "Text"],
Cell[58716, 1749, 1440, 41, 33, "Text"],
Cell[60159, 1792, 629, 24, 35, "Text"],
Cell[60791, 1818, 161, 6, 35, "Text"],
Cell[60955, 1826, 1375, 42, 39, "Text"],
Cell[62333, 1870, 8211, 224, 166, "Text"],
Cell[70547, 2096, 2637, 86, 53, "Text"],
Cell[73187, 2184, 3258, 101, 52, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[76482, 2290, 216, 9, 71, "Section"],
Cell[76701, 2301, 3595, 113, 36, "Text"],
Cell[80299, 2416, 1503, 48, 33, "Text"],
Cell[81805, 2466, 6915, 198, 94, "Text"],
Cell[88723, 2666, 1342, 44, 52, "Text"],
Cell[90068, 2712, 4494, 131, 95, "Text"],
Cell[94565, 2845, 2820, 89, 52, "Text"],
Cell[97388, 2936, 2497, 75, 52, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[99922, 3016, 98, 1, 70, "Section"],
Cell[100023, 3019, 681, 12, 54, "Text"],
Cell[100707, 3033, 834, 29, 35, "Text"],
Cell[101544, 3064, 4425, 115, 80, "Text"],
Cell[105972, 3181, 1316, 29, 72, "Text"],
Cell[107291, 3212, 80, 1, 31, "Input"],
Cell[CellGroupData[{
Cell[107396, 3217, 138, 3, 30, "Input"],
Cell[107537, 3222, 66, 1, 29, "Output"]
}, Open ]],
Cell[107618, 3226, 624, 17, 54, "Text"],
Cell[108245, 3245, 86, 1, 30, "Input"],
Cell[108334, 3248, 139, 3, 30, "Input"],
Cell[108476, 3253, 1883, 57, 33, "Text"],
Cell[110362, 3312, 19173, 546, 234, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[129572, 3863, 211, 4, 69, "Section"],
Cell[129786, 3869, 717, 12, 54, "Text"],
Cell[130506, 3883, 654, 11, 54, "Text"]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell[131209, 3900, 86, 1, 53, "Subtitle"],
Cell[131298, 3903, 1967, 57, 42, "Text"],
Cell[133268, 3962, 9992, 316, 97, "Text"],
Cell[143263, 4280, 135, 6, 35, "Text"],
Cell[143401, 4288, 350, 11, 34, "Text"],
Cell[143754, 4301, 112, 2, 30, "Input"],
Cell[143869, 4305, 1802, 48, 57, "Text"],
Cell[145674, 4355, 87, 1, 30, "Input"],
Cell[145764, 4358, 2295, 60, 64, "Text"],
Cell[148062, 4420, 737, 13, 167, "Input"],
Cell[148802, 4435, 54, 1, 30, "Input"],
Cell[148859, 4438, 62, 1, 30, "Input"],
Cell[148924, 4441, 1266, 30, 60, "Text"],
Cell[150193, 4473, 228, 6, 34, "Text"],
Cell[150424, 4481, 2142, 58, 114, "Text"],
Cell[152569, 4541, 1464, 26, 348, "Input"],
Cell[154036, 4569, 60, 1, 30, "Input"],
Cell[154099, 4572, 639, 16, 54, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[154775, 4593, 90, 1, 53, "Subtitle"],
Cell[154868, 4596, 1206, 35, 33, "Text"],
Cell[156077, 4633, 2058, 52, 94, "Text"],
Cell[158138, 4687, 13510, 388, 366, "Text"],
Cell[171651, 5077, 590, 16, 33, "Text"],
Cell[172244, 5095, 2306, 65, 69, "Text"],
Cell[174553, 5162, 2290, 66, 81, "Text"],
Cell[176846, 5230, 9661, 256, 268, "Text"],
Cell[186510, 5488, 123, 3, 35, "Text"],
Cell[186636, 5493, 4552, 108, 171, "Text"],
Cell[191191, 5603, 1794, 45, 68, "Text"],
Cell[192988, 5650, 1293, 23, 323, "Input"],
Cell[CellGroupData[{
Cell[194306, 5677, 63, 1, 30, "Input"],
Cell[194372, 5680, 461, 9, 25, "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[194870, 5694, 262, 4, 70, "Input"],
Cell[195135, 5700, 856, 15, 63, "Print"]
}, Open ]],
Cell[196006, 5718, 346, 7, 34, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[196389, 5730, 80, 1, 53, "Subtitle"],
Cell[196472, 5733, 2729, 64, 73, "Text"],
Cell[199204, 5799, 2406, 68, 52, "Text"],
Cell[201613, 5869, 616, 23, 55, "Text"],
Cell[202232, 5894, 482, 10, 54, "Text"],
Cell[202717, 5906, 1601, 42, 33, "Text"],
Cell[204321, 5950, 413, 10, 35, "Text"],
Cell[204737, 5962, 3391, 92, 139, "Text"],
Cell[208131, 6056, 386, 9, 34, "Text"],
Cell[208520, 6067, 972, 29, 49, "Text"],
Cell[209495, 6098, 16055, 515, 130, "Text"],
Cell[225553, 6615, 4385, 146, 52, "Text"],
Cell[229941, 6763, 2397, 55, 112, "Text"],
Cell[232341, 6820, 144, 7, 35, "Text"],
Cell[232488, 6829, 2579, 59, 72, "Text"],
Cell[235070, 6890, 1069, 19, 287, "Input"],
Cell[CellGroupData[{
Cell[236164, 6913, 58, 1, 30, "Input"],
Cell[236225, 6916, 521, 9, 25, "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[236783, 6930, 257, 4, 70, "Input"],
Cell[237043, 6936, 918, 16, 63, "Print"]
}, Open ]],
Cell[237976, 6955, 336, 9, 34, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[238349, 6969, 86, 1, 53, "Subtitle"],
Cell[238438, 6972, 4600, 127, 62, "Text"],
Cell[243041, 7101, 2792, 76, 58, "Text"],
Cell[245836, 7179, 3291, 92, 57, "Text"],
Cell[249130, 7273, 297, 8, 34, "Text"],
Cell[249430, 7283, 1086, 28, 53, "Text"],
Cell[250519, 7313, 264, 6, 34, "Text"],
Cell[250786, 7321, 1522, 39, 88, "Text"],
Cell[252311, 7362, 903, 19, 88, "Text"],
Cell[253217, 7383, 1109, 26, 88, "Text"],
Cell[254329, 7411, 123, 3, 35, "Text"],
Cell[254455, 7416, 3976, 99, 103, "Text"],
Cell[258434, 7517, 2221, 38, 613, "Input"],
Cell[CellGroupData[{
Cell[260680, 7559, 59, 1, 30, "Input"],
Cell[260742, 7562, 498, 10, 25, "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[261277, 7577, 258, 4, 70, "Input"],
Cell[261538, 7583, 886, 16, 63, "Print"]
}, Open ]],
Cell[262439, 7602, 509, 10, 54, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[262985, 7617, 99, 1, 53, "Subtitle"],
Cell[263087, 7620, 1105, 18, 74, "Text"],
Cell[CellGroupData[{
Cell[264217, 7642, 147, 3, 39, "Subsection"],
Cell[264367, 7647, 509, 9, 54, "Text"],
Cell[264879, 7658, 844, 14, 74, "Text"],
Cell[265726, 7674, 1270, 27, 117, "Text"],
Cell[266999, 7703, 609, 15, 95, "Text"],
Cell[267611, 7720, 127, 3, 35, "Text"]
}, Open ]]
}, Open ]]
}, Open ]]
}
]
*)
(*******************************************************************
End of Mathematica Notebook file.
*******************************************************************)