Number of Iteration In Robin Miller algo

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 Likes

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

you can go through this link!!

4 Likes

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

4 Likes

thnxx @kunal361

ok all depends on luck :stuck_out_tongue: hahah

2 Likes