×

# [closed] Number of Iteration In Robin Miller algo

 3 2 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 asked 25 May '13, 11:45 3.6k●13●35●55 accept rate: 10%

### The question has been closed for the following reason "The question is answered, right answer was accepted" by chandan11111 27 May '13, 12:26

 4 It highly depends on the input and also the random numbers generated!!! you can go through this link!! answered 25 May '13, 12:35 4★kunal361 6.0k●13●32●72 accept rate: 21% thnxx @kunal361 (25 May '13, 18:45)
 4 Yes it depends on random numbers. You are lucky if you got AC in minimum iterations. answered 25 May '13, 17:15 0●2●3 accept rate: 0% 2 ok all depends on luck :P hahah (25 May '13, 18:46)

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×16
×1

question asked: 25 May '13, 11:45

question was seen: 1,179 times

last updated: 27 May '13, 12:26