Fib(25561) from K-P combined test
- 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.
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
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
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)
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
goes through, with T replaced by G-1.
- On Sat, 07 Jul 2001 19:04:24 -0000
> 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,
> 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 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
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.