Creative Racket Competition 2022: January 1, 2022 → February 28, 2022

[spdegabrielle]

A new entry in the Creative Racket Competition:

Miller-Rabin Liars

Primality tests like the Fermat test and the Miller-Rabin test rely on so-called "witnesses." In the case of Fermat, if a^{p-1} = 1 (mod p) , for some a , then p is probably prime. The a is called a Fermat witness. However, if a composite passes the test for a given a , then a is called a Fermat liar . The same principle holds for Miller-Rabin, although the equation is slightly more complicated.

Which numbers are the most honest? Which ones are the most lying? That's what the given visualization is supposed to show. This is also a gradually typed program. The numeric computation happens in Typed Racket, while the visualization part happens in untyped Racket.