Miller–Rabin primality test: Difference between revisions
Add BQN
(Add BQN) |
|||
Line 469:
}
quit</lang>
=={{header|BQN}}==
The function <code>IsPrime</code> in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn] uses deterministic Miller-Rabin to test primality when trial division fails. The following function, derived from that library, selects witnesses at random. The left argument is the number of witnesses to test, with default 10.
<lang bqn>_modMul ← { n _𝕣: n|× }
MillerRabin ← { 𝕊n: 10𝕊n ; iter 𝕊 n: !2|n
# n = 1 + d×2⋆s
s ← 0 {𝕨 2⊸|◶⟨+⟜1𝕊2⌊∘÷˜⊢,⊣⟩ 𝕩} n-1
d ← (n-1) ÷ 2⋆s
# Arithmetic mod n
Mul ← n _modMul
Pow ← Mul{𝔽´𝔽˜⍟(/2|⌊∘÷⟜2⍟(↕1+·⌊2⋆⁼⊢)𝕩)𝕨}
# Miller-Rabin test
MR ← {
1 =𝕩 ? 𝕨≠s ;
(n-1)=𝕩 ? 0 ;
𝕨≤1 ? 1 ;
(𝕨-1) 𝕊 Mul˜𝕩
}
C ← { 𝕊a: s MR a Pow d } # Is composite
{0:1; C •rand.Range⌾(-⟜2) n ? 0; 𝕊𝕩-1} iter
}</lang>
The simple definition of <code>_modMul</code> is inaccurate when intermediate results fall outside the exact integer range (this can happen for inputs around <code>2⋆26</code>). When replaced with the definition below, <code>MillerRabin</code> remains accurate for all inputs, as floating point can't represent odd numbers outside of integer range.
<lang bqn># Compute n|𝕨×𝕩 in high precision
_modMul ← { n _𝕣:
# Split each argument into two 26-bit numbers, with the remaining
# mantissa bit encoded in the sign of the lower-order part.
q←1+2⋆27
Split ← { h←(q×𝕩)(⊣--)𝕩 ⋄ ⟨𝕩-h,h⟩ }
# The product, and an error relative to precise split multiplication.
Mul ← × (⊣ ⋈ -⊸(+´)) ·⥊×⌜○Split
((n×<⟜0)⊸+ -⟜n+⊢)´ n | Mul
}</lang>
{{out}}
<lang bqn> MillerRabin 15485867
1
MillerRabin¨⊸/ 101+2×↕10
⟨ 101 103 107 109 113 ⟩</lang>
=={{header|Bracmat}}==
| |||