Quadratic sieve - Wikipedia

<!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>Quadratic sieve - 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":"ae2ec40a-60c2-4bb6-9297-5615ef2d89ac","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Quadratic_sieve","wgTitle":"Quadratic sieve","wgCurRevisionId":1251006964,"wgRevisionId":1251006964,"wgArticleId":582340,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Webarchive template wayback links","Integer factorization algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Quadratic_sieve","wgRelevantArticleId":582340,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"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":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1151850","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=["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","mmv.bootstrap","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="Quadratic sieve - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Quadratic_sieve"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Quadratic_sieve&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/Quadratic_sieve"> <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-Quadratic_sieve rootpage-Quadratic_sieve 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=Quadratic+sieve" 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=Quadratic+sieve" 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=Quadratic+sieve" 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=Quadratic+sieve" 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-Basic_aim" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Basic_aim"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Basic aim</span> </div> </a> <ul id="toc-Basic_aim-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_approach" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_approach"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>The approach</span> </div> </a> <ul id="toc-The_approach-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_algorithm" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>The algorithm</span> </div> </a> <ul id="toc-The_algorithm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-How_QS_optimizes_finding_congruences" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#How_QS_optimizes_finding_congruences"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>How QS optimizes finding congruences</span> </div> </a> <button aria-controls="toc-How_QS_optimizes_finding_congruences-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 How QS optimizes finding congruences subsection</span> </button> <ul id="toc-How_QS_optimizes_finding_congruences-sublist" class="vector-toc-list"> <li id="toc-Partial_relations_and_cycles" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Partial_relations_and_cycles"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Partial relations and cycles</span> </div> </a> <ul id="toc-Partial_relations_and_cycles-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Checking_smoothness_by_sieving" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Checking_smoothness_by_sieving"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Checking smoothness by sieving</span> </div> </a> <ul id="toc-Checking_smoothness_by_sieving-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Example_of_basic_sieve" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Example_of_basic_sieve"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Example of basic sieve</span> </div> </a> <button aria-controls="toc-Example_of_basic_sieve-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 Example of basic sieve subsection</span> </button> <ul id="toc-Example_of_basic_sieve-sublist" class="vector-toc-list"> <li id="toc-Data_collection" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Data_collection"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Data collection</span> </div> </a> <ul id="toc-Data_collection-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Matrix_processing" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Matrix_processing"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Matrix processing</span> </div> </a> <ul id="toc-Matrix_processing-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Multiple_polynomials" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Multiple_polynomials"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Multiple polynomials</span> </div> </a> <ul id="toc-Multiple_polynomials-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Large_primes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Large_primes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Large primes</span> </div> </a> <button aria-controls="toc-Large_primes-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 Large primes subsection</span> </button> <ul id="toc-Large_primes-sublist" class="vector-toc-list"> <li id="toc-One_large_prime" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#One_large_prime"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>One large prime</span> </div> </a> <ul id="toc-One_large_prime-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-More_large_primes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#More_large_primes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>More large primes</span> </div> </a> <ul id="toc-More_large_primes-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Parameters_from_realistic_example" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Parameters_from_realistic_example"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Parameters from realistic example</span> </div> </a> <ul id="toc-Parameters_from_realistic_example-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Factoring_records" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Factoring_records"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Factoring records</span> </div> </a> <ul id="toc-Factoring_records-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>Implementations</span> </div> </a> <ul id="toc-Implementations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>See also</span> </div> </a> <ul id="toc-See_also-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">12</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Other_external_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Other_external_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">13</span> <span>Other external links</span> </div> </a> <ul id="toc-Other_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">Quadratic sieve</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="Go to an article in another language. Available in 14 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-14" 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">14 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Quadratisches_Sieb" title="Quadratisches Sieb – German" lang="de" hreflang="de" data-title="Quadratisches Sieb" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Criba_cuadr%C3%A1tica" title="Criba cuadrática – Spanish" lang="es" hreflang="es" data-title="Criba cuadrática" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Crible_quadratique" title="Crible quadratique – French" lang="fr" hreflang="fr" data-title="Crible quadratique" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%B0%A8_%EC%B2%B4" title="이차 체 – Korean" lang="ko" hreflang="ko" data-title="이차 체" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Crivello_quadratico" title="Crivello quadratico – Italian" lang="it" hreflang="it" data-title="Crivello quadratico" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A0%D7%A4%D7%94_%D7%A8%D7%99%D7%91%D7%95%D7%A2%D7%99%D7%AA" title="נפה ריבועית – Hebrew" lang="he" hreflang="he" data-title="נפה ריבועית" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Kwadratische_zeef" title="Kwadratische zeef – Dutch" lang="nl" hreflang="nl" data-title="Kwadratische zeef" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E3%81%B5%E3%82%8B%E3%81%84%E6%B3%95" title="二次ふるい法 – Japanese" lang="ja" hreflang="ja" data-title="二次ふるい法" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Sito_kwadratowe" title="Sito kwadratowe – Polish" lang="pl" hreflang="pl" data-title="Sito kwadratowe" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D1%80%D0%B5%D1%88%D0%B5%D1%82%D0%B0" title="Метод квадратичного решета – Russian" lang="ru" hreflang="ru" data-title="Метод квадратичного решета" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Neli%C3%B6seula" title="Neliöseula – Finnish" lang="fi" hreflang="fi" data-title="Neliöseula" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B8%B0%E0%B9%81%E0%B8%81%E0%B8%A3%E0%B8%87%E0%B8%81%E0%B8%B3%E0%B8%A5%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%AD%E0%B8%87" title="ตะแกรงกำลังสอง – Thai" lang="th" hreflang="th" data-title="ตะแกรงกำลังสอง" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B8%D1%87%D0%BD%D0%B5_%D1%80%D0%B5%D1%88%D0%B5%D1%82%D0%BE" title="Квадратичне решето – Ukrainian" lang="uk" hreflang="uk" data-title="Квадратичне решето" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E7%AF%A9%E9%81%B8%E6%B3%95" title="二次篩選法 – Chinese" lang="zh" hreflang="zh" data-title="二次篩選法" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1151850#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit 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/Quadratic_sieve" 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:Quadratic_sieve" 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/Quadratic_sieve"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Quadratic_sieve&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=Quadratic_sieve&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/Quadratic_sieve"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Quadratic_sieve&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=Quadratic_sieve&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/Quadratic_sieve" 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/Quadratic_sieve" 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=Quadratic_sieve&oldid=1251006964" 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=Quadratic_sieve&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=Quadratic_sieve&id=1251006964&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%2FQuadratic_sieve"><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%2FQuadratic_sieve"><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=Quadratic_sieve&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=Quadratic_sieve&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/Q1151850" 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"></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">Integer factorization algorithm</div> <p>The <b>quadratic sieve</b> <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> (<b>QS</b>) is an <a href="/wiki/Integer_factorization" title="Integer factorization">integer factorization</a> algorithm and, in practice, the second-fastest method known (after the <a href="/wiki/General_number_field_sieve" title="General number field sieve">general number field sieve</a>). It is still the fastest for <a href="/wiki/Integer" title="Integer">integers</a> under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by <a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a> in 1981 as an improvement to <a href="/wiki/Richard_Schroeppel" title="Richard Schroeppel">Schroeppel</a>'s linear sieve.<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> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Basic_aim">Basic aim</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=1" title="Edit section: Basic aim"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The algorithm attempts to set up a <a href="/wiki/Congruence_of_squares" title="Congruence of squares">congruence of squares</a> <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modulo</a> <i>n</i> (the integer to be factorized), which often leads to a factorization of <i>n</i>. The algorithm works in two phases: the <i>data collection</i> phase, where it collects information that may lead to a congruence of squares; and the <i>data processing</i> phase, where it puts all the data it has collected into a <a href="/wiki/Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> and solves it to obtain a congruence of squares. The data collection phase can be easily <a href="/wiki/Parallel_computing" title="Parallel computing">parallelized</a> to many processors, but the data processing phase requires large amounts of memory, and is difficult to parallelize efficiently over many nodes or if the processing nodes do not each have enough memory to store the whole matrix. The <a href="/wiki/Block_Wiedemann_algorithm" title="Block Wiedemann algorithm">block Wiedemann algorithm</a> can be used in the case of a few systems each capable of holding the matrix. </p><p>The naive approach to finding a congruence of squares is to pick a random number, square it, divide by <i>n</i> and hope the least non-negative remainder is a <a href="/wiki/Square_number" title="Square number">perfect square</a>. For example, <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 80^{2}\equiv 441=21^{2}{\pmod {5959}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>80</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mn>441</mn> <mo>=</mo> <msup> <mn>21</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>5959</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ebbdfd17847388a1f5a3ab549fc3b0493d883c68" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.776ex; height:3.176ex;" alt="{\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}}"></span>. This approach finds a congruence of squares only rarely for large <i>n</i>, but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of <a href="/wiki/Fermat%27s_factorization_method" title="Fermat's factorization method">Fermat's factorization method</a>. </p><p>The quadratic sieve is a modification of <a href="/wiki/Dixon%27s_factorization_method" title="Dixon's factorization method">Dixon's factorization method</a>. The general running time required for the quadratic sieve (to factor an integer <i>n</i>) is conjectured to be </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 e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>ln</mi> <mo>⁡</mo> <mi>n</mi> <mi>ln</mi> <mo>⁡</mo> <mi>ln</mi> <mo>⁡</mo> <mi>n</mi> </msqrt> </mrow> </mrow> </msup> <mo>=</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow> <mo>[</mo> <mrow> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo>,</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de9c66895e8688090355168d06beb348643041be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.862ex; height:3.509ex;" alt="{\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}"></span></dd></dl> <p>in the <a href="/wiki/L-notation" title="L-notation">L-notation</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The constant <i>e</i> is the base of the natural logarithm. </p> <div class="mw-heading mw-heading2"><h2 id="The_approach">The approach</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=2" title="Edit section: The approach"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To factorize the integer <i>n</i>, <a href="/wiki/Fermat%27s_factorization_method" title="Fermat's factorization method">Fermat's method</a> entails a search for a single number <i>a</i>, <span class="texhtml"><i>n</i><sup>1/2</sup> < <i>a</i> < <i>n</i>−1</span>, such that the remainder of <i>a</i><sup>2</sup> divided by <i>n</i> is a square. But these <i>a</i> are hard to find. The quadratic sieve consists of computing the remainder of <i>a</i><sup>2</sup>/<i>n</i> for several <i>a</i>, then finding a subset of these whose product is a square. This will yield a congruence of squares. </p><p>For example, consider attempting to factor the number 1649. We have: <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 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>41</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mn>32</mn> <mo>,</mo> <msup> <mn>42</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mn>115</mn> <mo>,</mo> <msup> <mn>43</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mn>200</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>1649</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e63dd67c4e56efbcd54ce0cc8ae0c5e5f809d394" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.134ex; height:3.176ex;" alt="{\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}"></span>. None of the integers <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 32,115,200}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>32</mn> <mo>,</mo> <mn>115</mn> <mo>,</mo> <mn>200</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 32,115,200}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd59e4f7fb387faa90dc15aed5d037c4e57f73e9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.368ex; height:2.509ex;" alt="{\displaystyle 32,115,200}"></span> is a square, but the product <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 32\cdot 200=80^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>32</mn> <mo>⋅</mo> <mn>200</mn> <mo>=</mo> <msup> <mn>80</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 32\cdot 200=80^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6569ec2c24fa38dbaef05714cdef53c96f6f2a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.969ex; height:2.676ex;" alt="{\displaystyle 32\cdot 200=80^{2}}"></span> is a square. We also had </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 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>32</mn> <mo>⋅</mo> <mn>200</mn> <mo>≡</mo> <msup> <mn>41</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>43</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mo stretchy="false">(</mo> <mn>41</mn> <mo>⋅</mo> <mn>43</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>114</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>1649</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6751fa8b23f72b324df8367d084acabe2bcadc3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:53.292ex; height:3.176ex;" alt="{\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}"></span></dd></dl> <p>since <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 41\cdot 43\equiv 114{\pmod {1649}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>41</mn> <mo>⋅</mo> <mn>43</mn> <mo>≡</mo> <mn>114</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>1649</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 41\cdot 43\equiv 114{\pmod {1649}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de32296ef1d390c813a1a3e9abafcc24b04998fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.249ex; height:2.843ex;" alt="{\displaystyle 41\cdot 43\equiv 114{\pmod {1649}}}"></span>. The observation that <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 32\cdot 200=80^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>32</mn> <mo>⋅</mo> <mn>200</mn> <mo>=</mo> <msup> <mn>80</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 32\cdot 200=80^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6569ec2c24fa38dbaef05714cdef53c96f6f2a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.969ex; height:2.676ex;" alt="{\displaystyle 32\cdot 200=80^{2}}"></span> thus gives a <a href="/wiki/Congruence_of_squares" title="Congruence of squares">congruence of squares</a> </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 114^{2}\equiv 80^{2}{\pmod {1649}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>114</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>80</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>1649</mn> <mo stretchy="false">)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 114^{2}\equiv 80^{2}{\pmod {1649}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e2692fd96be6ca89287ed2a9c3bd1532282c768" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26ex; height:3.176ex;" alt="{\displaystyle 114^{2}\equiv 80^{2}{\pmod {1649}}.}"></span></dd></dl> <p>Hence <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 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>114</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <msup> <mn>80</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mo stretchy="false">(</mo> <mn>114</mn> <mo>+</mo> <mn>80</mn> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>114</mn> <mo>−</mo> <mn>80</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>194</mn> <mo>⋅</mo> <mn>34</mn> <mo>=</mo> <mi>k</mi> <mo>⋅</mo> <mn>1649</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc31662bb0f32ed3f36a2fd15a1eb5e7e66af401" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:57.691ex; height:3.176ex;" alt="{\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}"></span> for some integer <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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span>. We can then factor </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 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1649</mn> <mo>=</mo> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mn>194</mn> <mo>,</mo> <mn>1649</mn> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mn>34</mn> <mo>,</mo> <mn>1649</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>97</mn> <mo>⋅</mo> <mn>17</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f95b2631d8daab2946735d16bd9e39fc0f24976" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:46.628ex; height:2.843ex;" alt="{\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}"></span></dd></dl> <p>using the <a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean algorithm</a> to calculate the <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a>. </p><p>So the problem has now been reduced to: given a set of integers, find a subset whose product is a square. By the <a href="/wiki/Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">fundamental theorem of arithmetic</a>, any positive integer can be written uniquely as a product of <a href="/wiki/Prime_power" title="Prime power">prime powers</a>. We do this in a vector format; for example, the prime-power factorization of 504 is 2<sup>3</sup>3<sup>2</sup>5<sup>0</sup>7<sup>1</sup>, it is therefore represented by the exponent vector (3,2,0,1). Multiplying two integers then corresponds to adding their exponent vectors. A number is a square when its exponent vector is even in every coordinate. For example, the vectors (3,2,0,1) + (1,0,0,1) = (4,2,0,2), so (504)(14) is a square. Searching for a square requires knowledge only of the <a href="/wiki/Parity_(mathematics)" title="Parity (mathematics)">parity</a> of the numbers in the vectors, so it is sufficient to compute these vectors mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0). So given a set of (0,1)-vectors, we need to find a subset which adds to the <a href="/wiki/Zero_vector" class="mw-redirect" title="Zero vector">zero vector</a> mod 2. </p><p>This is a <a href="/wiki/Linear_algebra" title="Linear algebra">linear algebra</a> problem since the <a href="/wiki/Ring_(mathematics)" title="Ring (mathematics)">ring</a> <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 \mathbb {Z} /2\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /2\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b3bb21abe942aa9c0c63bae35a0c38905e1712c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.426ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /2\mathbb {Z} }"></span> can be regarded as the <a href="/wiki/Galois_field" class="mw-redirect" title="Galois field">Galois field</a> of order 2, that is we can divide by all non-zero numbers (there is only one, namely 1) when calculating modulo 2. It is a <a href="/wiki/Rank%E2%80%93nullity_theorem" title="Rank–nullity theorem">theorem of linear algebra</a> that with more vectors than each vector has entries, a <a href="/wiki/Linear_dependency" class="mw-redirect" title="Linear dependency">linear dependency</a> always exists. It can be found by <a href="/wiki/Gaussian_elimination" title="Gaussian elimination">Gaussian elimination</a>. However, simply squaring many random numbers mod <i>n</i> produces a very large number of different <a href="/wiki/Prime_number" title="Prime number">prime</a> factors, and thus very long vectors and a very large matrix. The trick is to look specifically for numbers <i>a</i> such that <i>a</i><sup>2</sup> mod <i>n</i> has only small prime factors (they are <a href="/wiki/Smooth_number" title="Smooth number">smooth numbers</a>). They are harder to find, but using only smooth numbers keeps the vectors and matrices smaller and more tractable. The quadratic sieve searches for smooth numbers using a technique called <a href="/wiki/Sieve_theory" title="Sieve theory">sieving</a>, discussed later, from which the algorithm takes its name. </p> <div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=3" title="Edit section: The algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To summarize, the basic quadratic sieve algorithm has these main steps: </p> <ol><li>Choose a <a href="/wiki/Smooth_number#Definition" title="Smooth number">smoothness bound</a> <i>B</i>. The number π(<i>B</i>), <a href="/wiki/Prime-counting_function" title="Prime-counting function">denoting the number of prime numbers</a> less than <i>B</i>, will control both the length of the vectors and the number of vectors needed.</li> <li>Use sieving to locate π(<i>B</i>) + 1 numbers <i>a<sub>i</sub></i> such that <i>b<sub>i</sub></i> = (<i>a<sub>i</sub></i><sup>2</sup> mod <i>n</i>) is <i>B</i>-smooth.</li> <li>Factor the <i>b<sub>i</sub></i> and generate exponent vectors mod 2 for each one.</li> <li>Use linear algebra to find a subset of these vectors which add to the zero vector. Multiply the corresponding <i>a<sub>i</sub> </i>together and give the result mod <i>n</i> the name <i>a</i>; similarly, multiply the <i>b<sub>i</sub></i> together which yields a <i>B</i>-smooth square <i>b</i><sup>2</sup>.</li> <li>We are now left with the equality <i>a</i><sup>2</sup> = <i>b</i><sup>2</sup> mod <i>n</i> from which we get two square roots of (<i>a</i><sup>2</sup> mod <i>n</i>), one by taking the square root in the integers of <i>b</i><sup>2</sup> namely <i>b</i>, and the other the <i>a</i> computed in step 4.</li> <li>We now have the desired identity: <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 (a+b)(a-b)\equiv 0{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>+</mo> <mi>b</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>a</mi> <mo>−</mo> <mi>b</mi> <mo stretchy="false">)</mo> <mo>≡</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a+b)(a-b)\equiv 0{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66f38693cb65c80fe80fccbc518bcad0e3b9ea8a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.094ex; height:2.843ex;" alt="{\displaystyle (a+b)(a-b)\equiv 0{\pmod {n}}}"></span>. Compute the GCD of <i>n</i> with the difference (or sum) of <i>a</i> and <i>b</i>. This produces a factor, although it may be a trivial factor (<i>n</i> or 1). If the factor is trivial, try again with a different linear dependency or different <i>a</i>.</li></ol> <p>The remainder of this article explains details and extensions of this basic algorithm. </p> <div class="mw-heading mw-heading2"><h2 id="How_QS_optimizes_finding_congruences">How QS optimizes finding congruences</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=4" title="Edit section: How QS optimizes finding congruences"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The quadratic sieve attempts to find pairs of integers <i>x</i> and <i>y</i>(<i>x</i>) (where <i>y</i>(<i>x</i>) is a function of <i>x</i>) satisfying a much weaker condition than <i>x</i><sup>2</sup> ≡ <i>y</i><sup>2</sup> (mod <i>n</i>). It selects a set of <a href="/wiki/Prime_number" title="Prime number">primes</a> called the <i>factor base</i>, and attempts to find <i>x</i> such that the least absolute remainder of <i>y</i>(<i>x</i>) = <i>x</i><sup>2</sup> mod <i>n</i> factorizes completely over the factor base. Such <i>y</i> values are said to be <i>smooth</i> with respect to the factor base. </p><p>The factorization of a value of <i>y</i>(<i>x</i>) that splits over the factor base, together with the value of <i>x</i>, is known as a <i>relation</i>. The quadratic sieve speeds up the process of finding relations by taking <i>x</i> close to the square root of <i>n</i>. This ensures that <i>y</i>(<i>x</i>) will be smaller, and thus have a greater chance of being smooth. </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 y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mrow> <mo>(</mo> <mrow> <mrow> <mo>⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>n</mi> </msqrt> </mrow> <mo>⌉</mo> </mrow> <mo>+</mo> <mi>x</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mtext> (where </mtext> </mstyle> </mrow> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mtext> is a small integer)</mtext> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/632dfd1a2f52697f1e14bf435872a794b111db37" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:51.644ex; height:3.509ex;" alt="{\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}}"></span></dd> <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 y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>≈</mo> <mn>2</mn> <mi>x</mi> <mrow> <mo>⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>n</mi> </msqrt> </mrow> <mo>⌉</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/79f4cc3376722f4d5c893fbb598b20a99cf788e9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.668ex; height:3.009ex;" alt="{\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }"></span></dd></dl> <p>This implies that <i>y</i> is on the order of 2<i>x</i>[<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span>]. However, it also implies that <i>y</i> grows linearly with <i>x</i> times the square root of <i>n</i>. </p><p>Another way to increase the chance of smoothness is by simply increasing the size of the factor base. However, it is necessary to find at least one smooth relation more than the number of primes in the factor base, to ensure the existence of a linear dependency. </p> <div class="mw-heading mw-heading3"><h3 id="Partial_relations_and_cycles">Partial relations and cycles</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=5" title="Edit section: Partial relations and cycles"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Even if for some relation <i>y</i>(<i>x</i>) is not smooth, it may be possible to merge two of these <i>partial relations</i> to form a full one, if the two <i>y</i><span class="nowrap" style="padding-left:0.1em;">'</span>s are products of the same prime(s) outside the factor base. [Note that this is equivalent to extending the factor base.] For example, if the factor base is {2, 3, 5, 7} and <i>n</i> = 91, there are partial relations: </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 {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>21</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>7</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <mn>11</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>91</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4945314e1b687c2cb854e78aa3bdcd8714eda652" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.707ex; height:3.176ex;" alt="{\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}"></span></dd> <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 {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>29</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <mn>11</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>91</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60366629b303543620f02d01bba00b6c7b5d92db" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.707ex; height:3.176ex;" alt="{\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}"></span></dd></dl> <p>Multiply these together: </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 {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mn>21</mn> <mo>⋅</mo> <mn>29</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>7</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>11</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>91</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e24ff6dd4fb6b007c982f68a01d3bb5486432b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.471ex; height:3.176ex;" alt="{\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}"></span></dd></dl> <p>and multiply both sides by (11<sup>−1</sup>)<sup>2</sup> modulo 91. 11<sup>−1</sup> modulo 91 is 58, so: </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 (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>58</mn> <mo>⋅</mo> <mn>21</mn> <mo>⋅</mo> <mn>29</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>7</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>91</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d82336e536569e9f59e0a8f6b7aa1569ccb3a3c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.416ex; height:3.176ex;" alt="{\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}"></span></dd> <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 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>14</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>7</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>91</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c4006fa578174039c98d685793a27fd32a84caa8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.599ex; height:3.176ex;" alt="{\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}"></span></dd></dl> <p>producing a full relation. Such a full relation (obtained by combining partial relations) is called a <i>cycle</i>. Sometimes, forming a cycle from two partial relations leads directly to a congruence of squares, but rarely. </p> <div class="mw-heading mw-heading3"><h3 id="Checking_smoothness_by_sieving">Checking smoothness by sieving</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=6" title="Edit section: Checking smoothness by sieving"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are several ways to check for smoothness of the <i>y</i>s. The most obvious is by <a href="/wiki/Trial_division" title="Trial division">trial division</a>, although this increases the running time for the data collection phase. Another method that has some acceptance is the <a href="/wiki/Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">elliptic curve method</a> (ECM). In practice, a process called <i>sieving</i> is typically used. If <i>f</i>(<i>x</i>) is the <a href="/wiki/Polynomial" title="Polynomial">polynomial</a> <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 f(x)=x^{2}-n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)=x^{2}-n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f0f36aa75aa42e0f1a2d9c1b419a702253fe7593" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.135ex; height:3.176ex;" alt="{\displaystyle f(x)=x^{2}-n}"></span> we have </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 {\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mi>k</mi> <mi>p</mi> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mi>k</mi> <mi>p</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>2</mn> <mi>x</mi> <mi>k</mi> <mi>p</mi> <mo>+</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mi>p</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>2</mn> <mi>x</mi> <mi>k</mi> <mi>p</mi> <mo>+</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mi>p</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bdb3c4d11bcee3d433a89cb18526db1ab97a4c92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; margin-top: -0.271ex; width:52.073ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}}"></span></dd></dl> <p>Thus solving <i>f(x)</i> ≡ 0 (mod <i>p</i>) for <i>x</i> generates a whole sequence of numbers <i>y</i> for which <i>y</i>=<i>f</i>(<i>x</i>), all of which are divisible by <i>p</i>. This is finding a square root modulo a prime, for which there exist efficient algorithms, such as the <a href="/wiki/Shanks%E2%80%93Tonelli_algorithm" class="mw-redirect" title="Shanks–Tonelli algorithm">Shanks–Tonelli algorithm</a>. (This is where the quadratic sieve gets its name: <i>y</i> is a quadratic polynomial in <i>x</i>, and the sieving process works like the <a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a>.) </p><p>The sieve starts by setting every entry in a large array <i>A</i>[] of bytes to zero. For each <i>p</i>, solve the quadratic equation mod <i>p</i> to get two roots <i>α</i> and <i>β</i>, and then add an approximation to log(<i>p</i>) to every entry for which <i>y</i>(<i>x</i>) = 0 mod <i>p</i> ... that is, <i>A</i>[<i>kp</i> + <i>α</i>] and <i>A</i>[<i>kp</i> + <i>β</i>]. It is also necessary to solve the quadratic equation modulo small powers of <i>p</i> in order to recognise numbers divisible by small powers of a factor-base prime. </p><p>At the end of the factor base, any <i>A</i>[] containing a value above a threshold of roughly log(<i>x</i><sup>2</sup>−<i>n</i>) will correspond to a value of <i>y</i>(<i>x</i>) which splits over the factor base. The information about exactly which primes divide <i>y</i>(<i>x</i>) has been lost, but it has only small factors, and there are many good algorithms for factoring a number known to have only small factors, such as trial division by small primes, <a href="/wiki/SQUFOF" class="mw-redirect" title="SQUFOF">SQUFOF</a>, <a href="/wiki/Pollard_rho" class="mw-redirect" title="Pollard rho">Pollard rho</a>, and ECM, which are usually used in some combination. </p><p>There are many <i>y</i>(<i>x</i>) values that work, so the factorization process at the end doesn't have to be entirely reliable; often the processes misbehave on say 5% of inputs, requiring a small amount of extra sieving. </p> <div class="mw-heading mw-heading2"><h2 id="Example_of_basic_sieve">Example of basic sieve</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=7" title="Edit section: Example of basic sieve"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This example will demonstrate standard quadratic sieve without logarithm optimizations or prime powers. Let the number to be factored <i>N</i> = 15347, therefore the ceiling of the square root of <i>N</i> is 124. Since <i>N</i> is small, the basic polynomial is enough: <i>y</i>(<i>x</i>) = (<i>x</i> + 124)<sup>2</sup> − 15347. </p> <div class="mw-heading mw-heading3"><h3 id="Data_collection">Data collection</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=8" title="Edit section: Data collection"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since <i>N</i> is small, only four primes are necessary. The first four primes <i>p</i> for which 15347 has a square root mod <i>p</i> are 2, 17, 23, and 29 (in other words, 15347 is a <a href="/wiki/Quadratic_residue" title="Quadratic residue">quadratic residue</a> modulo each of these primes). These primes will be the basis for sieving. </p><p>Now we construct our sieve <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 V_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b6aec7566ccba7a946eca2221504813eb0408903" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.988ex; height:2.509ex;" alt="{\displaystyle V_{X}}"></span> of <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 Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>X</mi> <mo>+</mo> <mo fence="false" stretchy="false">⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mo fence="false" stretchy="false">⌉</mo> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>N</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>X</mi> <mo>+</mo> <mn>124</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>15347</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/472b481ae9f450532546c766ca18003833d82c08" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:50.236ex; height:3.176ex;" alt="{\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}"></span> and begin the sieving process for each prime in the basis, choosing to sieve the first 0 ≤ X < 100 of Y(X): </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 {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>V</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>4</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo stretchy="false">)</mo> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <mi>Y</mi> <mo stretchy="false">(</mo> <mn>99</mn> <mo stretchy="false">)</mo> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>29</mn> </mtd> <mtd> <mn>278</mn> </mtd> <mtd> <mn>529</mn> </mtd> <mtd> <mn>782</mn> </mtd> <mtd> <mn>1037</mn> </mtd> <mtd> <mn>1294</mn> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <mn>34382</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/852edfc776f0eb4c57993f15906fc4f79e2abc22" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:61.041ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}"></span></dd></dl> <p>The next step is to perform the sieve. For each <i>p</i> in our factor base <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 \lbrace 2,17,23,29\rbrace }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>2</mn> <mo>,</mo> <mn>17</mn> <mo>,</mo> <mn>23</mn> <mo>,</mo> <mn>29</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lbrace 2,17,23,29\rbrace }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2017d207e413764ae245056371fd4c7d2a2cb230" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.564ex; height:2.843ex;" alt="{\displaystyle \lbrace 2,17,23,29\rbrace }"></span> solve the equation </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 Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo>≡</mo> <mo stretchy="false">(</mo> <mi>X</mi> <mo>+</mo> <mo fence="false" stretchy="false">⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mo fence="false" stretchy="false">⌉</mo> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>N</mi> <mo>≡</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/217d1f6b64ce0eb5cbdd39046b509281cb76f8bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.428ex; height:3.176ex;" alt="{\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}"></span></dd></dl> <p>to find the entries in the array <i>V</i> which are divisible by <i>p</i>. </p><p>For <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 p=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d62e4100b94c1939c67f2d4b8580d26c78106c44" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.52ex; height:2.509ex;" alt="{\displaystyle p=2}"></span> solve <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+124)^{2}-15347\equiv 0{\pmod {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>X</mi> <mo>+</mo> <mn>124</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>15347</mn> <mo>≡</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9083674414ddbb62c8b73269df7451f6fa7e1de9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.931ex; height:3.176ex;" alt="{\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}"></span> to get the solution <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\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>15347</mn> </msqrt> </mrow> <mo>−</mo> <mn>124</mn> <mo>≡</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea75a78d2b7e674bc6ef3fd67941e41ffd91bf7c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.262ex; height:3.176ex;" alt="{\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}"></span>. </p><p>Thus, starting at X=1 and incrementing by 2, each entry will be divisible by 2. Dividing each of those entries by 2 yields </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 V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>29</mn> </mtd> <mtd> <mn>139</mn> </mtd> <mtd> <mn>529</mn> </mtd> <mtd> <mn>391</mn> </mtd> <mtd> <mn>1037</mn> </mtd> <mtd> <mn>647</mn> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <mn>17191</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81205e1cc19f8663dcfdb8a59a5e0bae9370498b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.649ex; height:2.843ex;" alt="{\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}"></span></dd></dl> <p>Similarly for the remaining primes <i>p</i> in <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 \lbrace 17,23,29\rbrace }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>17</mn> <mo>,</mo> <mn>23</mn> <mo>,</mo> <mn>29</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lbrace 17,23,29\rbrace }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/012f7e98e9d25780081d5d6081bd9960e28961eb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.368ex; height:2.843ex;" alt="{\displaystyle \lbrace 17,23,29\rbrace }"></span> the equation<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\equiv {\sqrt {15347}}-124{\pmod {p}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>15347</mn> </msqrt> </mrow> <mo>−</mo> <mn>124</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\equiv {\sqrt {15347}}-124{\pmod {p}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5e0da79c194aa2e4eb826a66aa097365f028a34f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.008ex; height:3.176ex;" alt="{\displaystyle X\equiv {\sqrt {15347}}-124{\pmod {p}}}"></span> is solved. Note that for every <i>p</i> > 2, there will be 2 resulting linear equations due to there being 2 modular square roots. </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 {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>X</mi> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>15347</mn> </msqrt> </mrow> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mo>≡</mo> <mn>8</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>3</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>17</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd /> <mtd> <mo>≡</mo> <mn>9</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>4</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>17</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>X</mi> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>15347</mn> </msqrt> </mrow> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mo>≡</mo> <mn>11</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>23</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd /> <mtd> <mo>≡</mo> <mn>12</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>3</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>23</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>X</mi> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>15347</mn> </msqrt> </mrow> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mo>≡</mo> <mn>8</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>29</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd /> <mtd> <mo>≡</mo> <mn>21</mn> <mo>−</mo> <mn>124</mn> </mtd> <mtd> <mi></mi> <mo>≡</mo> <mn>13</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>29</mn> <mo stretchy="false">)</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ebf6d263ea774a9e888c2fe3573891df264744d8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.005ex; width:53.089ex; height:19.176ex;" alt="{\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}"></span></dd></dl> <p>Each equation <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\equiv a{\pmod {p}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>≡</mo> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\equiv a{\pmod {p}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c6fc19f64301cd76de47b15910746a92f4502ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.162ex; height:2.843ex;" alt="{\displaystyle X\equiv a{\pmod {p}}}"></span> results in <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 V_{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a88cf63328bf1143403e78dea7b56fc71cb22cbe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.528ex; height:2.509ex;" alt="{\displaystyle V_{x}}"></span> being divisible by <i>p</i> at <i>x</i>=<i>a</i> and each <i>p</i>th value beyond that. Dividing <i>V</i> by <i>p</i> at <i>a</i>, <i>a</i>+<i>p</i>, <i>a</i>+2<i>p</i>, <i>a</i>+3<i>p</i>, etc., for each prime in the basis finds the smooth numbers which are products of unique primes (first powers). </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 V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>139</mn> </mtd> <mtd> <mn>23</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>61</mn> </mtd> <mtd> <mn>647</mn> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <mn>17191</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1c00003b08b0f44d2cf916ef6283957aea516818" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.674ex; height:2.843ex;" alt="{\displaystyle V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}"></span></dd></dl> <p>Any entry of <i>V</i> that equals 1 corresponds to a smooth number. Since <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 V_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ae15ff9b845587dc4e1816f59c3fed0e71a132f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{0}}"></span>, <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 V_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e240a0a3bcd3a6d628a5b796501771dff86ca493" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{3}}"></span>, and <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 V_{71}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>71</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{71}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43c44cc549270d066a800a98d5950b6d56294a1c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.231ex; height:2.509ex;" alt="{\displaystyle V_{71}}"></span> equal one, this corresponds to: </p> <table class="wikitable"> <tbody><tr> <th><i>X</i> + 124</th> <th><i>Y</i></th> <th>factors </th></tr> <tr> <td>124 </td> <td>29 </td> <td>2<sup>0</sup> • 17<sup>0</sup> • 23<sup>0</sup> • 29<sup>1</sup> </td></tr> <tr> <td>127 </td> <td>782 </td> <td>2<sup>1</sup> • 17<sup>1</sup> • 23<sup>1</sup> • 29<sup>0</sup> </td></tr> <tr> <td>195 </td> <td>22678 </td> <td>2<sup>1</sup> • 17<sup>1</sup> • 23<sup>1</sup> • 29<sup>1</sup> </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Matrix_processing">Matrix processing</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=9" title="Edit section: Matrix processing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since smooth numbers <i>Y</i> have been found with the property <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 Y\equiv Z^{2}{\pmod {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo>≡</mo> <msup> <mi>Z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y\equiv Z^{2}{\pmod {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/42ae23d6432349118b288c868bd0214a41de7f9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.382ex; height:3.176ex;" alt="{\displaystyle Y\equiv Z^{2}{\pmod {N}}}"></span>, the remainder of the algorithm follows equivalently to any other variation of <a href="/wiki/Dixon%27s_factorization_method" title="Dixon's factorization method">Dixon's factorization method</a>. </p><p>Writing the exponents of the product of a subset of the equations </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 {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mn>29</mn> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>17</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>23</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>29</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mn>782</mn> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>17</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>23</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>29</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mn>22678</mn> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>17</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>23</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>29</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3a0fce17db113417cdc6b896c84a9c104b667f8c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:27.054ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}"></span></dd></dl> <p>as a matrix<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 {\pmod {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\pmod {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f8d8091637b9907fbf714aa5bc07272e9ca8620c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.846ex; height:2.843ex;" alt="{\displaystyle {\pmod {2}}}"></span> yields: </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 S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>⋅</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mo>≡</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1fb09366d76fecee7b4011360fcaecda0ebeadaf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:46.256ex; height:9.176ex;" alt="{\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}"></span></dd></dl> <p>A solution to the equation is given by the <a href="/wiki/Left_null_space#Left_null_space" class="mw-redirect" title="Left null space">left null space</a>, simply </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 S={\begin{bmatrix}1&1&1\end{bmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d8f0bbfa73185cfe07a0e8e93b5c7b8c2de8e45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.775ex; height:2.843ex;" alt="{\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}"></span></dd></dl> <p>Thus the product of all three equations yields a square (mod N). </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 29\cdot 782\cdot 22678=22678^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>29</mn> <mo>⋅</mo> <mn>782</mn> <mo>⋅</mo> <mn>22678</mn> <mo>=</mo> <msup> <mn>22678</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 29\cdot 782\cdot 22678=22678^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/355134e9fa35aa23f53251f1684358cbae981edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:24.948ex; height:2.676ex;" alt="{\displaystyle 29\cdot 782\cdot 22678=22678^{2}}"></span></dd></dl> <p>and </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 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>124</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>127</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <msup> <mn>195</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <msup> <mn>3070860</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29dea8ed4112836d1f194d5bae80583c234836b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:29.273ex; height:2.676ex;" alt="{\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}"></span></dd></dl> <p>So the algorithm found </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 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>22678</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <msup> <mn>3070860</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>15347</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/69c1c71b3ab464fff4d52b7f33990922cd3593aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.653ex; height:3.176ex;" alt="{\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}"></span></dd></dl> <p>Testing the result yields GCD(3070860 - 22678, 15347) = 103, a nontrivial factor of 15347, the other being 149. </p><p>This demonstration should also serve to show that the quadratic sieve is only appropriate when <i>n</i> is large. For a number as small as 15347, this algorithm is overkill. <a href="/wiki/Trial_division" title="Trial division">Trial division</a> or <a href="/wiki/Pollard_rho" class="mw-redirect" title="Pollard rho">Pollard rho</a> could have found a factor with much less computation. </p> <div class="mw-heading mw-heading2"><h2 id="Multiple_polynomials">Multiple polynomials</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=10" title="Edit section: Multiple polynomials"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In practice, many different <a href="/wiki/Polynomial" title="Polynomial">polynomials</a> are used for <i>y</i> so that when <i>y</i>(<i>x</i>) starts to become large, resulting in poor density of smooth <i>y</i>, this growth can be reset by switching polynomials. As usual, we choose <i>y</i>(<i>x</i>) to be a square modulo <i>n</i>, but now with the form </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>A</mi> <mi>x</mi> <mo>+</mo> <mi>B</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> <mspace width="2em" /> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4e4ba768745e0ea2727ce7ddf52564b2106f79e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.393ex; height:3.176ex;" alt="{\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .}"></span> </p><p><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 B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> is chosen such that <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 B^{2}=n{\pmod {A}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>A</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B^{2}=n{\pmod {A}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a4a724f0c002d25396b889ad311d414cf1ee89e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.739ex; height:3.176ex;" alt="{\displaystyle B^{2}=n{\pmod {A}}}"></span>, so <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 B^{2}-n=AC}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> <mo>=</mo> <mi>A</mi> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B^{2}-n=AC}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e74ac462e8dc5d134010efa0635ffbb4396799c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.661ex; height:2.843ex;" alt="{\displaystyle B^{2}-n=AC}"></span> for some <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span>. The polynomial y(x) can then be written as <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 y(x)=A\cdot (Ax^{2}+2Bx+C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>A</mi> <mo>⋅</mo> <mo stretchy="false">(</mo> <mi>A</mi> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>2</mn> <mi>B</mi> <mi>x</mi> <mo>+</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/72652c613f59097f53f067b4474b5823f4b74db1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.455ex; height:3.176ex;" alt="{\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}"></span>. If <i>A</i> is a square or a smooth number, then only the factor <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 (Ax^{2}+2Bx+C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>A</mi> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>2</mn> <mi>B</mi> <mi>x</mi> <mo>+</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (Ax^{2}+2Bx+C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d7378301fa352df5cfa34a5fb63ea651ac9437e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.64ex; height:3.176ex;" alt="{\displaystyle (Ax^{2}+2Bx+C)}"></span> has to be checked for smoothness. </p><p>This approach, called Multiple Polynomial Quadratic Sieve (MPQS), is ideally suited for <a href="/wiki/Parallel_algorithm" title="Parallel algorithm">parallelization</a>, since each <a href="/wiki/Central_processing_unit" title="Central processing unit">processor</a> involved in the factorization can be given <i>n</i>, the factor base and a collection of polynomials, and it will have no need to communicate with the central processor until it has finished sieving with its polynomials. </p> <div class="mw-heading mw-heading2"><h2 id="Large_primes">Large primes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=11" title="Edit section: Large primes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="One_large_prime">One large prime</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=12" title="Edit section: One large prime"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If, after dividing by all the factors less than <i>A</i>, the remaining part of the number (the cofactor) is less than <i>A</i><sup>2</sup>, then this cofactor must be prime. In effect, it can be added to the factor base, by sorting the list of relations into order by cofactor. If y(a) = 7*11*23*137 and y(b) = 3*5*7*137, then y(a)y(b) = 3*5*11*23 * 7<sup>2</sup> * 137<sup>2</sup>. This works by reducing the threshold of entries in the sieving array above which a full factorization is performed. </p> <div class="mw-heading mw-heading3"><h3 id="More_large_primes">More large primes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=13" title="Edit section: More large primes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Reducing the threshold even further, and using an effective process for factoring y(x) values into products of even relatively large primes - ECM is superb for this - can find relations with most of their factors in the factor base, but with two or even three larger primes. Cycle finding then allows combining a set of relations sharing several primes into a single relation. </p> <div class="mw-heading mw-heading2"><h2 id="Parameters_from_realistic_example">Parameters from realistic example</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=14" title="Edit section: Parameters from realistic example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To illustrate typical parameter choices for a realistic example on a real implementation including the multiple polynomial and large prime optimizations, the tool <a rel="nofollow" class="external text" href="http://sourceforge.net/projects/msieve/">msieve</a> was run on a 267-bit <a href="/wiki/Semiprime" title="Semiprime">semiprime</a>, producing the following parameters: </p> <ul><li>Trial factoring cutoff: 27 bits</li> <li>Sieve interval (per polynomial): 393216 (12 blocks of size 32768)</li> <li>Smoothness bound: 1300967 (50294 primes)</li> <li>Number of factors for polynomial <i>A</i> coefficients: 10 <i>(see <a href="#Multiple_polynomials">Multiple polynomials</a> above)</i></li> <li>Large prime bound: 128795733 (26 bits) <i>(see <a href="#Large_primes">Large primes</a> above)</i></li> <li>Smooth values found: 25952 by sieving directly, 24462 by combining numbers with large primes</li> <li>Final matrix size: 50294 × 50414, reduced by filtering to 35750 × 35862</li> <li>Nontrivial dependencies found: 15</li> <li>Total time (on a 1.6 GHz UltraSPARC III): 35 min 39 seconds</li> <li>Maximum memory used: 8 MB</li></ul> <div class="mw-heading mw-heading2"><h2 id="Factoring_records">Factoring records</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=15" title="Edit section: Factoring records"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Until the discovery of the <a href="/wiki/General_number_field_sieve" title="General number field sieve">number field sieve</a> (NFS), QS was the asymptotically fastest known general-purpose factoring algorithm. Now, <a href="/wiki/Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">Lenstra elliptic curve factorization</a> has the same asymptotic running time as QS (in the case where <i>n</i> has exactly two prime factors of equal size), but in practice, QS is faster since it uses <a href="/wiki/Single-precision" class="mw-redirect" title="Single-precision">single-precision</a> operations instead of the <a href="/wiki/Multi-precision" class="mw-redirect" title="Multi-precision">multi-precision</a> operations used by the elliptic curve method. </p><p>On April 2, 1994, the factorization of <a href="/wiki/RSA-129" class="mw-redirect" title="RSA-129">RSA-129</a> was completed using QS. It was a 129-digit number, the product of two large primes, one of 64 digits and the other of 65 digits. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 <a href="/w/index.php?title=MIPS-year&action=edit&redlink=1" class="new" title="MIPS-year (page does not exist)">MIPS-years</a>, done in distributed fashion over the Internet. The data collected totaled 2<a href="/wiki/Gigabyte" title="Gigabyte">GB</a>. The data processing phase took 45 hours on <a href="/wiki/Bellcore" class="mw-redirect" title="Bellcore">Bellcore</a>'s (now <a href="/wiki/Telcordia_Technologies" class="mw-redirect" title="Telcordia Technologies">Telcordia Technologies</a>) <a href="/wiki/MasPar" title="MasPar">MasPar</a> (massively parallel) supercomputer. This was the largest published factorization by a general-purpose algorithm, until NFS was used to factor <a href="/wiki/RSA-130" class="mw-redirect" title="RSA-130">RSA-130</a>, completed April 10, 1996. All <a href="/wiki/RSA_number" class="mw-redirect" title="RSA number">RSA numbers</a> factored since then have been factored using NFS. </p><p>The current QS factorization record is the 140-digit (463-bit) RSA-140, which was factored by Patrick Konsor in June 2020 using approximately 6,000 core hours over 6 days.<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> </p> <div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=16" title="Edit section: Implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://www.asahi-net.or.jp/~KC2H-MSM/cn">PPMPQS and PPSIQS</a></li> <li><a rel="nofollow" class="external text" href="http://gforge.inria.fr/projects/mpqs/">mpqs</a></li> <li><a rel="nofollow" class="external text" href="http://www.friedspace.com/QS/">SIMPQS</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200506164219/http://www.friedspace.com/QS/">Archived</a> 2020-05-06 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> is a fast implementation of the self-initialising multiple polynomial quadratic sieve written by William Hart. It provides support for the large prime variant and uses Jason Papadopoulos' <a href="/wiki/Block_Lanczos_algorithm" title="Block Lanczos algorithm">block Lanczos</a> implementation for the linear algebra stage. SIMPQS is accessible as the qsieve command in the <a href="/wiki/SageMath" title="SageMath">SageMath</a> computer algebra package, is part of the <a href="/wiki/Fast_Library_for_Number_Theory" title="Fast Library for Number Theory">Fast Library for Number Theory</a>, or can be downloaded in source form. SIMPQS is optimized for use on Athlon and Opteron machines, but will operate on most common 32- and 64-bit architectures. It is written entirely in C.</li> <li>a <a rel="nofollow" class="external text" href="https://www.alpertron.com.ar/ECM.HTM">factoring applet</a> by Dario Alpern, that uses the quadratic sieve if certain conditions are met.</li> <li>The <a href="/wiki/PARI/GP" title="PARI/GP">PARI/GP</a> computer algebra package includes an implementation of the self-initialising multiple polynomial quadratic sieve implementing the large prime variant. It was adapted by Thomas Papanikolaou and Xavier Roblot from a sieve written for the LiDIA project. The self-initialisation scheme is based on an idea from the thesis of Thomas Sosnowski.</li> <li>A variant of the quadratic sieve is available in the <a href="/wiki/Magma_computer_algebra_system" class="mw-redirect" title="Magma computer algebra system">MAGMA</a> computer algebra package. It is based on an implementation of Arjen Lenstra from 1995, used in his "factoring by email" program.</li> <li><a rel="nofollow" class="external text" href="http://sourceforge.net/projects/msieve/">msieve</a>, an implementation of the multiple polynomial quadratic sieve with support for single and double large primes, written by Jason Papadopoulos. Source code and a Windows binary are available.</li> <li><a rel="nofollow" class="external text" href="https://github.com/bbuhrow/yafu">YAFU</a>, written by Ben Buhrow, is probably the fastest available implementation of the quadratic sieve. For example, <a href="/wiki/RSA-100" class="mw-redirect" title="RSA-100">RSA-100</a> was factored in less than 15 minutes on four cores of a 2.5 GHz Xeon 6248 CPU. All of the critical subroutines make use of <a href="/wiki/AVX2" class="mw-redirect" title="AVX2">AVX2</a> or <a href="/wiki/AVX-512" title="AVX-512">AVX-512</a> <a href="/wiki/SIMD" class="mw-redirect" title="SIMD">SIMD</a> instructions for AMD or Intel processors. It uses Jason Papadopoulos' block Lanczos code. Source code and binaries for Windows and Linux are available.</li> <li><a rel="nofollow" class="external text" href="http://sourceforge.net/projects/arielqs/">Ariel</a>, a simple Java implementation of the quadratic sieve for didactic purposes.</li> <li>The <a rel="nofollow" class="external text" href="https://github.com/TilmanNeumann/java-math-library">java-math-library</a> contains probably the fastest quadratic sieve written in Java (the successor of PSIQS 4.0).</li> <li><a rel="nofollow" class="external text" href="https://github.com/gazman-sdk/quadratic-sieve">Java QS</a>, an open source Java project containing basic implementation of QS. Released at February 4, 2016 by Ilya Gazman</li> <li><a rel="nofollow" class="external text" href="https://github.com/michel-leonard/C-Quadratic-Sieve">C Quadratic Sieve</a>, a factorizer written entirely in C containing implementation of self-initialising Quadratic Sieve. The project is inspired by a William Hart's FLINT factorizer. The source released in 2022 by Michel Leonard does not rely on external library, it is capable of factoring 240-bit numbers in a minute and 300-bit numbers in 2 hours.</li> <li>The <a rel="nofollow" class="external text" href="https://cran.r-project.org/package=RcppBigIntAlgos">RcppBigIntAlgos</a> package by Joseph Wood, provides an efficient implementation of the multiple polynomial quadratic sieve for the <a href="/wiki/R_(programming_language)" title="R (programming language)">R programming language</a>. It is written in C++ and is capable of comfortably factoring 100-digit <a href="/wiki/Semiprime" title="Semiprime">semiprimes</a>. For example, a 300-bit semiprime (91 digits) was factored in 1 hour and the <a href="/wiki/RSA-100" class="mw-redirect" title="RSA-100">RSA-100</a> was factored in under 10 hours on a MacBook Air with an Apple M2 processor.</li></ul> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=17" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/0/0b/Wikiversity_logo_2017.svg/40px-Wikiversity_logo_2017.svg.png" decoding="async" width="40" height="33" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/0/0b/Wikiversity_logo_2017.svg/60px-Wikiversity_logo_2017.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/0/0b/Wikiversity_logo_2017.svg/80px-Wikiversity_logo_2017.svg.png 2x" data-file-width="626" data-file-height="512" /></span></span></div> <div class="side-box-text plainlist">Wikiversity has learning resources about <i><b><a href="https://en.wikiversity.org/wiki/Quadratic_Sieve" class="extiw" title="v:Quadratic Sieve">Quadratic Sieve</a></b></i></div></div> </div> <ul><li><a href="/wiki/Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">Lenstra elliptic curve factorization</a></li> <li><a href="/wiki/Primality_test" title="Primality test">primality test</a></li></ul> <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=Quadratic_sieve&action=edit&section=18" title="Edit section: References"><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"> <div class="mw-references-wrap"><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">Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><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="CITEREFPomerance1996" class="citation news cs1"><a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (December 1996). <a rel="nofollow" class="external text" href="https://www.ams.org/notices/199612/pomerance.pdf">"A Tale of Two Sieves"</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>. Vol. 43, no. 12. pp. 1473–1485.</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=A+Tale+of+Two+Sieves&rft.volume=43&rft.issue=12&rft.pages=1473-1485&rft.date=1996-12&rft.aulast=Pomerance&rft.aufirst=Carl&rft_id=https%3A%2F%2Fwww.ams.org%2Fnotices%2F199612%2Fpomerance.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadratic+sieve" 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 class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.mersenneforum.org/showthread.php?t=25676">"Useless Accomplishment: RSA-140 Factorization with Quadratic Sieve - mersenneforum.org"</a>. <i>www.mersenneforum.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-07-07</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.mersenneforum.org&rft.atitle=Useless+Accomplishment%3A+RSA-140+Factorization+with+Quadratic+Sieve+-+mersenneforum.org&rft_id=https%3A%2F%2Fwww.mersenneforum.org%2Fshowthread.php%3Ft%3D25676&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadratic+sieve" class="Z3988"></span></span> </li> </ol></div></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin" style=""> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCrandallPomerance2001" class="citation book cs1"><a href="/wiki/Richard_Crandall" title="Richard Crandall">Crandall, Richard</a>; <a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (2001). "Section 6.1: The quadratic sieve factorization method". <i>Prime Numbers: A Computational Perspective</i> (1st ed.). Springer. pp. 227–244. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-387-94777-9" title="Special:BookSources/0-387-94777-9"><bdi>0-387-94777-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Section+6.1%3A+The+quadratic+sieve+factorization+method&rft.btitle=Prime+Numbers%3A+A+Computational+Perspective&rft.pages=227-244&rft.edition=1st&rft.pub=Springer&rft.date=2001&rft.isbn=0-387-94777-9&rft.aulast=Crandall&rft.aufirst=Richard&rft.au=Pomerance%2C+Carl&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadratic+sieve" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWagstaff2013" class="citation book cs1"><a href="/wiki/Samuel_S._Wagstaff_Jr." title="Samuel S. Wagstaff Jr.">Wagstaff, Samuel S. Jr.</a> (2013). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://www.ams.org/bookpages/stml-68"><i>The Joy of Factoring</i></a></span>. Providence, RI: <a href="/wiki/American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a>. pp. 195–202. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4704-1048-3" title="Special:BookSources/978-1-4704-1048-3"><bdi>978-1-4704-1048-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Joy+of+Factoring&rft.place=Providence%2C+RI&rft.pages=195-202&rft.pub=American+Mathematical+Society&rft.date=2013&rft.isbn=978-1-4704-1048-3&rft.aulast=Wagstaff&rft.aufirst=Samuel+S.+Jr.&rft_id=https%3A%2F%2Fwww.ams.org%2Fbookpages%2Fstml-68&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadratic+sieve" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFContini1997" class="citation thesis cs1">Contini, Scott Patrick (1997). <a rel="nofollow" class="external text" href="http://web.archive.org/web/20150405063620/http://www.crypto-world.com/documents/contini_siqs.pdf"><i>Factoring Integers with the Self-Initializing Quadratic Sieve</i></a> <span class="cs1-format">(PDF)</span> (M.A. thesis). University of Georgia. Archived from <a rel="nofollow" class="external text" href="http://www.crypto-world.com/documents/contini_siqs.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2015-04-05.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Factoring+Integers+with+the+Self-Initializing+Quadratic+Sieve&rft.degree=M.A.&rft.inst=University+of+Georgia&rft.date=1997&rft.aulast=Contini&rft.aufirst=Scott+Patrick&rft_id=http%3A%2F%2Fwww.crypto-world.com%2Fdocuments%2Fcontini_siqs.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadratic+sieve" class="Z3988"></span> Describes many practical implementation details.</li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="Other_external_links">Other external links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadratic_sieve&action=edit&section=19" title="Edit section: Other external links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Reference paper <a rel="nofollow" class="external text" href="http://www.cs.virginia.edu/crab/QFS_Simple.pdf">"The Quadratic Sieve Factoring Algorithm"</a> by Eric Landquist</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="Number-theoretic_algorithms" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed 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:Number-theoretic_algorithms" title="Template:Number-theoretic algorithms"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Number-theoretic_algorithms" title="Template talk:Number-theoretic algorithms"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Number-theoretic_algorithms" title="Special:EditPage/Template:Number-theoretic algorithms"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Number-theoretic_algorithms" style="font-size:114%;margin:0 4em"><a href="/wiki/Number_theory" title="Number theory">Number-theoretic</a> <a href="/wiki/Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Primality_test" title="Primality test">Primality tests</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/AKS_primality_test" title="AKS primality test">AKS</a></li> <li><a href="/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test" title="Adleman–Pomerance–Rumely primality test">APR</a></li> <li><a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li> <li><a href="/wiki/Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li> <li><a href="/wiki/Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li> <li><a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat</a></li> <li><a href="/wiki/Lucas_primality_test" title="Lucas primality test">Lucas</a></li> <li><i><a href="/wiki/Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></i></li> <li><i><a href="/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></i></li> <li><i><a href="/wiki/Proth%27s_theorem" title="Proth's theorem">Proth's theorem</a></i></li> <li><i><a href="/wiki/P%C3%A9pin%27s_test" title="Pépin's test">Pépin's</a></i></li> <li><a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li> <li><a href="/wiki/Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li> <li><a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</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/Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li> <li><a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li> <li><a href="/wiki/Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li> <li><a href="/wiki/Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li> <li><a href="/wiki/Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</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/Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li> <li><a href="/wiki/Dixon%27s_factorization_method" title="Dixon's factorization method">Dixon's</a></li> <li><a href="/wiki/Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li> <li><a href="/wiki/Euler%27s_factorization_method" title="Euler's factorization method">Euler's</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li> <li><a href="/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm"><i>p</i> − 1</a></li> <li><a href="/wiki/Williams%27s_p_%2B_1_algorithm" title="Williams's p + 1 algorithm"><i>p</i> + 1</a></li> <li><a class="mw-selflink selflink">Quadratic sieve (QS)</a></li> <li><a href="/wiki/General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li> <li><i><a href="/wiki/Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></i></li> <li><a href="/wiki/Rational_sieve" title="Rational sieve">Rational sieve</a></li> <li><a href="/wiki/Fermat%27s_factorization_method" title="Fermat's factorization method">Fermat's</a></li> <li><a href="/wiki/Shanks%27s_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li> <li><a href="/wiki/Trial_division" title="Trial division">Trial division</a></li> <li><a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">Multiplication</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/Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li> <li><a href="/wiki/Long_multiplication" class="mw-redirect" title="Long multiplication">Long</a></li> <li><a href="/wiki/Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li> <li><a href="/wiki/Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook</a></li> <li><a href="/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li> <li><a href="/wiki/F%C3%BCrer%27s_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Euclidean_division" title="Euclidean division">Euclidean</a> <a href="/wiki/Division_algorithm" title="Division algorithm">division</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/Binary_division" class="mw-redirect" title="Binary division">Binary</a></li> <li><a href="/wiki/Chunking_(division)" title="Chunking (division)">Chunking</a></li> <li><a href="/wiki/Fourier_division" title="Fourier division">Fourier</a></li> <li><a href="/wiki/Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li> <li><a href="/wiki/Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li> <li><a href="/wiki/Long_division" title="Long division">Long</a></li> <li><a href="/wiki/Short_division" title="Short division">Short</a></li> <li><a href="/wiki/SRT_division" class="mw-redirect" title="SRT division">SRT</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</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/Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li> <li><a href="/wiki/Pollard%27s_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li> <li><a href="/wiki/Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li> <li><a href="/wiki/Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li> <li><a href="/wiki/Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</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/Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li> <li><a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li> <li><a href="/wiki/Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li> <li><a href="/wiki/Lehmer%27s_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quadratic_residue" title="Quadratic residue">Modular square root</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/Cipolla%27s_algorithm" title="Cipolla's algorithm">Cipolla</a></li> <li><a href="/wiki/Pocklington%27s_algorithm" title="Pocklington's algorithm">Pocklington's</a></li> <li><a href="/wiki/Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li> <li><a href="/wiki/Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li> <li><a href="/wiki/Kunerth%27s_algorithm" title="Kunerth's algorithm">Kunerth</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</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/Chakravala_method" title="Chakravala method">Chakravala</a></li> <li><a href="/wiki/Cornacchia%27s_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li> <li><a href="/wiki/Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li> <li><a href="/wiki/Integer_square_root" title="Integer square root">Integer square root</a></li> <li><a href="/wiki/Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="/wiki/Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li> <li><a href="/wiki/Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li> <li><a href="/wiki/Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li> <li><a href="/wiki/Schoof%27s_algorithm" title="Schoof's algorithm">Schoof</a></li> <li><a href="/wiki/Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div> <ul><li><i>Italics</i> indicate that algorithm is for numbers of special forms</li></ul> </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=Quadratic_sieve&oldid=1251006964">https://en.wikipedia.org/w/index.php?title=Quadratic_sieve&oldid=1251006964</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">Category</a>: <ul><li><a href="/wiki/Category:Integer_factorization_algorithms" title="Category:Integer factorization algorithms">Integer factorization algorithms</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:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</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 13 October 2024, at 20:50<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=Quadratic_sieve&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-jlfln","wgBackendResponseTime":827,"wgPageParseReport":{"limitreport":{"cputime":"0.435","walltime":"0.630","ppvisitednodes":{"value":1137,"limit":1000000},"postexpandincludesize":{"value":31608,"limit":2097152},"templateargumentsize":{"value":698,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":27516,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 401.393 1 -total"," 29.62% 118.889 1 Template:Number_theoretic_algorithms"," 27.73% 111.301 1 Template:Navbox"," 23.66% 94.950 1 Template:Reflist"," 22.07% 88.581 1 Template:Short_description"," 19.16% 76.910 1 Template:Cite_news"," 12.56% 50.407 2 Template:Pagetype"," 8.50% 34.125 1 Template:Wikiversity"," 8.06% 32.341 1 Template:Sister_project"," 7.43% 29.806 1 Template:Side_box"]},"scribunto":{"limitreport-timeusage":{"value":"0.237","limit":"10.000"},"limitreport-memusage":{"value":4673467,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-jlfln","timestamp":"20241122141834","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Quadratic sieve","url":"https:\/\/en.wikipedia.org\/wiki\/Quadratic_sieve","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1151850","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1151850","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":"2004-04-07T17:01:17Z","dateModified":"2024-10-13T20:50:32Z","headline":"Integer factorization algorithm"}</script> </body> </html>

CINXE.COM

Quadratic sieve - Wikipedia