reduction mod

Printable View

June 11th 2008, 02:42 PM
duggaboy

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?
June 11th 2008, 11:24 PM
CaptainBlack

Quote:

Originally Posted by duggaboy

let $n=1105,$ so $n-1=2^4\times 69$ Compute the values of

$[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 $1105$ we have $s=4$ and $d=69$

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

$<br /> a^d \not \equiv 1 \mod 1105<br />$

and

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

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

RonL
June 12th 2008, 10:53 AM
duggaboy

http://www.mathhelpforum.com/math-he...c4468b91-1.gif
Can you explain the last part of this to me?
June 12th 2008, 02:05 PM
CaptainBlack

Quote:

Originally Posted by duggaboy

http://www.mathhelpforum.com/math-he...c4468b91-1.gif
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