CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Fermat's factorization method - 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":"809617c3-fdc8-4d1a-80ab-4370e9922d3e","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Fermat's_factorization_method","wgTitle":"Fermat's factorization method","wgCurRevisionId":1249789677,"wgRevisionId":1249789677,"wgArticleId":2132433,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles needing additional references from February 2022","All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from January 2015","Integer factorization algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Fermat's_factorization_method" ,"wgRelevantArticleId":2132433,"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":10000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q983978","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.math.styles":"ready","ext.cite.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="Fermat's factorization method - 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/Fermat%27s_factorization_method"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Fermat%27s_factorization_method&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/Fermat%27s_factorization_method"> <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-Fermat_s_factorization_method rootpage-Fermat_s_factorization_method 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=Fermat%27s+factorization+method" 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=Fermat%27s+factorization+method" 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=Fermat%27s+factorization+method" 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=Fermat%27s+factorization+method" 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_method" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Basic_method"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Basic method</span> </div> </a> <ul id="toc-Basic_method-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Fermat's_and_trial_division" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Fermat's_and_trial_division"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Fermat's and trial division</span> </div> </a> <ul id="toc-Fermat's_and_trial_division-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sieve_improvement" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Sieve_improvement"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Sieve improvement</span> </div> </a> <ul id="toc-Sieve_improvement-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Multiplier_improvement" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Multiplier_improvement"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Multiplier improvement</span> </div> </a> <ul id="toc-Multiplier_improvement-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Other_improvements" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Other_improvements"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Other improvements</span> </div> </a> <ul id="toc-Other_improvements-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">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Fermat's factorization method</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 11 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-11" 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">11 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B7%D8%B1%D9%8A%D9%82%D8%A9_%D8%A7%D9%84%D8%AA%D8%B9%D9%85%D9%8A%D9%84_%D9%84%D9%81%D9%8A%D8%B1%D9%85%D8%A7" title="طريقة التعميل لفيرما – Arabic" lang="ar" hreflang="ar" data-title="طريقة التعميل لفيرما" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat" title="Faktorisierungsmethode von Fermat – German" lang="de" hreflang="de" data-title="Faktorisierungsmethode von Fermat" 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/M%C3%A9todo_de_factorizaci%C3%B3n_de_Fermat" title="Método de factorización de Fermat – Spanish" lang="es" hreflang="es" data-title="Método de factorización de Fermat" 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/M%C3%A9thode_de_factorisation_de_Fermat" title="Méthode de factorisation de Fermat – French" lang="fr" hreflang="fr" data-title="Méthode de factorisation de Fermat" 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-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Metodo_di_fattorizzazione_di_Fermat" title="Metodo di fattorizzazione di Fermat – Italian" lang="it" hreflang="it" data-title="Metodo di fattorizzazione di Fermat" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Fermats_factorisatiemethode" title="Fermats factorisatiemethode – Dutch" lang="nl" hreflang="nl" data-title="Fermats factorisatiemethode" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Algorytm_Fermata" title="Algorytm Fermata – Polish" lang="pl" hreflang="pl" data-title="Algorytm Fermata" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/M%C3%A9todo_de_fatora%C3%A7%C3%A3o_de_Fermat" title="Método de fatoração de Fermat – Portuguese" lang="pt" hreflang="pt" data-title="Método de fatoração de Fermat" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</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_%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%A4%D0%B5%D1%80%D0%BC%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-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%81%E0%B8%A2%E0%B8%81%E0%B8%95%E0%B8%B1%E0%B8%A7%E0%B8%9B%E0%B8%A3%E0%B8%B0%E0%B8%81%E0%B8%AD%E0%B8%9A%E0%B8%82%E0%B8%AD%E0%B8%87%E0%B8%88%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%99%E0%B9%80%E0%B8%95%E0%B9%87%E0%B8%A1%E0%B8%82%E0%B8%AD%E0%B8%87%E0%B9%81%E0%B8%9F%E0%B8%A3%E0%B9%8C%E0%B8%A1%E0%B8%B2%E0%B8%95%E0%B9%8C" 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%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D1%96%D1%97_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0" title="Метод факторизації Ферма – Ukrainian" lang="uk" hreflang="uk" data-title="Метод факторизації Ферма" data-language-autonym="Українська" data-language-local-name="Ukrainian" 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/Q983978#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/Fermat%27s_factorization_method" 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:Fermat%27s_factorization_method" 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/Fermat%27s_factorization_method"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Fermat%27s_factorization_method&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=Fermat%27s_factorization_method&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/Fermat%27s_factorization_method"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Fermat%27s_factorization_method&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=Fermat%27s_factorization_method&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/Fermat%27s_factorization_method" 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/Fermat%27s_factorization_method" 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=Fermat%27s_factorization_method&oldid=1249789677" 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=Fermat%27s_factorization_method&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=Fermat%27s_factorization_method&id=1249789677&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%2FFermat%2527s_factorization_method"><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%2FFermat%2527s_factorization_method"><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=Fermat%27s_factorization_method&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=Fermat%27s_factorization_method&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/Q983978" 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">Mathematics equation</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Fermat%27s_factorization_method" title="Special:EditPage/Fermat's factorization method">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Fermat%27s+factorization+method%22">"Fermat's factorization method"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Fermat%27s+factorization+method%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Fermat%27s+factorization+method%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Fermat%27s+factorization+method%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Fermat%27s+factorization+method%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Fermat%27s+factorization+method%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">February 2022</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p><b>Fermat's factorization method</b>, named after <a href="/wiki/Pierre_de_Fermat" title="Pierre de Fermat">Pierre de Fermat</a>, is based on the representation of an <a href="/wiki/Even_and_odd_numbers" class="mw-redirect" title="Even and odd numbers">odd</a> <a href="/wiki/Integer" title="Integer">integer</a> as the <a href="/wiki/Difference_of_two_squares" title="Difference of two squares">difference of two 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 N=a^{2}-b^{2}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=a^{2}-b^{2}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98c714e3deb8b0afe1b9bf534d090276cf9108dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.985ex; height:2.843ex;" alt="{\displaystyle N=a^{2}-b^{2}.}"></span></dd></dl> <p>That difference is <a href="/wiki/Algebra" title="Algebra">algebraically</a> factorable 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 (a+b)(a-b)}"> <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> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a+b)(a-b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13577604d52dd40f6de382e5f475e2cb369fddb8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.754ex; height:2.843ex;" alt="{\displaystyle (a+b)(a-b)}"></span>; if neither factor equals one, it is a proper factorization of <i>N</i>. </p><p>Each odd number has such a representation. Indeed, if <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 N=cd}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mi>c</mi> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=cd}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60af0ab0758fa1c298b712ab6144883cc977022a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.385ex; height:2.176ex;" alt="{\displaystyle N=cd}"></span> is a factorization of <i>N</i>, then </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 N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <msup> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>c</mi> <mo>+</mo> <mi>d</mi> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <msup> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>c</mi> <mo>−</mo> <mi>d</mi> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60b0e75237e9b25effa6ee21768206d86b41528a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:28.752ex; height:6.509ex;" alt="{\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}}"></span></dd></dl> <p>Since <i>N</i> is odd, then <i>c</i> and <i>d</i> are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let <i>c</i> and <i>d</i> be even.) </p><p>In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either by itself. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Basic_method">Basic method</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=1" title="Edit section: Basic method"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>One tries various values of <i>a</i>, hoping 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 a^{2}-N=b^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>N</mi> <mo>=</mo> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}-N=b^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d8011ea38d69c0f59bf692fc0476bd503e88d29" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.338ex; height:2.843ex;" alt="{\displaystyle a^{2}-N=b^{2}}"></span>, a square. </p> <pre>FermatFactor(N): <i>// N should be odd</i> a ← ceiling(sqrt(N)) b2 ← a*a - N <b>repeat until</b> b2 <b>is</b> a square: a ← a + 1 b2 ← a*a - N // equivalently: // b2 ← b2 + 2*a + 1<i> </i> // a ← a + 1 <b>return</b> a - sqrt(b2) <i>// or a + sqrt(b2)</i> </pre> <p>For example, to 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 N=5959}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mn>5959</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=5959}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/73bbf02a077e81cee0800296be2d71802e3139e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.812ex; height:2.176ex;" alt="{\displaystyle N=5959}"></span>, the first try for <i>a</i> is the square root of <span class="texhtml">5959</span> rounded up to the next integer, which is <span class="texhtml">78</span>. Then <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}=78^{2}-5959=125}"> <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> <msup> <mn>78</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>5959</mn> <mo>=</mo> <mn>125</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b^{2}=78^{2}-5959=125}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a25c9f3543341baef9c603a8f3c481f473b9020b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:22.605ex; height:2.843ex;" alt="{\displaystyle b^{2}=78^{2}-5959=125}"></span>. Since 125 is not a square, a second try is made by increasing the value of <i>a</i> by 1. The second attempt also fails, because 282 is again not a square. </p> <table class="wikitable" style="text-align:right;"> <tbody><tr> <th>Try: </th> <td>1</td> <td>2</td> <td>3 </td></tr> <tr> <th><i>a</i> </th> <td>78</td> <td>79</td> <td>80 </td></tr> <tr> <th><i>b</i><sup>2</sup> </th> <td>125</td> <td>282</td> <td>441 </td></tr> <tr> <th><i>b</i> </th> <td>11.18</td> <td>16.79</td> <td>21 </td></tr></tbody></table> <p>The third try produces the perfect square of 441. Thus, <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=80}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mn>80</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=80}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91a71a6d98e0ff70a0fa31c4b57ac762f01614ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.653ex; height:2.176ex;" alt="{\displaystyle a=80}"></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 b=21}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo>=</mo> <mn>21</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b=21}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4b92bb35b895260bc5b09f64d0297e9db190192" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.421ex; height:2.176ex;" alt="{\displaystyle b=21}"></span>, and the factors of <span class="texhtml">5959</span> are <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=59}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>−</mo> <mi>b</mi> <mo>=</mo> <mn>59</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a-b=59}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11388388274bbd5c3d352dd5470d4ac197faa103" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.491ex; height:2.343ex;" alt="{\displaystyle a-b=59}"></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 a+b=101}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>+</mo> <mi>b</mi> <mo>=</mo> <mn>101</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a+b=101}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/578801d46b5e57ea7e9f7971ffdbe6d7f6bf204f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.654ex; height:2.343ex;" alt="{\displaystyle a+b=101}"></span>. </p><p>Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of <i>a</i> and <i>b</i>. That is, <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>+</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a+b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a2391acf09244b9dba74eb940e871a6be7e7973a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.068ex; height:2.343ex;" alt="{\displaystyle a+b}"></span> is the smallest factor ≥ the square-root of <i>N</i>, and 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 a-b=N/(a+b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>−</mo> <mi>b</mi> <mo>=</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>+</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a-b=N/(a+b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/faad0f3b03c1340cbda92ad7c5e5a318a7806895" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.269ex; height:2.843ex;" alt="{\displaystyle a-b=N/(a+b)}"></span> is the largest factor ≤ root-<i>N</i>. If the procedure finds <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 N=1\cdot N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mn>1</mn> <mo>⋅</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=1\cdot N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b28af1dfde117bd25f6c6f6df1f9b083627168c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.067ex; height:2.176ex;" alt="{\displaystyle N=1\cdot N}"></span>, that shows that <i>N</i> is prime. </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 N=cd}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mi>c</mi> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=cd}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60af0ab0758fa1c298b712ab6144883cc977022a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.385ex; height:2.176ex;" alt="{\displaystyle N=cd}"></span>, let <i>c</i> be the largest subroot 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 a=(c+d)/2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>c</mi> <mo>+</mo> <mi>d</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=(c+d)/2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/768e2b6552a0f3638b83cddad766862652eb9f1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.526ex; height:2.843ex;" alt="{\displaystyle a=(c+d)/2}"></span>, so the number of steps is approximately <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+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>c</mi> <mo>+</mo> <mi>d</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mo>=</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>d</mi> </msqrt> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>c</mi> </msqrt> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo>=</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mo>−</mo> <mi>c</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/322f2d40c8d8b00679712273c9cf0d80adbe8e08" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:50.399ex; height:3.343ex;" alt="{\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}"></span>. </p><p>If <i>N</i> is prime (so 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 c=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e3467f9e219a5ea38a30da5c3a02c2c23f61a79" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c=1}"></span>), one needs <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 O(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78484c5c26cfc97bb3b915418caa09454421e80b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}"></span> steps. This is a bad way to prove primality. But if <i>N</i> has a factor close to its square root, the method works quickly. More precisely, if <i>c</i> differs less than <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 {\left(4N\right)}^{1/4}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mrow> <mn>4</mn> <mi>N</mi> </mrow> <mo>)</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>4</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\left(4N\right)}^{1/4}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43969ebeb297419ba7637fbb0c5da76ed16ffbdf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.734ex; height:3.509ex;" alt="{\displaystyle {\left(4N\right)}^{1/4}}"></span> from <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 {\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3d8948b2c154ccc7f7523b035ae7e254e04190" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}"></span>, the method requires only one step; this is independent of the size of <i>N</i>.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (January 2015)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="Fermat's_and_trial_division"><span id="Fermat.27s_and_trial_division"></span>Fermat's and trial division</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=2" title="Edit section: Fermat's and trial division"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Consider trying to factor the prime number <span class="nowrap"><i>N</i> = 2,345,678,917</span>, but also compute <i>b</i> and <span class="nowrap"><i>a</i> − <i>b</i></span> throughout. Going up from <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 {\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3d8948b2c154ccc7f7523b035ae7e254e04190" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}"></span> rounded up to the next integer, which is 48,433, we can tabulate: </p> <table class="wikitable"> <tbody><tr> <th>Try </th> <td>1st</td> <td>2nd</td> <td>3rd</td> <td>4th </td></tr> <tr> <th><i>a</i> </th> <td>48,433</td> <td>48,434</td> <td>48,435</td> <td>48,436 </td></tr> <tr> <th><i>b</i><sup>2</sup> </th> <td>76,572</td> <td>173,439</td> <td>270,308</td> <td>367,179 </td></tr> <tr> <th><i>b</i> </th> <td>276.7</td> <td>416.5</td> <td>519.9</td> <td>605.9 </td></tr> <tr> <th><i>a</i> − <i>b</i> </th> <td>48,156.3</td> <td>48,017.5</td> <td>47,915.1</td> <td>47,830.1 </td></tr></tbody></table> <p>In practice, one wouldn't bother with that last row until <i>b</i> is an integer. But observe that if <i>N</i> had a subroot factor above <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=47830.1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>−</mo> <mi>b</mi> <mo>=</mo> <mn>47830.1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a-b=47830.1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8bbded08bb2d962b371c6004c6ce15117f5491cc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.788ex; height:2.343ex;" alt="{\displaystyle a-b=47830.1}"></span>, Fermat's method would have found it already. </p><p>Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality. </p><p>This all suggests a combined factoring method. Choose some bound <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_{\mathrm {max} }>{\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> <mo>></mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ef5f01422cfbf41639d765d0ddeded3a925ebd00" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.619ex; height:3.009ex;" alt="{\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}"></span>; use Fermat's method for factors between <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 {\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3d8948b2c154ccc7f7523b035ae7e254e04190" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}"></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 a_{\mathrm {max} }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{\mathrm {max} }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9ba772b0159e2d8bc66cdd619022d948e6df44b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.521ex; height:2.009ex;" alt="{\displaystyle a_{\mathrm {max} }}"></span>. This gives a bound for trial division which is <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_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msubsup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> <mo>−</mo> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6aefc0ae4cf507fbd19a0a7b191608c81af63158" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.11ex; height:3.509ex;" alt="{\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}"></span>. In the above example, with <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_{\mathrm {max} }=48436}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> <mo>=</mo> <mn>48436</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{\mathrm {max} }=48436}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7792dbfcbaaf8c615b6b40b6e514c606ff54a122" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.432ex; height:2.509ex;" alt="{\displaystyle a_{\mathrm {max} }=48436}"></span> the bound for trial division is 47830. A reasonable choice could be <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_{\mathrm {max} }=55000}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> <mo>=</mo> <mn>55000</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{\mathrm {max} }=55000}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/97dfde1c8e0b120e6792272afdcedaa5f6a46bf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.432ex; height:2.509ex;" alt="{\displaystyle a_{\mathrm {max} }=55000}"></span> giving a bound of 28937. </p><p>In this regard, Fermat's method gives diminishing returns. One would surely stop before this point: </p> <table class="wikitable"> <tbody><tr> <th><i>a</i> </th> <td>60,001</td> <td>60,002 </td></tr> <tr> <th><i>b</i><sup>2</sup> </th> <td>1,254,441,084</td> <td>1,254,561,087 </td></tr> <tr> <th><i>b</i> </th> <td>35,418.1</td> <td>35,419.8 </td></tr> <tr> <th><i>a</i> − <i>b</i> </th> <td>24,582.9</td> <td>24,582.2 </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Sieve_improvement">Sieve improvement</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=3" title="Edit section: Sieve improvement"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When considering the table 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 N=2345678917}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mn>2345678917</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=2345678917}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef6ec34c31db6ec2ba4cad0aa73e8793146d67d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:16.787ex; height:2.176ex;" alt="{\displaystyle N=2345678917}"></span>, one can quickly tell that none of the values 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 b^{2}}"> <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> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/acf98b04bfc723606ebb4a7942fa3ab94becd2ee" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.052ex; height:2.676ex;" alt="{\displaystyle b^{2}}"></span> are squares: </p> <table class="wikitable" style="text-align:right;"> <tbody><tr> <th><i>a</i> </th> <td>48,433</td> <td>48,434</td> <td>48,435</td> <td>48,436 </td></tr> <tr> <th><i>b</i><sup>2</sup> </th> <td>76,572</td> <td>173,439</td> <td>270,308</td> <td>367,179 </td></tr> <tr> <th><i>b</i> </th> <td>276.7</td> <td>416.5</td> <td>519.9</td> <td>605.9 </td></tr></tbody></table> <p>It is not necessary to compute all the square-roots 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 a^{2}-N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}-N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bec1b3e3d7755f6ee482d346b902cc7f92450820" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.188ex; height:2.843ex;" alt="{\displaystyle a^{2}-N}"></span>, nor even examine all the values for <span class="texhtml mvar" style="font-style:italic;">a</span>. Squares are always congruent to 0, 1, 4, 5, 9, 16 <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modulo</a> 20. The values repeat with each increase of <span class="texhtml mvar" style="font-style:italic;">a</span> by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), <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^{2}-N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}-N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bec1b3e3d7755f6ee482d346b902cc7f92450820" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.188ex; height:2.843ex;" alt="{\displaystyle a^{2}-N}"></span> produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, <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^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f564e5dc0b6e68af32ca8614e972f5b36e944a24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.284ex; height:2.676ex;" alt="{\displaystyle a^{2}}"></span> must be 1 mod 20, which means that <span class="texhtml mvar" style="font-style:italic;">a</span> is 1, 9, 11 or 19 mod 20; it will produce 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 b^{2}}"> <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> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/acf98b04bfc723606ebb4a7942fa3ab94becd2ee" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.052ex; height:2.676ex;" alt="{\displaystyle b^{2}}"></span> which ends in 4 mod 20 and, if square, <span class="texhtml mvar" style="font-style:italic;">b</span> will end in 2 or 8 mod 10. </p><p>This can be performed with any modulus. Using the same <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 N=2345678917}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mn>2345678917</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=2345678917}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef6ec34c31db6ec2ba4cad0aa73e8793146d67d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:16.787ex; height:2.176ex;" alt="{\displaystyle N=2345678917}"></span>, </p> <table> <tbody><tr> <td>modulo 16:</td> <td>Squares are</td> <td>0, 1, 4, or 9 </td></tr> <tr> <td></td> <td>N mod 16 is</td> <td>5 </td></tr> <tr> <td></td> <td>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 a^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f564e5dc0b6e68af32ca8614e972f5b36e944a24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.284ex; height:2.676ex;" alt="{\displaystyle a^{2}}"></span> can only be</td> <td>9 </td></tr> <tr> <td></td> <td>and <span class="texhtml mvar" style="font-style:italic;">a</span> must be</td> <td>3 or 5 or 11 or 13 modulo 16 </td></tr> <tr> <td>modulo 9:</td> <td>Squares are</td> <td>0, 1, 4, or 7 </td></tr> <tr> <td></td> <td>N mod 9 is</td> <td>7 </td></tr> <tr> <td></td> <td>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 a^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f564e5dc0b6e68af32ca8614e972f5b36e944a24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.284ex; height:2.676ex;" alt="{\displaystyle a^{2}}"></span> can only be</td> <td>7 </td></tr> <tr> <td></td> <td>and <span class="texhtml mvar" style="font-style:italic;">a</span> must be</td> <td>4 or 5 modulo 9 </td></tr></tbody></table> <p>One generally chooses a power of a different prime for each modulus. </p><p>Given a sequence of <i>a</i>-values (start, end, and step) and a modulus, one can proceed thus: </p> <pre>FermatSieve(N, astart, aend, astep, modulus) a ← astart <b>do</b> modulus <b>times</b>: b2 ← a*a - N <b>if</b> b2 is a square, modulo modulus: FermatSieve(N, a, aend, astep * modulus, NextModulus) <b>endif</b> a ← a + astep <b>enddo</b> </pre> <p>But the <a href="/wiki/Recursion_(computer_science)" title="Recursion (computer science)">recursion</a> is stopped when few <i>a</i>-values remain; that is, when (aend-astart)/astep is small. Also, because <i>a'</i>s step-size is constant, one can compute successive b2's with additions. </p> <div class="mw-heading mw-heading2"><h2 id="Multiplier_improvement">Multiplier improvement</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=4" title="Edit section: Multiplier improvement"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Fermat's method works best when there is a factor near the square-root of <i>N</i>. </p><p>If the approximate ratio of two factors (<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 d/c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d/c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cdfaa8ece95a4996a2c73c460f3d4c5b9771ee1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.385ex; height:2.843ex;" alt="{\displaystyle d/c}"></span>) is known, then a <a href="/wiki/Rational_number" title="Rational number">rational number</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 v/u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v/u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/32663c8817e5b225f34550f3b904d07247e47749" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.62ex; height:2.843ex;" alt="{\displaystyle v/u}"></span> can be picked near that value. <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 Nuv=cv\cdot du}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mi>u</mi> <mi>v</mi> <mo>=</mo> <mi>c</mi> <mi>v</mi> <mo>⋅</mo> <mi>d</mi> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Nuv=cv\cdot du}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/20755bbb80ba3de52f57bbc15d21e7e571aa83ef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.979ex; height:2.176ex;" alt="{\displaystyle Nuv=cv\cdot du}"></span>, and Fermat's method, applied to <i>Nuv</i>, will find the factors <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 cv}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle cv}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b3ab2711369b7b89594e57280b618c830379df1b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.134ex; height:1.676ex;" alt="{\displaystyle cv}"></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 du}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle du}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d33341cb51d52b43431e85e57ffceadeb44b04a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle du}"></span> quickly. Then <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 \gcd(N,cv)=c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>,</mo> <mi>c</mi> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gcd(N,cv)=c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/318dc8332490cedba6317cb3a6bedd1e4251ee61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.634ex; height:2.843ex;" alt="{\displaystyle \gcd(N,cv)=c}"></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 \gcd(N,du)=d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>,</mo> <mi>d</mi> <mi>u</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gcd(N,du)=d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/03e5aa80c4734e9f82e6cd78e21cd089cb5b8197" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.254ex; height:2.843ex;" alt="{\displaystyle \gcd(N,du)=d}"></span>. (Unless <i>c</i> divides <i>u</i> or <i>d</i> divides <i>v</i>.) </p><p>Generally, if the ratio is not known, various <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 u/v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u/v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed502b04fa48173735a0a402f23386a3a195d509" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.62ex; height:2.843ex;" alt="{\displaystyle u/v}"></span> values can be tried, and try to factor each resulting <i>Nuv</i>. R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N 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 O(N^{1/3})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N^{1/3})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1d0d589dd1bedc8d57bc7e265c1801ff9ff349b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.404ex; height:3.343ex;" alt="{\displaystyle O(N^{1/3})}"></span> time.<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> <div class="mw-heading mw-heading2"><h2 id="Other_improvements">Other improvements</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=5" title="Edit section: Other improvements"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The fundamental ideas of Fermat's factorization method are the basis of the <a href="/wiki/Quadratic_sieve" title="Quadratic sieve">quadratic sieve</a> and <a href="/wiki/General_number_field_sieve" title="General number field sieve">general number field sieve</a>, the best-known algorithms for factoring large <a href="/wiki/Semiprimes" class="mw-redirect" title="Semiprimes">semiprimes</a>, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence 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 a^{2}-n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{2}-n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a35fcc4931fc2e03b660eba25b614ccac4c03b4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.519ex; height:2.843ex;" alt="{\displaystyle a^{2}-n}"></span>, it finds a subset of elements of this sequence whose <i>product</i> is a square, and it does this in a highly efficient manner. The end result is the same: a difference of squares mod <i>n</i> that, if nontrivial, can be used to factor <i>n</i>. </p> <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=Fermat%27s_factorization_method&action=edit&section=6" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Completing_the_square" title="Completing the square">Completing the square</a></li> <li><a href="/wiki/Factorization_of_polynomials" title="Factorization of polynomials">Factorization of polynomials</a></li> <li><a href="/wiki/Factor_theorem" title="Factor theorem">Factor theorem</a></li> <li><a href="/wiki/FOIL_rule" class="mw-redirect" title="FOIL rule">FOIL rule</a></li> <li><a href="/wiki/Monoid_factorisation" title="Monoid factorisation">Monoid factorisation</a></li> <li><a href="/wiki/Pascal%27s_triangle" title="Pascal's triangle">Pascal's triangle</a></li> <li><a href="/wiki/Prime_factor" class="mw-redirect" title="Prime factor">Prime factor</a></li> <li><a href="/wiki/Factorization" title="Factorization">Factorization</a></li> <li><a href="/wiki/Euler%27s_factorization_method" title="Euler's factorization method">Euler's factorization method</a></li> <li><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a></li> <li><a href="/wiki/Program_synthesis" title="Program synthesis">Program synthesis</a></li> <li><a href="/wiki/Table_of_Gaussian_integer_factorizations" title="Table of Gaussian integer factorizations">Table of Gaussian integer factorizations</a></li> <li><a href="/wiki/Unique_factorization_domain" title="Unique factorization domain">Unique factorization</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=7" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <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"><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="CITEREFLehman1974" class="citation journal cs1">Lehman, R. Sherman (1974). <a rel="nofollow" class="external text" href="https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf">"Factoring Large Integers"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></i>. <b>28</b> (126): 637–646. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2005940">10.2307/2005940</a></span>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2005940">2005940</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=Factoring+Large+Integers&rft.volume=28&rft.issue=126&rft.pages=637-646&rft.date=1974&rft_id=info%3Adoi%2F10.2307%2F2005940&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2005940%23id-name%3DJSTOR&rft.aulast=Lehman&rft.aufirst=R.+Sherman&rft_id=https%3A%2F%2Fwww.ams.org%2Fjournals%2Fmcom%2F1974-28-126%2FS0025-5718-1974-0340163-2%2FS0025-5718-1974-0340163-2.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat%27s+factorization+method" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=8" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFermat1894" class="citation cs2">Fermat (1894), <i>Oeuvres de Fermat</i>, vol. 2, p. 256</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Oeuvres+de+Fermat&rft.pages=256&rft.date=1894&rft.au=Fermat&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat%27s+factorization+method" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMcKee1999" class="citation journal cs1">McKee, J (1999). <a rel="nofollow" class="external text" href="https://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html">"Speeding Fermat's factoring method"</a>. <i>Mathematics of Computation</i>. <b>68</b> (228): 1729–1737. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-99-01133-3">10.1090/S0025-5718-99-01133-3</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=Speeding+Fermat%27s+factoring+method&rft.volume=68&rft.issue=228&rft.pages=1729-1737&rft.date=1999&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-99-01133-3&rft.aulast=McKee&rft.aufirst=J&rft_id=https%3A%2F%2Fwww.ams.org%2Fmcom%2F1999-68-228%2FS0025-5718-99-01133-3%2Fhome.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat%27s+factorization+method" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat%27s_factorization_method&action=edit&section=9" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html">Fermat's factorization running time</a>, at blogspot.in</li> <li><a rel="nofollow" class="external text" href="https://windowspros.ru/projects/fermat-factorization-online-calculator/">Fermat's Factorization Online Calculator</a>, at windowspros.ru</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 href="/wiki/Quadratic_sieve" title="Quadratic sieve">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 class="mw-selflink selflink">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=Fermat%27s_factorization_method&oldid=1249789677">https://en.wikipedia.org/w/index.php?title=Fermat%27s_factorization_method&oldid=1249789677</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_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_February_2022" title="Category:Articles needing additional references from February 2022">Articles needing additional references from February 2022</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_January_2015" title="Category:Articles with unsourced statements from January 2015">Articles with unsourced statements from January 2015</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 6 October 2024, at 20:53<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=Fermat%27s_factorization_method&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-zdfpm","wgBackendResponseTime":131,"wgPageParseReport":{"limitreport":{"cputime":"0.361","walltime":"0.569","ppvisitednodes":{"value":1357,"limit":1000000},"postexpandincludesize":{"value":39320,"limit":2097152},"templateargumentsize":{"value":1508,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":20894,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 377.718 1 -total"," 24.91% 94.087 1 Template:Number_theoretic_algorithms"," 24.06% 90.882 1 Template:Reflist"," 23.36% 88.223 1 Template:Navbox"," 22.04% 83.252 2 Template:Cite_journal"," 19.14% 72.290 1 Template:Refimprove"," 18.33% 69.228 1 Template:Short_description"," 17.49% 66.069 1 Template:Ambox"," 11.37% 42.948 2 Template:Pagetype"," 4.79% 18.078 1 Template:Citation_needed"]},"scribunto":{"limitreport-timeusage":{"value":"0.214","limit":"10.000"},"limitreport-memusage":{"value":5133320,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-g84kv","timestamp":"20241122155245","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Fermat's factorization method","url":"https:\/\/en.wikipedia.org\/wiki\/Fermat%27s_factorization_method","sameAs":"http:\/\/www.wikidata.org\/entity\/Q983978","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q983978","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":"2005-06-28T22:16:56Z","dateModified":"2024-10-06T20:53:06Z","headline":"integer factorization algorithm"}</script> </body> </html>