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.

-
@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. –  Antimony Nov 23 '12 at 4:36
@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. –  Antimony Nov 23 '12 at 15:37
@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.) –  D.W. Nov 23 '12 at 23:53
@fgrieu Whenever I try to copy your number, I get a bunch of nonascii junk mixed in. Are you sure you pasted it correctly? –  Antimony Nov 24 '12 at 0:56
@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. –  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

-
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. –  Antimony Nov 24 '12 at 14:49
@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. –  fgrieu Nov 24 '12 at 17:14
It can find anything with $B_2$ less than say, 10,000 in minutes. 20 bits would take around 42 hours. –  Antimony Nov 24 '12 at 17:26