Re: [PrimeNumbers] spsps (no, my cat has not jumped on my keyboard)
- On Fri, 02 November 2001, Marcel Martin wrote:
> >Note, however, that this linearity doesn't make the problem a simple one. One still has toIn 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 basesNice.
> >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).
> 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!
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!