Quelle  chap0_mj.html   Sprache: HTML

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (FactInt) - Contents</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap0"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap0.html">[MathJax off]</a></p>
<p><a id="X7D2C85EC87DD46E5" name="X7D2C85EC87DD46E5"></a></p>
<div class="pcenter">

<h1>FactInt</h1>


<h2>Advanced Methods for Factoring Integers</h2>

<p>
    1.6.3</p>

<p>
    15 November 2019
  </p>

</div>
<p><b>
    Stefan Kohl



  </b>
<br />Email: <span class="URL"><a href="mailto:stefan@gap-system.org">stefan@gap-system.org</a></span>
<br />Homepage: <span class="URL"><a href="https://stefan-kohl.github.io/">https://stefan-kohl.github.io/</a></span>
</p>

<p><a id="X7AA6C5737B711C89" name="X7AA6C5737B711C89"></a></p>
<h3>Abstract</h3>
<p>This package for <strong class="pkg">GAP</strong> 4 provides a general-purpose integer factorization routine, which makes use of a combination of factoring methods. In particular it contains implementations of the following algorithms:</p>


<ul>
<li><p>Pollard's <span class="SimpleMath">\(p-1\)</span></p>

</li>
<li><p>Williams' <span class="SimpleMath">\(p+1\)</span></p>

</li>
<li><p>Elliptic Curves Method (ECM)</p>

</li>
<li><p>Continued Fraction Algorithm (CFRAC)</p>

</li>
<li><p>Multiple Polynomial Quadratic Sieve (MPQS)</p>

</li>
</ul>
<p>It also contains code by Frank Lübeck for making use of Richard P. Brent's tables of factors of integers of the form <span class="SimpleMath">\(b^k \pm 1\)</span>. <strong class="pkg">FactInt</strong> is completely written in the <strong class="pkg">GAP</strong> language and contains / requires no external binaries. It needs <strong class="pkg">GAPDoc</strong> 1.6 <a href="chapBib_mj.html#biBGAPDoc">[LN17]</a> or higher. <strong class="pkg">FactInt</strong> must be installed in the <code class="file">pkg</code> subdirectory of the <strong class="pkg">GAP</strong> distribution.</p>

<p><a id="X81488B807F2A1CF1" name="X81488B807F2A1CF1"></a></p>
<h3>Copyright</h3>
<p>© 1999 - 2017 by Stefan Kohl.</p>

<p><strong class="pkg">FactInt</strong> is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.</p>

<p><strong class="pkg">FactInt</strong> is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.</p>

<p>For a copy of the GNU General Public License, see the file <code class="file">GPL</code> in the <code class="file">etc</code> directory of the <strong class="pkg">GAP</strong> distribution or see <span class="URL"><a href="http://www.gnu.org/licenses/gpl.html">http://www.gnu.org/licenses/gpl.html</a></span>.</p>

<p><a id="X82A988D47DFAFCFA" name="X82A988D47DFAFCFA"></a></p>
<h3>Acknowledgements</h3>
<p>I would like to thank Bettina Eick and Steve Linton for their support and many interesting discussions.</p>

<p><a id="X8537FEB07AF2BEC8" name="X8537FEB07AF2BEC8"></a></p>

<div class="contents">
<h3>Contents<a id="contents" name="contents"></a></h3>

<div class="ContChap"><a href="chap1_mj.html#X874E1D45845007FE">1 <span class="Heading">Preface</span></a>
</div>
<div class="ContChap"><a href="chap2_mj.html#X7B1A84BB788FC526">2 <span class="Heading">The General Factorization Routine</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X83BF2CD28017ABC5">2.1 <span class="Heading">The method for <code class="code">Factors</code></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X833B087D7A83BC7A">2.1-1 Factors</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X866CD23D78460060">2.1-2 FactInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X80EB87DD80462F80">2.2 <span class="Heading">Getting information about the factoring process</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X8093BB787C2E764B">2.2-1 InfoFactInt</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap3_mj.html#X7E7EE1A1785A8009">3 <span class="Heading">The Routines for Specific Factorization Methods</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7A0392177E697956">3.1 <span class="Heading">Trial division</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7C4D255A789F54B4">3.1-1 FactorsTD</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X8081FF657DA9C674">3.2 <span class="Heading">Pollard's <span class="SimpleMath">\(p-1\)</span></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7AF95E2E87F58200">3.2-1 FactorsPminus1</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X860B4BE37DABDE10">3.3 <span class="Heading">Williams' <span class="SimpleMath">\(p+1\)</span></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8079A0367DE4FC35">3.3-1 FactorsPplus1</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7837106783A5194B">3.4 <span class="Heading">The Elliptic Curves Method (ECM)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X87B162F878AD031C">3.4-1 FactorsECM</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X78466BB97BEE5495">3.5 <span class="Heading">The Continued Fraction Algorithm (CFRAC)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7A5C8BC5861CFC8C">3.5-1 FactorsCFRAC</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7A5C621C7FCFAA8A">3.6 <span class="Heading">The Multiple Polynomial Quadratic Sieve (MPQS)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X86F8DFB681442E05">3.6-1 FactorsMPQS</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap4_mj.html#X85B6B6E4796B99EE">4 <span class="Heading">How much Time does a Factorization take?</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X825FC33479FE2B1D">4.1 <span class="Heading">Timings for the general factorization routine</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X8131C8BD7F637545">4.2 <span class="Heading">Timings for the ECM</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X7E2D09BD7AD0D77F">4.3 <span class="Heading">Timings for the MPQS</span></a>
</span>
</div>
</div>
<div class="ContChap"><a href="chapBib_mj.html"><span class="Heading">References</span></a></div>
<div class="ContChap"><a href="chapInd_mj.html"><span class="Heading">Index</span></a></div>
<br />
</div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>