-2

Possible Duplicate:
Fastest primality test

Can somebody give an efficient algorithm for determining the primality of an number?

The conventional iteration method seems to take a lot of time when testing primality of large numbers. I have tried some probabilistic algorithms but was not satisfied by the accuracy.

Community
  • 1
  • 1
Vijeenrosh P.W
  • 359
  • 1
  • 3
  • 8
  • As far as I know, you will always have a trade off between accuracy and efficiency when you use a primality test. I have only used the [Miller Rabin primality test](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test), but I think you will have to more precises in what you are doing. – Lucas Nov 15 '11 at 18:38
  • Also, just choose a sufficiently large k. 2^-k (or any n^-k for n > 1) gets small exponentially fast (read: VERY FAST). – Thomas Eding Nov 15 '11 at 18:45
  • Wow, there are a lot more duplicates than that - just search for primality test. – Cascabel Nov 15 '11 at 18:52

1 Answers1

2

On of the most efficient probabilistic primality tests is the Rabin-Miller primality test (implementation in C). This is what RSA uses.

Deterministic tests are more difficult if you need speed and are seldomly useful in real world applications.

andand
  • 17,134
  • 11
  • 53
  • 79
Dennis
  • 14,264
  • 2
  • 48
  • 57