0
$\begingroup$

In an article about the Miller-Rabin primality test, in the example section it says: "Suppose we wish to determine if $n = 221$ is prime. We write $n − 1 = 220$ as $2^{2}\times 55$, so that we have $s = 2$ and $d = 55$."

My question is: What are the missing steps that enables us to go from $220$ to $2^2\times 55$?

  • 0
    See http://en.wikipedia.org/wiki/Divisibility_rule and more generally http://en.wikipedia.org/wiki/Integer_factorization .2011-06-15

2 Answers 2

5

Just divide by $2$ as many times as needed until the quotient is odd. In this case you divide twice, hence the factor $2^2$. The crucial thing is you are looking for $2^s \times d$, not an unknown prime $p$ in $p^s \times n$

0

You factor 220 into powers of 2. 4 divides evenly into 220 which is $2^2$.