(***********************************************************************

                    Mathematica-Compatible Notebook

This notebook can be used on any computer system with Mathematica 4.0,
MathReader 4.0, or any compatible application. 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[     23693,        663]*)
(*NotebookOutlinePosition[     30617,        873]*)
(*  CellTagsIndexPosition[     30049,        846]*)
(*WindowFrame->Normal*)



Notebook[{
Cell[TextData[{
  "NumberTheory",
  StyleBox["`", "MB"],
  "PrimeQ",
  StyleBox["`", "MB"]
}], "Subsection",
  CellTags->{"S5.69.1", "1.1"}],

Cell[TextData[{
  "This package implements primality proving. If ",
  StyleBox["ProvablePrimeQ[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " returns ",
  StyleBox["True", "MR"],
  ", then the number ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " can be mathematically proven to be prime. In addition, ",
  StyleBox["PrimeQCertificate[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " prints a certificate that can be used to verify that ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " is prime or composite. Note that the built\[Hyphen]in primality testing \
function ",
  StyleBox["PrimeQ", "MR"],
  " does not actually give a proof that a number is prime. However, as of \
this writing, there are no known examples where ",
  StyleBox["PrimeQ", "MR"],
  " fails. "
}], "Text",
  CellTags->{"S5.69.1", "1.2"}],

Cell[BoxData[
    FormBox[
      StyleBox[
        FrameBox[
          StyleBox[GridBox[{
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"ProvablePrimeQ[\\\\\\\"\\\
\", \\\"MR\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\)\
\\!\\(\\*StyleBox[\\\"\\\\\\\"]\\\\\\\"\\\", \\\"MR\\\"]\\) \"\>", "\<\"give \
\\!\\(\\*StyleBox[\\\"\\\\\\\"True\\\\\\\"\\\", \\\"MR\\\"]\\) if \
\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\) can be proved to \
be prime, and \\!\\(\\*StyleBox[\\\"\\\\\\\"False\\\\\\\"\\\", \\\"MR\\\"]\\) \
if \\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\) can be proved \
to be composite\"\>"},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"ProvablePrimeQ[\\\\\\\"\\\
\", \\\"MR\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\)\
\\!\\(\\*StyleBox[\\\"\\\\\\\",\\\\\\\"\\\", \\\"MR\\\"]\\) \
\\!\\(\\*StyleBox[\\\"\\\\\\\"Certificate\\\\\\\"\\\", \\\"MR\\\"]\\) \
\\!\\(\\*StyleBox[\\\"\\\\\\\"->\\\\\\\"\\\", \\\"MR\\\"]\\) \
\\!\\(\\*StyleBox[\\\"\\\\\\\"True]\\\\\\\"\\\", \\\"MR\\\"]\\) \"\>", \
"\<\"print a certificate that can be used to verify the result\"\>"},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"PrimeQCertificate[\\\\\\\"\
\\\", \\\"MR\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \
\\\"TI\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"]\\\\\\\"\\\", \\\"MR\\\"]\\) \
\"\>", "\<\"print a certificate that \
\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\) is prime or that \
\\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\"TI\\\"]\\) is \
composite\"\>"},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"PrimeQCertificateCheck[\\\
\\\\\"\\\", \\\"MR\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"cert\\\\\\\"\\\", \
\\\"TI\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\",\\\\\\\"\\\", \\\"MR\\\"]\\) \\!\
\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \
\\\"TI\\\"]\\)\\!\\(\\*StyleBox[\\\"\\\\\\\"]\\\\\\\"\\\", \\\"MR\\\"]\\) \
\"\>", "\<\"verify that the certificate \
\\!\\(\\*StyleBox[\\\"\\\\\\\"cert\\\\\\\"\\\", \\\"TI\\\"]\\) proves the \
primality or compositeness of \\!\\(\\*StyleBox[\\\"\\\\\\\"n\\\\\\\"\\\", \\\
\"TI\\\"]\\)\"\>"}
                },
              ColumnAlignments->{Right, Left}],
            GridBoxOptions->{RowLines->False}]],
        "2ColumnBox"], TraditionalForm]], "Text",
  CellTags->{"S5.69.1", "1.3"}],

Cell["Proving primality or compositeness. ", "Caption",
  CellTags->"S5.69.1"],

