|
First off, if you're doing William's p+1 test, then also doing Pollard's p-1 is redundant, since the p+1 test covers both cases, right? Second, why is the recurrence $V_{n+1} = aV_n - V_{n-1}$ used? Using $V_{n+1} = V_n + bV_{n-1}$ instead would give you a provable $\frac{1}{2}$ chance of getting a quadratic nonresidue for each choice of $b$. But no reference I've ever seen uses this variation. |
|||||||||||||
|
|
Note: this is only an attempt at answering the first part of the question, asking if William's p+1 factorization method is redundant with Pollard's p-1, on the basis of how the algorithms are used in practice. Pollard's p-1 (resp. William's p+1) factorization method is efficient to find a factor of $n$ if any of the factors $p$ of $n$ is such that $p-1$ (resp. $p+1$) has no prime factor above some moderate bound $B$. An improvement puts a bound $B_2$ for the highest prime factor of $p-1$ (resp. $p+1$), and another bound $B_1\ll B_2$ for the other factors. The original paper on Williams's p+1 also presents Pollard's p-1. Pollard's p-1 factorization is used in some recent factorization efforts with bounds up to $B_1≈2^{40}$ and $B_2≈2^{50}$; if unsuccessful, that's sometime followed by William's p+1 with slightly lower bounds, before gearing-in ECM. If we construct a 1024-bit integer $n=p⋅q$, with $p+1=p_0⋅c_0$, $q+1=q_0⋅c_1$, $p−1=p_1⋅p_2⋅p_3⋅⋅⋅p_{11}⋅p_{12}⋅c_2$; $p$, $q$, $p_j$, $q_0$ primes; $p$ 415-bit, $q$ 610-bit, $p_0$ and $q_0$ at least 200-bit, other $p_j$ 32-bit; then it is likely amenable to Pollard's p-1 factorization (because $p-1$ has no factor wider than 32-bit), but One such integer (also in this pastebin) is $n =$ 170008213545910965886460576572090982063408798024984543559001546422534644045470603998698706971810963093964580198788881904271608774213396896678573575267676754780622889919559692654436815810637860509009977667589657189496387034548011094365919416175990986348895410113935005204972304311894659720336969894022598750477 Another similarly constructed integer of 448 bits, factorisable with Pollard's p-1 setup with $B_1=4000$, $B_2=10000$, is $n =$ 726286104974888320831459714524497735770165786243885681724247623636059281197969465033496277725004244158329276076523947799294094896411843 |
|||||||
|
