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

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

Expand Messages
  • d.broadhurst@open.ac.uk
    Phil is clearly deep into pseudoprimes. I have nothing of use to add. Marcel has already contributed more than I can say. Yet this thread has prompted a
    Message 1 of 4 , Nov 1, 2001
    • 0 Attachment
      Phil is clearly deep into pseudoprimes.

      I have nothing of use to add. Marcel has already
      contributed more than I can say.

      Yet this thread has prompted a lateral thought.

      I don't know the theory, but the praxis is this:
      composite factors of Phi(n,b) are (weak) base-b PrPs.

      So I had this funny thought.

      Suppose we know some of the factors of Phi(n,b)
      and want to find more. We already know how to
      do a modular sieve, to take into account that
      each factor is 1 mod n. But there is a stronger constraint
      on any new factor: its product with previous
      factors is a base-b pseudoprime.

      Example: Phi(102,137) has the easily found factors
      409 5101 24360253

      To proceeed, we need a factor, F, with

      1) F = 1 mod 102
      2) F*409 is 137-PrP
      3) F*5101 is 137-PrP
      4) F*24360253 is 137-PrP
      5) F*409*5101 is 137-PrP
      6) F*409*24360253 is 137-PrP
      7) F*5101*24360253 is 137-PrP
      8) F*409*5101*24360253 is 137-PrP

      The factor in question is

      F = 168934634606425055593

      Question: Is there any way of using the facts that

      168934634606425055593*409 is 137-PRP!
      168934634606425055593*5101 is 137-PRP!
      168934634606425055593*24360253 is 137-PRP!
      168934634606425055593*409*5101 is 137-PRP!
      168934634606425055593*409*24360253 is 137-PRP!
      168934634606425055593*5101*24360253 is 137-PRP!
      168934634606425055593*409*5101*24360253 is 137-PRP!

      to speed up finding this factor?

      David
    • Phil Carmody
      ... Note, however, that this linearity doesn t make the problem a simple one. One still has to brute-force through the set of primes. ... I thought about this
      Message 2 of 4 , Nov 2, 2001
      • 0 Attachment
        On Thu, 01 November 2001, Marcel Martin wrote:
        > Phil,
        >
        > >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.

        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 others, though, the question looks utterly intractible.
        > >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.

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

        > An odd number N = Q*2^k + 1, with Q odd, is said to be B-spp if
        > 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.

        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.

        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
      • 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 3 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.