Cell[TextData[{
  "The functions provided in this package not only prove primality, but they \
also generate a ",
  StyleBox["certificate", "TI"],
  " of primality. A certificate of primality is a relatively short set of \
data that can be easily used to prove primality. The word easily means that \
using the data to prove primality is much easier and faster than generating \
the data in the first place. As a simple example of a certificate, the \
factors of a composite number provide a certificate of compositeness. \
Multiplying the numbers together to show that they are the factors is much \
easier than finding the factors. The advantage of providing certificates is \
that the user does not have to trust the internal mechanism of the algorithm \
that generated the certificate. It is fairly easy to write a program (in any \
system) that checks that the certificate provides a proof of primality. "
}], "Text",
  CellTags->{"S5.69.1", "1.4"}],

Cell["This loads the package. ", "MathCaption",
  CellTags->{"S5.69.1", "1.5"}],

Cell["<<NumberTheory`PrimeQ`", "Input",
  CellLabel->"In[1]:= ",
  CellTags->"S5.69.1"],

Cell[TextData[{
  StyleBox["PrimeQ", "MR"],
  " indicates that the number 1093 is prime. "
}], "MathCaption",
  CellTags->{"S5.69.1", "1.6"}],

Cell[CellGroupData[{

Cell["PrimeQ[1093]", "Input",
  CellLabel->"In[2]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \(True\)], "Output",
  CellLabel->"Out[2]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell[TextData[{
  StyleBox["ProvablePrimeQ", "MR"],
  " gives the same result, but it has generated a certificate. "
}], "MathCaption",
  CellTags->{"S5.69.1", "1.7"}],

Cell[CellGroupData[{

Cell["ProvablePrimeQ[1093]", "Input",
  CellLabel->"In[3]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \(True\)], "Output",
  CellLabel->"Out[3]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["This prints the certificate. ", "MathCaption",
  CellTags->{"S5.69.1", "1.8"}],

Cell[CellGroupData[{

Cell["PrimeQCertificate[1093]", "Input",
  CellLabel->"In[4]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({1093, 
      5, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}, {13, 
          2, {2, {3, 2, {2}}}}}}\)], "Output",
  CellLabel->"Out[4]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["This prints the certificate directly. ", "MathCaption",
  CellTags->{"S5.69.1", "1.9"}],

Cell[CellGroupData[{

Cell["ProvablePrimeQ[1093, Certificate->True]", "Input",
  CellLabel->"In[5]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({True, {1093, 
        5, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}, {13, 
            2, {2, {3, 2, {2}}}}}}}\)], "Output",
  CellLabel->"Out[5]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell[TextData[{
  "The certificate of primality used in this package for large ",
  StyleBox["n", "TI"],
  " is based on the theory of elliptic curves. The basic idea was discovered \
by S.\[NonBreakingSpace]Goldwasser and J.\[NonBreakingSpace]Kilian, \
\[OpenCurlyDoubleQuote]Almost All Primes Can Be Quickly Certified,\
\[CloseCurlyDoubleQuote] in ",
  StyleBox["Proc. 18th STOC", "TI"],
  ", 1986, pp. 316\[Dash]329. Their algorithm was only of theoretical \
significance, however. A.\[NonBreakingSpace]O.\[NonBreakingSpace]L.\
\[NonBreakingSpace]Atkin found a way to make it practical by using ideas from \
complex multiplication, which is a branch of number theory that combines the \
fields of complex analysis, Galois theory and modular forms. This method was \
implemented very successfully by F.\[NonBreakingSpace]Morain in \
\[OpenCurlyDoubleQuote]Implementation of the \
Atkin\[Hyphen]Goldwasser\[Hyphen]Kilian Primality Testing Algorithm,\
\[CloseCurlyDoubleQuote] ",
  StyleBox["INRIA Research Report", "TI"],
  ", # 911, October 1988. In November 1989, Morain was able to give a \
primality proof for a 1065\[Hyphen]digit number, the first titanic prime (",
  Cell[BoxData[
      \(TraditionalForm\`\(\(>\)\(1000\)\)\)], "InlineFormula"],
  " digits) to be tested without special purpose algorithms. Since that time \
Atkin and Morain have written an extensive treatise on the algorithm: A.\
\[NonBreakingSpace]O.\[NonBreakingSpace]L. Atkin and F. Morain, \
\[OpenCurlyDoubleQuote]Elliptic Curves and Primality Proving,\
\[CloseCurlyDoubleQuote] ",
  StyleBox["Mathematics of Computation", "TI"],
  ", 1993, 29\[Dash]68. \nFor an introduction to primality testing and \
elliptic curves, see D.\[NonBreakingSpace]Bressoud, ",
  StyleBox["Factorization and Primality Testing", "TI"],
  ", Springer\[Hyphen]Verlag, 1989. \nThis package can also be used to \
generate certificates of compositeness for composite numbers. These \
certificates are based on showing that simple properties that are true of \
prime numbers are not true for the given number. For example, ",
  StyleBox["PrimeQCertificate[3837523]", "MR"],
  " returns the certificate ",
  StyleBox["{2,", "MR"],
  " ",
  StyleBox["3837522,", "MR"],
  " ",
  StyleBox["3837523}", "MR"],
  ", which is intended to show that ",
  Cell[BoxData[
      \(TraditionalForm\`2\^3837522\ \((mod\ 3837523)\)\)], "InlineFormula"],
  " is not equal to 1. \n",
  StyleBox["ProvablePrimeQ[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " returns ",
  StyleBox["True", "MR"],
  " or ",
  StyleBox["False", "MR"],
  " depending on whether ",
  StyleBox["n", "MR"],
  " is prime or not. The certificate for primality or compositeness is \
generated by ",
  StyleBox["PrimeQCertificate[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  ". ",
  StyleBox["ProvablePrimeQ", "MR"],
  " calls ",
  StyleBox["PrimeQCertificate", "MR"],
  " and stores the result, so it does not take any extra time to create a \
certificate once ",
  StyleBox["ProvablePrimeQ", "MR"],
  " has returned an answer. The certificate generated by ",
  StyleBox["PrimeQCertificate", "MR"],
  " can be checked by ",
  StyleBox["PrimeQCertificateCheck", "MR"],
  ". This function recognizes whether the certificate asserts primality or \
compositeness and then uses the certificate to verify the assertion. "
}], "Text",
  CellTags->{"S5.69.1", "1.10"}],

Cell["This prints the certificate of the prime number. ", "MathCaption",
  CellTags->{"S5.69.1", "1.11"}],

Cell[CellGroupData[{

Cell["\<\
ProvablePrimeQ[1093,
      Certificate -> True]\
\>", "Input",
  CellLabel->"In[6]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({True, {1093, 
        5, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}, {13, 
            2, {2, {3, 2, {2}}}}}}}\)], "Output",
  CellLabel->"Out[6]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["This verifies primality using the certificate. ", "MathCaption",
  CellTags->{"S5.69.1", "1.12"}],

Cell[CellGroupData[{

Cell["PrimeQCertificateCheck[Last[%], 1093]", "Input",
  CellLabel->"In[7]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \(True\)], "Output",
  CellLabel->"Out[7]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["\<\
Here is the certificate for a composite number. You can recognize a \
certificate of compositeness because it will always be a list of three \
integers. \
\>", "MathCaption",
  CellTags->{"S5.69.1", "1.13"}],

Cell[CellGroupData[{

Cell["PrimeQCertificate[1093 * 3511]", "Input",
  CellLabel->"In[8]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({2, 3837522, 3837523}\)], "Output",
  CellLabel->"Out[8]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["This verifies the compositeness. ", "MathCaption",
  CellTags->{"S5.69.1", "1.14"}],

Cell[CellGroupData[{

Cell["PrimeQCertificateCheck[%, 3837523]", "Input",
  CellLabel->"In[9]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \(True\)], "Output",
  CellLabel->"Out[9]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell[TextData[{
  "The built\[Hyphen]in function ",
  StyleBox["PrimeQ", "MR"],
  " first tests for divisibility using small primes, then uses the Miller\
\[Hyphen]Rabin strong pseudoprime test base 2 and base 3, and then uses the \
Lucas test. As of 1998, this procedure is known to be correct only for ",
  Cell[BoxData[
      \(TraditionalForm\`n < 10\^16\)], "InlineFormula"],
  ", and it is conceivable that for larger ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " it could claim a composite number to be prime. However, it is a \
mathematical theorem that when ",
  StyleBox["PrimeQ[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " returns ",
  StyleBox["False", "MR"],
  ", the number ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " is genuinely composite. Thus ",
  StyleBox["PrimeQ[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " can only fail if ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " is composite but ",
  StyleBox["PrimeQ", "MR"],
  " declares it to be prime. It is important to note that ",
  StyleBox["PrimeQ", "MR"],
  " is deterministic; no computations based on random numbers are involved. \n\
This package is not meant to replace the built\[Hyphen]in primality tester ",
  StyleBox["PrimeQ", "MR"],
  " but rather to allow one to be completely secure that a number is truly \
prime. The package should be used only to certify results after all the \
number theoretical work has been done. For example, it would be a mistake to \
use ",
  StyleBox["ProvablePrimeQ", "MR"],
  " as a primality test for an integer factoring algorithm. Rather, only when \
the complete factorization has been achieved (using ",
  StyleBox["PrimeQ", "MR"],
  " for primality testing) would one use ",
  StyleBox["ProvablePrimeQ", "MR"],
  " to certify the primality of the prime factors given by the algorithm. The \
reason for this is that ",
  StyleBox["PrimeQ", "MR"],
  " will be, in general, several orders of magnitude faster than ",
  StyleBox["ProvablePrimeQ", "MR"],
  ". \nAs noted above, there is a possibility that ",
  StyleBox["PrimeQ", "MR"],
  " is incorrect, that is, it asserts that a number is prime when it is \
really composite. It is unclear whether ",
  StyleBox["ProvablePrimeQ", "MR"],
  " always detects this; but if it does, a warning message is generated \
indicating a counterexample to ",
  StyleBox["PrimeQ", "MR"],
  ", and ",
  StyleBox["False", "MR"],
  " is returned. This behavior can be simulated by artificially setting ",
  StyleBox["PrimeQ[", "MR"],
  StyleBox["n", "TI"],
  StyleBox["]", "MR"],
  " to ",
  StyleBox["True", "MR"],
  " for a known composite ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  ". "
}], "Text",
  CellTags->{"S5.69.1", "1.15"}],

Cell[TextData[{
  "Here ",
  StyleBox["PrimeQ", "MR"],
  " is artificially set to give an incorrect answer. ",
  StyleBox["ProvablePrimeQ", "MR"],
  " detects that ",
  StyleBox["PrimeQ", "MR"],
  " is incorrect, prints a warning message, and returns the correct answer. "
}], "MathCaption",
  CellTags->{"S5.69.1", "1.16"}],

Cell[CellGroupData[{

Cell["\<\
(Unprotect[PrimeQ];
PrimeQ[38200901201] = True;
ProvablePrimeQ[38200901201])\
\>", "Input",
  CellLabel->"In[10]:= ",
  CellTags->"S5.69.1"],

Cell["\<\
SqrtMod::fail: Warning: $IterationLimit exceeded; \
PrimeQ[38200901201] may be incorrect.

PrimeQCertificate::qrsqrtmod:
   Failure of elliptic curves certificate for p = 38200901201. Unable to find \
quadratic representation 4*p = u^2 + 7*v^2 due to failure of SqrtMod[-7 , p].

PrimeQCertificate::false:
   Warning: PrimeQCertificate has detected a counterexample to PrimeQ:
    PowerMod[3, 38200901200, 38200901201] != 1.
\
\>", "Message",
  CellTags->"S5.69.1"],

Cell["False", "Output",
  CellLabel->"Out[10]=",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell[BoxData[
    FormBox[
      StyleBox[
        FrameBox[
          StyleBox[GridBox[{
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"option name\\\\\\\"\\\", \
\\\"TI\\\"]\\) \"\>", "\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"default \
value\\\\\\\"\\\", \\\"TI\\\"]\\) \"\>", "\[Null]"},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"SmallPrime\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", "\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"10^10\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", \("lower bound for using the Atkin\[Hyphen]Morain \
primality test"\)},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"Certificate\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", "\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"False\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", \("whether to print a certificate"\)},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"PollardPTest\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", \
"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"Automatic\\\\\\\"\\\", \\\"MR\\\"]\\) \
\"\>", 
                  RowBox[{"\<\"whether to apply the Pollard \"\>", 
                    StyleBox[\(p - 1\),
                      
                      "InlineFormula"], "\<\" factoring algorithm in the \
search for the next prime in the recursive certificate\"\>"}]},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"PollardRhoTest\\\\\\\"\\\"\
, \\\"MR\\\"]\\) \"\>", \
"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"Automatic\\\\\\\"\\\", \\\"MR\\\"]\\) \
\"\>", 
                  RowBox[{"\<\"whether to apply the Pollard \"\>", 
                    StyleBox["\[Rho]",
                      
                      "InlineFormula"], "\<\" factoring algorithm in the \
search for the next prime in the recursive certificate\"\>"}]},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"TrialDivisionLimit\\\\\\\"\
\\\", \\\"MR\\\"]\\) \"\>", \
"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"Automatic\\\\\\\"\\\", \\\"MR\\\"]\\) \
\"\>", "\<\"number of primes to be used in the trial division part of \
\\!\\(\\*StyleBox[\\\"\\\\\\\"PrimeQCertificate\\\\\\\"\\\", \\\"MR\\\"]\\)\"\
\>"},
                {"\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"PrimeQMessages\\\\\\\"\\\"\
, \\\"MR\\\"]\\) \"\>", "\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"False\\\\\\\"\\\", \
\\\"MR\\\"]\\) \"\>", \("whether to print out the progress of the \
algorithm"\)}
                },
              ColumnAlignments->{Left}],
            GridBoxOptions->{RowLines->{True, False}}]],
        "3ColumnBox"], TraditionalForm]], "Text",
  CellTags->{"S5.69.1", "1.17"}],

Cell[TextData[{
  "Options for ",
  StyleBox["ProvablePrimeQ", "MR"],
  " and ",
  StyleBox["PrimeQCertificate", "MR"],
  "."
}], "Caption",
  CellTags->"S5.69.1"],

Cell[TextData[{
  "When ",
  Cell[BoxData[
      \(TraditionalForm\`n\)], "InlineFormula"],
  " is larger than the value of the option ",
  StyleBox["SmallPrime", "MR"],
  ", ",
  StyleBox["ProvablePrimeQ", "MR"],
  " uses the Atkin\[Hyphen]Morain test as described above. This primality \
proving algorithm is suboptimal if the number is within the range of \
efficient factoring algorithms. When this is the case, a method of V.\
\[NonBreakingSpace]Pratt is preferable: V.\[NonBreakingSpace]Pratt, \
\[OpenCurlyDoubleQuote]Every Prime Has a Succinct Certificate,\
\[CloseCurlyDoubleQuote] ",
  StyleBox["SIAM Journal of Computation", "TI"],
  " 4 (1975), pages 214\[Dash]220. An implementation of this algorithm in ",
  StyleBox["Mathematica", "TI"],
  " is described in S. Wagon, ",
  StyleBox["Mathematica in Action", "TI"],
  ", W. H. Freeman, 1991, Section\[NonBreakingSpace]8.7. \nNote that you must \
use the same value of ",
  StyleBox["SmallPrime", "MR"],
  " when you check a certificate using ",
  StyleBox["PrimeQCertificate", "MR"],
  " that you used when you generated it using ",
  StyleBox["ProvablePrimeQ", "MR"],
  " or ",
  StyleBox["PrimeQCertificate", "MR"],
  ". "
}], "Text",
  CellTags->{"S5.69.1", "1.18"}],

Cell[TextData[{
  "Since the default value of ",
  StyleBox["SmallPrime", "MR"],
  " is larger than the given number, Pratt's certificate of primality is \
returned. "
}], "MathCaption",
  CellTags->{"S5.69.1", "1.19"}],

Cell[CellGroupData[{

Cell["PrimeQCertificate[3511]", "Input",
  CellLabel->"In[11]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({3511, 
      7, {2, {3, 2, {2}}, {5, 2, {2}}, {13, 
          2, {2, {3, 2, {2}}}}}}\)], "Output",
  CellLabel->"Out[11]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell[TextData[{
  "Here, the value of ",
  StyleBox["SmallPrime", "MR"],
  " has been reset so that it is less than the given number. This causes the \
Atkin\[Hyphen]Goldwasser\[Hyphen]Kilian\[Hyphen]Morain certificate to be \
returned. "
}], "MathCaption",
  CellTags->{"S5.69.1", "1.20"}],

Cell[CellGroupData[{

Cell["PrimeQCertificate[3511, SmallPrime -> 1000]", "Input",
  CellLabel->"In[12]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({{CertificatePrime \[Rule] 3511, 
        CertificatePoint \[Rule] PointEC[2, 2467, 1447, 2135, 3511], 
        CertificateK \[Rule] 32, CertificateM \[Rule] 3424, 
        CertificateNextPrime \[Rule] 107, 
        CertificateDiscriminant \[Rule] \(-7\)}, 107, 
      2, {2, {53, 2, {2, {13, 2, {2, {3, 2, {2}}}}}}}}\)], "Output",
  CellLabel->"Out[12]= ",
  CellTags->"S5.69.1"]
}, Open  ]],

Cell["\<\
For large numbers, the certificate can be quite long and involved. \
\
\>", "MathCaption",
  CellTags->{"S5.69.1", "1.21"}],

Cell[CellGroupData[{

Cell["PrimeQCertificate[10^20 + 39]", "Input",
  CellLabel->"In[13]:= ",
  CellTags->"S5.69.1"],

Cell[BoxData[
    \({{CertificatePrime \[Rule] 100000000000000000039, 
        CertificatePoint \[Rule] 
          PointEC[2, 1729260293697269439, 64272530717713441964, 
            28545061435426883889, 100000000000000000039], 
        CertificateK \[Rule] 1012, 
        CertificateM \[Rule] 100000000010180551292, 
        CertificateNextPrime \[Rule] 98814229259071691, 
        CertificateDiscriminant \[Rule] \(-43\)}, {CertificatePrime \[Rule] 
          98814229259071691, 
        CertificatePoint \[Rule] 
          PointEC[2, 14775259946196422, 20390237783617966, 79469644695126438, 
            98814229259071691], CertificateK \[Rule] 2822600, 
        CertificateM \[Rule] 98814229876628200, 
        CertificateNextPrime \[Rule] 35008229957, 
        CertificateDiscriminant \[Rule] \(-7\)}, {CertificatePrime \[Rule] 
          35008229957, 
        CertificatePoint \[Rule] 
          PointEC[5, 11747318414, 5556861890, 30747969158, 35008229957], 
        CertificateK \[Rule] 4, CertificateM \[Rule] 35008421452, 
        CertificateNextPrime \[Rule] 8752105363, 
        CertificateDiscriminant \[Rule] \(-7\)}, 8752105363, 
      2, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}, {11, 
          2, {2, {5, 2, {2}}}}, {13, 2, {2, {3, 2, {2}}}}, {43, 
          3, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}}}, {33889, 
          13, {2, {3, 2, {2}}, {353, 
              3, {2, {11, 2, {2, {5, 2, {2}}}}}}}}}}\)], "Output",
  CellLabel->"Out[13]= ",
  CellTags->"S5.69.1"]
}, Open  ]]
},
FrontEndVersion->"4.0 for X",
ScreenRectangle->{{0, 800}, {0, 600}},
WindowSize->{520, 455},
WindowMargins->{{140, Automatic}, {Automatic, 72}},
StyleDefinitions -> "HelpBrowser.nb"
]


(***********************************************************************
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->{
  "S5.69.1"->{
    Cell[1717, 49, 140, 6, 70, "Subsection",
      CellTags->{"S5.69.1", "1.1"}],
    Cell[1860, 57, 883, 25, 70, "Text",
      CellTags->{"S5.69.1", "1.2"}],
    Cell[2746, 84, 2344, 40, 70, "Text",
      CellTags->{"S5.69.1", "1.3"}],
    Cell[5093, 126, 78, 1, 70, "Caption",
      CellTags->"S5.69.1"],
    Cell[5174, 129, 954, 15, 70, "Text",
      CellTags->{"S5.69.1", "1.4"}],
    Cell[6131, 146, 79, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.5"}],
    Cell[6213, 149, 87, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[6303, 153, 141, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.6"}],
    Cell[6469, 161, 77, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[6549, 165, 86, 3, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[6650, 171, 167, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.7"}],
    Cell[6842, 179, 85, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[6930, 183, 86, 3, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[7031, 189, 84, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.8"}],
    Cell[7140, 194, 88, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[7231, 198, 180, 5, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[7426, 206, 93, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.9"}],
    Cell[7544, 211, 104, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[7651, 215, 192, 5, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[7858, 223, 3394, 74, 70, "Text",
      CellTags->{"S5.69.1", "1.10"}],
    Cell[11255, 299, 105, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.11"}],
    Cell[11385, 304, 120, 5, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[11508, 311, 192, 5, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[11715, 319, 103, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.12"}],
    Cell[11843, 324, 102, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[11948, 328, 86, 3, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[12049, 334, 217, 5, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.13"}],
    Cell[12291, 343, 95, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[12389, 347, 103, 3, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[12507, 353, 89, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.14"}],
    Cell[12621, 358, 99, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[12723, 362, 86, 3, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[12824, 368, 2820, 71, 70, "Text",
      CellTags->{"S5.69.1", "1.15"}],
    Cell[15647, 441, 324, 9, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.16"}],
    Cell[15996, 454, 150, 6, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[16149, 462, 475, 13, 70, "Message",
      CellTags->"S5.69.1"],
    Cell[16627, 477, 71, 2, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[16713, 482, 2455, 47, 70, "Text",
      CellTags->{"S5.69.1", "1.17"}],
    Cell[19171, 531, 163, 7, 70, "Caption",
      CellTags->"S5.69.1"],
    Cell[19337, 540, 1232, 30, 70, "Text",
      CellTags->{"S5.69.1", "1.18"}],
    Cell[20572, 572, 219, 6, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.19"}],
    Cell[20816, 582, 89, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[20908, 586, 168, 5, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[21091, 594, 290, 7, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.20"}],
    Cell[21406, 605, 109, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[21518, 609, 400, 8, 70, "Output",
      CellTags->"S5.69.1"],
    Cell[21933, 620, 133, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.21"}],
    Cell[22091, 628, 95, 2, 70, "Input",
      CellTags->"S5.69.1"],
    Cell[22189, 632, 1488, 28, 70, "Output",
      CellTags->"S5.69.1"]},
  "1.1"->{
    Cell[1717, 49, 140, 6, 70, "Subsection",
      CellTags->{"S5.69.1", "1.1"}]},
  "1.2"->{
    Cell[1860, 57, 883, 25, 70, "Text",
      CellTags->{"S5.69.1", "1.2"}]},
  "1.3"->{
    Cell[2746, 84, 2344, 40, 70, "Text",
      CellTags->{"S5.69.1", "1.3"}]},
  "1.4"->{
    Cell[5174, 129, 954, 15, 70, "Text",
      CellTags->{"S5.69.1", "1.4"}]},
  "1.5"->{
    Cell[6131, 146, 79, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.5"}]},
  "1.6"->{
    Cell[6303, 153, 141, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.6"}]},
  "1.7"->{
    Cell[6650, 171, 167, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.7"}]},
  "1.8"->{
    Cell[7031, 189, 84, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.8"}]},
  "1.9"->{
    Cell[7426, 206, 93, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.9"}]},
  "1.10"->{
    Cell[7858, 223, 3394, 74, 70, "Text",
      CellTags->{"S5.69.1", "1.10"}]},
  "1.11"->{
    Cell[11255, 299, 105, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.11"}]},
  "1.12"->{
    Cell[11715, 319, 103, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.12"}]},
  "1.13"->{
    Cell[12049, 334, 217, 5, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.13"}]},
  "1.14"->{
    Cell[12507, 353, 89, 1, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.14"}]},
  "1.15"->{
    Cell[12824, 368, 2820, 71, 70, "Text",
      CellTags->{"S5.69.1", "1.15"}]},
  "1.16"->{
    Cell[15647, 441, 324, 9, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.16"}]},
  "1.17"->{
    Cell[16713, 482, 2455, 47, 70, "Text",
      CellTags->{"S5.69.1", "1.17"}]},
  "1.18"->{
    Cell[19337, 540, 1232, 30, 70, "Text",
      CellTags->{"S5.69.1", "1.18"}]},
  "1.19"->{
    Cell[20572, 572, 219, 6, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.19"}]},
  "1.20"->{
    Cell[21091, 594, 290, 7, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.20"}]},
  "1.21"->{
    Cell[21933, 620, 133, 4, 70, "MathCaption",
      CellTags->{"S5.69.1", "1.21"}]}
  }
*)

(*CellTagsIndex
CellTagsIndex->{
  {"S5.69.1", 24318, 680},
  {"1.1", 28029, 779},
  {"1.2", 28123, 782},
  {"1.3", 28212, 785},
  {"1.4", 28302, 788},
  {"1.5", 28392, 791},
  {"1.6", 28487, 794},
  {"1.7", 28583, 797},
  {"1.8", 28679, 800},
  {"1.9", 28774, 803},
  {"1.10", 28870, 806},
  {"1.11", 28963, 809},
  {"1.12", 29062, 812},
  {"1.13", 29161, 815},
  {"1.14", 29260, 818},
  {"1.15", 29358, 821},
  {"1.16", 29452, 824},
  {"1.17", 29551, 827},
  {"1.18", 29645, 830},
  {"1.19", 29739, 833},
  {"1.20", 29838, 836},
  {"1.21", 29937, 839}
  }
*)

(*NotebookFileOutline
Notebook[{
Cell[1717, 49, 140, 6, 70, "Subsection",
  CellTags->{"S5.69.1", "1.1"}],
Cell[1860, 57, 883, 25, 70, "Text",
  CellTags->{"S5.69.1", "1.2"}],
Cell[2746, 84, 2344, 40, 70, "Text",
  CellTags->{"S5.69.1", "1.3"}],
Cell[5093, 126, 78, 1, 70, "Caption",
  CellTags->"S5.69.1"],
Cell[5174, 129, 954, 15, 70, "Text",
  CellTags->{"S5.69.1", "1.4"}],
Cell[6131, 146, 79, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.5"}],
Cell[6213, 149, 87, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[6303, 153, 141, 4, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.6"}],

Cell[CellGroupData[{
Cell[6469, 161, 77, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[6549, 165, 86, 3, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[6650, 171, 167, 4, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.7"}],

Cell[CellGroupData[{
Cell[6842, 179, 85, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[6930, 183, 86, 3, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[7031, 189, 84, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.8"}],

Cell[CellGroupData[{
Cell[7140, 194, 88, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[7231, 198, 180, 5, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[7426, 206, 93, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.9"}],

Cell[CellGroupData[{
Cell[7544, 211, 104, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[7651, 215, 192, 5, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[7858, 223, 3394, 74, 70, "Text",
  CellTags->{"S5.69.1", "1.10"}],
Cell[11255, 299, 105, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.11"}],

Cell[CellGroupData[{
Cell[11385, 304, 120, 5, 70, "Input",
  CellTags->"S5.69.1"],
Cell[11508, 311, 192, 5, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[11715, 319, 103, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.12"}],

Cell[CellGroupData[{
Cell[11843, 324, 102, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[11948, 328, 86, 3, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[12049, 334, 217, 5, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.13"}],

Cell[CellGroupData[{
Cell[12291, 343, 95, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[12389, 347, 103, 3, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[12507, 353, 89, 1, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.14"}],

Cell[CellGroupData[{
Cell[12621, 358, 99, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[12723, 362, 86, 3, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[12824, 368, 2820, 71, 70, "Text",
  CellTags->{"S5.69.1", "1.15"}],
Cell[15647, 441, 324, 9, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.16"}],

Cell[CellGroupData[{
Cell[15996, 454, 150, 6, 70, "Input",
  CellTags->"S5.69.1"],
Cell[16149, 462, 475, 13, 70, "Message",
  CellTags->"S5.69.1"],
Cell[16627, 477, 71, 2, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[16713, 482, 2455, 47, 70, "Text",
  CellTags->{"S5.69.1", "1.17"}],
Cell[19171, 531, 163, 7, 70, "Caption",
  CellTags->"S5.69.1"],
Cell[19337, 540, 1232, 30, 70, "Text",
  CellTags->{"S5.69.1", "1.18"}],
Cell[20572, 572, 219, 6, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.19"}],

Cell[CellGroupData[{
Cell[20816, 582, 89, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[20908, 586, 168, 5, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[21091, 594, 290, 7, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.20"}],

Cell[CellGroupData[{
Cell[21406, 605, 109, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[21518, 609, 400, 8, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]],
Cell[21933, 620, 133, 4, 70, "MathCaption",
  CellTags->{"S5.69.1", "1.21"}],

Cell[CellGroupData[{
Cell[22091, 628, 95, 2, 70, "Input",
  CellTags->"S5.69.1"],
Cell[22189, 632, 1488, 28, 70, "Output",
  CellTags->"S5.69.1"]
}, Open  ]]
}
]
*)




(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)

