Thread: Efficient large prime checker

Originally Posted by Andreea

For the implementation I thought of something like this: http://en.literateprograms.org/index...(C)&oldid=6349

It is more complicated.

Ah, yes.

Actually, the relevant code is not at all complicated. Just look at miller_rabin_pass() in lines 59 to 93 of miller-rabin.c (on the page linked above).

Most of the other code there is just a simple big-integer library, so you can test primality on natural numbers much bigger than what the hardware would otherwise support.

Perhaps you didn't notice that the original poster talked about integers in the millions to tens of millions -- well within 32-bit integer range --, not integers with millions to tens of millions of digits?

I saw , but the thinking step between a quick fix and a big integer library is not so big.

Originally Posted by Andreea

I saw , but the thinking step between a quick fix and a big integer library is not so big.

No, it's not . While I recommend new programmers to look at existing libraries first (especially the GNU Multiple Precision Arithmetic Library), a big integer library is not difficult to write.

I've even posted one here. It's just a quick hack, for a standalone Blum-Blum-Shub pseudorandom number generator.

In cases like primality checking, writing the big integer library from scratch will probably yield better efficiency, as there are many places where you can simplify compared to full big integer handling. For example, you can assume the a in Miller-Rabin test is always small (say, no more than half a limb), or even open-code the first few prime a (since those are the ones you'll usually use), and use big integers for others.

Nice

even open-code the first few prime a (since those are the ones you'll usually use), and use big integers for others.

a really good idea! The one with a small is a straightforward hack.