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

Pseudoprimes

Expand Messages
  • jka_br
    How can the expected probability of primality for a pseudoprime of a specific base b in Fermat s Little Theorem be calculated? Julian Arni
    Message 1 of 8 , Jul 29, 2002
    • 0 Attachment
      How can the expected probability of primality for a pseudoprime of a
      specific base b in Fermat's Little Theorem be calculated?
      Julian Arni
    • Phil Carmody
      ... There are two ways that I can think of, neither is particularly satisfying. One is to simply look at example data, and use that as something upon which to
      Message 2 of 8 , Jul 29, 2002
      • 0 Attachment
        --- jka_br <jka_br@...> wrote:
        > How can the expected probability of primality for a pseudoprime of
        > a
        > specific base b in Fermat's Little Theorem be calculated?

        There are two ways that I can think of, neither is particularly
        satisfying.

        One is to simply look at example data, and use that as something upon
        which to base heuristics.

        Secondly, you could (maybe, I've not followed this train of thought
        through) model PSPs of 2, 3, 4, etc factors, and work out the
        probability of all of the individual residues for the factors being
        correct. This path may lead to madness.

        The third method is to follow all the references in the literature.
        Probably papers by Jaeschke (that surely can't be the right spelling)
        and Miller on this matter probably have some interesting leads.
        References are available on Professor Caldwell's prime pages
        http://primepages.org/ , under a section titled something along the
        lines of 'how probable' in the context of probable/pseudo-primes.

        Phil (thus proving 2=3)

        =====
        --
        "One cannot delete the Web browser from KDE without
        losing the ability to manage files on the user's own
        hard disk." - Prof. Stuart E Madnick, MIT.
        So called "expert" witness for Microsoft. 2002/05/02

        __________________________________________________
        Do You Yahoo!?
        Yahoo! Health - Feel better, live better
        http://health.yahoo.com
      • Max B
        Consider the possible values for smallest pseudoprime ( n ) to base n. ? foo(500) = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 66,
        Message 3 of 8 , Dec 17, 2002
        • 0 Attachment
          Consider the possible values for smallest pseudoprime
          ( > n ) to base n.

          ? foo(500)
          = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
          55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
          95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
          125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
          159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
          187, 189, 190, 195, 196, 201, 203, 205, 207,
          [snip]
          339, 341, 343, 345, 351, 355, 357, etc. etc..
          [snip]

          How do I know if I've missed any values?
        • Phil Carmody
          ... Instant tangent, just add Phil: Noticable members of that list are 4, 9, 25, 49, 121, 169, ... and 27, 81 125, 343 ... Given that perfect-power testing can
          Message 4 of 8 , Dec 17, 2002
          • 0 Attachment
            --- Max B <zen_ghost_floating@...> wrote:
            >
            > Consider the possible values for smallest pseudoprime
            > ( > n ) to base n.
            >
            > ? foo(500)
            > = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
            > 55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
            > 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
            > 125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
            > 159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
            > 187, 189, 190, 195, 196, 201, 203, 205, 207,
            > [snip]
            > 339, 341, 343, 345, 351, 355, 357, etc. etc..
            > [snip]
            >
            > How do I know if I've missed any values?

            Instant tangent, just add Phil:

            Noticable members of that list are
            4, 9, 25, 49, 121, 169, ...
            and
            27, 81 125, 343 ...

            Given that perfect-power testing can be done in Bernsteinian linear time,
            there are some who would say that they shouldn't even be passed to a
            probable primality test.

            However, it can't be denied that if you do pass them to such a PRP test
            they do occasionally come out as pseudoprimes as indicated.

            As you were,
            Phil


            =====
            I Pledge Allegiance to the flag
            That appears on my Desktop Startup Screen.
            And to the Monopoly for which it Stands:
            One Operating System over all, inescapable,
            With Freedom and Privacy for none. -- Telecommando on /.

            __________________________________________________
            Do you Yahoo!?
            Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
            http://mailplus.yahoo.com
          • Max B
            ... Phil, that is very interesting, as is Bernstein s home/web/page http://cr.yp.to/djb.html which I had fun tripping out on for a couple of hours today. but
            Message 5 of 8 , Dec 18, 2002
            • 0 Attachment
              >Noticable members of that list are
              > 4, 9, 25, 49, 121, 169, ...
              >and
              > 27, 81 125, 343 ...
              >
              >Given that perfect-power testing can be done in
              >Bernsteinian linear time, there are some who would say
              >that they shouldn't even be passed to a probable
              >primality test.

              Phil, that is very interesting, as is Bernstein's home/web/page
              http://cr.yp.to/djb.html
              which I had fun tripping out on for a couple of hours
              today. but what I am trying to find out is the limit I have
              to compute up to before i know with certainty that all the
              values below another lower limit are all included in the
              aforementioned sequence, without excluding any possible
              values. For example, would I have to compute up
              to 10^6 to get the first 100 terms of the sequence correct
              I wonder? Anyone know the theoretical/analytical
              phantasmagoria behind this?



              ----- Original Message -----
              From: Phil Carmody
              To: primenumbers
              Sent: Tuesday, December 17, 2002 10:37 AM
              Subject: Re: [PrimeNumbers] Pseudoprimes


              --- Max B <zen_ghost_floating@...> wrote:
              >
              > Consider the possible values for smallest pseudoprime
              > ( > n ) to base n.
              >
              > ? foo(500)
              > = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
              > 55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
              > 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
              > 125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
              > 159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
              > 187, 189, 190, 195, 196, 201, 203, 205, 207,
              > [snip]
              > 339, 341, 343, 345, 351, 355, 357, etc. etc..
              > [snip]
              >
              > How do I know if I've missed any values?

              Instant tangent, just add Phil:

              Noticable members of that list are
              4, 9, 25, 49, 121, 169, ...
              and
              27, 81 125, 343 ...

              Given that perfect-power testing can be done in Bernsteinian linear time,
              there are some who would say that they shouldn't even be passed to a
              probable primality test.

              However, it can't be denied that if you do pass them to such a PRP test
              they do occasionally come out as pseudoprimes as indicated.

              As you were,
              Phil


              =====
              I Pledge Allegiance to the flag
              That appears on my Desktop Startup Screen.
              And to the Monopoly for which it Stands:
              One Operating System over all, inescapable,
              With Freedom and Privacy for none. -- Telecommando on /.
            • Nathan Russell
              Hi folks, What should be done to a number to make sure the chance of it being pseudoprime or a Carmichael number is below the human scale of reasonable things
              Message 6 of 8 , Apr 30, 2003
              • 0 Attachment
                Hi folks,

                What should be done to a number to make sure the chance of it being
                pseudoprime or a Carmichael number is below the human scale of reasonable
                things to worry about?

                In particular, are there any forms that are likely to be pseudoprime to
                more than one base?

                Thanks

                Nathan
              • Paul Underwood
                ... reasonable ... pseudoprime to ... Maybe I can answer the first question. If the number is small and you have the time you could use Primo to prove the
                Message 7 of 8 , Apr 30, 2003
                • 0 Attachment
                  --- Nathan wrote:
                  > Hi folks,
                  >
                  > What should be done to a number to make sure the chance of it being
                  > pseudoprime or a Carmichael number is below the human scale of
                  reasonable
                  > things to worry about?
                  >
                  > In particular, are there any forms that are likely to be
                  pseudoprime to
                  > more than one base?
                  >

                  Maybe I can answer the first question.

                  If the number is small and you have the time you could use Primo to
                  prove the number prime thereby eliminate any doubt. If the number is
                  small (say less than 2000 bits) you could use the Miller-Rabin test
                  repeadedly -- decreasing the chance of it being a pseudoprime. PFGW
                  reports a Lucas test as well as a PRP if it can not prove the prime.
                  I would like to see a FFT-based Perrin composite test ;-)

                  Paul

                  > Thanks
                  >
                  > Nathan
                • Paul Leyland
                  ... If you choose your numbers uniformly and at random from all integers of size N bits, then a single Miller-Rabin pseudoprimality test to a randomly chosen
                  Message 8 of 8 , May 1 1:37 AM
                  • 0 Attachment
                    > From: Nathan Russell [mailto:nrussell@...]

                    > What should be done to a number to make sure the chance of it being
                    > pseudoprime or a Carmichael number is below the human scale
                    > of reasonable things to worry about?

                    If you choose your numbers uniformly and at random from all integers of size N bits, then a single Miller-Rabin pseudoprimality test to a randomly chosen base is sufficient. Only a very tiny fraction of integers have the property that a M-R test has a probability close to 1/4 of failing.

                    If you are allowed to chose your numbers in such a way that you guarantee it has close to a 1/4 chance of failing a test, pick a power of four sufficiently large that you find it comfortable. I personally don't worry much about things which occur with probability less than 4^(-20) in my expected lifetime.


                    Paul
                  Your message has been successfully submitted and would be delivered to recipients shortly.