Re: Primes and strong pseudoprimes of the form x^y+y^x
- Phil Carmody wrote:
> I don't have any number I wish to prove at the momentBouk de Water has a wonderfully juicy target.
Contact him offlist IFF you can get Cycloprov to run.
[I have already done a hefty N-1 factorization for him.]
> and don't know the expected running time eitherDepends on how much factorization of N-1 and/or N+1 one has.
According to Preda it ought to very speedy when
factorization is about 25%.
Consider this marvel:
4^7057-3 4249 PM 1998 Cyclotomy (notes)
<<As announced in my post of November 1997/14 to this list, cyclotomy
may be used for performing proofs for numbers which cannot be proved
by some Lucas - Lehmer method, despite of the fact that a considerable
amount of factors of n+/-1 are known. In such cases Jacobi sums
provide the missing factors, and the proof is considerably faster than
a standard cyclotomy proof, while slightely slower than a Lucas -
Lehmer proof, of course. Thus the gap between general proving and
special purpose algorithm becomes more fluid. I chose the example of
Underwood, because it ideally reflects this situation: the size is
considerable, and the missing factored part of 6% is just enough to
make any Lucas - Lehmer proof impossible>>
In this case N-1 and N+1 were both used, to give 28.8% factorization.
Then CycloProv took less than 3 days!!!
It is a shame that no-one seems to be using it these days:
it is *far* faster than Titanix or VFYPR in such