Strong pseudoprime

Oct 2007
722
168
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 \(\displaystyle p\) we are testing is of the form \(\displaystyle d \cdot 2^s + 1\), then it is a strong pseudoprime (to base 2 for ex) if...

\(\displaystyle 2^d \equiv 1\) mod p

So,
\(\displaystyle 561 = 35\cdot 2^4 + 1\)

Now since 561 = 3x11x17, we use the method shown by tonio here... http://www.mathhelpforum.com/math-help/number-theory/141542-there-quicker-way-solve-congruence.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?
 
Oct 2007
722
168
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.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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 \(\displaystyle p\) we are testing is of the form \(\displaystyle d \cdot 2^s + 1\), then it is a strong pseudoprime (to base 2 for ex) if...

\(\displaystyle 2^d \equiv 1\) mod p

So,
\(\displaystyle 561 = 35\cdot 2^4 + 1\)

Now since 561 = 3x11x17, we use the method shown by tonio here... http://www.mathhelpforum.com/math-help/number-theory/141542-there-quicker-way-solve-congruence.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?
I haven't looked at the definition in textbooks, but Wikipedia's definition matches 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

\(\displaystyle 2^{35\cdot2^0} \not \equiv -1\ (\text{mod }561)\)

\(\displaystyle 2^{35\cdot2^1} \not \equiv -1\ (\text{mod }561)\)

\(\displaystyle 2^{35\cdot2^2} \not \equiv -1\ (\text{mod }561)\)

\(\displaystyle 2^{35\cdot2^3} \not \equiv -1\ (\text{mod }561)\)

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 \(\displaystyle 2^{35\cdot2^0} \equiv 263 \not \equiv -1\ (\text{mod }561)\), and then we can write

\(\displaystyle 2^{35\cdot2^1} \equiv (2^{35})^2 \equiv 263^2\ (\text{mod }561)\)

and afterwards,

\(\displaystyle 2^{35\cdot2^2} \equiv (2^{35\cdot2^1})^2\ (\text{mod }561)\)

etc.

(Edited the last part a bit.)
 
  • Like
Reactions: Deadstar

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Actually, it's not even necessary to determine that \(\displaystyle 2^{35} \equiv 263\ (\text{mod } 561)\), because of the following two statements.

\(\displaystyle a \equiv 1 \ (\text{mod } 561) \iff a \equiv 1 \ (\text{mod } 3) \ \&\ a \equiv 1 \ (\text{mod } 11) \ \&\ a \equiv 1 \ (\text{mod } 17)\)

\(\displaystyle a \equiv -1 \ (\text{mod } 561) \iff a \equiv -1 \ (\text{mod } 3) \ \&\ a \equiv -1 \ (\text{mod } 11) \ \&\ a \equiv -1 \ (\text{mod } 17)\)

And we would apply the same reasoning to make the second condition of strong pseudoprime easier to prove or disprove without a calculator.