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.

  • $\begingroup$ @fgrieu But William's p+1 will also find factors such that p-1 is smooth, since you'll get quadratic residues half the time. $\endgroup$ – Antimony Nov 23 '12 at 4:36
  • $\begingroup$ @fgrieu I'd be really interested to try that challenge. Is there anyway for you to send me the numbers? I don't think SO's comment system is really suitable for that. $\endgroup$ – Antimony Nov 23 '12 at 15:37
  • 2
    $\begingroup$ @fgrieu, I'm far from expert on this, but based on this, with prob. $1/2$ we have $(D/p)=1$, and then if $p-1$ is smooth, it looks like William's p+1 method should find $p$. At least, I assume this is the background behind Antimony's reasoning. (I don't know the answer to Antimony's question, either, but I'm just trying to elaborate what Antimony might be referring to.) $\endgroup$ – D.W. Nov 23 '12 at 23:53
  • $\begingroup$ @fgrieu Whenever I try to copy your number, I get a bunch of nonascii junk mixed in. Are you sure you pasted it correctly? $\endgroup$ – Antimony Nov 24 '12 at 0:56
  • $\begingroup$ @D.W.: I now start to understand what you, and I guess Antinomy, are thinking of. In addition of the argument, that is supported by the "degenerates into a slow version of Pollard's p − 1 algorithm" fragment in the Wikipedia entry for William's p+1. I do not know to what degree that applies in practice, and will be thinking about it. Meanwhile I'll remove my earlier comments, and update my tentative start of an answer accordingly. $\endgroup$ – fgrieu Nov 24 '12 at 16:59

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 I see no reason why I can't tell if it would be amenable to William's p+1 factorization (because both $p+1$ and $q+1$ have a high prime factor).

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

  • $\begingroup$ At the current rate, it will take my script 10-20 years to solve that, assuming that you used 32 bit factors. But that is unoptimized python running on a five year old laptop. I guess I need to find a more optimized implementation. Or you could use smaller factors. $\endgroup$ – Antimony Nov 24 '12 at 14:49
  • $\begingroup$ @Antinomy: I just start to understand your question. Also, I can make another smaller number; what about $N$ of 448 bits, a bound $B_2$ of 20 bits, a bound $B_1$ of 15 bits? Feel free to change that until I post it. $\endgroup$ – fgrieu Nov 24 '12 at 17:14
  • $\begingroup$ It can find anything with $B_2$ less than say, 10,000 in minutes. 20 bits would take around 42 hours. $\endgroup$ – Antimony Nov 24 '12 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.