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?

Printable View

- Jun 11th 2008, 02:42 PMduggaboyreduction 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? - Jun 11th 2008, 11:24 PMCaptainBlack
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 - Jun 12th 2008, 10:53 AMduggaboy
http://www.mathhelpforum.com/math-he...c4468b91-1.gif

Can you explain the last part of this to me? - Jun 12th 2008, 02:05 PMCaptainBlack