Browse Groups

• ## Re: [PrimeNumbers] testing if 32 bit integer is prime number

(5)
• NextPrevious
• 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 1 of 5 , Oct 2, 2001
View Source
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@...
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

_________________________________________________________________
• ... Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at
Message 1 of 5 , Oct 2, 2001
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.