nx_miller_rabin.nx
buildroot/runtime/nx_miller_rabin.nx
about
nx_miller_rabin.nx -- Miller-Rabin probabilistic primality test.
genealogy_id: miller_1976_plus_rabin_1980
lineage_id: primality_testing
references: Miller 1976 STOC; Rabin 1980 J. Number Theory.
license: public_domain
complexity: O(k log^3 n) for k witnesses.
Deterministic for n < 3,317,044,064,679,887,385,961,981 using witnesses
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}. We use the first 7 which
are deterministic for n < 3.3 * 10^14 -- sufficient for fits-in-i64.
dependencies 3 imports · 1 importers
imports: nx_syscalls.nxnx_tier.nxnx_pow_mod.nx
imported by: nx_miller_rabin_test.nx
structs
| none |
consts
| none |
functions
| 25 | func nx_mr_witness(a: nx_int, d: nx_int, r: nx_int, n: nx_int) -> nx_int |
| 39 | func nx_miller_rabin(n: nx_int) -> nx_int |