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

testing if 32 bit integer is prime number

Expand Messages
  • ylar.jyrviste@mail.ee
    Hi, I need to show if a 32 bit integer is prime or not. Is it enough to prove that the number is greater than 2,odd number and divisible by 3? Or is there
    Message 1 of 5 , Oct 2, 2001
      Hi,

      I need to show if a 32 bit integer is prime or not. Is it enough to
      prove that the number is greater than 2,odd number and divisible by 3?

      Or is there another simple algorithm to prove it(I hvae to implement
      it in assembler)

      Thanks

      a computer science student
    • Phil Carmody
      ... Tere Ylar, ... Think of 25... So you could add another check for divisibility by 5. Then think of 49. Hmmm, looks like you need to go a bit further... ...
      Message 2 of 5 , Oct 2, 2001
        On Tue, 02 October 2001, ylar.jyrviste@... wrote:
        > Hi,

        Tere Ylar,

        > I need to show if a 32 bit integer is prime or not. Is it enough to
        > prove that the number is greater than 2,odd number and divisible by 3?

        Think of 25...
        So you could add another check for divisibility by 5.
        Then think of 49.
        Hmmm, looks like you need to go a bit further...

        > Or is there another simple algorithm to prove it(I hvae to implement
        > it in assembler)

        You have made the first few steps, the extension is to test all primes up to and including the square root of the number you want to test (equivalently - until p squared is larger than the number you're testing). For 32bit numbers this isn't too lengthy a process, but don't try it for larger numbers. The process is called 'wheel factoring', 'trial division', or simply 'brute force'.

        Another question is how to generate all the primes easily.
        There are two equally simple answers:
        1) write a quick sieve to generate all primes up to 16-bits (which can be done really easily if you already know all primes up to 8-bits). See the Prime Pages for information on such a sieve:
        http://www.utm.edu/research/primes/glossary/SieveOfEratosthenes.html

        2) Don't bother - simply be prepared to be a bit wasteful with your tests.
        Trial divide by 2 and 3 first, then after that trial divide by
        6n-1 and 6n+1 for every n>=1 (so that's 5, 7, then 11, 13, then 17, 19, then 23, 25 (wasteful - already done 5) ...)
        The above optimisation can be extended to
        first do trial division by 2, 3, 5, 7, 11 and 13
        then do trial division by 30n-13, 30n-11, 30n-7, 30n-1, 30n+1, 30n+7, 30n+11, 30n+13 for each n>=1.

        Oh, and when I say 'every' or 'each' above, you are permitted to stop as soon as you find a factor!

        There's more info about factoring, and some sample code at
        http://www.frenchfries.net/paul/factoring/
        There's more info about primality proving in general on the Prime Pages http://primepages.org/
        but we're always here to answer questions too.


        N�gemist,
        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
      • Paul Leyland
        ... You mean *not* divisible by 3, otherwise it certainly isn t prime. Even that s not good enough. Consider 25: odd, 2 and not divisible by 3. It s not
        Message 3 of 5 , Oct 2, 2001
          > I need to show if a 32 bit integer is prime or not. Is it enough to
          > prove that the number is greater than 2,odd number and divisible by 3?

          You mean *not* divisible by 3, otherwise it certainly isn't prime.

          Even that's not good enough. Consider 25: odd, >2 and not divisible by
          3. It's not prime either.

          >
          > Or is there another simple algorithm to prove it(I hvae to implement
          > it in assembler)


          There are many simple algorithms. Without knowing your constraints,
          it's hard to give definite advice. The answers to the following
          questions should guide you:

          Can the input number be negative?
          Although the input number may be 32 bits, are all 2^32 values possible?
          Are you optimizing for speed, for data space, for program size, for
          simplicity of programming or what?


          If you have a lot of data storage, for instance, you could have a very
          large table of primes and index into it to see whether a given value is
          prime or not.


          Paul
        • James Thoms
          May I suggest that you use strong pseudoprimes as described in http://www.utm.edu/research/primes/prove/prove2_3.html It may seem a bit more complex then the
          Message 4 of 5 , Oct 2, 2001
            May I suggest that you use strong pseudoprimes as described in
            http://www.utm.edu/research/primes/prove/prove2_3.html
            It may seem a bit more complex then the other methods, but requires almost
            no storage space and shouldn't be TOO difficult to implement. Specifically,
            you can use other people's work to reduce your workload by using bases 2, 7
            and 61, which can verify a number to be prime if it is less than 4759123141
            (more than 32 bits). Bitshifting can be used to take care of any necessary
            divisions by two and the modulus and exponentiation algorithms won't be very
            hard to implement in assembly (you would probably need a modulus or
            equivalent function for trial divisions anyway). At the very least, it is
            an interesting alternative to trial division.

            Hope this helps,

            James




            James Thoms
            3B Computer Engineering
            University of Waterloo



            From: ylar.jyrviste@...
            To: primenumbers@yahoogroups.com
            Subject: [PrimeNumbers] testing if 32 bit integer is prime number
            Date: Tue, 02 Oct 2001 11:58:19 -0000


            Hi,

            I need to show if a 32 bit integer is prime or not. Is it enough to
            prove that the number is greater than 2,odd number and divisible by 3?

            Or is there another simple algorithm to prove it(I hvae to implement
            it in assembler)

            Thanks

            a computer science student



            _________________________________________________________________
            Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp
          • Phil Carmody
            ... Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at
            Message 5 of 5 , Oct 2, 2001
              On Tue, 02 October 2001, "James Thoms" wrote:
              > May I suggest that you use strong pseudoprimes as described in
              > http://www.utm.edu/research/primes/prove/prove2_3.html
              > It may seem a bit more complex then the other methods, but requires almost
              > no storage space and shouldn't be TOO difficult to implement. Specifically,
              > you can use other people's work to reduce your workload by using bases 2, 7
              > and 61, which can verify a number to be prime if it is less than 4759123141
              > (more than 32 bits). Bitshifting can be used to take care of any necessary
              > divisions by two and the modulus and exponentiation algorithms won't be very
              > hard to implement in assembly (you would probably need a modulus or
              > equivalent function for trial divisions anyway). At the very least, it is
              > an interesting alternative to trial division.


              Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at

              http://primes.utm.edu/curios/includes/file.php/primetest.html

              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.