Probabilistic primality test useful?

[triska]

As of git commit https://github.com/SWI-Prolog/packages-ssl/commit/a2f661c892317fcc803bd77799830a40b83f0c86, SWI-Prolog provides the predicate crypto_is_prime/2 in library(crypto).

You can call it as crypto_is_prime(P, []), and it succeeds iff P passes a probabilistic primality test. Thus, the predicate succeeds for every prime, and fails for non-primes with very high probability.

Please consider whether it is worthwhile to use this predicate in Brachylog as a quick additional check for potential primality of an integer. I hope you find it useful!

[JCumin]

@triska I'll look into it in a few days (I'm quite busy at the moment). Nevertheless, it's good to see more and more arithmetic related built-ins added to SWI.

[JCumin]

@triska brachylog_prime now uses that predicate as of this commit.

Since this is a recent addition, it checks whether the predicate is availaible or not, and if not uses the old implementation.

I still check with the old implementation if the prime is indeed prime (although this is extremely unlikely that it is composite, I want the predicate to be theoretically non-probabilistic).

This is thus now slightly slower if the number is prime (though this is unmeasurable for non-huge numbers) and much much faster for composite numbers (especially the ones that have only large prime factors).

On that note, it seems that there is some kind of memoization feature with crypto_is_prime/2:

?- time(brachylog_prime('default','integer':12387023476478364963163,_)).
% 20,443 inferences, 0.858 CPU in 0.939 seconds (91% CPU, 23826 Lips)
false.

?- time(brachylog_prime('default','integer':12387023476478364963163,_)).
% 103 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
false.

I assume this is intended? I don't see it documented in the commit you linked.

[triska]

I think it is definitely very good that you are aiming for certainty, and are not satisfied with a probabilistic check!

Maybe conditional compilation could be useful to simplify the code somewhat:

:- if(current_predicate(crypto_is_prime/2)).
probably_prime(P) :- crypto_is_prime(P, []).
:- else.
probably_prime(_).
:- endif.

You can then simply use probably_prime/1 and keep the previous code mostly unmodified.

As far as I can tell (from the OpenSSL source code), there is no memoization for this feature. Maybe loading library(crypto) slows down the first call? Please try adding :- use_module(library(crypto)). to your code.

[JCumin]

@triska Using conditional compilation is indeed much shorter and cleaner, thanks!

Adding :- use_module(library(crypto)). did not seem to change this strange time difference. This is not a big deal but that's definitely a strange behavior.