Results 1 to 4 of 4

Math Help - Strong pseudoprime

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Strong pseudoprime

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Deadstar View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2-pseudoprime!
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 20th 2011, 05:32 AM
  2. Proving a Pseudoprime?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 30th 2010, 01:52 AM
  3. How to prove 161038 is pseudoprime?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 06:47 PM
  4. Fermat Pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 31st 2009, 02:52 AM
  5. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum