Haha just realized that the miller-rabin-SHANG test does not exist and its the miller-rabin strong test! I just copied it down wrong...
Anyway my question about whether what I did was enough to answer the question still stands.
Could someone just clear up what exactly a strong pseudoprime is for me? Every book seems to say something slightly different!
From my notes it appears it might be if it passes the Miller-Rabin-Shang pseudoprime test however that doesn't actually say strong pseudoprime in my notes but seems to be the method used in tutorials for the strong pseudoprime problem...
Here's the question I'm doing...
Show that the Carmichael number 561 is not a strong pseudoprime to base 2, but that 2047 is. Show, however, that 2047 is not a strong pseudoprime to base 3.
The way I have been doing it is based on wikipedia. The number we are testing is of the form , then it is a strong pseudoprime (to base 2 for ex) if...
Now since 561 = 3x11x17, we use the method shown by tonio here... http://www.mathhelpforum.com/math-he...ongruence.html to find an answer.
Now since I got 263 from this, does that mean that 561 is NOT a strong pseudoprime to base 2 or do I have show it does not pass both of the tests here Strong pseudoprime - Wikipedia, the free encyclopedia...
Is that even how i answer this question?
MathWorld's definition, so I would assume it's reliable. Since the problem doesn't state to use Guy's definition, I think that for base 2 you would additionally need to verify that
and only then will you be able to conclude that 561 is not a strong pseudoprime to base 2.
But this may not be as much work as it seems because we already know that , and then we can write
(Edited the last part a bit.)