- Fib(25561) from K-P combined test

A few months ago, the proof requirement for Pfgw

was 33.33% factorization of either N-1 or N+1.

Then there were two rather significant developments:

1) Chris Nash implemented the BLS proof method

with 3*F_max + Fmin > 1, where F_max=max(F1,F2)

and F_min=min(F1,F2), with F1 being the proportion

of the digits of N-1 that are factorized, and F2

the proportion of N+1. This brought Pfgw

up to the standard of the BLS part of VFYPR.

2) Andy Steward implemented, in Ubasic, a

Konyagin-Pomerance proof, in the case F1 > 0.3.

I then implemented it in Pari, which was far faster,

thanks to the commands "contfrac" and "polroots".

When Andy and I met recently with Bouk de Water

in Amsterdam, the hot topic was rather obvious:

how to combine both advances?

Today I worked out how it goes; it is enough to have

11*F1 > 10*F1 + 3*F2 > 3

[give or take a few bits: precise conditions appended.]

Colleagues with sharp minds are invited to check the theorem,

below, which is a rather straightforward adaptation of

my improvement of K-P to benefit from extra square tests.

This has an immediate and very pleasant consequence.

Until today the Fibonacci roll of hour had only

5 titanic entries

U(81839) 17103 p54 2001 Fibonacci number

U(14431) 3016 p54 2001 Fibonacci number

U(9677) 2023 c2 2000 Fibonacci number

U(9311) 1946 DK 1995 Fibonacci number

U(5387) 1126 WM 1990 Fibonacci number

To these, Bouk and I now add

U(25561) 5342 p54 2001 Fibonacci number

thanks to the fractions F1=0.2865, F2=0.05704

and the corresponding cubic and square tests.

David Broadhurst

Appendix:

Theorem [KP combined test]

==========================

Let N=F*R+1 with gcd(F,R)=1 and R>F^2.

Let N=G*S-1 with gcd(F,G)=1.

Suppose that the BLS tests establish

that every factor of N is 1 mod F

and +/- 1 mod G.

Let c1 be the unique integer in [1,F-1]

such that c4=(R-c1)/F is an integer.

Now test that

(c1+t*F)^2+4*t-4*c4

is not a square when t=t_G

and t_G is the unique integer in [0,G-1]

with t=c4 mod G.

Now *modify* the KP cubic algorithm

by taking u/v to be the continued

fraction convergent to c1/F with

maximal v < F^(1/3). [sic]

Suppose that we construct the cubic

P(X) = v*X^3 + (u*F-c1*v)*X^2 + (c4*v-d*F+u)*X - d

with d=round(c4*v/F)

and verify that none of its roots is an integer.

Then N is prime, if

F^(1/3)/6 > G+1 > 3*N/F^(10/3)

==============================

Proof:

======

Suppose that N were not prime,

but instead of the form N=(a1*F+1)*(a2*F+1).

Let t = c4-a1*a2.

One of a1*F and a2*F must be divisible by G.

Hence t = c4 mod G, since gcd(F,G)=1.

When t = t_G has been ruled out,

the proof given in

http://groups.yahoo.com/group/primeform/message/2142

goes through, with T replaced by G-1. - On Sat, 07 Jul 2001 19:04:24 -0000

d.broadhurst@... wrote:

> Theorem [KP combined test]

[snip]

> ==========================

>

> Let N=F*R+1 with gcd(F,R)=1 and R>F^2.

> Let N=G*S-1 with gcd(F,G)=1.

>

Broadhurst's combined test is very excellent,

> Proof:

> ======

>

> Suppose that N were not prime,

> but instead of the form N=(a1*F+1)*(a2*F+1).

> Let t = c4-a1*a2.

> One of a1*F and a2*F must be divisible by G.

> Hence t = c4 mod G, since gcd(F,G)=1.

especially from computational view point .

The conditions above restricts the possible values of a1,a2.

This decreases extremely square tests.

If we admit some extra square tests, G may be more smaller.

Satoshi Tomabechi - Satoshi Tomabechi wrote

> Broadhurst's combined test is very excellent,

In fact I have made further improvements

> especially from computational view point.

> The conditions above restricts the possible values of a1,a2.

> This decreases extremely square tests.

> If we admit some extra square tests, G may be more smaller.

by finding a way to combine APRCL tests

with the KP cubic and BLS square tests.

First let's summarize what VFYPR can do:

Suppose that N=F1*R1+1=F2*R2-1, with

2|F1, gcd(F1,R1)=1,

2|F2, gcd(F2,R2)=1,

and the BLS tests proving that

every divisor d of N has

d = 1 mod F1, (1)

d = +/-1 mod F2. (2)

Suppose further that for some S

with gcd(S,N^2-1)=1 the APRCL

tests prove that every divisor has

d = N^i mod S, (3)

for some i<T.

Let F_max=max(F1,F2) and F_min=min(F1,F2).

Then the classic APRCL + BLS-combined

method enables a proof in the case

2*N < F_max^3 * F_min * S [VFYPR]

at the expense of a single square test and a

simple divisor test for each of the 2*T residue

classes mod (F1*F2*S/2) that result from

using the Chinese remainder theorem on (1,2,3).

I have derived a stronger result:

Pomerance^2 = APRCL + KP

========================

Provided that N < F_max^4, a proof is

also possible in the case

6*N < F_max^(10/3) * F_min * S [APR-CL-KP]

at the expense of

no more than 2*T square tests and

no more than 2 cubic tests.

Uses: Suppose that we have only 25%

from N-1, then we need 16.66% from

N+1 and S.

However, there is a pressing case

with 29.62% of the 4,200 digits of N-1.

Here we need only 1.3% from N+1 and S, i.e.

55 digits. Bouk and I have 8 digits from

N+1 and hence can complete with S=O(10^47)

from APRCL, which is feasible at 4,200 digits.

David Broadhurst