Primality test. Is this program performing faster than all others?

Question

bool is_prime(BigInt num)
{
    if(num == 0 || num == 1 || (num != 2 && num % 2 == 0))
        return false;

        BigInt sq = sqrt(num);

        for(BigInt i = 3; i <= sq; i += 2)
            if(num % i == 0)
                 return false;

       return true;
}

We only need to check upto square root. Proof -> https://scienceparv.blogspot.com/2021/07/mathematics-if-one-divisor-of-dividend.html

Answer 1

Your code is doing so called Trial Division primality test, which is slow for big numbers. It has time complexity O(Sqrt(N)) of primitive operations.

If you have really big numbers, 1024 bits or bigger then Trial Division will be a way too slow.

There are two kinds of Primality Tests - deterministic and probabilistic. Trial Division is one example of deterministic algorithm. All deterministic algorithms are much slower then probabilitic.

Probabilistic algorithms are never certain about if a number is really prime. But for any small chosen probability P they can tell in very little computational time if the number is prime with certainty of this probability. Deterministic algorithm are always certain if a number is prime or not.

There exist faster than yours algorithms of deterministic primality testing, for example Elliptic Curve Primality Test, which is fast but difficult to implement. But you can easily test any number for free with fast software like Primo for Linux, this is free software but with closed sources and for Linux only (there is no Windows version at all).

I decided to implement for you from scratch one probabilistic primality test, which is Fermat Primality Test, it is very fast and easy to implement in few lines of code, which I did in below C++ code. It has complexity of O(Log2(N)) which is blazingly fast time even for 20000-bit numbers.

Try it online!

#include <cstdint>
#include <iostream>

using Word = uint32_t;
using DWord = uint64_t;

Word PowMod(Word a, Word b, Word const & c) {
    // https://en.wikipedia.org/wiki/Modular_exponentiation
    Word r = 1;
    while (b != 0) {
        if (b & 1)
            r = (DWord(r) * a) % c;
        a = (DWord(a) * a) % c;
        b >>= 1;
    }
    return r;
}

Word Rand(Word const & prev, Word const & begin, Word const & end) {
    Word constexpr magic_prime = uint32_t(-1) - 4;
    return Word((DWord(prev) * magic_prime) % (end - begin)) + begin;
}

bool IsFermatProbablePrime(Word const & n, int trials = 32) {
    // https://en.wikipedia.org/wiki/Fermat_primality_test
    if (n <= 16)
        return n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13;
    Word witness = 2;
    for (size_t i = 0; i < trials; ++i) {
        witness = Rand(witness, 2, n - 2);
        if (PowMod(witness, n - 1, n) != 1)
            return false;
    }
    return true;
}

int main() {
    Word const prime_num = 3941362591U, comp_num = 2245837171U;
    std::cout
        << std::boolalpha
        << "num1 is prime: " << IsFermatProbablePrime(prime_num) << ", "
        << "num2 is prime: " << IsFermatProbablePrime(comp_num)  << std::endl;
}

Output:

num1 is prime: true, num2 is prime: false

(and really first number prime_num is prime and second comp_num is composite)

You can see that I used two typedefs for Word and DWord, like this:

using Word = uint32_t;
using DWord = uint64_t;

This kind of typedefs only allow you to check primality of 32-bit numbers, for your case to check big numbers just replace with:

using Word = BigInt;
using DWord = BigInt;

to use your class BigInt that you already used in your code.

Answer 2

Is this program performing faster than all others?

No.

There are faster primality tests than trial division.

For example:

https://en.wikipedia.org/wiki/Elliptic_curve_primality

https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test

Also see: https://en.wikipedia.org/wiki/Primality_test