Write Rabin Miller Algorithm for primality testing. Test whether 341 i | Information Security 2081

Information Security20815 marksNumerical: Rabin Miller primality testPrimality testing algorithms

Write Rabin Miller Algorithm for primality testing. Test whether 341 is prime or not using the algorithm. [5]

Number to test: $n = 341$ - Witness base (standard choice): $a = 2$ --- If $n$ is an odd prime, write $n - 1 = 2^s \cdot d$ with $d$ odd. Then for any witness $a$ coprime to $n$ , either: $a^d \equiv 1 \pmod{n} \quad\text{OR}\quad a^{2^r d} \equiv -1 \pmod{n} \text{ for some } 0 \le r < s$ If ...

Number to test: $n = 341$ - Witness base (standard choice): $a = 2$ --- If $n$ is an odd prime, write $n - 1 = 2^s \cdot d$ with $d$ odd. Then for any witness $a$ coprime to $n$, either: $$a^d \equiv 1 \pmod{n} \quad\text{OR}\quad a^{2^r d} \equiv -1 \pmod{n} \text{ for some } 0 \le r < s$$ If ...