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 iterationthe 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,N1] x = mod n if x =1 or x = n1 Next iteration for r = 1 to s1 x = mod n if x = 1 return false if x = N1 Next iteration return false return true asked 25 May '13, 11:45

The question has been closed for the following reason "The question is answered, right answer was accepted" by chandan11111 27 May '13, 12:26
Yes it depends on random numbers. You are lucky if you got AC in minimum iterations. answered 25 May '13, 17:15
