nx_miller_rabin.nx source
↩ module page · 77 lines · 2742 B
1// nx_miller_rabin.nx -- Miller-Rabin probabilistic primality test.
2//
3// genealogy_id: miller_1976_plus_rabin_1980
4// lineage_id: primality_testing
5// references: Miller 1976 STOC; Rabin 1980 J. Number Theory.
6// license: public_domain
7// complexity: O(k log^3 n) for k witnesses.
8//
9// Deterministic for n < 3,317,044,064,679,887,385,961,981 using witnesses
10// {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}. We use the first 7 which
11// are deterministic for n < 3.3 * 10^14 -- sufficient for fits-in-i64.
12
13// nx_safety_envelope:
14// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
15// sil_target: SIL1
16// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
17// verdict: NOT_YET_EVALUATED
18
19import "nx_syscalls.nx"
20import "nx_tier.nx"
21import "nx_pow_mod.nx"
22
23// Miller-Rabin witness check: returns 1 if n passes the witness test
24// (probably prime), 0 if witness 'a' proves n composite.
25func nx_mr_witness(a: nx_int, d: nx_int, r: nx_int, n: nx_int) -> nx_int {
26 var x: nx_int = nx_pow_mod(a, d, n)
27 if x == 1 { return 1 }
28 if x == n - 1 { return 1 }
29 var i: nx_int = 1
30 while i < r {
31 x = (x * x) - ((x * x) / n) * n
32 if x == n - 1 { return 1 }
33 i = i + 1
34 }
35 return 0
36}
37
38// Probabilistic primality test: 1 = probably prime, 0 = composite.
39func nx_miller_rabin(n: nx_int) -> nx_int {
40 if n < 2 { return 0 }
41 if n == 2 { return 1 }
42 if n == 3 { return 1 }
43 if (n - (n / 2) * 2) == 0 { return 0 } // n even and > 2
44
45 // Decompose n - 1 = 2^r * d with d odd.
46 // NishiLang parser needs a flag-driven loop (no inline `while (expr) == 0`).
47 var d: nx_int = n - 1
48 var r: nx_int = 0
49 var still_even: nx_int = 1
50 while still_even == 1 {
51 let mod2: nx_int = d - (d / 2) * 2
52 if mod2 == 0 {
53 d = d / 2
54 r = r + 1
55 }
56 if mod2 != 0 { still_even = 0 }
57 }
58
59 // Deterministic witnesses for n < 3.3e14 (covers all 64-bit integers
60 // in practice -- next pseudoprime requires witness 41).
61 let w1: nx_int = 2
62 let w2: nx_int = 3
63 let w3: nx_int = 5
64 let w4: nx_int = 7
65 let w5: nx_int = 11
66 let w6: nx_int = 13
67 let w7: nx_int = 17
68
69 if w1 < n { if nx_mr_witness(w1, d, r, n) == 0 { return 0 } }
70 if w2 < n { if nx_mr_witness(w2, d, r, n) == 0 { return 0 } }
71 if w3 < n { if nx_mr_witness(w3, d, r, n) == 0 { return 0 } }
72 if w4 < n { if nx_mr_witness(w4, d, r, n) == 0 { return 0 } }
73 if w5 < n { if nx_mr_witness(w5, d, r, n) == 0 { return 0 } }
74 if w6 < n { if nx_mr_witness(w6, d, r, n) == 0 { return 0 } }
75 if w7 < n { if nx_mr_witness(w7, d, r, n) == 0 { return 0 } }
76 return 1
77}