Results 1 to 6 of 6

Math Help - Fermat Pseudoprime problem

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    36

    Fermat Pseudoprime problem

    Fermat test base a,  (a,N)=1 , \ \ a^{N-1} = 1 \ \ mod \ N

    problem is, how many values of a are necessary to determine the primality or compositeness of N < 1000000 excluding Carmichael numbers ?

    i found, if we test with primes 2,3,5,7,11 and it will find all the primes < 1000000. so i guess we need to test at least 5 values of a?


    this is actually a programming problem, and i dont think it is possible to answer without testing
    Last edited by amberxinya; December 31st 2009 at 02:08 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    You cannot determine it definitely. Even if you tested all values of a, it could still be composite. But the more values of a you test, the higher the probability that it is prime.
    I cannot find this information on the internet anymore, but I think the probability that the number is prime is equal to 1 - 10^{\frac{-k}{2}}, where k is the number of values of a tested. I cannot guarantee this is the real probability formula, but it is something in this fashion.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    36

    pro

    the problem is, the question asks to test with some a in range <1000000 excluding the carmichael. so the problem is to find out whether it is composite or prime. there is no probability of getting a carmichael becausee we remove it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Try with 20 values of a. That should be good enough.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    36

    well

    well, i tried 2,3,5,7,11 and it works. it gives all prime numbers...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Then everything's good, try to find the probability formula
    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, 06:32 AM
  2. Proving a Pseudoprime?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 30th 2010, 02:52 AM
  3. Strong pseudoprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 10th 2010, 11:24 AM
  4. programming for pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 29th 2009, 04:03 AM
  5. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 10:15 PM

Search Tags


/mathhelpforum @mathhelpforum