(* Content-type: application/vnd.wolfram.mathematica *)

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

(* CreatedBy='Wolfram 15.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       154,          7]
NotebookDataLength[     28136,        722]
NotebookOptionsPosition[     22922,        628]
NotebookOutlinePosition[     24876,        672]
CellTagsIndexPosition[     24833,        669]
WindowTitle->BatchGCD
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{
Cell[BoxData[GridBox[{
   {GridBox[{
      {
       ItemBox[Cell[BoxData[
         RowBox[{
          TemplateBox[{12},
           "Spacer1"], Cell[
          "WOLFRAM INSTITUTE/ PUZZLES SYMBOL", "PacletNameCell",
           TextAlignment->Center,ExpressionUUID->
           "bf65a085-8b8e-4387-8cce-6413fb8ab219"], 
          TemplateBox[{8},
           "Spacer1"]}]],
         TextAlignment->Center,ExpressionUUID->
         "d02adea5-ee99-463c-8b54-05b538b7491e"],
        Background->LightDarkSwitched[
          RGBColor[0.490196, 0.576471, 0.690196]],
        ItemSize->Full], ""}
     },
     GridBoxAlignment->{"Rows" -> {{Center}}},
     GridBoxItemSize->{"Columns" -> {Full, 
         Scaled[0.02]}, "Rows" -> {{2.5}}}], Cell[TextData[{
     Cell[BoxData[
      TagBox[
       ActionMenuBox[
        FrameBox[Cell[TextData[{
          "See Also",
          " ",
          Cell[BoxData[
           GraphicsBox[
            {GrayLevel[0.66667], Thickness[0.13], 
             LineBox[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]},
            AspectRatio->1,
            ImageSize->20,
            PlotRange->{{-3, 4}, {-1, 1}}]],ExpressionUUID->
           "baa77b23-de20-4dd3-9b3f-8f4a533db945"]
         }],ExpressionUUID->"be784257-6a56-48d6-a13a-bba0e43c9dcd"],
         StripOnInput->False],{
        StyleBox["\"GCD\"", "SeeAlsoRelated", StripOnInput -> False] :> 
         Documentation`HelpLookup["paclet:ref/GCD"], 
         StyleBox[
          "\"FactorInteger\"", "SeeAlsoRelated", StripOnInput -> False] :> 
         Documentation`HelpLookup["paclet:ref/FactorInteger"], Delimiter, 
         StyleBox[
          "\"Functions\"", "SeeAlsoSection", FontSize -> 14, FontSlant -> 
           "Italic", StripOnInput -> False] :> 
         NotebookFind[EvaluationNotebook[], "SeeAlsoSection", All, CellStyle],
          StyleBox[
          StyleBox[
           "\"WienerAttack\"", "SeeAlsoRelated", StripOnInput -> False], 
           "SeeAlsoRelated", StripOnInput -> False] :> 
         Documentation`HelpLookup[
          "paclet:WolframInstitute/Puzzles/ref/WienerAttack"], 
         StyleBox[
          StyleBox[
           "\"WienerBound\"", "SeeAlsoRelated", StripOnInput -> False], 
           "SeeAlsoRelated", StripOnInput -> False] :> 
         Documentation`HelpLookup[
          "paclet:WolframInstitute/Puzzles/ref/WienerBound"]},
        Appearance->None,
        MenuAppearance->Automatic,
        MenuStyle->"SeeAlso"],
       MouseAppearanceTag["LinkHand"]]],
      LineSpacing->{1.4, 0},ExpressionUUID->
      "1e94055a-db43-4c4b-a1b7-8327c14c7b55"],
     "\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\
\[ThickSpace]",
     Cell[BoxData[
      TagBox[
       ActionMenuBox[
        FrameBox[Cell[TextData[{
          "Related Guides",
          " ",
          Cell[BoxData[
           GraphicsBox[
            {GrayLevel[0.66667], Thickness[0.13], 
             LineBox[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]},
            AspectRatio->1,
            ImageSize->20,
            PlotRange->{{-3, 4}, {-1, 1}}]],ExpressionUUID->
           "513232f8-22f1-40c7-94b7-4532f6443bb8"]
         }],ExpressionUUID->"bf6cf3e7-05f4-4784-b73f-f4ac3e06526c"],
         StripOnInput->False],{
        "\"Search\"" :> 
         Documentation`HelpLookup[
          "paclet:WolframInstitute/Puzzles/guide/Search"]},
        Appearance->None,
        MenuAppearance->Automatic,
        MenuStyle->"MoreAbout"],
       MouseAppearanceTag["LinkHand"]]],
      LineSpacing->{1.4, 0},ExpressionUUID->
      "3598cbe7-f68d-4dfb-a86e-93645a556552"],
     "\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\
\[ThickSpace]",
     Cell[BoxData[
      TagBox[
       ActionMenuBox[
        FrameBox[Cell[TextData[{
          "URL",
          " ",
          Cell[BoxData[
           GraphicsBox[
            {GrayLevel[0.66667], Thickness[0.13], 
             LineBox[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]},
            AspectRatio->1,
            ImageSize->20,
            PlotRange->{{-3, 4}, {-1, 1}}]],ExpressionUUID->
           "c89e8a32-9638-4c9e-91d6-c0d94d69c9b8"]
         }],ExpressionUUID->"ea5afaa9-57b1-4f30-9286-08c3cb1ea067"],
         StripOnInput->False],{
        "\"WolframInstitute/Puzzles/ref/BatchGCD\"" :> None, 
         "\"Copy Wolfram Documentation Center URL\"" :> 
         CopyToClipboard["WolframInstitute/Puzzles/ref/BatchGCD"], Delimiter, 
         "\"Copy web URL\"" :> 
         Module[{DocumentationSearch`Private`nb$}, 
           DocumentationSearch`Private`nb$ = 
            NotebookPut[
             Notebook[{
               Cell[BoxData[
                 MakeBoxes[
                  Hyperlink[
                   "http://reference.wolfram.com/language/WolframInstitute/\
Puzzles/ref/BatchGCD.html"], StandardForm]], "Input", TextClipboardType -> 
                 "PlainText"]}, Visible -> False]]; 
           SelectionMove[DocumentationSearch`Private`nb$, All, Notebook]; 
           FrontEndTokenExecute[DocumentationSearch`Private`nb$, "Copy"]; 
           NotebookClose[DocumentationSearch`Private`nb$]; Null], 
         "\"Go to web URL\"" :> 
         FrontEndExecute[{
           NotebookLocate[{
             URL[If[TrueQ[False], 
                 "http://reference.wolfram.com/system-modeler/", 
                 "http://reference.wolfram.com/language/"] <> 
               "WolframInstitute/Puzzles/ref/BatchGCD" <> ".html"], None}]}]},
        
        Appearance->None,
        MenuAppearance->Automatic,
        MenuStyle->"URLMenu"],
       MouseAppearanceTag["LinkHand"]]],
      LineSpacing->{1.4, 0},ExpressionUUID->
      "80e74848-107b-437d-8bc6-c4e494812a11"]
    }], "AnchorBar",
     CacheGraphics->False,ExpressionUUID->
     "e1a7ba5e-6738-489c-8ad1-ff950c548827"]}
  }]], "AnchorBarGrid",
 CellID->1,ExpressionUUID->"5d36962a-13bf-423d-8c70-6097b1aa9fd1"],

Cell["WolframInstitute`Puzzles`", "ContextNameCell",ExpressionUUID->"7a375019-de90-40d6-ba51-09a1a71993a0"],

Cell[CellGroupData[{

Cell[BoxData[GridBox[{
   {Cell[TextData[{
     Cell[
     "BatchGCD", "ObjectName",ExpressionUUID->
      "c14fe640-fa32-4f35-a8aa-e6c898dc5804"],
     Cell[BoxData[
      TemplateBox[{8},
       "Spacer1"]],ExpressionUUID->"b0cbb27d-b2e6-4e90-8b29-c85032cf5972"],
     Cell[BoxData[
     ""], "ObjectNameTranslation",ExpressionUUID->
      "52e91671-7bfa-4bab-8852-6473c42793e3"]
    }],ExpressionUUID->"48b9b8d5-d99a-4750-9621-b310b3607747"], 
    "\[SpanFromLeft]"}
  }]], "ObjectNameGrid",ExpressionUUID->"eee3bf83-f0a9-4598-b534-\
6513e2573f13"],

Cell[BoxData[GridBox[{
   {"", Cell[TextData[{
     Cell[BoxData[
      RowBox[{
       TemplateBox[{
         Cell[
          TextData["BatchGCD"]], 
         "paclet:WolframInstitute/Puzzles/ref/BatchGCD", 
         "WolframInstitute/Puzzles Package Symbol"},
        "PackageLink",
        BaseStyle->"InlineFormula"], "[", 
       RowBox[{"{", 
        RowBox[{
         StyleBox["n\:2081", "TI"], ",", " ", 
         StyleBox["n\:2082", "TI"], ",", " ", "\[Ellipsis]"}], "}"}], "]"}]], 
      "InlineFormula",
      FontFamily->"Source Sans Pro",
      FontSize->0.9 Inherited,ExpressionUUID->
      "45146bd8-8060-4b76-a8ef-e562b8ee7fce"],
     "\[LineSeparator]",
     "gives, for each modulus ",
     StyleBox["n", "TI"],
     "\:1d62, the greatest common divisor of ",
     StyleBox["n", "TI"],
     "\:1d62 with the product of all the others, computed by Bernstein's \
product and remainder trees rather than by comparing every pair."
    }],ExpressionUUID->"d84e8129-a48f-4b3e-9595-74998435bf80"]}
  }]], "Usage",ExpressionUUID->"a5c9acc6-ae42-41ca-83db-9c07f0a9ee41"]
}, Open  ]],

Cell[CellGroupData[{

Cell[TextData[Cell[BoxData[Cell[TextData[{
  Cell[BoxData[
   DynamicBox[ToBoxes[
     If[CurrentValue[
        EvaluationCell[], "CellGroupOpen"] =!= Closed, 
      Style[
       Graphics[{
         Thickness[0.18], 
         RGBColor[0.8509803921568627, 0.396078431372549, 0], 
         Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
        PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
       0.68 Inherited], 
      Rotate[
       Style[
        Graphics[{
          Thickness[0.18], 
          RGBColor[0.8509803921568627, 0.396078431372549, 0], 
          Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
         PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
        0.68 Inherited], Rational[1, 2] Pi, {-1.65, -1}]]],
    ImageSizeCache->{
     13.600000000000001`, {-0.1685058593749993, 13.768505859375}}]],
   ExpressionUUID->"dfb4ebef-4c58-4cc6-ab2f-b20797cbab8b"],
  Cell[BoxData[
   TemplateBox[{1},
    "Spacer1"]],ExpressionUUID->"2a0f5e4d-69e3-4a0c-8985-e86426eb92c4"],
  "Details and Options"
 }], "NotesFrameText",ExpressionUUID->
  "f7182729-ff46-49a2-a336-71f81c9fda8f"]],ExpressionUUID->"0fd1a300-d961-\
4769-a4a9-f281ea3296f9"]], "NotesSection",
 ShowGroupOpener->"Thumbnail",
 WholeCellGroupOpener->True,
 CellGroupingRules->{"SectionGrouping", 50},
 CacheGraphics->False,
 CellID->679229032,ExpressionUUID->"35356e25-380f-48fe-a6a3-1f1b9e1cb185"],

Cell[TextData[{
 "An entry of 1 means that modulus shares no factor with any other. An entry \
strictly between 1 and ",
 StyleBox["n", "TI"],
 "\:1d62 is a shared prime, and ",
 Cell[BoxData[
  RowBox[{
   TemplateBox[{
     Cell[
      TextData["Quotient"]], "paclet:ref/Quotient"},
    "RefLink",
    BaseStyle->{"InlineFormula"}], "[", 
   RowBox[{
    StyleBox["n\:1d62", "TI"], ",", " ", 
    StyleBox["entry", "TI"]}], "]"}]], "InlineFormula",
  FontFamily->"Source Sans Pro",
  FontSize->0.9 Inherited,ExpressionUUID->
  "d59ba819-cc53-4c4e-8cf4-07fe1ba8702a"],
 " is the other factor. An entry equal to ",
 StyleBox["n", "TI"],
 "\:1d62 means the modulus is a duplicate, or shares both of its factors."
}], "Notes",ExpressionUUID->"302cc0e4-c09b-4e86-8851-f40fec7a3970"],

Cell[TextData[{
 "Two RSA moduli that share one prime are both completely broken, since a \
single ",
 Cell[BoxData[
  TemplateBox[{
    Cell[
     TextData["GCD"]], "paclet:ref/GCD"},
   "RefLink",
   BaseStyle->"InlineFormula"]], "InlineFormula",
  FontFamily->"Source Sans Pro",
  FontSize->0.9 Inherited,ExpressionUUID->
  "7ef10432-9129-4d87-a738-eb610c5652f7"],
 " splits them. The difficulty in practice is that nobody knows ",
 StyleBox["which", "TI"],
 " pair collides, and the all-pairs scan is quadratic. This is the \
quasi-linear alternative."
}], "Notes",ExpressionUUID->"1a5c3267-28f5-49a1-816d-87a1875e33bd"],

Cell[TextData[{
 "The remainder tree carries the full product reduced modulo ",
 StyleBox["n", "TI"],
 "\:1d62\.b2 rather than the product itself, so intermediate values stay the \
size of the inputs."
}], "Notes",ExpressionUUID->"24a77430-0e0b-4378-8135-9d257c0f4525"],

Cell["\<\
Supported for a list of at least two integers greater than 1; anything else \
is left unevaluated.\
\>", "Notes",ExpressionUUID->"ce40315c-a97d-4abe-b67b-f9e14af331e6"],

Cell[TextData[{
 "This is the attack of ",
 StyleBox["Mining Your Ps and Qs", "TI"],
 " (USENIX Security 2012), which recovered the private keys of over 64000 \
live TLS and SSH hosts whose key generation had drawn from a low-entropy \
source."
}], "Notes",ExpressionUUID->"104676e6-8c4e-4b7b-8de3-1af8f9f364c2"]
}, Closed]],

Cell["", "PageDelimiter",ExpressionUUID->"d62e5563-e79b-415a-ab59-9b57bcf48b11"],

Cell[CellGroupData[{

Cell[TextData[{
 Cell[BoxData[
  DynamicBox[ToBoxes[
    If[
     MatchQ[
      CurrentValue[
       EvaluationNotebook[], {
       TaggingRules, "Openers", "PrimaryExamplesSection"}, Open], 
      Alternatives[True, Open]], 
     Style[
      Graphics[{
        Thickness[0.18], 
        RGBColor[0.8509803921568627, 0.396078431372549, 0], 
        Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
       PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
      0.68 Inherited], 
     Rotate[
      Style[
       Graphics[{
         Thickness[0.18], 
         RGBColor[0.8509803921568627, 0.396078431372549, 0], 
         Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
        PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
       0.68 Inherited], Rational[1, 2] Pi, {-1.65, -1}]]],
   ImageSizeCache->{
    13.600000000000001`, {4.251494140625001, 9.348505859375}}]],
  ExpressionUUID->"a04c306f-4d47-4bd1-b1e3-96e16d3d0070"],
 Cell[BoxData[
  TemplateBox[{1},
   "Spacer1"]],ExpressionUUID->"4f489497-e831-4fa8-b0f0-42f1f225b134"],
 "Examples",
 "\[NonBreakingSpace]\[NonBreakingSpace]",
 Cell["(2)", "ExampleCount",ExpressionUUID->
  "88f483bc-96f8-434e-8efe-63e7daec1908"]
}], "PrimaryExamplesSection",
 WholeCellGroupOpener->True,
 CacheGraphics->False,
 CellID->1926757019,ExpressionUUID->"45cb0f4e-26ec-4ce6-9357-2e1589797cac"],

Cell[BoxData[
 RowBox[{"Needs", "[", "\"\<WolframInstitute`Puzzles`\>\"", "]"}]], "Input", \
"ExampleInitialization",
 CellLabel->"In[1]:=",
 CellID->1969679695,ExpressionUUID->"ba00b76b-3e21-4542-a085-db5ffe30b2db"],

Cell[CellGroupData[{

Cell[TextData[{
 Cell[BoxData[
  DynamicBox[ToBoxes[
    If[CurrentValue[
       EvaluationCell[], "CellGroupOpen"] =!= Closed, 
     Style[
      Graphics[{
        Thickness[0.18], 
        RGBColor[0.8509803921568627, 0.396078431372549, 0], 
        Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
       PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
      0.68 Inherited], 
     Rotate[
      Style[
       Graphics[{
         Thickness[0.18], 
         RGBColor[0.8509803921568627, 0.396078431372549, 0], 
         Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
        PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
       0.68 Inherited], Rational[1, 2] Pi, {-1.65, -1}]]]]],ExpressionUUID->
  "411968f8-3d3f-485d-959a-42908b7364eb"],
 Cell[BoxData[
  TemplateBox[{1},
   "Spacer1"]],ExpressionUUID->"15113ca0-1b60-4eec-afcb-2b1e2b24e712"],
 "Basic Examples",
 "\[NonBreakingSpace]\[NonBreakingSpace]",
 Cell["(1)", "ExampleCount",ExpressionUUID->
  "c89955f8-31c2-43c1-a64a-198b7a7aab79"]
}], "ExampleSection", "ExampleSection",
 WholeCellGroupOpener->True,
 CacheGraphics->False,
 CellID->1099305220,ExpressionUUID->"39601004-cca4-444b-97d7-90f0e0ba47c8"],

Cell["Three moduli, of which the first two share a prime:", "ExampleText",ExpressionUUID->"1ad9243b-a51c-4fe4-9ee5-99a2b83d1d85"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"BatchGCD", "[", 
  RowBox[{"{", 
   RowBox[{"15", ",", " ", "21", ",", " ", "22"}], "}"}], "]"}]], "Input",
 CellProlog:>Needs["WolframInstitute`Puzzles`"],
 CellLabel->"In[1]:=",ExpressionUUID->"f2ceee28-ccd7-4510-8a88-011285a6d5d4"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"3", ",", "3", ",", "1"}], "}"}]], "Output",
 CellLabel->"Out[1]= ",ExpressionUUID->"1a56c246-9d89-4f77-a543-b924ab650205"]
}, Open  ]],

Cell["Recovering both factors of a modulus from the shared prime:", \
"ExampleText",ExpressionUUID->"4e576c9d-aec0-4830-a970-3d4a142bb2d7"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"With", "[", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{
     RowBox[{"n1", " ", "=", " ", 
      RowBox[{"3229", " ", "*", " ", "5563"}]}], ",", " ", 
     RowBox[{"n2", " ", "=", " ", 
      RowBox[{"3229", " ", "*", " ", "7919"}]}]}], "}"}], ",", "\n", "\t", 
   RowBox[{"With", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"g", " ", "=", " ", 
       RowBox[{"First", "[", 
        RowBox[{"BatchGCD", "[", 
         RowBox[{"{", 
          RowBox[{"n1", ",", " ", "n2"}], "}"}], "]"}], "]"}]}], "}"}], ",", 
     " ", 
     RowBox[{"{", 
      RowBox[{"g", ",", " ", 
       RowBox[{"Quotient", "[", 
        RowBox[{"n1", ",", " ", "g"}], "]"}], ",", " ", 
       RowBox[{"Quotient", "[", 
        RowBox[{"n2", ",", " ", "g"}], "]"}]}], "}"}]}], "]"}]}], "\n", 
  "]"}]], "Input",
 CellProlog:>Needs["WolframInstitute`Puzzles`"],
 CellLabel->"In[2]:=",ExpressionUUID->"d301ba58-602d-4c6b-a30e-b833ad0d37fd"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"3229", ",", "5563", ",", "7919"}], "}"}]], "Output",
 CellLabel->"Out[2]= ",ExpressionUUID->"5f4969b1-f184-486d-8b16-db53f8b66225"]
}, Open  ]],

Cell["Moduli with nothing in common all report 1:", "ExampleText",ExpressionUUID->"7e35f557-8973-4c43-954c-8fbf912d2d09"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"BatchGCD", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"3229", " ", "*", " ", "5563"}], ",", " ", 
    RowBox[{"7919", " ", "*", " ", "6907"}]}], "}"}], "]"}]], "Input",
 CellProlog:>Needs["WolframInstitute`Puzzles`"],
 CellLabel->"In[3]:=",ExpressionUUID->"e4cfc792-69f0-4998-ab56-033ff57f2bbd"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"1", ",", "1"}], "}"}]], "Output",
 CellLabel->"Out[3]= ",ExpressionUUID->"97ba1a94-8fe5-46c2-9ebf-6310bd9138b7"]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell[TextData[{
 Cell[BoxData[
  DynamicBox[ToBoxes[
    If[CurrentValue[
       EvaluationCell[], "CellGroupOpen"] =!= Closed, 
     Style[
      Graphics[{
        Thickness[0.18], 
        RGBColor[0.8509803921568627, 0.396078431372549, 0], 
        Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
       PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
      0.68 Inherited], 
     Rotate[
      Style[
       Graphics[{
         Thickness[0.18], 
         RGBColor[0.8509803921568627, 0.396078431372549, 0], 
         Line[{{-1.8, 0.5}, {0, 0}, {1.8, 0.5}}]}, AspectRatio -> 1, 
        PlotRange -> {{-3, 4}, {-1, 1}}, ImageSize -> 20], Magnification -> 
       0.68 Inherited], Rational[1, 2] Pi, {-1.65, -1}]]]]],ExpressionUUID->
  "65e44cef-47c6-44b0-bfac-9ae53b9c5959"],
 Cell[BoxData[
  TemplateBox[{1},
   "Spacer1"]],ExpressionUUID->"51fda0e9-e42f-42b2-adcd-b11f740f9ac3"],
 "Possible Issues",
 "\[NonBreakingSpace]\[NonBreakingSpace]",
 Cell["(1)", "ExampleCount",ExpressionUUID->
  "0ec956b0-1bad-4760-a308-ac3b8bcf0819"]
}], "ExampleSection", "ExampleSection",
 WholeCellGroupOpener->True,
 CacheGraphics->False,
 CellID->1305812373,ExpressionUUID->"f3842d32-da4a-4fdf-a9ea-cb36003235f0"],

Cell[TextData[{
 "The result is a divisor, not a factorization: a modulus whose entry equals \
the modulus itself is either a duplicate of another entry or shares both \
primes, and in neither case has anything been learned. Test for ",
 Cell[BoxData[
  RowBox[{"1", " ", "<", " ", "entry", " ", "<", " ", "n"}]], "InlineFormula",
  
  FontFamily->"Source Sans Pro",
  FontSize->0.9 Inherited,ExpressionUUID->
  "12ad1019-29ac-4f2a-8675-ea02a9c22362"],
 " before treating an entry as a recovered prime."
}], "ExampleText",ExpressionUUID->"975f71b5-ab5f-45e7-823c-b64cd102336f"],

Cell["\<\
The whole product of the inputs is formed, so memory grows with the total bit \
length of the list rather than with the largest modulus. That is the cost \
that buys the quasi-linear running time.\
\>", "ExampleText",ExpressionUUID->"cdf0bdea-7f04-4285-8977-d2d41ffdb633"],

Cell[TextData[{
 "A result of all 1s means no two moduli in ",
 StyleBox["this", "TI"],
 " list share a factor. It says nothing about whether any of them is \
factorable by other means."
}], "ExampleText",ExpressionUUID->"29eeb99a-b282-460a-b95b-a793974dbf24"]
}, Closed]]
}, Open  ]],

Cell[BoxData[GridBox[{
   {
    DynamicBox[FEPrivate`ImportImage[
      FrontEnd`FileName[{"Documentation", "FooterIcons"}, 
       "RelatedFunction.png"]]], GridBox[{
      {
       StyleBox[
        RowBox[{"See", " ", "Also"}], "SeeAlsoSection"]},
      {Cell[TextData[{
        Cell[BoxData[
         TemplateBox[{
           Cell[
            TextData["WienerAttack"]], 
           "paclet:WolframInstitute/Puzzles/ref/WienerAttack", 
           "WolframInstitute/Puzzles Package Symbol"},
          "PackageLink",
          BaseStyle->"InlineFormula"]], "InlineFormula",
         FontFamily->"Source Sans Pro",ExpressionUUID->
         "05f7c159-3d8d-4aff-a837-1c31a9cc6c87"],
        "\[NonBreakingSpace]",
        StyleBox[
        "\[MediumSpace]\[FilledVerySmallSquare]\[MediumSpace]", 
         "InlineSeparator"],
        " ",
        Cell[BoxData[
         TemplateBox[{
           Cell[
            TextData["WienerBound"]], 
           "paclet:WolframInstitute/Puzzles/ref/WienerBound", 
           "WolframInstitute/Puzzles Package Symbol"},
          "PackageLink",
          BaseStyle->"InlineFormula"]], "InlineFormula",
         FontFamily->"Source Sans Pro",ExpressionUUID->
         "071b3456-9e4f-4460-a4a3-17f5173460a0"],
        "\[NonBreakingSpace]",
        StyleBox[
        "\[MediumSpace]\[FilledVerySmallSquare]\[MediumSpace]", 
         "InlineSeparator"],
        " ",
        Cell[BoxData[
         TemplateBox[{
           Cell[
            TextData["GCD"]], "paclet:ref/GCD"},
          "RefLink",
          BaseStyle->"InlineFormula"]], "InlineFormula",
         FontFamily->"Source Sans Pro",ExpressionUUID->
         "b5b5aa6f-f007-45e3-9e03-c3d475b9acdf"],
        "\[NonBreakingSpace]",
        StyleBox[
        "\[MediumSpace]\[FilledVerySmallSquare]\[MediumSpace]", 
         "InlineSeparator"],
        " ",
        Cell[BoxData[
         TemplateBox[{
           Cell[
            TextData["FactorInteger"]], "paclet:ref/FactorInteger"},
          "RefLink",
          BaseStyle->"InlineFormula"]], "InlineFormula",
         FontFamily->"Source Sans Pro",ExpressionUUID->
         "fba31b5a-88fe-4ea9-8892-2cc748b73bdf"]
       }], "SeeAlso",ExpressionUUID->"854b07cf-c5ad-43b0-a738-83b46ff5fce6"]}
     }]}
  }]], "SeeAlsoSection",ExpressionUUID->"8826ed37-7f95-40e4-82ef-\
3622df4bd185"],

Cell[BoxData[GridBox[{
   {
    DynamicBox[FEPrivate`ImportImage[
      FrontEnd`FileName[{"Documentation", "FooterIcons"}, 
       "RelatedGuide.png"]]], GridBox[{
      {
       StyleBox[
        RowBox[{"Related", " ", "Guides"}], "MoreAboutSection"]},
      {
       RowBox[{"\[FilledVerySmallSquare]", Cell[BoxData[
         TemplateBox[{
           Cell[
            TextData["Search"]], 
           "paclet:WolframInstitute/Puzzles/guide/Search"},
          "RefLinkPlain",
          BaseStyle->{"MoreAbout"}]], "MoreAbout",ExpressionUUID->
         "c2a2c014-05ff-404c-a9f1-09318bd673f0"]}]}
     }]}
  }]], "MoreAboutSection",ExpressionUUID->"9c7e3062-0ab5-46c1-9788-\
912819fae85f"],

Cell[" ", "FooterCell",ExpressionUUID->"c8d73dc2-5867-46e0-8ef6-685d15e5b112"]
},
Saveable->False,
ScreenStyleEnvironment->"Working",
WindowSize->{900, 830},
WindowMargins->{{0, Automatic}, {Automatic, 0}},
WindowTitle->"BatchGCD",
TaggingRules->{
 "ModificationHighlight" -> False, "ColorType" -> "", "LinkTrails" -> "", 
  "ExampleCounter" -> 1, 
  "Openers" -> {
   "PrimaryExamplesSection" -> Open, "ExampleSection" -> {"0" -> Open}, 
    "AllOptsTable" -> Closed}, "NewStyles" -> True, 
  "CitationPopupData" -> $Failed, "ShowCitation" -> False, "HasOptions" -> 
  True, "RootCaptions" -> "", "HeaderCoreAreaLink" -> {}, 
  "Metadata" -> {
   "built" -> "{2026, 8, 27, 0, 11, 10.260700}", 
    "history" -> {"XX", "", "", ""}, "context" -> "WolframInstitute`Puzzles`",
     "keywords" -> {}, "specialkeywords" -> {}, 
    "tutorialcollectionlinks" -> {}, "index" -> True, "label" -> 
    "Wolfram Institute/ Puzzles Symbol", "language" -> "en", "paclet" -> 
    "WolframInstitute/Puzzles", "status" -> "None", "summary" -> 
    "PackageLink[BatchGCD,paclet : WolframInstitute/Puzzles/ref/BatchGCD, \
WolframInstitute/Puzzles Package Symbol][{n\:2081, n\:2082, ...}] gives, for \
each modulus n\:1d62, the greatest common divisor of n\:1d62 with the product \
of all the others, computed by Bernstein's product and remainder trees rather \
than by comparing every pair.", "synonyms" -> {}, "tabletags" -> {}, "title" -> 
    "BatchGCD", "titlemodifier" -> "", "metadescription" -> "", "windowtitle" -> 
    "BatchGCD", "type" -> "Symbol", "uri" -> 
    "WolframInstitute/Puzzles/ref/BatchGCD", "WorkflowDockedCell" -> ""}, 
  "SearchTextTranslated" -> ""},
CellContext->CellGroup,
FrontEndVersion->"15.0 for Mac OS X ARM (64-bit) (May 19, 2026)",
StyleDefinitions->FrontEnd`FileName[{"Wolfram"}, "Reference.nb"],
ExpressionUUID->"27d33db2-751e-4d78-88e7-fe7419f33ecd"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[576, 21, 5851, 144, 70, "AnchorBarGrid",ExpressionUUID->"5d36962a-13bf-423d-8c70-6097b1aa9fd1",
 CellID->1],
Cell[6430, 167, 107, 0, 70, "ContextNameCell",ExpressionUUID->"7a375019-de90-40d6-ba51-09a1a71993a0"],
Cell[CellGroupData[{
Cell[6562, 171, 551, 14, 70, "ObjectNameGrid",ExpressionUUID->"eee3bf83-f0a9-4598-b534-6513e2573f13"],
Cell[7116, 187, 1079, 27, 70, "Usage",ExpressionUUID->"a5c9acc6-ae42-41ca-83db-9c07f0a9ee41"]
}, Open  ]],
Cell[CellGroupData[{
Cell[8232, 219, 1443, 34, 70, "NotesSection",ExpressionUUID->"35356e25-380f-48fe-a6a3-1f1b9e1cb185",
 CellGroupingRules->{"SectionGrouping", 50},
 CellID->679229032],
Cell[9678, 255, 779, 21, 70, "Notes",ExpressionUUID->"302cc0e4-c09b-4e86-8851-f40fec7a3970"],
Cell[10460, 278, 624, 16, 70, "Notes",ExpressionUUID->"1a5c3267-28f5-49a1-816d-87a1875e33bd"],
Cell[11087, 296, 269, 5, 70, "Notes",ExpressionUUID->"24a77430-0e0b-4378-8135-9d257c0f4525"],
Cell[11359, 303, 178, 3, 70, "Notes",ExpressionUUID->"ce40315c-a97d-4abe-b67b-f9e14af331e6"],
Cell[11540, 308, 312, 6, 70, "Notes",ExpressionUUID->"104676e6-8c4e-4b7b-8de3-1af8f9f364c2"]
}, Closed]],
Cell[11867, 317, 80, 0, 70, "PageDelimiter",ExpressionUUID->"d62e5563-e79b-415a-ab59-9b57bcf48b11"],
Cell[CellGroupData[{
Cell[11972, 321, 1401, 37, 70, "PrimaryExamplesSection",ExpressionUUID->"45cb0f4e-26ec-4ce6-9357-2e1589797cac",
 CellID->1926757019],
Cell[13376, 360, 216, 4, 70, "Input",ExpressionUUID->"ba00b76b-3e21-4542-a085-db5ffe30b2db",
 CellID->1969679695],
Cell[CellGroupData[{
Cell[13617, 368, 1236, 31, 70, "ExampleSection",ExpressionUUID->"39601004-cca4-444b-97d7-90f0e0ba47c8",
 CellID->1099305220],
Cell[14856, 401, 129, 0, 70, "ExampleText",ExpressionUUID->"1ad9243b-a51c-4fe4-9ee5-99a2b83d1d85"],
Cell[CellGroupData[{
Cell[15010, 405, 258, 5, 70, "Input",ExpressionUUID->"f2ceee28-ccd7-4510-8a88-011285a6d5d4"],
Cell[15271, 412, 162, 3, 70, "Output",ExpressionUUID->"1a56c246-9d89-4f77-a543-b924ab650205"]
}, Open  ]],
Cell[15448, 418, 139, 1, 70, "ExampleText",ExpressionUUID->"4e576c9d-aec0-4830-a970-3d4a142bb2d7"],
Cell[CellGroupData[{
Cell[15612, 423, 942, 26, 70, "Input",ExpressionUUID->"d301ba58-602d-4c6b-a30e-b833ad0d37fd"],
Cell[16557, 451, 171, 3, 70, "Output",ExpressionUUID->"5f4969b1-f184-486d-8b16-db53f8b66225"]
}, Open  ]],
Cell[16743, 457, 121, 0, 70, "ExampleText",ExpressionUUID->"7e35f557-8973-4c43-954c-8fbf912d2d09"],
Cell[CellGroupData[{
Cell[16889, 461, 322, 7, 70, "Input",ExpressionUUID->"e4cfc792-69f0-4998-ab56-033ff57f2bbd"],
Cell[17214, 470, 152, 3, 70, "Output",ExpressionUUID->"97ba1a94-8fe5-46c2-9ebf-6310bd9138b7"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[17415, 479, 1237, 31, 70, "ExampleSection",ExpressionUUID->"f3842d32-da4a-4fdf-a9ea-cb36003235f0",
 CellID->1305812373],
Cell[18655, 512, 577, 11, 70, "ExampleText",ExpressionUUID->"975f71b5-ab5f-45e7-823c-b64cd102336f"],
Cell[19235, 525, 282, 4, 70, "ExampleText",ExpressionUUID->"cdf0bdea-7f04-4285-8977-d2d41ffdb633"],
Cell[19520, 531, 260, 5, 70, "ExampleText",ExpressionUUID->"29eeb99a-b282-460a-b95b-a793974dbf24"]
}, Closed]]
}, Open  ]],
Cell[19807, 540, 2335, 63, 70, "SeeAlsoSection",ExpressionUUID->"8826ed37-7f95-40e4-82ef-3622df4bd185"],
Cell[22145, 605, 692, 19, 70, "MoreAboutSection",ExpressionUUID->"9c7e3062-0ab5-46c1-9788-912819fae85f"],
Cell[22840, 626, 78, 0, 70, "FooterCell",ExpressionUUID->"c8d73dc2-5867-46e0-8ef6-685d15e5b112"]
}
]
*)

(* End of internal cache information *)

