Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Phil Carmody
    ... 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.