 # Number of Iteration In Robin Miller algo

#1

My Question is that what will be the effect of number of iteration in Robin miller algo
sometimes it produce correct answer after passing 0 or 1 iteration sometimes it need upto 8 iteration
whats the reason ??
i got AC using 1 iteration in PON (spoj)
while i got AC using 8 iteration in http://www.codechef.com/MAY13/problems/WITMATH(may challenge)
here is the algorithm
Algorithm

Input :A number N to be tested and a variable iteration-the number
of ‘a’ for which algorithm will test N.
Output :0 if N is definitely a composite and 1 if N is probably a prime.

Write N as
For each iteration
Pick a random a in [1,N-1]
x = mod n
if x =1 or x = n-1
Next iteration
for r = 1 to s-1
x = mod n
if x = 1
return false
if x = N-1
Next iteration
return false
return true

#2

It highly depends on the input and also the random numbers generated!!!

you can go through this link!!

#3

Yes it depends on random numbers. You are lucky if you got AC in minimum iterations.

#4

thnxx @kunal361

#5

ok all depends on luck hahah