Results 1 to 6 of 6

Thread: Fermat Pseudoprime problem

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    36

    Fermat Pseudoprime problem

    Fermat test base a, $\displaystyle (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; Dec 31st 2009 at 01: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 $\displaystyle a$, it could still be composite. But the more values of $\displaystyle 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 $\displaystyle 1 - 10^{\frac{-k}{2}}$, where $\displaystyle k$ is the number of values of $\displaystyle 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: Nov 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. Strong pseudoprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 10th 2010, 10:24 AM
  4. programming for pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 29th 2009, 03:03 AM
  5. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum