Improving trial division primality test

Question

I'm learning about checking is number a prime, and I curious how can I make it faster for big numbers (Like 2^64-1)

bool IsPrime(BigInteger number)
{
    if (number< 2) return false;
    else if (number< 4) return true;
    else if (number% 2 == 0) return false;
    else for (BigInteger u = 3; u*u <= Num; u += 2)
        if (number % u == 0) return false;
    return true;
}

Did you read [this wikipedia article](https://en.wikipedia.org/wiki/Primality_test) about primality tests ? What else did you try so far ? — m.raynal, Apr 24 '19 at 07:56
If you want to make it faster for 64-bit integers, use the appropriate type ``ulong``. For more ideas on optimizing this test, see http://codinghelmet.com/exercises/prime-testing — dumetrulo, Apr 24 '19 at 07:58
For numbers as large as 2^64, trial division is virtually out of question. — , Apr 24 '19 at 08:00
I read about Miller–Rabin, sieve and AKS. Even try miller-rabin test (which is great) but dont really know how to improve this basic algorithm even more ( 6k ± 1 maybe?) — Scarkz Aflaton, Apr 24 '19 at 08:01
Another remark I'd make is that I see mainly two ways of testing if a number is prime faster: 1- Use probabilistic techniques, as they are the only ones scaling with very large numbers (PRIME is CO-NP) 2- If you want to stick with trial division, you can then switch to a faster compiled language, such as C(++),rust, ... But globally, there is no way to really improve (non-marginally) the trial division. — m.raynal, Apr 24 '19 at 08:03
And why `number / 2` ??? This adds about 40% of useless work. — , Apr 24 '19 at 08:16
Not a huge improvement but instead of `u*u <= Num` (I guess you meant `number`?) you could calculate the square root and check only against that to save the multiplications (e.g. [this method](https://stackoverflow.com/a/16804098/1782792) seems fast). — jdehesa, Apr 24 '19 at 12:05
You can pull the multiplication out of the ``for`` loop, and have the same effect (multiplying only once instead of on every iteration; possibly the compiler will apply that optimization automatically). Regarding the square root: I like the method you pointed to but it features division, which especially in the case of BigIntegers is not fast; I have a method (not sure now where I found it) that is recursive but uses only addition, multiplication, left shift, and right shift, each once per iteration. — dumetrulo, Apr 24 '19 at 13:00
thanks guys, I use sieve of atkin to generate list of pramies and mod by them, seems to be fastest method so far. — Scarkz Aflaton, Apr 24 '19 at 13:37
@dumetrulo Yes, I really just looked up something that seemed good and simple since I don't know that much about BigInt, but yes divisions are slow, so not sure what's the best algorithm. About the multiplication though, it cannot really be skipped, since `u` changes on every iteration, so it is needed every time. Maybe you could just have a `u_squared` number and update it with additions on each iteration instead. — jdehesa, Apr 24 '19 at 17:33
As @YvesDaoust noted, for numbers approaching the upper part of the range *none* of the hints about using sieves or faster arithmetic will work. You need to use a better algorithm. Deterministic Miller-Rabin is probably the fastest for these numbers. See the [wikipedia](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases) article for the list of bases you need to test. — President James K. Polk, Apr 24 '19 at 23:03

score 0 · Answer 1 · answered Apr 24 '19 at 15:47

For a very minor improvement, so minor you won't notice it, you can save a single if statement:

if (number < 2) return false;
else if (number % 2 == 0) return number == 2;
else for...

For a noticeable improvement I would suggest using the Sieve of Eratosthenes in place of trial division. If that is still too slow, then research other methods, such as Miller-Rabin.

Even with the fast methods, it is worth using the slower methods for a short time, say trying all the primes up to 5,000 as factors, before going to the trouble of setting up one of the more complex tests. There is no point in doing a lot of work to determine that 4,327,856,799,435 is composite.

Improving trial division primality test

1 Answers1