Strong pseudoprime

**Deadstar** · May 10th 2010, 09:00 AM

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

$2^d \equiv 1$ mod p

So,
$561 = 35\cdot 2^4 + 1$

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?

**Deadstar** · May 10th 2010, 09:09 AM

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** · May 10th 2010, 09:27 AM

Originally Posted by Deadstar

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

$2^d \equiv 1$ mod p

So,
$561 = 35\cdot 2^4 + 1$

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?

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

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

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

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

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

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

and afterwards,

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

etc.

(Edited the last part a bit.)

**undefined** · May 10th 2010, 10:24 AM

Actually, it's not even necessary to determine that $2^{35} \equiv 263\ (\text{mod } 561)$ , because of the following two statements.

$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)$

$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.

Thread: Strong pseudoprime

LinkBack

Thread Tools

Display

Strong pseudoprime

Similar Math Help Forum Discussions

2-pseudoprime!

Proving a Pseudoprime?

How to prove 161038 is pseudoprime?

Fermat Pseudoprime problem

Fermat pseudoprime

Search Tags