Question

Use the Miller–Rabin test on each of the following numbers. In each case, either provide a Miller–Rabin witness for the compositeness of n, or conclude that n is probably prime by providing 10 numbers that are not Miller–Rabin witnesses for n.(a) n = 1105.(b) n = 294409(c) n = 294439(d) n = 118901509(e) n = 118901521(f) n = 118901527(g) n = 118915387

Answer 1

In miller-Rabin test, write n-1 as product of an odd number 'm' and 'a' power of 2.

∴
`n - 1 = mx2^k`

The format test in 'a" can be written as
`a^(n-1) = a^(mx2^k)`

find
`\bar I = a^mmodn`

⇒ if
`\bar I = 1` , n is a composite, otherwise 'n' is a prime.

Explanation:

see details