1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pohlig-Hellman and Pseudoprimes

  1. Sep 17, 2012 #1
    1. The problem statement, all variables and given/known data

    To compute the discrete log of 3344 to base 3 in Z(29^3)* using Pohlig-Hellman.

    Secondly, im supposed to figure out how many bases b that for n = 837 makes n euler pseudoprime to the base b.


    2. Relevant equations

    Pohlig-Hellman algorithm.
    Pseudoprime def: b^((n-1)/2) congruent to jacobisymbol (b/n) gives that n is pseudoprime to base b

    3. The attempt at a solution

    For the first one I just cant seem to get the right values for the chinese remainder theorem.. I get a = 2 mod 4, a = 2 mod 7, a = 1 mod 13 and a = 1 mod 67 but it should be 3 and 2 on the last ones. I have checked it out a bit, and it seems that 3 and 2 works, but so does 1?

    Secondly, my best idea so far is to do a brute force search.. Seems pretty random to me how many such bases there are for a given number n.
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?