CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Safe and Sophie Germain primes - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"0f8eb739-bccb-4b43-9f25-19fcfc8adcc7","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Safe_and_Sophie_Germain_primes","wgTitle":"Safe and Sophie Germain primes","wgCurRevisionId":1256361461,"wgRevisionId":1256361461,"wgArticleId":89244,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","All articles with unsourced statements","Articles with unsourced statements from June 2020","Classes of prime numbers","Unsolved problems in number theory"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Safe_and_Sophie_Germain_primes","wgRelevantArticleId":89244,"wgIsProbablyEditable":true, "wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Sophie_Germain_prime","wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgInternalRedirectTargetUrl":"/wiki/Safe_and_Sophie_Germain_primes","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q105971314","wgCheckUserClientHintsHeadersJsApi":["brands","architecture", "bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP", "ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Safe and Sophie Germain primes - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Safe_and_Sophie_Germain_primes rootpage-Safe_and_Sophie_Germain_primes skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Safe+and+Sophie+Germain+primes" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Safe+and+Sophie+Germain+primes" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Safe+and+Sophie+Germain+primes" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Safe+and+Sophie+Germain+primes" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Individual_numbers" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Individual_numbers"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Individual numbers</span> </div> </a> <ul id="toc-Individual_numbers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Properties</span> </div> </a> <button aria-controls="toc-Properties-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Properties subsection</span> </button> <ul id="toc-Properties-sublist" class="vector-toc-list"> <li id="toc-Modular_restrictions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Modular_restrictions"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Modular restrictions</span> </div> </a> <ul id="toc-Modular_restrictions-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Infinitude_and_density" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Infinitude_and_density"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Infinitude and density</span> </div> </a> <ul id="toc-Infinitude_and_density-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Strong_primes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Strong_primes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Strong primes</span> </div> </a> <ul id="toc-Strong_primes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Applications</span> </div> </a> <button aria-controls="toc-Applications-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Applications subsection</span> </button> <ul id="toc-Applications-sublist" class="vector-toc-list"> <li id="toc-Cryptography" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Cryptography"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Cryptography</span> </div> </a> <ul id="toc-Cryptography-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Primality_testing" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Primality_testing"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Primality testing</span> </div> </a> <ul id="toc-Primality_testing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pseudorandom_number_generation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Pseudorandom_number_generation"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.3</span> <span>Pseudorandom number generation</span> </div> </a> <ul id="toc-Pseudorandom_number_generation-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-In_popular_culture" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_popular_culture"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>In popular culture</span> </div> </a> <ul id="toc-In_popular_culture-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Safe and Sophie Germain primes</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="This article exist only in this language. Add the article for other languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-0" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">Add languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> <div class="after-portlet after-portlet-lang"><span class="uls-after-portlet-link"></span><span class="wb-langlinks-add wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q105971314#sitelinks-wikipedia" title="Add interlanguage links" class="wbc-editpage">Add links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Safe_and_Sophie_Germain_primes" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Safe_and_Sophie_Germain_primes" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Safe_and_Sophie_Germain_primes"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Safe_and_Sophie_Germain_primes"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Safe_and_Sophie_Germain_primes" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Safe_and_Sophie_Germain_primes" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&oldid=1256361461" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Safe_and_Sophie_Germain_primes&id=1256361461&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSafe_and_Sophie_Germain_primes"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSafe_and_Sophie_Germain_primes"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Safe_and_Sophie_Germain_primes&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q105971314" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=Sophie_Germain_prime&redirect=no" class="mw-redirect" title="Sophie Germain prime">Sophie Germain prime</a>)</span></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">A prime pair (p, 2p+1)</div> <p>In <a href="/wiki/Number_theory" title="Number theory">number theory</a>, a <a href="/wiki/Prime_number" title="Prime number">prime number</a> <i>p</i> is a <span id="Sophie_Germain_prime"><b>Sophie Germain prime</b></span> if 2<i>p</i> + 1 is also prime. The number 2<i>p</i> + 1 associated with a Sophie Germain prime is called a <span id="safe_prime"><b>safe prime</b></span>. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in <a href="/wiki/Public_key_cryptography" class="mw-redirect" title="Public key cryptography">public key cryptography</a> and <a href="/wiki/Primality_testing" class="mw-redirect" title="Primality testing">primality testing</a>. It has been <a href="/wiki/Conjecture" title="Conjecture">conjectured</a> that there are <a href="/wiki/Infinite_set" title="Infinite set">infinitely</a> many Sophie Germain primes, but this remains unproven. </p><p>Sophie Germain primes are named after French mathematician <a href="/wiki/Sophie_Germain" title="Sophie Germain">Sophie Germain</a>, who used them in her investigations of <a href="/wiki/Fermat%27s_Last_Theorem" title="Fermat's Last Theorem">Fermat's Last Theorem</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> One attempt by Germain to prove Fermat’s Last Theorem was to let <i>p</i> be a prime number of the form 8<i>k</i> + 7 and to let <i>n</i> = <i>p</i> – 1. In this case, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{n}+y^{n}=z^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>+</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>=</mo> <msup> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{n}+y^{n}=z^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c34dcc46ebfb58e1b91a6c0caa1470e76139543a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.175ex; height:2.676ex;" alt="{\displaystyle x^{n}+y^{n}=z^{n}}"></span> is unsolvable. Germain’s proof, however, remained unfinished.<sup id="cite_ref-:0_2-0" class="reference"><a href="#cite_note-:0-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if <i>p</i> is an odd prime and 2<i>p</i> + 1 is also prime, then <i>p</i> must divide <i>x</i>, <i>y</i>, or <i>z.</i> Otherwise, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x^{n}+y^{n}\neq z^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>+</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>≠</mo> <msup> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle x^{n}+y^{n}\neq z^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f0e6c9a0dc9d7757213fc720b98ecb7898607f5d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.175ex; height:2.676ex;" alt="{\textstyle x^{n}+y^{n}\neq z^{n}}"></span>. This case where <i>p</i> does not divide <i>x</i>, <i>y</i>, or <i>z</i> is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time.<sup id="cite_ref-:0_2-1" class="reference"><a href="#cite_note-:0-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Later work by Kummer and others always divided the problem into first and second cases. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Individual_numbers">Individual numbers</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=1" title="Edit section: Individual numbers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The first few Sophie Germain primes (those less than 1000) are </p> <dl><dd>2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A005384" class="extiw" title="oeis:A005384">A005384</a></span></dd></dl> <p>Hence, the first few safe primes are </p> <dl><dd>5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A005385" class="extiw" title="oeis:A005385">A005385</a></span></dd></dl> <p>In <a href="/wiki/Cryptography" title="Cryptography">cryptography</a> much larger Sophie Germain primes like 1,846,389,521,368 + 11<sup>600</sup> are required. </p><p>Two distributed computing projects, <a href="/wiki/PrimeGrid" title="PrimeGrid">PrimeGrid</a> and <a href="/wiki/Twin_Prime_Search" title="Twin Prime Search">Twin Prime Search</a>, include searches for large Sophie Germain primes. Some of the largest known Sophie Germain primes are given in the following table.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <table class="wikitable"> <tbody><tr> <th>Value</th> <th>Number<br />of digits</th> <th>Time of<br />discovery</th> <th>Discoverer </th></tr> <tr> <td>2618163402417 × 2<sup>1290000</sup> − 1</td> <td align="right">388342</td> <td>February 2016</td> <td>Dr. James Scott Brown in a distributed <a href="/wiki/PrimeGrid" title="PrimeGrid">PrimeGrid</a> search using the programs TwinGen and <a href="/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">LLR</a><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>18543637900515 × 2<sup>666667</sup> − 1</td> <td align="right">200701</td> <td>April 2012</td> <td>Philipp Bliedung in a distributed <a href="/wiki/PrimeGrid" title="PrimeGrid">PrimeGrid</a> search using the programs TwinGen and <a href="/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">LLR</a><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>183027 × 2<sup>265440</sup> − 1</td> <td align="right">79911</td> <td>March 2010</td> <td>Tom Wu using LLR<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td style="white-space:nowrap">648621027630345 × 2<sup>253824</sup> − 1 and<br />620366307356565 × 2<sup>253824</sup> − 1</td> <td align="right">76424</td> <td style="white-space:nowrap">November 2009</td> <td>Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>1068669447 × 2<sup>211088</sup> − 1</td> <td align="right">63553</td> <td>May 2020</td> <td>Michael Kwok<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>99064503957 × 2<sup>200008</sup> − 1</td> <td align="right">60220</td> <td>April 2016</td> <td>S. Urushihata<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>607095 × 2<sup>176311</sup> − 1</td> <td align="right">53081</td> <td style="white-space:nowrap">September 2009</td> <td>Tom Wu<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>48047305725 × 2<sup>172403</sup> − 1</td> <td align="right">51910</td> <td>January 2007</td> <td>David Underbakke using TwinGen and LLR<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td style="white-space:nowrap">137211941292195 × 2<sup>171960</sup> − 1</td> <td align="right">51780</td> <td>May 2006</td> <td>Járai et al.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </td></tr> </tbody></table> <p>On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a <a href="/wiki/Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a> modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240) using a <a href="/wiki/General_number_field_sieve" title="General number field sieve">number field sieve</a> algorithm; see <a href="/wiki/Discrete_logarithm_records" title="Discrete logarithm records">Discrete logarithm records</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=2" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There is no special primality test for safe primes the way there is for <a href="/wiki/Fermat_prime" class="mw-redirect" title="Fermat prime">Fermat primes</a> and <a href="/wiki/Mersenne_prime" title="Mersenne prime">Mersenne primes</a>. However, <a href="/wiki/Pocklington_primality_test" title="Pocklington primality test">Pocklington's criterion</a> can be used to prove the primality of 2<i>p</i> + 1 once one has proven the primality of <i>p</i>. </p><p>Just as every term except the last one of a <a href="/wiki/Cunningham_chain" title="Cunningham chain">Cunningham chain</a> of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10<i>n</i> + 7, are the last terms in such chains when they occur, since 2(10<i>n</i> + 7) + 1 = 20<i>n</i> + 15 is <a href="/wiki/Divisibility" class="mw-redirect" title="Divisibility">divisible</a> by 5. </p><p>For a safe prime, every <a href="/wiki/Quadratic_nonresidue" class="mw-redirect" title="Quadratic nonresidue">quadratic nonresidue</a>, except -1 (if nonresidue<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup>), is a <a href="/wiki/Primitive_root_modulo_n" title="Primitive root modulo n">primitive root</a>. It follows that for a safe prime, the least positive primitive root is a prime number.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Modular_restrictions">Modular restrictions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=3" title="Edit section: Modular restrictions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>With the exception of 7, a safe prime <i>q</i> is of the form 6<i>k</i> − 1 or, equivalently, <i>q</i> ≡ 5 (<a href="/wiki/Modulo_operation" class="mw-redirect" title="Modulo operation">mod</a> 6) – as is <i>p</i> > 3. Similarly, with the exception of 5, a safe prime <i>q</i> is of the form 4<i>k</i> − 1 or, equivalently, <i>q</i> ≡ 3 (mod 4) — trivially true since (<i>q</i> − 1) / 2 must evaluate to an <a href="/wiki/Parity_(mathematics)" title="Parity (mathematics)">odd</a> <a href="/wiki/Natural_number" title="Natural number">natural number</a>. Combining both forms using <a href="/wiki/Least_common_multiple" title="Least common multiple">lcm</a>(6, 4) we determine that a safe prime <i>q</i> > 7 also must be of the form 12<i>k</i> − 1 or, equivalently, <i>q</i> ≡ 11 (mod 12). </p><p>It follows that, for any safe prime <i>q</i> > 7: </p> <ul><li>both 3 and 12 are <a href="/wiki/Quadratic_residue" title="Quadratic residue">quadratic residues</a> mod <i>q</i> (per <a href="/wiki/Quadratic_residue#Law_of_quadratic_reciprocity" title="Quadratic residue">law of quadratic reciprocity</a>) <ul><li>neither 3 nor 12 is a <a href="/wiki/Primitive_root_modulo_n" title="Primitive root modulo n">primitive root</a> of <i>q</i></li> <li>the only safe primes that are also <a href="/wiki/Full_reptend_prime" title="Full reptend prime">full reptend primes</a> in <a href="/wiki/Base_12" class="mw-redirect" title="Base 12">base 12</a> are 5 and 7</li> <li><i>q</i> divides 3<sup>(<i>q</i>−1)/2</sup> − 1 and 12<sup>(<i>q</i>−1)/2</sup> − 1, same as 3<sup>(<i>q</i>−1)/2</sup> ≡ 1 mod <i>q</i> and 12<sup>(<i>q</i>−1)/2</sup> ≡ 1 mod <i>q</i> (per <a href="/wiki/Euler%27s_criterion" title="Euler's criterion">Euler's criterion</a>)</li></ul></li> <li><i>q</i>-3, <i>q</i>-4, <i>q</i>-9, <i>q</i>-12 are quadratic nonresidues <ul><li><i>q</i>-3, <i>q</i>-4, <i>q</i>-9, and, for <i>q</i> > 11, <i>q</i>-12 are primitive roots</li></ul></li></ul> <p>If <i>p</i> is a Sophie Germain prime greater than 3, then <i>p</i> must be congruent to 2 mod 3. For, if not, it would be congruent to 1 mod 3 and 2<i>p</i> + 1 would be congruent to 3 mod 3, impossible for a prime number.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> Similar restrictions hold for larger prime moduli, and are the basis for the choice of the "correction factor" 2<i>C</i> in the Hardy–Littlewood estimate on the density of the Sophie Germain primes.<sup id="cite_ref-shoup_18-0" class="reference"><a href="#cite_note-shoup-18"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p><p>If a Sophie Germain prime <i>p</i> is <a href="/wiki/Congruence_relation" title="Congruence relation">congruent</a> to 3 (mod 4) (<span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A002515" class="extiw" title="oeis:A002515">A002515</a></span>, <i>Lucasian primes</i>), then its matching safe prime 2<i>p</i> + 1 (<a href="/wiki/Modular_arithmetic" title="Modular arithmetic">congruent</a> to 7 modulo 8) will be a divisor of the <a href="/wiki/Mersenne_number" class="mw-redirect" title="Mersenne number">Mersenne number</a> 2<sup><i>p</i></sup> − 1. Historically, this result of <a href="/wiki/Leonhard_Euler" title="Leonhard Euler">Leonhard Euler</a> was the first known criterion for a Mersenne number with a prime index to be <a href="/wiki/Composite_number" title="Composite number">composite</a>.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Infinitude_and_density">Infinitude and density</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=4" title="Edit section: Infinitude and density"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1233989161">.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:#ccc solid;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("https://upload.wikimedia.org/wikipedia/commons/2/26/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}</style> <div role="note" aria-labelledby="unsolved-label-mathematics" class="unsolved"> <div><span class="unsolved-label" id="unsolved-label-mathematics">Unsolved problem in mathematics</span>:</div> <div class="unsolved-body">Are there infinitely many Sophie Germain primes?</div> <div class="unsolved-more"><a href="/wiki/List_of_unsolved_problems_in_mathematics" title="List of unsolved problems in mathematics">(more unsolved problems in mathematics)</a></div> </div> <p>It is <a href="/wiki/Conjecture" title="Conjecture">conjectured</a> that there are infinitely many Sophie Germain primes, but this has not been <a href="/wiki/Mathematical_proof" title="Mathematical proof">proven</a>.<sup id="cite_ref-shoup_18-1" class="reference"><a href="#cite_note-shoup-18"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> Several other famous conjectures in number theory generalize this and the <a href="/wiki/Twin_prime_conjecture" class="mw-redirect" title="Twin prime conjecture">twin prime conjecture</a>; they include the <a href="/wiki/Dickson%27s_conjecture" title="Dickson's conjecture">Dickson's conjecture</a>, <a href="/wiki/Schinzel%27s_hypothesis_H" title="Schinzel's hypothesis H">Schinzel's hypothesis H</a>, and the <a href="/wiki/Bateman%E2%80%93Horn_conjecture" title="Bateman–Horn conjecture">Bateman–Horn conjecture</a>. </p><p>A <a href="/wiki/Heuristic" title="Heuristic">heuristic</a> estimate for the <a href="/wiki/Number" title="Number">number</a> of Sophie Germain primes less than <i>n</i> is<sup id="cite_ref-shoup_18-2" class="reference"><a href="#cite_note-shoup-18"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mrow> <mo stretchy="false">(</mo> <mi>ln</mi> <mo>⁡</mo> <mi>n</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>≈</mo> <mn>1.32032</mn> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mrow> <mo stretchy="false">(</mo> <mi>ln</mi> <mo>⁡</mo> <mi>n</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8838d10c080770fb1137bd874795b79238d13b3c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:28.491ex; height:5.509ex;" alt="{\displaystyle 2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}}"></span></dd></dl> <p>where </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>=</mo> <munder> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mo>></mo> <mn>2</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>p</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>≈</mo> <mn>0.660161</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f1bd77e7da451a58c5abca90eb5cdb3cf9e770a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:29.091ex; height:7.176ex;" alt="{\displaystyle C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161}"></span></dd></dl> <p>is <a href="/wiki/Twin_prime#First_Hardy–Littlewood_conjecture" title="Twin prime">Hardy–Littlewood's twin prime constant</a>. For <i>n</i> = 10<sup>4</sup>, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. For <i>n</i> = 10<sup>7</sup>, the estimate predicts 50822, which is still 10% off from the exact value of 56032. The form of this estimate is due to <a href="/wiki/G._H._Hardy" title="G. H. Hardy">G. H. Hardy</a> and <a href="/wiki/J._E._Littlewood" class="mw-redirect" title="J. E. Littlewood">J. E. Littlewood</a>, who applied a similar estimate to <a href="/wiki/Twin_prime" title="Twin prime">twin primes</a>.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </p><p>A <a href="/wiki/Integer_sequence" title="Integer sequence">sequence</a> (<i>p</i>, 2<i>p</i> + 1, 2(2<i>p</i> + 1) + 1, ...) in which all of the numbers are prime is called a <a href="/wiki/Cunningham_chain" title="Cunningham chain">Cunningham chain</a> of the first kind. Every term of such a sequence except the last is a Sophie Germain prime, and every term except the first is a safe prime. Extending the conjecture that there exist infinitely many Sophie Germain primes, it has also been conjectured that arbitrarily long Cunningham chains exist,<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> although infinite chains are known to be impossible.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Strong_primes">Strong primes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=5" title="Edit section: Strong primes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A prime number <i>q</i> is a <a href="/wiki/Strong_prime" title="Strong prime">strong prime</a> if <span class="nowrap"><i>q</i> + 1</span> and <span class="nowrap"><i>q</i> − 1</span> both have some large (around 500 digits) prime factors. For a safe prime <span class="nowrap"><i>q</i> = 2<i>p</i> + 1</span>, the number <span class="nowrap"><i>q</i> − 1</span> naturally has a large prime factor, namely <i>p</i>, and so a safe prime <i>q</i> meets part of the criteria for being a strong prime. The running times of some methods of <a href="/wiki/Integer_factorization" title="Integer factorization">factoring</a> a number with <i>q</i> as a prime factor depend partly on the size of the prime factors of <span class="nowrap"><i>q</i> − 1</span>. This is true, for instance, of the <a href="/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm"><i>p</i> − 1 method</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=6" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Cryptography">Cryptography</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=7" title="Edit section: Cryptography"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Safe primes are also important in cryptography because of their use in <a href="/wiki/Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a>-based techniques like <a href="/wiki/Diffie%E2%80%93Hellman_key_exchange" title="Diffie–Hellman key exchange">Diffie–Hellman key exchange</a>. If <span class="nowrap">2<i>p</i> + 1</span> is a safe prime, the multiplicative <a href="/wiki/Group_(mathematics)" title="Group (mathematics)">group</a> of integers <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modulo</a> <span class="nowrap">2<i>p</i> + 1</span> has a <a href="/wiki/Subgroup" title="Subgroup">subgroup</a> of large prime <a href="/wiki/Order_(group_theory)" title="Order (group theory)">order</a>. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to <i>p</i>. </p><p>A prime number <i>p</i> = 2<i>q</i> + 1 is called a <i>safe prime</i> if <i>q</i> is prime. Thus, <i>p</i> = 2<i>q</i> + 1 is a safe prime if and only if <i>q</i> is a Sophie Germain prime, so finding safe primes and finding Sophie Germain primes are equivalent in computational difficulty. The notion of a safe prime can be strengthened to a strong prime, for which both <i>p</i> − 1 and <i>p</i> + 1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in the <a href="/wiki/RSA_(cryptosystem)" title="RSA (cryptosystem)">RSA cryptosystem</a>, because they prevent the system being broken by some <a href="/wiki/Integer_factorization" title="Integer factorization">factorization</a> algorithms such as <a href="/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm">Pollard's <i>p</i> − 1 algorithm</a>. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> </p><p>Similar issues apply in other cryptosystems as well, including <a href="/wiki/Diffie%E2%80%93Hellman_key_exchange" title="Diffie–Hellman key exchange">Diffie–Hellman key exchange</a> and similar systems that depend on the security of the <a href="/wiki/Discrete_logarithm_problem" class="mw-redirect" title="Discrete logarithm problem">discrete logarithm problem</a> rather than on integer factorization.<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p><p>In <a href="/wiki/Sophie_Germain_Counter_Mode" title="Sophie Germain Counter Mode">Sophie Germain Counter Mode</a>, it was proposed to use the arithmetic in the <a href="/wiki/Finite_field" title="Finite field">finite field</a> of order equal to the safe prime 2<sup>128</sup> + 12451, to counter weaknesses in <a href="/wiki/Galois/Counter_Mode" title="Galois/Counter Mode">Galois/Counter Mode</a> using the binary finite field GF(2<sup>128</sup>). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Primality_testing">Primality testing</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=8" title="Edit section: Primality testing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the first version of the <a href="/wiki/AKS_primality_test" title="AKS primality test">AKS primality test</a> paper, a conjecture about Sophie Germain primes is used to lower the worst-case complexity from <span class="texhtml">O(log<sup>12</sup><i>n</i>)</span> to <span class="texhtml">O(log<sup>6</sup><i>n</i>)</span>. A later version of the paper is shown to have time complexity <span class="texhtml">O(log<sup>7.5</sup><i>n</i>)</span> which can also be lowered to <span class="texhtml">O(log<sup>6</sup><i>n</i>)</span> using the conjecture.<sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> Later variants of AKS have been proven to have complexity of <span class="texhtml">O(log<sup>6</sup><i>n</i>)</span> without any conjectures or use of Sophie Germain primes. </p> <div class="mw-heading mw-heading3"><h3 id="Pseudorandom_number_generation">Pseudorandom number generation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=9" title="Edit section: Pseudorandom number generation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Safe primes obeying certain congruences can be used to generate <a href="/wiki/Pseudo-random_numbers" class="mw-redirect" title="Pseudo-random numbers">pseudo-random numbers</a> of use in <a href="/wiki/Monte_Carlo_simulation" class="mw-redirect" title="Monte Carlo simulation">Monte Carlo simulation</a>. </p><p>Similarly, Sophie Germain primes may be used in the generation of <a href="/wiki/Pseudo-random_numbers" class="mw-redirect" title="Pseudo-random numbers">pseudo-random numbers</a>. The decimal expansion of 1/<i>q</i> will produce a <a href="/wiki/Recurring_decimal#Fractions_with_prime_denominators" class="mw-redirect" title="Recurring decimal">stream</a> of <i>q</i> − 1 pseudo-random digits, if <i>q</i> is the safe prime of a Sophie Germain prime <i>p</i>, with <i>p</i> <a href="/wiki/Modular_arithmetic#Congruence" title="Modular arithmetic">congruent</a> to 3, 9, or 11 modulo 20.<sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> Thus "suitable" prime numbers <i>q</i> are 7, 23, 47, 59, 167, 179, etc. (<span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A000353" class="extiw" title="oeis:A000353">A000353</a></span>) (corresponding to <i>p</i> = 3, 11, 23, 29, 83, 89, etc.) (<span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A000355" class="extiw" title="oeis:A000355">A000355</a></span>). The result is a stream of <a href="/wiki/Period_length" class="mw-redirect" title="Period length">length</a> <i>q</i> − 1 digits (including leading zeros). So, for example, using <i>q</i> = 23 generates the pseudo-random digits 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Note that these digits are not appropriate for cryptographic purposes, as the value of each can be derived from its predecessor in the digit-stream.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (June 2020)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="In_popular_culture">In popular culture</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=10" title="Edit section: In popular culture"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Sophie Germain primes are mentioned in the stage play <i><a href="/wiki/Proof_(play)" title="Proof (play)">Proof</a></i><sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> and the <a href="/wiki/Proof_(2005_film)" title="Proof (2005 film)">subsequent film</a>.<sup id="cite_ref-31" class="reference"><a href="#cite_note-31"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=11" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-lower-alpha"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">-1 is a quadratic residue only when the safe prime is equal 5; for all other safe primes, -1 is a nonresidue</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=12" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Specifically, Germain proved that the first case of Fermat's Last Theorem, in which the exponent divides one of the bases, is true for every Sophie Germain prime, and she used similar arguments to prove the same for all other primes up to 100. For details see <style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFEdwards2000" class="citation cs2"><a href="/wiki/Harold_Edwards_(mathematician)" title="Harold Edwards (mathematician)">Edwards, Harold M.</a> (2000), <i>Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory</i>, Graduate Texts in Mathematics, vol. 50, Springer, pp. 61–65, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780387950020" title="Special:BookSources/9780387950020"><bdi>9780387950020</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fermat%27s+Last+Theorem%3A+A+Genetic+Introduction+to+Algebraic+Number+Theory&rft.series=Graduate+Texts+in+Mathematics&rft.pages=61-65&rft.pub=Springer&rft.date=2000&rft.isbn=9780387950020&rft.aulast=Edwards&rft.aufirst=Harold+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-:0-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDalmedico1991" class="citation journal cs1">Dalmedico, Amy (1991). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/24938838">"Sophie Germain"</a>. <i>Scientific American</i>. <b>265</b> (6): 116–123. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fscientificamerican1291-116">10.1038/scientificamerican1291-116</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/24938838">24938838</a> – via JSTOR.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Scientific+American&rft.atitle=Sophie+Germain&rft.volume=265&rft.issue=6&rft.pages=116-123&rft.date=1991&rft_id=info%3Adoi%2F10.1038%2Fscientificamerican1291-116&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F24938838%23id-name%3DJSTOR&rft.aulast=Dalmedico&rft.aufirst=Amy&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F24938838&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLaubenbacherPengelley2010" class="citation journal cs1">Laubenbacher, Reinhard; Pengelley, David (2010-11-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.hm.2009.12.002">"<span class="cs1-kern-left"></span>"Voici ce que j'ai trouvé:" Sophie Germain's grand plan to prove Fermat's Last Theorem"</a>. <i>Historia Mathematica</i>. <b>37</b> (4): 641–692. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0801.1809">0801.1809</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.hm.2009.12.002">10.1016/j.hm.2009.12.002</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0315-0860">0315-0860</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Historia+Mathematica&rft.atitle=%22Voici+ce+que+j%27ai+trouv%C3%A9%3A%22+Sophie+Germain%27s+grand+plan+to+prove+Fermat%27s+Last+Theorem&rft.volume=37&rft.issue=4&rft.pages=641-692&rft.date=2010-11-01&rft_id=info%3Aarxiv%2F0801.1809&rft.issn=0315-0860&rft_id=info%3Adoi%2F10.1016%2Fj.hm.2009.12.002&rft.aulast=Laubenbacher&rft.aufirst=Reinhard&rft.au=Pengelley%2C+David&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252Fj.hm.2009.12.002&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/top20/page.php?id=2">The Top Twenty Sophie Germain Primes</a> — from the <a href="/wiki/Prime_Pages" class="mw-redirect" title="Prime Pages">Prime Pages</a>. Retrieved 17 May 2020.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.primegrid.com/download/SGS_2618163402417_1290000.pdf">"PrimeGrid's Sophie Germain Prime Search"</a> <span class="cs1-format">(PDF)</span>. PrimeGrid. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://www.primegrid.com/download/SGS_2618163402417_1290000.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09<span class="reference-accessdate">. Retrieved <span class="nowrap">29 February</span> 2016</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=PrimeGrid%27s+Sophie+Germain+Prime+Search&rft.pub=PrimeGrid&rft_id=https%3A%2F%2Fwww.primegrid.com%2Fdownload%2FSGS_2618163402417_1290000.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.primegrid.com/download/SGS_666667.pdf">"PrimeGrid's Sophie Germain Prime Search"</a> <span class="cs1-format">(PDF)</span>. PrimeGrid. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://www.primegrid.com/download/SGS_666667.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09<span class="reference-accessdate">. Retrieved <span class="nowrap">18 April</span> 2012</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=PrimeGrid%27s+Sophie+Germain+Prime+Search&rft.pub=PrimeGrid&rft_id=http%3A%2F%2Fwww.primegrid.com%2Fdownload%2FSGS_666667.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=92222">The Prime Database: 183027*2^265440-1</a>. From The <a href="/wiki/Prime_Pages" class="mw-redirect" title="Prime Pages">Prime Pages</a>.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=90907">The Prime Database: 648621027630345*2^253824-1</a>.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=90711">The Prime Database: 620366307356565*2^253824-1</a></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://primes.utm.edu/primes/page.php?id=130903">The Prime Database: 1068669447*2^211088-1</a> From The <a href="/wiki/Prime_Pages" class="mw-redirect" title="Prime Pages">Prime Pages</a>.</span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://primes.utm.edu/primes/page.php?id=121507">The Prime Database: 99064503957*2^200008-1</a> From The <a href="/wiki/Prime_Pages" class="mw-redirect" title="Prime Pages">Prime Pages</a>.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=89999">The Prime Database: 607095*2^176311-1</a>.</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=79261">The Prime Database: 48047305725*2^172403-1</a>.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://primes.utm.edu/primes/page.php?id=77705">The Prime Database: 137211941292195*2^171960-1</a>.</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRameshMakeshwari2022" class="citation journal cs1">Ramesh VP, Makeshwari M (16 September 2022). "Least Primitive Root of any Safe Prime is Prime". <i>The American Mathematical Monthly</i>. <b>129</b> (10). <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00029890.2022.2115816">10.1080/00029890.2022.2115816</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+American+Mathematical+Monthly&rft.atitle=Least+Primitive+Root+of+any+Safe+Prime+is+Prime&rft.volume=129&rft.issue=10&rft.date=2022-09-16&rft_id=info%3Adoi%2F10.1080%2F00029890.2022.2115816&rft.aulast=Ramesh&rft.aufirst=VP&rft.au=Makeshwari%2C+M&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKrantz2010" class="citation cs2">Krantz, Steven G. (2010), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ulmAH-6IzNoC&pg=PA206"><i>An Episodic History of Mathematics: Mathematical Culture Through Problem Solving</i></a>, Mathematical Association of America, p. 206, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780883857663" title="Special:BookSources/9780883857663"><bdi>9780883857663</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=An+Episodic+History+of+Mathematics%3A+Mathematical+Culture+Through+Problem+Solving&rft.pages=206&rft.pub=Mathematical+Association+of+America&rft.date=2010&rft.isbn=9780883857663&rft.aulast=Krantz&rft.aufirst=Steven+G.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DulmAH-6IzNoC%26pg%3DPA206&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-shoup-18"><span class="mw-cite-backlink">^ <a href="#cite_ref-shoup_18-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-shoup_18-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-shoup_18-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShoup2009" class="citation cs2"><a href="/wiki/Victor_Shoup" title="Victor Shoup">Shoup, Victor</a> (2009), "5.5.5 Sophie Germain primes", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=pWFdMf5hb5oC&pg=PA123"><i>A Computational Introduction to Number Theory and Algebra</i></a>, Cambridge University Press, pp. 123–124, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521516440" title="Special:BookSources/9780521516440"><bdi>9780521516440</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=5.5.5+Sophie+Germain+primes&rft.btitle=A+Computational+Introduction+to+Number+Theory+and+Algebra&rft.pages=123-124&rft.pub=Cambridge+University+Press&rft.date=2009&rft.isbn=9780521516440&rft.aulast=Shoup&rft.aufirst=Victor&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DpWFdMf5hb5oC%26pg%3DPA123&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRibenboim1983" class="citation cs2"><a href="/wiki/Paulo_Ribenboim" title="Paulo Ribenboim">Ribenboim, P.</a> (1983), "1093", <i><a href="/wiki/The_Mathematical_Intelligencer" title="The Mathematical Intelligencer">The Mathematical Intelligencer</a></i>, <b>5</b> (2): 28–34, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF03023623">10.1007/BF03023623</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0737682">0737682</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Mathematical+Intelligencer&rft.atitle=1093&rft.volume=5&rft.issue=2&rft.pages=28-34&rft.date=1983&rft_id=info%3Adoi%2F10.1007%2FBF03023623&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D737682%23id-name%3DMR&rft.aulast=Ribenboim&rft.aufirst=P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDubner1996" class="citation cs2"><a href="/wiki/Harvey_Dubner" title="Harvey Dubner">Dubner, Harvey</a> (1996), "Large Sophie Germain primes", <i>Mathematics of Computation</i>, <b>65</b> (213): 393–396, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.2395">10.1.1.106.2395</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-96-00670-9">10.1090/S0025-5718-96-00670-9</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1320893">1320893</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=Large+Sophie+Germain+primes&rft.volume=65&rft.issue=213&rft.pages=393-396&rft.date=1996&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.106.2395%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1320893%23id-name%3DMR&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-96-00670-9&rft.aulast=Dubner&rft.aufirst=Harvey&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRibenboim1999" class="citation cs2"><a href="/wiki/Paulo_Ribenboim" title="Paulo Ribenboim">Ribenboim, Paulo</a> (1999), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=XPrQmE5trIgC&pg=PA141"><i>Fermat's Last Theorem for Amateurs</i></a>, Springer, p. 141, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780387985084" title="Special:BookSources/9780387985084"><bdi>9780387985084</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fermat%27s+Last+Theorem+for+Amateurs&rft.pages=141&rft.pub=Springer&rft.date=1999&rft.isbn=9780387985084&rft.aulast=Ribenboim&rft.aufirst=Paulo&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DXPrQmE5trIgC%26pg%3DPA141&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWells2011" class="citation cs2">Wells, David (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=1MTcYrbTdsUC&pg=PA35"><i>Prime Numbers: The Most Mysterious Figures in Math</i></a>, John Wiley & Sons, p. 35, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781118045718" title="Special:BookSources/9781118045718"><bdi>9781118045718</bdi></a>, <q>If the strong prime <i>k</i>-tuples conjecture is true, then Cunningham chains can reach any length.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Prime+Numbers%3A+The+Most+Mysterious+Figures+in+Math&rft.pages=35&rft.pub=John+Wiley+%26+Sons&rft.date=2011&rft.isbn=9781118045718&rft.aulast=Wells&rft.aufirst=David&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D1MTcYrbTdsUC%26pg%3DPA35&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLöh1989" class="citation cs2">Löh, Günter (1989), "Long chains of nearly doubled primes", <i><a href="/wiki/Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></i>, <b>53</b> (188): 751–759, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-1989-0979939-8">10.1090/S0025-5718-1989-0979939-8</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0979939">0979939</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=Long+chains+of+nearly+doubled+primes&rft.volume=53&rft.issue=188&rft.pages=751-759&rft.date=1989&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-1989-0979939-8&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0979939%23id-name%3DMR&rft.aulast=L%C3%B6h&rft.aufirst=G%C3%BCnter&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRivestSilverman1999" class="citation cs2">Rivest, Ronald L.; Silverman, Robert D. (November 22, 1999), <a rel="nofollow" class="external text" href="https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf"><i>Are 'strong' primes needed for RSA?</i></a> <span class="cs1-format">(PDF)</span>, <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf">archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Are+%27strong%27+primes+needed+for+RSA%3F&rft.date=1999-11-22&rft.aulast=Rivest&rft.aufirst=Ronald+L.&rft.au=Silverman%2C+Robert+D.&rft_id=https%3A%2F%2Fpeople.csail.mit.edu%2Frivest%2Fpubs%2FRS01.version-1999-11-22.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCheon2006" class="citation cs2"><a href="/wiki/Cheon_Jung-Hee" class="mw-redirect" title="Cheon Jung-Hee">Cheon, Jung Hee</a> (2006), "Security analysis of the strong Diffie–Hellman problem", <a rel="nofollow" class="external text" href="http://www.iacr.org/cryptodb/archive/2006/EUROCRYPT/2143/2143.pdf"><i>24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings</i></a> <span class="cs1-format">(PDF)</span>, <a href="/wiki/Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, vol. 4004, Springer-Verlag, pp. 1–11, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11761679_1">10.1007/11761679_1</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Security+analysis+of+the+strong+Diffie%E2%80%93Hellman+problem&rft.btitle=24th+Annual+International+Conference+on+the+Theory+and+Applications+of+Cryptographic+Techniques+%28EUROCRYPT%2706%29%2C+St.+Petersburg%2C+Russia%2C+May+28+%E2%80%93+June+1%2C+2006%2C+Proceedings&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=1-11&rft.pub=Springer-Verlag&rft.date=2006&rft_id=info%3Adoi%2F10.1007%2F11761679_1&rft.aulast=Cheon&rft.aufirst=Jung+Hee&rft_id=http%3A%2F%2Fwww.iacr.org%2Fcryptodb%2Farchive%2F2006%2FEUROCRYPT%2F2143%2F2143.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGordon1985" class="citation cs2">Gordon, John A. (1985), "Strong primes are easy to find", <i>Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984</i>, Lecture Notes in Computer Science, vol. 209, Springer-Verlag, pp. 216–223, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-39757-4_19">10.1007/3-540-39757-4_19</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Strong+primes+are+easy+to+find&rft.btitle=Proceedings+of+EUROCRYPT+84%2C+A+Workshop+on+the+Theory+and+Application+of+Cryptographic+Techniques%2C+Paris%2C+France%2C+April+9%E2%80%9311%2C+1984&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=216-223&rft.pub=Springer-Verlag&rft.date=1985&rft_id=info%3Adoi%2F10.1007%2F3-540-39757-4_19&rft.aulast=Gordon&rft.aufirst=John+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFYapYeoHengHenricksen2013" class="citation cs2">Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), "Security analysis of GCM for communication", <i>Security and Communication Networks</i>, <b>7</b> (5): 854–864, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fsec.798">10.1002/sec.798</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Security+and+Communication+Networks&rft.atitle=Security+analysis+of+GCM+for+communication&rft.volume=7&rft.issue=5&rft.pages=854-864&rft.date=2013&rft_id=info%3Adoi%2F10.1002%2Fsec.798&rft.aulast=Yap&rft.aufirst=Wun-She&rft.au=Yeo%2C+Sze+Ling&rft.au=Heng%2C+Swee-Huay&rft.au=Henricksen%2C+Matt&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAgrawalKayalSaxena2004" class="citation cs2">Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), <a rel="nofollow" class="external text" href="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">"PRIMES is in P"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>, <b>160</b> (2): 781–793, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4007%2Fannals.2004.160.781">10.4007/annals.2004.160.781</a></span>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3597229">3597229</a>, <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=PRIMES+is+in+P&rft.volume=160&rft.issue=2&rft.pages=781-793&rft.date=2004&rft_id=info%3Adoi%2F10.4007%2Fannals.2004.160.781&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F3597229%23id-name%3DJSTOR&rft.aulast=Agrawal&rft.aufirst=Manindra&rft.au=Kayal%2C+Neeraj&rft.au=Saxena%2C+Nitin&rft_id=http%3A%2F%2Fwww.cse.iitk.ac.in%2Fusers%2Fmanindra%2Falgebra%2Fprimality_v6.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMatthews1992" class="citation cs2">Matthews, Robert A. J. (1992), "Maximally periodic reciprocals", <i>Bulletin of the Institute of Mathematics and Its Applications</i>, <b>28</b> (9–10): 147–148, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1192408">1192408</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bulletin+of+the+Institute+of+Mathematics+and+Its+Applications&rft.atitle=Maximally+periodic+reciprocals&rft.volume=28&rft.issue=9%E2%80%9310&rft.pages=147-148&rft.date=1992&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1192408%23id-name%3DMR&rft.aulast=Matthews&rft.aufirst=Robert+A.+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span>.</span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPeterson2002" class="citation cs2"><a href="/wiki/Ivars_Peterson" title="Ivars Peterson">Peterson, Ivars</a> (Dec 21, 2002), <a rel="nofollow" class="external text" href="http://www.thefreelibrary.com/Drama+in+numbers%3A+putting+a+passion+for+mathematics+on+stage.-a096417274">"Drama in numbers: putting a passion for mathematics on stage"</a>, <i><a href="/wiki/Science_News" title="Science News">Science News</a></i>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F4013968">10.2307/4013968</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/4013968">4013968</a>, <q>[Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1." "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Science+News&rft.atitle=Drama+in+numbers%3A+putting+a+passion+for+mathematics+on+stage&rft.date=2002-12-21&rft_id=info%3Adoi%2F10.2307%2F4013968&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F4013968%23id-name%3DJSTOR&rft.aulast=Peterson&rft.aufirst=Ivars&rft_id=http%3A%2F%2Fwww.thefreelibrary.com%2FDrama%2Bin%2Bnumbers%253A%2Bputting%2Ba%2Bpassion%2Bfor%2Bmathematics%2Bon%2Bstage.-a096417274&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> <li id="cite_note-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-31">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFUllman2006" class="citation cs2">Ullman, Daniel (2006), <a rel="nofollow" class="external text" href="http://www.ams.org/notices/200603/rev-ullman.pdf">"Movie Review: Proof"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Notices_of_the_AMS" class="mw-redirect" title="Notices of the AMS">Notices of the AMS</a></i>, <b>53</b> (3): 340–342, <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://www.ams.org/notices/200603/rev-ullman.pdf">archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09, <q>There are a couple of breaks from realism in <i>Proof</i> where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Notices+of+the+AMS&rft.atitle=Movie+Review%3A+Proof&rft.volume=53&rft.issue=3&rft.pages=340-342&rft.date=2006&rft.aulast=Ullman&rft.aufirst=Daniel&rft_id=http%3A%2F%2Fwww.ams.org%2Fnotices%2F200603%2Frev-ullman.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Safe_and_Sophie_Germain_primes&action=edit&section=13" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://planetmath.org/SafePrime">Safe prime</a> at <a href="/wiki/PlanetMath" title="PlanetMath">PlanetMath</a>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFM._Abramowitz,_I._A._Stegun1972" class="citation book cs1"><a href="/wiki/M._Abramowitz" class="mw-redirect" title="M. Abramowitz">M. Abramowitz</a>, <a href="/wiki/I._A._Stegun" class="mw-redirect" title="I. A. Stegun">I. A. Stegun</a>, ed. (1972). <a rel="nofollow" class="external text" href="http://www.math.sfu.ca/~cbm/aands/"><i>Handbook of Mathematical Functions</i></a>. Applied Math. Series. Vol. 55 (Tenth Printing ed.). National Bureau of Standards. p. 870.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+Mathematical+Functions&rft.series=Applied+Math.+Series&rft.pages=870&rft.edition=Tenth+Printing&rft.pub=National+Bureau+of+Standards&rft.date=1972&rft_id=http%3A%2F%2Fwww.math.sfu.ca%2F~cbm%2Faands%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASafe+and+Sophie+Germain+primes" class="Z3988"></span></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Prime_number_classes" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Prime_number_classes" title="Template:Prime number classes"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Prime_number_classes" title="Template talk:Prime number classes"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Prime_number_classes" title="Special:EditPage/Template:Prime number classes"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Prime_number_classes" style="font-size:114%;margin:0 4em"><a href="/wiki/Prime_number" title="Prime number">Prime number</a> classes</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">By formula</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fermat_number" title="Fermat number">Fermat (<span class="texhtml texhtml-big" style="font-size:110%;">2<sup>2<sup><i>n</i></sup></sup> + 1</span>)</a></li> <li><a href="/wiki/Mersenne_prime" title="Mersenne prime">Mersenne (<span class="texhtml texhtml-big" style="font-size:110%;">2<sup><i>p</i></sup> − 1</span>)</a></li> <li><a href="/wiki/Double_Mersenne_number" title="Double Mersenne number">Double Mersenne (<span class="texhtml texhtml-big" style="font-size:110%;">2<sup>2<sup><i>p</i></sup>−1</sup> − 1</span>)</a></li> <li><a href="/wiki/Wagstaff_prime" title="Wagstaff prime">Wagstaff <span class="texhtml texhtml-big" style="font-size:110%;">(2<sup><i>p</i></sup> + 1)/3</span></a></li> <li><a href="/wiki/Proth_prime" title="Proth prime">Proth (<span class="texhtml texhtml-big" style="font-size:110%;"><i>k</i>·2<sup><i>n</i></sup> + 1</span>)</a></li> <li><a href="/wiki/Factorial_prime" title="Factorial prime">Factorial (<span class="texhtml texhtml-big" style="font-size:110%;"><i>n</i>! ± 1</span>)</a></li> <li><a href="/wiki/Primorial_prime" title="Primorial prime">Primorial (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p<sub>n</sub></i># ± 1</span>)</a></li> <li><a href="/wiki/Euclid_number" title="Euclid number">Euclid (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p<sub>n</sub></i># + 1</span>)</a></li> <li><a href="/wiki/Pythagorean_prime" title="Pythagorean prime">Pythagorean (<span class="texhtml texhtml-big" style="font-size:110%;">4<i>n</i> + 1</span>)</a></li> <li><a href="/wiki/Pierpont_prime" title="Pierpont prime">Pierpont (<span class="texhtml texhtml-big" style="font-size:110%;">2<sup><i>m</i></sup>·3<sup><i>n</i></sup> + 1</span>)</a></li> <li><a href="/wiki/Quartan_prime" title="Quartan prime">Quartan (<span class="texhtml texhtml-big" style="font-size:110%;"><i>x</i><sup>4</sup> + <i>y</i><sup>4</sup></span>)</a></li> <li><a href="/wiki/Solinas_prime" title="Solinas prime">Solinas (<span class="texhtml texhtml-big" style="font-size:110%;">2<sup><i>m</i></sup> ± 2<sup><i>n</i></sup> ± 1</span>)</a></li> <li><a href="/wiki/Cullen_number" title="Cullen number">Cullen (<span class="texhtml texhtml-big" style="font-size:110%;"><i>n</i>·2<sup><i>n</i></sup> + 1</span>)</a></li> <li><a href="/wiki/Woodall_number" title="Woodall number">Woodall (<span class="texhtml texhtml-big" style="font-size:110%;"><i>n</i>·2<sup><i>n</i></sup> − 1</span>)</a></li> <li><a href="/wiki/Cuban_prime" title="Cuban prime">Cuban (<span class="texhtml texhtml-big" style="font-size:110%;"><i>x</i><sup>3</sup> − <i>y</i><sup>3</sup>)/(<i>x</i> − <i>y</i></span>)</a></li> <li><a href="/wiki/Leyland_number" title="Leyland number">Leyland (<span class="texhtml texhtml-big" style="font-size:110%;"><i>x<sup>y</sup></i> + <i>y<sup>x</sup></i></span>)</a></li> <li><a href="/wiki/Thabit_number" title="Thabit number">Thabit (<span class="texhtml texhtml-big" style="font-size:110%;">3·2<sup><i>n</i></sup> − 1</span>)</a></li> <li><a href="/wiki/Williams_number" title="Williams number">Williams (<span class="texhtml texhtml-big" style="font-size:110%;">(<i>b</i>−1)·<i>b</i><sup><i>n</i></sup> − 1</span>)</a></li> <li><a href="/wiki/Mills%27_constant" title="Mills' constant">Mills (<span class="texhtml texhtml-big" style="font-size:110%;"><span style="font-size:1em">⌊</span><i>A</i><sup>3<sup><i>n</i></sup></sup><span style="font-size:1em">⌋</span></span>)</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">By integer sequence</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fibonacci_prime" title="Fibonacci prime">Fibonacci</a></li> <li><a href="/wiki/Lucas_prime" class="mw-redirect" title="Lucas prime">Lucas</a></li> <li><a href="/wiki/Pell_prime" class="mw-redirect" title="Pell prime">Pell</a></li> <li><a href="/wiki/Newman%E2%80%93Shanks%E2%80%93Williams_prime" title="Newman–Shanks–Williams prime">Newman–Shanks–Williams</a></li> <li><a href="/wiki/Perrin_prime" class="mw-redirect" title="Perrin prime">Perrin</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">By property</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Wieferich_prime" title="Wieferich prime">Wieferich</a> (<a href="/wiki/Wieferich_pair" title="Wieferich pair">pair</a>)</li> <li><a href="/wiki/Wall%E2%80%93Sun%E2%80%93Sun_prime" title="Wall–Sun–Sun prime">Wall–Sun–Sun</a></li> <li><a href="/wiki/Wolstenholme_prime" title="Wolstenholme prime">Wolstenholme</a></li> <li><a href="/wiki/Wilson_prime" title="Wilson prime">Wilson</a></li> <li><a href="/wiki/Lucky_number" title="Lucky number">Lucky</a></li> <li><a href="/wiki/Fortunate_number" title="Fortunate number">Fortunate</a></li> <li><a href="/wiki/Ramanujan_prime" title="Ramanujan prime">Ramanujan</a></li> <li><a href="/wiki/Pillai_prime" title="Pillai prime">Pillai</a></li> <li><a href="/wiki/Regular_prime" title="Regular prime">Regular</a></li> <li><a href="/wiki/Strong_prime" title="Strong prime">Strong</a></li> <li><a href="/wiki/Stern_prime" title="Stern prime">Stern</a></li> <li><a href="/wiki/Supersingular_prime_(algebraic_number_theory)" title="Supersingular prime (algebraic number theory)">Supersingular (elliptic curve)</a></li> <li><a href="/wiki/Supersingular_prime_(moonshine_theory)" title="Supersingular prime (moonshine theory)">Supersingular (moonshine theory)</a></li> <li><a href="/wiki/Good_prime" title="Good prime">Good</a></li> <li><a href="/wiki/Super-prime" title="Super-prime">Super</a></li> <li><a href="/wiki/Higgs_prime" title="Higgs prime">Higgs</a></li> <li><a href="/wiki/Highly_cototient_number" title="Highly cototient number">Highly cototient</a></li> <li><a href="/wiki/Reciprocals_of_primes#Unique_primes" title="Reciprocals of primes">Unique</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Radix" title="Radix">Base</a>-dependent</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Palindromic_prime" title="Palindromic prime">Palindromic</a></li> <li><a href="/wiki/Emirp" title="Emirp">Emirp</a></li> <li><a href="/wiki/Repunit" title="Repunit">Repunit <span class="texhtml texhtml-big" style="font-size:110%;">(10<sup><i>n</i></sup> − 1)/9</span></a></li> <li><a href="/wiki/Permutable_prime" title="Permutable prime">Permutable</a></li> <li><a href="/wiki/Circular_prime" title="Circular prime">Circular</a></li> <li><a href="/wiki/Truncatable_prime" title="Truncatable prime">Truncatable</a></li> <li><a href="/wiki/Minimal_prime_(recreational_mathematics)" title="Minimal prime (recreational mathematics)">Minimal</a></li> <li><a href="/wiki/Delicate_prime" title="Delicate prime">Delicate</a></li> <li><a href="/wiki/Primeval_number" title="Primeval number">Primeval</a></li> <li><a href="/wiki/Full_reptend_prime" title="Full reptend prime">Full reptend</a></li> <li><a href="/wiki/Unique_prime_number" class="mw-redirect" title="Unique prime number">Unique</a></li> <li><a href="/wiki/Happy_number#Happy_primes" title="Happy number">Happy</a></li> <li><a href="/wiki/Self_number" title="Self number">Self</a></li> <li><a href="/wiki/Smarandache%E2%80%93Wellin_prime" class="mw-redirect" title="Smarandache–Wellin prime">Smarandache–Wellin</a></li> <li><a href="/wiki/Strobogrammatic_prime" class="mw-redirect" title="Strobogrammatic prime">Strobogrammatic</a></li> <li><a href="/wiki/Dihedral_prime" title="Dihedral prime">Dihedral</a></li> <li><a href="/wiki/Tetradic_number" title="Tetradic number">Tetradic</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Patterns</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="k-tuples" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Prime_k-tuple" title="Prime k-tuple"><i>k</i>-tuples</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Twin_prime" title="Twin prime">Twin (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, <i>p</i> + 2</span>)</a></li> <li><a href="/wiki/Prime_triplet" title="Prime triplet">Triplet (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, <i>p</i> + 2 or <i>p</i> + 4, <i>p</i> + 6</span>)</a></li> <li><a href="/wiki/Prime_quadruplet" title="Prime quadruplet">Quadruplet (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, <i>p</i> + 2, <i>p</i> + 6, <i>p</i> + 8</span>)</a></li> <li><a href="/wiki/Cousin_prime" title="Cousin prime">Cousin (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, <i>p</i> + 4</span>)</a></li> <li><a href="/wiki/Sexy_prime" title="Sexy prime">Sexy (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, <i>p</i> + 6</span>)</a></li> <li><a href="/wiki/Primes_in_arithmetic_progression" title="Primes in arithmetic progression">Arithmetic progression (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i> + <i>a·n</i>, <i>n</i> = 0, 1, 2, 3, ...</span>)</a></li> <li><a href="/wiki/Balanced_prime" title="Balanced prime">Balanced (<span class="texhtml texhtml-big" style="font-size:110%;">consecutive <i>p</i> − <i>n</i>, <i>p</i>, <i>p</i> + <i>n</i></span>)</a></li></ul> </div></td></tr></tbody></table><div> <ul><li><a href="/wiki/Bi-twin_chain" title="Bi-twin chain">Bi-twin chain (<span class="texhtml texhtml-big" style="font-size:110%;"><i>n</i> ± 1, 2<i>n</i> ± 1, 4<i>n</i> ± 1, …</span>)</a></li> <li><a href="/wiki/Chen_prime" title="Chen prime">Chen</a></li> <li><a class="mw-selflink selflink">Sophie Germain/Safe (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, 2<i>p</i> + 1</span>)</a></li> <li><a href="/wiki/Cunningham_chain" title="Cunningham chain">Cunningham (<span class="texhtml texhtml-big" style="font-size:110%;"><i>p</i>, 2<i>p</i> ± 1, 4<i>p</i> ± 3, 8<i>p</i> ± 7, ...</span>)</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">By size</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <li><a href="/wiki/Megaprime" title="Megaprime">Mega (1,000,000+ digits)</a></li> <li><a href="/wiki/Largest_known_prime_number" title="Largest known prime number">Largest known</a> <ul><li><a href="/wiki/List_of_largest_known_primes_and_probable_primes" title="List of largest known primes and probable primes">list</a></li></ul></li> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Complex_number" title="Complex number">Complex numbers</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Eisenstein_prime" class="mw-redirect" title="Eisenstein prime">Eisenstein prime</a></li> <li><a href="/wiki/Gaussian_integer#Gaussian_primes" title="Gaussian integer">Gaussian prime</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Composite_number" title="Composite number">Composite numbers</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Pseudoprime" title="Pseudoprime">Pseudoprime</a> <ul><li><a href="/wiki/Catalan_pseudoprime" title="Catalan pseudoprime">Catalan</a></li> <li><a href="/wiki/Elliptic_pseudoprime" title="Elliptic pseudoprime">Elliptic</a></li> <li><a href="/wiki/Euler_pseudoprime" title="Euler pseudoprime">Euler</a></li> <li><a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi</a></li> <li><a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat</a></li> <li><a href="/wiki/Frobenius_pseudoprime" title="Frobenius pseudoprime">Frobenius</a></li> <li><a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas</a></li> <li><a href="/wiki/Perrin_pseudoprime" class="mw-redirect" title="Perrin pseudoprime">Perrin</a></li> <li><a href="/wiki/Somer%E2%80%93Lucas_pseudoprime" title="Somer–Lucas pseudoprime">Somer–Lucas</a></li> <li><a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">Strong</a></li></ul></li> <li><a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a></li> <li><a href="/wiki/Almost_prime" title="Almost prime">Almost prime</a></li> <li><a href="/wiki/Semiprime" title="Semiprime">Semiprime</a></li> <li><a href="/wiki/Sphenic_number" title="Sphenic number">Sphenic number</a></li> <li><a href="/wiki/Interprime" title="Interprime">Interprime</a></li> <li><a href="/wiki/Pernicious_number" title="Pernicious number">Pernicious</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Probable_prime" title="Probable prime">Probable prime</a></li> <li><a href="/wiki/Industrial-grade_prime" title="Industrial-grade prime">Industrial-grade prime</a></li> <li><a href="/wiki/Illegal_prime" class="mw-redirect" title="Illegal prime">Illegal prime</a></li> <li><a href="/wiki/Formula_for_primes" title="Formula for primes">Formula for primes</a></li> <li><a href="/wiki/Prime_gap" title="Prime gap">Prime gap</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">First 60 primes</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/2" title="2">2</a></li> <li><a href="/wiki/3" title="3">3</a></li> <li><a href="/wiki/5" title="5">5</a></li> <li><a href="/wiki/7" title="7">7</a></li> <li><a href="/wiki/11_(number)" title="11 (number)">11</a></li> <li><a href="/wiki/13_(number)" title="13 (number)">13</a></li> <li><a href="/wiki/17_(number)" title="17 (number)">17</a></li> <li><a href="/wiki/19_(number)" title="19 (number)">19</a></li> <li><a href="/wiki/23_(number)" title="23 (number)">23</a></li> <li><a href="/wiki/29_(number)" title="29 (number)">29</a></li> <li><a href="/wiki/31_(number)" title="31 (number)">31</a></li> <li><a href="/wiki/37_(number)" title="37 (number)">37</a></li> <li><a href="/wiki/41_(number)" title="41 (number)">41</a></li> <li><a href="/wiki/43_(number)" title="43 (number)">43</a></li> <li><a href="/wiki/47_(number)" title="47 (number)">47</a></li> <li><a href="/wiki/53_(number)" title="53 (number)">53</a></li> <li><a href="/wiki/59_(number)" title="59 (number)">59</a></li> <li><a href="/wiki/61_(number)" title="61 (number)">61</a></li> <li><a href="/wiki/67_(number)" title="67 (number)">67</a></li> <li><a href="/wiki/71_(number)" title="71 (number)">71</a></li> <li><a href="/wiki/73_(number)" title="73 (number)">73</a></li> <li><a href="/wiki/79_(number)" title="79 (number)">79</a></li> <li><a href="/wiki/83_(number)" title="83 (number)">83</a></li> <li><a href="/wiki/89_(number)" title="89 (number)">89</a></li> <li><a href="/wiki/97_(number)" title="97 (number)">97</a></li> <li><a href="/wiki/101_(number)" title="101 (number)">101</a></li> <li><a href="/wiki/103_(number)" title="103 (number)">103</a></li> <li><a href="/wiki/107_(number)" title="107 (number)">107</a></li> <li><a href="/wiki/109_(number)" title="109 (number)">109</a></li> <li><a href="/wiki/113_(number)" title="113 (number)">113</a></li> <li><a href="/wiki/127_(number)" title="127 (number)">127</a></li> <li><a href="/wiki/131_(number)" title="131 (number)">131</a></li> <li><a href="/wiki/137_(number)" title="137 (number)">137</a></li> <li><a href="/wiki/139_(number)" title="139 (number)">139</a></li> <li><a href="/wiki/149_(number)" title="149 (number)">149</a></li> <li><a href="/wiki/151_(number)" title="151 (number)">151</a></li> <li><a href="/wiki/157_(number)" title="157 (number)">157</a></li> <li><a href="/wiki/163_(number)" title="163 (number)">163</a></li> <li><a href="/wiki/167_(number)" title="167 (number)">167</a></li> <li><a href="/wiki/173_(number)" title="173 (number)">173</a></li> <li><a href="/wiki/179_(number)" title="179 (number)">179</a></li> <li><a href="/wiki/181_(number)" title="181 (number)">181</a></li> <li><a href="/wiki/191_(number)" title="191 (number)">191</a></li> <li><a href="/wiki/193_(number)" title="193 (number)">193</a></li> <li><a href="/wiki/197_(number)" title="197 (number)">197</a></li> <li><a href="/wiki/199_(number)" title="199 (number)">199</a></li> <li><a href="/wiki/211_(number)" title="211 (number)">211</a></li> <li><a href="/wiki/223_(number)" title="223 (number)">223</a></li> <li><a href="/wiki/227_(number)" title="227 (number)">227</a></li> <li><a href="/wiki/229_(number)" title="229 (number)">229</a></li> <li><a href="/wiki/233_(number)" title="233 (number)">233</a></li> <li><a href="/wiki/239_(number)" title="239 (number)">239</a></li> <li><a href="/wiki/241_(number)" title="241 (number)">241</a></li> <li><a href="/wiki/251_(number)" title="251 (number)">251</a></li> <li><a href="/wiki/257_(number)" title="257 (number)">257</a></li> <li><a href="/wiki/263_(number)" title="263 (number)">263</a></li> <li><a href="/wiki/269_(number)" title="269 (number)">269</a></li> <li><a href="/wiki/271_(number)" title="271 (number)">271</a></li> <li><a href="/wiki/277_(number)" title="277 (number)">277</a></li> <li><a href="/wiki/281_(number)" title="281 (number)">281</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div><a href="/wiki/List_of_prime_numbers" title="List of prime numbers">List of prime numbers</a></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Safe_and_Sophie_Germain_primes&oldid=1256361461">https://en.wikipedia.org/w/index.php?title=Safe_and_Sophie_Germain_primes&oldid=1256361461</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Classes_of_prime_numbers" title="Category:Classes of prime numbers">Classes of prime numbers</a></li><li><a href="/wiki/Category:Unsolved_problems_in_number_theory" title="Category:Unsolved problems in number theory">Unsolved problems in number theory</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_June_2020" title="Category:Articles with unsourced statements from June 2020">Articles with unsourced statements from June 2020</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 9 November 2024, at 15:39<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Safe_and_Sophie_Germain_primes&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-d8f47","wgBackendResponseTime":140,"wgPageParseReport":{"limitreport":{"cputime":"0.481","walltime":"0.626","ppvisitednodes":{"value":3874,"limit":1000000},"postexpandincludesize":{"value":98066,"limit":2097152},"templateargumentsize":{"value":5722,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":95668,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 483.966 1 -total"," 41.09% 198.862 2 Template:Reflist"," 28.62% 138.513 16 Template:Citation"," 24.15% 116.870 2 Template:Navbox"," 23.44% 113.461 1 Template:Prime_number_classes"," 13.39% 64.816 1 Template:Short_description"," 9.52% 46.069 1 Template:Cn"," 8.03% 38.841 1 Template:Fix"," 7.53% 36.457 2 Template:Pagetype"," 6.87% 33.271 35 Template:Math"]},"scribunto":{"limitreport-timeusage":{"value":"0.257","limit":"10.000"},"limitreport-memusage":{"value":5701447,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-2fxxf","timestamp":"20241124001149","ttl":85696,"transientcontent":true}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Safe and Sophie Germain primes","url":"https:\/\/en.wikipedia.org\/wiki\/Safe_and_Sophie_Germain_primes","sameAs":"http:\/\/www.wikidata.org\/entity\/Q105971314","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q105971314","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2002-09-22T08:55:41Z","dateModified":"2024-11-09T15:39:18Z","headline":"A prime pair (p, 2p+1)"}</script> </body> </html>