WA in miller rabin test

#1

I implemented miller rabin test for Primiality Testing Question but it gives WA in 1 Test Case for 10000 iteration. is there something i misseed

#2

@utkarsh.lal9430310535 Please provide me your code in Coding Blocks IDE

#3
#4

@utkarsh.lal9430310535 when we will multiply two large numbers under modulo we will have overflow (as here number under which we are taking mod might it self be very big so this leaves a possibility of overflow)

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

can you please debug the code?

#7

i have tried almost everything

#8

these test are only based on probability. And they can create false negatives. i.e miller rabin may say that the number is prime, but it may be prime. These are probabilistic test.
If you need 100 score. Fermat primality test gives accurate result in these test cases, but these are just based on luck I guess. There will be cases where these tests may give false negatives.


I would suggest to give it a read. https://cp-algorithms.com/algebra/primality_tests.html
It is a really good article.