# Thread:

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.

2. ## 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.

#### Search Tags

View Tag Cloud

Copyright © 2005-2013 Math Help Forum. All rights reserved.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 2, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9235260486602783, "perplexity_flag": "middle"}