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.
Description
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 somea
, thenp
is probably prime. Thea
is called a Fermat witness. However, if a composite passes the test for a givena
, thena
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.
Location for Entry
How you made your entry?
Licence
Licence for you image or media file: https://creativecommons.org/licenses/by-sa/4.0/ Licence for you code: MIT/Apache 2 like Racket