Primeshard
0:00.0

The Miller-Rabin primality test is a probabilistic algorithm. For a given odd integer n>3n > 3, we write n1=2sdn - 1 = 2^s \cdot d where dd is odd. If ad1(modn)a^d \equiv 1 \pmod n or a2rd1(modn)a^{2^r \cdot d} \equiv -1 \pmod n for some 0r<s0 \le r < s, then nn is a 'strong probable prime' to base aa. For n=121n = 121, which base a=3a=3 reveals it as composite?