As a general rule, if you want to check if a number is prime, it turns out that the deterministic solutions are rather slow. In fact, they tend to be too slow for general use. So I figured, while writing Number::Properties that is_prime() should use the Miller-Rabin primality tests. My code had some issues, but I suspect this had something to do with Perl's lack of precision. As a result, and since Perl is a bit slow for work like this, I figured I would write the code in XS. I used the C from Top Coder's primality testing article, but quickly got stuck with the following error:
Error: 'long long' not in typemap in Properties.xs, line 64
Please specify prototyping behavior for Properties.xs (see perlxs manual)
Much googling suggests to me that there's not a simple way around this that's also robust. Damn. I may have to switch back to Perl.