1. ## reduction mod

let n=1105, so n-1=2^4(69) Compute the values of

2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105),

Use the Rabin Miller test to conclue that n is composite....

Where do I begin and how?

2. Originally Posted by duggaboy
let $\displaystyle n=1105,$ so $\displaystyle n-1=2^4\times 69$ Compute the values of

$\displaystyle [2^{69} \mod 1105],\ [2^{2 \times 69} \mod 1105],\ [2^{4 \times 69}\mod 1105],\ [2^{8 \times 69} \mod 1105]$

Use the Rabin Miller test to conclue that n is composite....

Where do I begin and how?
In the Rabin-Miller test for the (pseudo) primality of $\displaystyle 1105$ we have $\displaystyle s=4$ and $\displaystyle d=69$

So $\displaystyle a$ is a witness to the primallity of $\displaystyle 1105$ if:

$\displaystyle a^d \not \equiv 1 \mod 1105$

and

$\displaystyle a^{2^r.d} \not \equiv -1 \mod 1105; \forall \ r \in \{0,\ ..., \ s-1\}$

So if you compute the values asked for and the first is not congruent to $\displaystyle \pm 1 \mod 1105$ and the others are not congruent to $\displaystyle -1 \mod 1105$, then $\displaystyle 2$ is a witness to the compositness of $\displaystyle 1105$. (In fact if the conditions hold then 1105 is certainly composite, if they fail 1105 is probably prime)

RonL

3. Can you explain the last part of this to me?

4. Originally Posted by duggaboy

Can you explain the last part of this to me?
It is that these:

"2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105)"

are not congruent to -1 modulo 1105.

RonL