You are not logged in. Please login at to post your questions!


[closed] 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 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

chandan11111's gravatar image

accept rate: 10%

closed 27 May '13, 12:26

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

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

you can go through this link!!


answered 25 May '13, 12:35

kunal361's gravatar image

accept rate: 21%

thnxx @kunal361

(25 May '13, 18:45) chandan111113★

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


answered 25 May '13, 17:15

simle_coders's gravatar image

accept rate: 0%


ok all depends on luck :P hahah

(25 May '13, 18:46) chandan111113★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 25 May '13, 11:45

question was seen: 1,179 times

last updated: 27 May '13, 12:26