- On Thu, 01 November 2001, Marcel Martin wrote:
> Phil,

Note, however, that this linearity doesn't make the problem a simple one. One still has to brute-force through the set of primes.

>

> >For X=fermat, the answer certainly looks simplest due to the 'linearity' of FermatPRP >tests.

> >Thus the full set of answers can be built up from the that answers to each prime.

>

> Clearly, yes.

> >For others, though, the question looks utterly intractible.

I thought about this a month ago, when I was going to submit an idea on whether it was better or not to use prime bases in SPRP tests. However, my conclusion was that the status quo was actually better, so there was no announcement (i.e. use prime bases). (Hey, everyone - listen! Keep doing what you're currently doing! Haha.)

> >Is it?

>

> Maybe not. At least not completely. What I mean is that, even with

> strong pseudoprimality (SPP) tests that are not 'stable' for the

> bases, i.e., the fact that N is 2-spp and 3-spp doesn't imply it is

> 6-spp, we can deduce the values for a big lot of composite bases

> knowing only the values for prime bases.

> Paul Landon raised this problem a few months ago. That's why

> I already thought of it.

> An odd number N = Q*2^k + 1, with Q odd, is said to be B-spp if

Yes, they were bascally my conclusions last month. The case of an even number of equally-levelled bases making the two -1's a +1 however, _doesn't_ preclude further multiples of this composite base as long as you add another odd number of bases with that level to map it back onto -1 again, or a base with a higher level which will dominate with its -1.

> we have

>

> B^Q = 1 mod N

>

> or if it exists j such that 0 <= j < k so that

>

> B^(Q*2^j) = -1 mod N

>

> First thing to do: For all tested prime bases B, we store j (we can

> call it the 'level' or the 'height', no importance). For the case

> B^Q = 1 mod N, we set j = -1 (arbitrarily, we only need it is smaller

> than other levels).

> At this point we have couples (B,j) and the composite bases are not

> yet tested. We can eliminate a lot of them by applying some simple

> rules.

>

> (1) If a base B has level -1, all its powers have level -1.

> (2) If a base B has level 0, all its powers have level -1 or 0

> (3) If two bases have not the same level, their product has a level

> equal to the greatest level.

> (4) If an odd number of bases have the same level J, the level of

> their product is J. (This includes the case where the bases are

> equal).

> (5) Other rules I do not think of at the moment :-)

>

> Proofs (for clarity, I suppressed "mod N"):

> -------------------------------------------

> (1) B^Q = 1 --> (B^u)^Q = 1

>

> (2) B^Q = -1 --> (B^u)^Q = -1 if u is odd

> --> (B^u)^Q = 1 if u is even

>

> (3) B^(Q*2^i) = -1 and C^(Q*2^j) = -1 with i <> j

> Suppose i < j, by squaring B^(Q*2^i) j-i times [*] we get

> B^(Q*2^j) = 1, so (B*C)^(Q*2^j) = -1

> [*] not with level = -1, but when a base has level -1, it can be

> combined with any other base having any level.

>

> (4) Assuming you survive up to now, this is obvious.

The real problem of course, is that we can't even determine easily which bases a number is even a FermatPRP to. (All the primes involved in the above mix must be SPRPs, thus PRPs).

Phil

Mathematics should not have to involve martyrdom;

Support Eric Weisstein, see http://mathworld.wolfram.com

Find the best deals on the web at AltaVista Shopping!

http://www.shopping.altavista.com - On Fri, 02 November 2001, Marcel Martin wrote:
> >Note, however, that this linearity doesn't make the problem a simple one. One still has to

In the particular case I had in mind, GMP uses a random (odd?) number with the same number of bits as the number you're testing for its SPRP tests. i.e. a number probably impractically large to try to represent in terms of its factors.

> >brute-force through the set of primes.

>

> But that's already an enormous gain.

> Moreover, it also depends on which range you want work. Do you want

> work up to a small limit (like the one given by GRH) or on the

> complete range [2..N-2]? In that case, it may occur that 1/B mod N is

> also prime and, when a number is B-pp, it is also (1/B)-pp.

> >The real problem of course, is that we can't even determine easily which bases

Nice.

> >a number is even a FermatPRP to. (All the primes involved in the above mix must

> >be SPRPs, thus PRPs).

>

> Yes, the fact that a number is SPP for all prime bases implies it is

> PP for all bases (of course, the bases B such that GCD(B,N)=1).

>

>

> A thing I didn't see yesterday.

> If N is B-spp then it is B-spp for all its powers (even when the

> exponent is even).

>

> Proof:

> ------

> Case B^Q = +/-1. Obvious.

>

> Case B^(Q*2^j) = -1 with 0 < j < k.

> Just write B^(Q*2^j) = (B^2)^(Q*2^(j-1)) = -1. So if N is B-spp with

> level j, it is also (B^2)-spp with level j-1.

I hadn't spotted that, but you make it seem so obvious in retrospect!

Cheers,

Phil

Mathematics should not have to involve martyrdom;

Support Eric Weisstein, see http://mathworld.wolfram.com

Find the best deals on the web at AltaVista Shopping!

http://www.shopping.altavista.com