<h3>3 <span class="Heading">The Routines for Specific Factorization Methods</span></h3>
<p>Descriptions of the factoring methods implemented in this package can be found in <a href="chapBib_mj.html#biBBressoud89">[Bre89]</a> and <a href="chapBib_mj.html#biBCohen93">[Coh93]</a>. Cohen's book contains also descriptions of the other methods mentioned in the preface.
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsTD</code>( <var class="Arg">n</var>[, <var class="Arg">Divisors</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of two lists: The first list contains the prime factors found, and the second list contains remaining unfactored parts of <var class="Arg">n</var>, if there are any.</p>
<p>This function tries to factor <var class="Arg">n</var> by trial division. The optional argument <var class="Arg">Divisors</var> is the list of trial divisors. If not given, it defaults to the list of primes <span class="SimpleMath">\(p < 1000\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsPminus1</code>( <var class="Arg">n</var>[[, <var class="Arg">a</var>], <var class="Arg">Limit1</var>[, <var class="Arg">Limit2</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of two lists: The first list contains the prime factors found, and the second list contains remaining unfactored parts of <var class="Arg">n</var>, if there are any.</p>
<p>This function tries to factor <var class="Arg">n</var> using Pollard's \(p-1\). It uses a as base for exponentiation, Limit1 as first stage limit and Limit2 as second stage limit. If the function is called with three arguments, these arguments are interpreted as n, Limit1 and Limit2. Defaults are chosen for all arguments which are omitted.
<p>Pollard's \(p-1\) is based on the fact that exponentiation (mod \(n\)) can be done efficiently enough to compute \(a^{k!}\) mod \(n\) for sufficiently large \(k\) in a reasonable amount of time. Assume that \(p\) is a prime factor of \(n\) which does not divide \(a\), and that \(k!\) is a multiple of \(p-1\). Then Lagrange's Theorem states that <span class="SimpleMath">\(a^{k!} \equiv 1\)</span> (mod <span class="SimpleMath">\(p\)</span>). If <span class="SimpleMath">\(k!\)</span> is not a multiple of <span class="SimpleMath">\(q-1\)</span> for another prime factor <span class="SimpleMath">\(q\)</span> of <span class="SimpleMath">\(n\)</span>, it is likely that the factor <span class="SimpleMath">\(p\)</span> can be determined by computing <span class="SimpleMath">\(\gcd(a^{k!}-1,n)\)</span>. A prime factor <span class="SimpleMath">\(p\)</span> is usually found if the largest prime factor of <span class="SimpleMath">\(p-1\)</span> is not larger than <var class="Arg">Limit2</var>, and the second-largest one is not larger than <var class="Arg">Limit1</var>. (Compare with <code class="func">FactorsPplus1</code> (<a href="chap3_mj.html#X8079A0367DE4FC35"><span class="RefLink">3.3-1</span></a>) and <code class="func">FactorsECM</code> (<a href="chap3_mj.html#X87B162F878AD031C"><span class="RefLink">3.4-1</span></a>).)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsPplus1</code>( <var class="Arg">n</var>[[, <var class="Arg">Residues</var>], <var class="Arg">Limit1</var>[, <var class="Arg">Limit2</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of two lists: The first list contains the prime factors found, and the second list contains remaining unfactored parts of <var class="Arg">n</var>, if there are any.</p>
<p>This function tries to factor <var class="Arg">n</var> using Williams' \(p+1\). It tries Residues different residues, and uses Limit1 as first stage limit and Limit2 as second stage limit. If the function is called with three arguments, these arguments are interpreted as n, Limit1 and Limit2. Defaults are chosen for all arguments which are omitted.
<p>Williams' \(p+1\) is very similar to Pollard's <span class="SimpleMath">\(p-1\)</span> (see <code class="func">FactorsPminus1</code> (<a href="chap3_mj.html#X7AF95E2E87F58200"><span class="RefLink">3.2-1</span></a>)). The difference is that the underlying group here can either have order <span class="SimpleMath">\(p+1\)</span> or <span class="SimpleMath">\(p-1\)</span>, and that the group operation takes more time. A prime factor <span class="SimpleMath">\(p\)</span> is usually found if the largest prime factor of the group order is at most <var class="Arg">Limit2</var> and the second-largest one is not larger than <var class="Arg">Limit1</var>. (Compare also with <code class="func">FactorsECM</code> (<a href="chap3_mj.html#X87B162F878AD031C"><span class="RefLink">3.4-1</span></a>).)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsECM</code>( <var class="Arg">n</var>[, <var class="Arg">Curves</var>[, <var class="Arg">Limit1</var>[, <var class="Arg">Limit2</var>[, <var class="Arg">Delta</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ECM</code>( <var class="Arg">n</var>[, <var class="Arg">Curves</var>[, <var class="Arg">Limit1</var>[, <var class="Arg">Limit2</var>[, <var class="Arg">Delta</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of two lists: The first list contains the prime factors found, and the second list contains remaining unfactored parts of <var class="Arg">n</var>, if there are any.</p>
<p>This function tries to factor <var class="Arg">n</var> using the Elliptic Curves Method (ECM). The argument <var class="Arg">Curves</var> is the number of curves to be tried. The argument <var class="Arg">Limit1</var> is the initial first stage limit, and <var class="Arg">Limit2</var> is the initial second stage limit. The argument <var class="Arg">Delta</var> is the increment per curve for the first stage limit. The second stage limit is adjusted appropriately. Defaults are chosen for all arguments which are omitted.</p>
<p><code class="code">FactorsECM</code> recognizes the option <var class="Arg">ECMDeterministic</var>. If set, the choice of the curves is deterministic. This means that in repeated runs of <codeclass="code">FactorsECM</code> the same curves are used, and hence for the same <span class="SimpleMath">\(n\)</span> the same factors are found after the same number of trials.</p>
<p>The Elliptic Curves Method is based on the fact that exponentiation in the elliptic curve groups <span class="SimpleMath">\(E(a,b)/n\)</span> can be performed fast enough to compute for example <span class="SimpleMath">\(g^{k!}\)</span> for <span class="SimpleMath">\(k\)</span> large enough (e.g. 100000 or so) in a reasonable amount of time and without using much memory, and on Lagrange's Theorem. Assume that \(p\) is a prime divisor of \(n\). Then Lagrange's Theorem states that if <span class="SimpleMath">\(k!\)</span> is a multiple of <span class="SimpleMath">\(|E(a,b)/p|\)</span>, then for any elliptic curve point <span class="SimpleMath">\(g\)</span>, the power <span class="SimpleMath">\(g^{k!}\)</span> is the identity element of <span class="SimpleMath">\(E(a,b)/p\)</span>. In this situation -- under reasonable circumstances -- the factor <span class="SimpleMath">\(p\)</span> can be determined by taking an appropriate gcd.</p>
<p>In practice, the algorithm chooses in some sense "better" products <span class="SimpleMath">\(P_k\)</span> of small primes rather than <span class="SimpleMath">\(k!\)</span> as exponents. After reaching the first stage limit with <span class="SimpleMath">\(P_{Limit1}\)</span>, it considers further products <span class="SimpleMath">\(P_{Limit1}q\)</span> for primes <span class="SimpleMath">\(q\)</span> up to the second stage limit <var class="Arg">Limit2</var>, which is usually set equal to something like 100 times the first stage limit. The prime <span class="SimpleMath">\(q\)</span> corresponds to the largest prime factor of the order of the group <span class="SimpleMath">\(E(a,b)/p\)</span>.</p>
<p>A prime divisor <span class="SimpleMath">\(p\)</span> is usually found if the largest prime factor of the order of one of the examined elliptic curve groups <span class="SimpleMath">\(E(a,b)/p\)</span> is at most <var class="Arg">Limit2</var> and the second-largest one is at most <var class="Arg">Limit1</var>. Thus trying a larger number of curves increases the chance of factoring <var class="Arg">n</var> as well as choosing a larger value for <var class="Arg">Limit1</var> and/or <var class="Arg">Limit2</var>. It turns out to be not optimal either to try a large number of curves with very small <var class="Arg">Limit1</var> and <var class="Arg">Limit2</var> or to try only a few curves with very large limits. (Compare with <code class="func">FactorsPminus1</code> (<a href="chap3_mj.html#X7AF95E2E87F58200"><span class="RefLink">3.2-1</span></a>).)</p>
<p>The elements of the group <span class="SimpleMath">\(E(a,b)/n\)</span> are the points <span class="SimpleMath">\((x,y)\)</span> given by the solutions of <span class="SimpleMath">\(y^2 = x^3 + ax + by\)</span> in the residue class ring (mod <span class="SimpleMath">\(n\)</span>), and an additional point <span class="SimpleMath">\(\infty\)</span> at infinity, which serves as identity element. To turn this set into a group, define the product (although elliptic curve groups are usually written additively, I prefer using the multiplicative notation here to retain the analogy to <code class="func">FactorsPminus1</code> (<a href="chap3_mj.html#X7AF95E2E87F58200"><spanclass="RefLink">3.2-1</span></a>) and <code class="func">FactorsPplus1</code> (<a href="chap3_mj.html#X8079A0367DE4FC35"><span class="RefLink">3.3-1</span></a>)) of two points <span class="SimpleMath">\(p_1\)</span> and <span class="SimpleMath">\(p_2\)</span> as follows: If <span class="SimpleMath">\(p_1 \neq p_2\)</span>, let <span class="SimpleMath">\(l\)</span> be the line through <span class="SimpleMath">\(p_1\)</span> and <span class="SimpleMath">\(p_2\)</span>, otherwise let <span class="SimpleMath">\(l\)</span> be the tangent to the curve <span class="SimpleMath">\(C\)</span> given by the above equation in the point <span class="SimpleMath">\(p_1 = p_2\)</span>. The line <span class="SimpleMath">\(l\)</span> intersects <span class="SimpleMath">\(C\)</span> in a third point, say <span class="SimpleMath">\(p_3\)</span>. If <span class="SimpleMath">\(l\)</span> does not intersect the curve in a third affine point, then set <span class="SimpleMath">\(p_3 := \infty\)</span>. Define <span class="SimpleMath">\(p_1 \cdot p_2\)</span> by the image of <span class="SimpleMath">\(p_3\)</span> under the reflection across the <span class="SimpleMath">\(x\)</span>-axis. Define the product of any curve point <span class="SimpleMath">\(p\)</span> and <span class="SimpleMath">\(\infty\)</span> by <span class="SimpleMath">\(p\)</span> itself. This -- more or less obviously, checking associativity requires some calculation -- turns the set of points on the given curve into an abelian group <span class="SimpleMath">\(E(a,b)/n\)</span>.</p>
<p>However, the calculations are done in projective coordinates to have an explicit representation of the identity element and to avoid calculating inverses (mod <span class="SimpleMath">\(n\)</span>) for the group operation. Otherwise this would require using an <span class="SimpleMath">\(O((log \ n)^3)\)</span>-algorithm, while multiplication (mod <span class="SimpleMath">\(n\)</span>) is only <span class="SimpleMath">\(O((log \ n)^2)\)</span>. The corresponding equation is given by <span class="SimpleMath">\(bY^2Z = X^3 + aX^2Z + XZ^2\)</span>. This form allows even more efficient computations than the Weierstrass model <span class="SimpleMath">\(Y^2Z = X^3 + aXZ^2 + bZ^3\)</span>, which is the projective equivalent of the affine representation <span class="SimpleMath">\(y^2 = x^3 + ax + by\)</span> mentioned above. The algorithm only keeps track of two of the three coordinates, namely <span class="SimpleMath">\(X\)</span> and <span class="SimpleMath">\(Z\)</span>. The curves are chosen in a way that ensures the order of the corresponding group to be divisible by 12. This increases the chance that it is smooth enough to find a factor of <spanclass="SimpleMath">\(n\)</span>. The implementation follows the description of R. P. Brent given in <a href="chapBib_mj.html#biBBrent96">[Bre96]</a>, pp. 5 -- 8. In terms of this paper, for the second stage the "improved standard continuation" is used.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsCFRAC</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CFRAC</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of the prime factors of <var class="Arg">n</var>.</p>
<p>This function tries to factor <var class="Arg">n</var> using the Continued Fraction Algorithm (CFRAC), also known as Brillhart-Morrison Algorithm. In case of failure an error is signalled.</p>
<p>Caution: The run time of this function depends only on the size of <var class="Arg">n</var>, and not on the size of the factors. Thus if a small factor is not found during the preprocessing which is done before invoking the sieving process, the run time is as long as if <var class="Arg">n</var> would have two prime factors of roughly equal size.</p>
<p>The Continued Fraction Algorithm tries to find integers <span class="SimpleMath">\(x\)</span> and <span class="SimpleMath">\(y\)</span> such that <span class="SimpleMath">\(x^2 \equiv y^2\)</span> (mod <span class="SimpleMath">\(n\)</span>), but not <span class="SimpleMath">\(\pm x \equiv \pm y\)</span> (mod <span class="SimpleMath">\(n\)</span>). In this situation, taking <span class="SimpleMath">\(\gcd(x - y,n)\)</span> yields a nontrivial divisor of <span class="SimpleMath">\(n\)</span>. For determining such a pair <span class="SimpleMath">\((x,y)\)</span>, the algorithm uses the continued fraction expansion of the square root of <span class="SimpleMath">\(n\)</span>. If <span class="SimpleMath">\(x_i/y_i\)</span> is a continued fraction approximation of the square root of <span class="SimpleMath">\(n\)</span>, then <span class="SimpleMath">\(c_i := x_i^2 - ny_i^2\)</span> is bounded by a small constant times the square root of <span class="SimpleMath">\(n\)</span>. The algorithm tries to find as many <span class="SimpleMath">\(c_i\)</span> as possible which factor completely over a chosen factor base (a list of small primes) or with only one factor not in the factor base. The latter ones can be used if and only if a second <span class="SimpleMath">\(c_i\)</span> with the same "large" factor is found. Once enough values <span class="SimpleMath">\(c_i\)</span> have been factored, as a final stage Gaussian Elimination over GF(2) is used to determine which of the congruences <span class="SimpleMath">\(x_i^2 \equiv c_i\)</span> (mod <span class="SimpleMath">\(n\)</span>) have to be multiplied together to obtain a congruence of the desired form <span class="SimpleMath">\(x^2 \equiv y^2\)</span> (mod <span class="SimpleMath">\(n\)</span>). Let <span class="SimpleMath">\(M\)</span> be the corresponding matrix. Then the entries of <span class="SimpleMath">\(M\)</span> are given by <span class="SimpleMath">\(M_{ij} = 1\)</span> if an odd power of the <span class="SimpleMath">\(j\)</span>-th element of the factor base divides the <span class="SimpleMath">\(i\)</span>-th usable factored value, and <span class="SimpleMath">\(M_{ij} = 0\)</span> otherwise. To obtain the desired congruence, it is necessary that the rows of <span class="SimpleMath">\(M\)</span> are linearly dependent. In other words, this means that the number of factored <span class="SimpleMath">\(c_i\)</span> needs to be larger than the rank of <span class="SimpleMath">\(M\)</span>, which is approximately given by the size of the factor base. (Compare with <code class="func">FactorsMPQS</code> (<a href="chap3_mj.html#X86F8DFB681442E05"><span class="RefLink">3.6-1</span></a>).)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorsMPQS</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MPQS</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of the prime factors of <var class="Arg">n</var>.</p>
<p>This function tries to factor <var class="Arg">n</var> using the Single Large Prime Variation of the Multiple Polynomial Quadratic Sieve (MPQS). In case of failure an error is signalled.</p>
<p>Caution: The run time of this function depends only on the size of <var class="Arg">n</var>, and not on the size of the factors. Thus if a small factor is not found during the preprocessing which is done before invoking the sieving process, the run time is as long as if <var class="Arg">n</var> would have two prime factors of roughly equal size.</p>
<p>The intermediate results of a computation can be saved by interrupting it with <code class="code">[Ctrl][C]</code> and calling <code class="code">Pause();</code> from the break loop. This causes all data needed for resuming the computation again to be pushed as a record <var class="Arg">MPQSTmp</var> on the options stack. When called again with the same argument <var class="Arg">n</var>, <code class="code">FactorsMPQS</code> takes the record from the options stack and continues with the previously computed factorization data. For continuing the factorization process in another session, one needs to write this record to a file. This can be done by the function <code class="code">SaveMPQSTmp(<var class="Arg">filename</var>)</code>. The file written by this function can be read by the standard <code class="code">Read</code>-function of <strong class="pkg">GAP</strong>.</p>
<p>The Multiple Polynomial Quadratic Sieve tries to find integers <span class="SimpleMath">\(x\)</span> and <span class="SimpleMath">\(y\)</span> such that <span class="SimpleMath">\(x^2 \equiv y^2\)</span> (mod <span class="SimpleMath">\(n\)</span>), but not <span class="SimpleMath">\(\pm x \equiv \pm y\)</span> (mod <span class="SimpleMath">\(n\)</span>). In this situation, taking <span class="SimpleMath">\(\gcd(x - y,n)\)</span> yields a nontrivial divisor of <span class="SimpleMath">\(n\)</span>. For determining such a pair <span class="SimpleMath">\((x,y)\)</span>, the algorithm chooses polynomials <span class="SimpleMath">\(f_a\)</span> of the form <span class="SimpleMath">\(f_a(r) = ar^2 + 2br + c\)</span> with suitably chosen coefficients <span class="SimpleMath">\(a\)</span>, <span class="SimpleMath">\(b\)</span> and <span class="SimpleMath">\(c\)</span> which satisfy <span class="SimpleMath">\(b^2 \equiv n\)</span> (mod <span class="SimpleMath">\(a\)</span>) and <span class="SimpleMath">\(c = (b^2 - n)/a\)</span>. The identity <span class="SimpleMath">\(a \cdot f_a(r) = (ar + b)^2 - n\)</span> yields a congruence (mod <span class="SimpleMath">\(n\)</span>) with a perfect square on one side and <span class="SimpleMath">\(a \cdot f_a(r)\)</span> on the other. The algorithm uses a sieving technique similar to the Sieve of Eratosthenes over an appropriately chosen sieving interval to search for factorizations of values <spanclass="SimpleMath">\(f_a(r)\)</span> over a chosen factor base. Any two factorizations with the same single "large" factor which does not belong to the factor base can also be used. Taking more polynomials and hence shorter sieving intervals has the advantage of having to factor smaller values <span class="SimpleMath">\(f_a(r)\)</span> over the factor base.</p>
<p>Once enough values <span class="SimpleMath">\(f_a(r)\)</span> have been factored, as a final stage Gaussian Elimination over GF(2) is used to determine which congruences have to be multiplied together to obtain a congruence of the desired form <span class="SimpleMath">\(x^2 \equiv y^2\)</span> (mod <span class="SimpleMath">\(n\)</span>). Let <span class="SimpleMath">\(M\)</span> be the corresponding matrix. Then the entries of <span class="SimpleMath">\(M\)</span> are given by <span class="SimpleMath">\(M_{ij} = 1\)</span> if an odd power of the <span class="SimpleMath">\(j\)</span>-th element of the factor base divides the <span class="SimpleMath">\(i\)</span>-th usable factored value, and <span class="SimpleMath">\(M_{ij} = 0\)</span> otherwise. To obtain the desired congruence, it is necessary that the rows of <span class="SimpleMath">\(M\)</span> are linearly dependent. In other words, this means that the number of usable factorizations of values <span class="SimpleMath">\(f_a(r)\)</span> needs to be larger than the rank of <span class="SimpleMath">\(M\)</span>. The latter is approximately equal to the size of the factor base. (Compare with <code class="func">FactorsCFRAC</code> (<a href="chap3_mj.html#X7A5C8BC5861CFC8C"><span class="RefLink">3.5-1</span></a>).)</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
