## Re: [PrimeNumbers] spsps (no, my cat has not jumped on my keyboard)

Expand Messages
• ... 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
Message 1 of 4 , Nov 2, 2001
• 0 Attachment
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
> >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.

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.

> >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).
>
> 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.

Nice.

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
Your message has been successfully submitted and would be delivered to recipients shortly.