Results 1 to 2 of 2

Math Help - Calculation 300 digit Sophie Germain prime number

  1. #1
    Newbie
    Joined
    May 2012
    From
    London
    Posts
    1

    Calculation 300 digit Sophie Germain prime number

    I have been set a challenge to produce a 300 digit Sophie Germain prime number using computer code.

    Maths at this level is not something that I use a great deal and certain not with these size of numbers. So I apologise if this is all a bit "basic".

    Working on the basis of A prime number p is a [COLOR=rgb(0.000000%, 69.400000%, 31.400000%)]Sophie Germain Prime, [/COLOR]when also 2p + 1 is a prime.

    But, I need to generate this result in the most efficient method possible and would like any assistance or advice on how to produce such a number without making my starting point of 3 and working up to this size of number. Is there a more efficient method to achieve this?

    Any assistance would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Re: Calculation 300 digit Sophie Germain prime number

    No! There's no reason to start with 3! Why not start with 10^{300}+1? There's no magic formula that I know of to produce these things, but in the 300 digit range, about .14% of numbers are prime, so the starting odds of p and 2p+1 being prime are one in about 475000. Sure, that's a half a million primality tests, but it certainly beats starting at 3.

    If it was me, I would start with a table of a million or so random 300 digit numbers, along with their "partners" giving you random pairs (p,2p+1) in the range you're looking for. Then sieve out the evens, multiples of 3, then 5, 7, 11, etc, until you get to about 10^6. Whatever you have left over, use a high-powered primality test like Lucas-Lehmer to eliminate your pairs. You might be able to get away with only a few thousand tests after sieving.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Digit sum & digit product of number x
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 19th 2011, 08:07 AM
  3. Replies: 4
    Last Post: October 31st 2010, 03:06 PM
  4. sophie germain prime primitive root
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 24th 2010, 09:17 AM
  5. two-digit number
    Posted in the Algebra Forum
    Replies: 6
    Last Post: October 10th 2009, 07:59 AM

Search Tags


/mathhelpforum @mathhelpforum