- Some time ago, in another [*] place, I commented on

the Williams-Lenstra proofs for the following primes:

V(57724) 12063 Lucas primitive part

U(35999) 7523 Fibonacci number

U(30757) 6428 Fibonacci number

W(13339) 5106 NSW prime

Bouk de Water and I now add another 4 cyclotomic proofs:

lucasU(287,-1,3079) 7566 Generalized Lucas number

primV( 4, 1,7487) 4282 Generalized Lucas primitive part

primV( 4, 1,7451) 4261 Generalized Lucas primitive part

lucasU( 9,-1,3671) 3671 Generalized Lucas number

The common feature of these 8 was that neither

the Brillhart-Lehmer-Selfridge (BLS) nor

the Konyagin-Pomerance (KP) method sufficed.

Let F1 be the fraction of the digits of N-1

that is completely factorized into proven primes.

Let F2 be the corresponding fraction for N+1.

Finally, let Fmax=max(F1,F2) and Fmin=min(F1,F2).

Then BLS, as implemented by OpenPFGW, requires

3*Fmax + Fmin > 1

for completion of a proof.

My extension of the KP method improves this to

(10/3)*Fmax + Fmin > 1

which I have implemented in Pari.

However there are situations in which the KP

(and, a fortiori, the BLS) method is insufficient,

while the Williams-Lenstra (WL) condition

3*Fmax + 3*Fmin > 1

is satisfied. In such a case it is necessary

to test the Lenstra residue classes. For

this I have written dedicated Pari [*] code.

To give an idea of how much work was done by

the Elliptic Curve Method (ECM) and the

Double-Large-Prime Self-Initiating Quadratic Sieve

(PPSIQS) method, I give a table of Cmin, F1, F2,

KPneed, where Cmin is the number of decimal digits

in the smallest remaining composite factor of N^2-1,

and KPneed is the number of digits still needed for KP.

N Cmin F1 F2 KPneed

lucasU(287,-1,3079) 96 0.1912 0.1490 485

primV( 4, 1,7487) 172 0.2621 0.0818 57

primV( 4, 1,7451) 108 0.2275 0.1254 149

lucasU( 9,-1,3671) 93 0.2413 0.1074 94

More than 10 CPU-days of ECM and PPSIQS were expended to

attain these substantial factorizations, after systematic

exploitation of cyclotomic and Aurifeuillian theory.

All of the remaining composites had by then received

a substantial amount of unsuccessful ECM effort.

Needless to say, all prime factors were

proven by Pfgw/Titanix/Primo, and all BLS

tests were passed, upon running Pfgw with

the resultant helper files.

At the end, only minutes of Pari work was

needed to test the Lenstra residue classes.

Clearly one should cease factorization when

less than an hour of WL work becomes sufficient,

yet KP or BLS theory is very likely to require

several days of further ECM or PPSIQS effort.

David Broadhurst

[*] http://groups.yahoo.com/group/primeform/message/2268 - Andrew Walker wrote:

> lucasU(3,1,n) no primes

To understand those 4 blanks,

> lucasV(4,-1,n)/4 no primes (only n=3)

> lucasU(4,1,n) no primes

> lucasU(5,1,n) no primes

simply factorize s=(p+sqrt(d))/2

with d=p^2-4*q

p q d s

3 1 5 (3+sqrt(5))/2 = r^2

4 -1 20 2+sqrt(5) = r^3

4 1 12 2+sqrt(3) = (1+sqrt(3))^2/2

5 1 21 (5+sqrt(21))/2 = (sqrt(3)+sqrt(7))^2/2

where r=(1+sqrt(5))/2. So, for example,

lucasU(3, 1,n)=lucasU(1,-1,2*n)

lucasV(4,-1,n)=lucasV(1,-1,3*n)

are clearly composite, for sufficiently large n.

> I'd really like to be able to generalise some of these.

Here's a pretty powerful generalization to chew on:

lucasU(lucasV(p,q,k),q^k,n) = lucasU(p,q,k*n)/lucasU(p,q,k)

So far you are only scratching the surface of this,

with q=+/-1.

Those guys Lucas (in 1878) and Carmichael (in 1913)

were pretty impressive!

David