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 CodeChef: Practical coding for everyone(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
hahah