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 challenge)
here is the 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


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

you can go through this link!!


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


thnxx @kunal361

ok all depends on luck :stuck_out_tongue: hahah