Expand Messages
• ... Paul Underwood s preprint at http://www.mersenneforum.org/showpost.php?p=298027&postcount=44 has a rather neat observation in Section 4, which is all one
Message 1 of 33 , May 29 2:40 PM
"paulunderwooduk" <paulunderwood@> wrote:

> Please see my draft paper

Paul Underwood's preprint at
http://www.mersenneforum.org/showpost.php?p=298027&postcount=44
has a rather neat observation in Section 4, which is all one
really needs to read to understand how Paul can do in
2 selfridges what takes BPSW 1 + 2 selfridges and takes
Grantham 2 + 1 selfridges, using the Frobenius method of
Crandall and Pomerance.

Shorn of any references to matrices, Paul's proposal is to
test an odd non-square target N for probable primality using
a Frobenius test based on the Lucas sequence with
P = A*x + 2*B and Q = A*B*x + A^2 + B^2, where A > 0 and B
are small integers and x is the smallest non-negative
integer such that kronecker(x^2-4,N) = -1. Specifically, Paul
has found that with A = 1 and B = 2 there are no pseudoprimes
with N < 4*10^12.

Crandall and Pomerance show, in Algorithm 3.5.9, how to
accomplish a Lucas test in 2 selfridges and then strengthen
it to a Frobenius test at the expense of a 3rd selfridge.
(Note that CP denote the Lucas parameters (P,Q) by (a,b),
which I avoid doing, since Paul uses the symbols (a,b) for
a different purpose.}

A Frobenius test involves modular exponentiation of

z mod (N, z^2 - P*z + Q)

In Paul's case this turns into modular exponentiation of

(A*lambda + B) mod (N, lambda^2 - x*lambda + 1)

Using left-right binary exponentiation, the cost, at large
N, is dominated by squaring (a*lambda + b) where (a,b) are
large integers, mod N, from the previous step. (The cost of
also multiplying by (A*lambda + B), when the bit is odd, is
asymptotically negligible, in comparison, since A and B are
assumed to be small integers.)

Now comes the neat bit: the cost of computing

(a*lambda + b)^2 = a*(a*x + 2*b)*lambda + (b - a)*(b + a)
mod (N, lambda^2 - x*lambda + 1) ...... [*]

is dominated by only 2 multiplications of large numbers,
a*(a*x + 2*b) and (b - a)*(b + a), mod N, since x is small.
Defining a "selfridge" as log(N)/log(2) times the cost of a
modular multiplication of two large numbers of order N, this
is clearly a 2-selfridge test. Yet it accomplishes not only
a Lucas test but also a Fermat test, Q^(N-1) = 1 mod N,
where Q = A*B*x + A^2 + B^2 is 2*x + 5 in Paul's preferred
case, with A = 1 and B = 2.

Like many good ideas, Paul's modular equation [*], above, is
both simple and effective. I think that it might usefully be
decoupled from the rest of the preprint in a short (and also
matrix-free) note along the lines "Lucas tests with Fermat
tests for free", with due reference to C&P's 2 + 1 selfridge

Caveat lector: the BPSW test with, 1 + 2 selfridges, will
beat Paul's 2 selfridge test, when applied to a large number
of random targets of size N, since the BPSW 2-selfridge
second part is invoked only in a fraction O(1/log(N)) of the
cases that the initial 1-selfridge Fermat test fails to
detect a composite.

Thus there should be no suggestion that folk may benefit by
switching from BPSW to Paul's method, when processing large
batches. Paul acknowledges this in his preprint, by frankly
admitting that his testing was a 1 + 2 selfridge process,
with filtering by the Fermat test in base Q = 2*x + 5. If
this did not detect a composite, he then performed the
2-selfridge Frobenius test that amounts to a Lucas test plus
the Fermat test that he /already/ knows will work. Thus there
is no free lunch, when batch processing.

Moreover, as so often in such discussions, selfridge-counts
for testing a known PRP are irrelevant in comparison with
the much larger effort of finding that PRP, which costs,
generically, exp(-Euler)*log(N)/log(p) selfridges, after
sensibly sieving to a decent depth p.

However, if one has found a probable prime N and wishes to
tell someone else that it is a (P,Q) Frobenius probable
prime, this may be now be achieved in 2 selfridges, with
Paul's preferred choice P = x + 4, Q = 2*x + 5, and
kronecker(Delta,N) = -1, where Delta = P^2 - 4*Q = x^2 - 4.

With thanks to Paul, for his neat observation,

• ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
Message 33 of 33 , Sep 21, 2012
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
:

> I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
> {
> 0m32.374s pfgw64 (3-prp)
> 1m9.876s pfgw64 -t
> 1m53.535s pfgw64 -tp
> 3m0.483s pfgw64 -tc
> 5m12.972s pfgw64 scriptify
> 4m4.811s gmp (-O3/no pgo)
> 4m9.148 pari-gp
> 1m15s theoretical Woltman implementation
> }
>

I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
{
17.505s pfgw (3-prp)
1m1.986s pfgw -tp
1m13.789s gmp (-O3/no pgo)
}

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.