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?
In the Rabin-Miller test for the (pseudo) primality of we have and
So is a witness to the primallity of if:
and
So if you compute the values asked for and the first is not congruent to and the others are not congruent to , then is a witness to the compositness of . (In fact if the conditions hold then 1105 is certainly composite, if they fail 1105 is probably prime)
RonL