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>Frobenius pseudoprime - 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":"8e663d24-510e-4557-83d0-dba230c1151f","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Frobenius_pseudoprime","wgTitle":"Frobenius pseudoprime","wgCurRevisionId":1214574423,"wgRevisionId":1214574423,"wgArticleId":2246360,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Wikipedia articles that are too technical from August 2021","All articles that are too technical","Pseudoprimes"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Frobenius_pseudoprime","wgRelevantArticleId":2246360,"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":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q5505102","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging", "ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Frobenius pseudoprime - 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/Frobenius_pseudoprime"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Frobenius_pseudoprime&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/Frobenius_pseudoprime"> <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-Frobenius_pseudoprime rootpage-Frobenius_pseudoprime 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=Frobenius+pseudoprime" 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=Frobenius+pseudoprime" 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=Frobenius+pseudoprime" 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=Frobenius+pseudoprime" 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-Frobenius_pseudoprimes_w.r.t._quadratic_polynomials" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Frobenius_pseudoprimes_w.r.t._quadratic_polynomials"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Frobenius pseudoprimes w.r.t. quadratic polynomials</span> </div> </a> <ul id="toc-Frobenius_pseudoprimes_w.r.t._quadratic_polynomials-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Relations_to_other_pseudoprimes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relations_to_other_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Relations to other pseudoprimes</span> </div> </a> <ul id="toc-Relations_to_other_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Strong_Frobenius_pseudoprimes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Strong_Frobenius_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Strong Frobenius pseudoprimes</span> </div> </a> <ul id="toc-Strong_Frobenius_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pseudoprimality_tests" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pseudoprimality_tests"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Pseudoprimality tests</span> </div> </a> <button aria-controls="toc-Pseudoprimality_tests-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Pseudoprimality tests subsection</span> </button> <ul id="toc-Pseudoprimality_tests-sublist" class="vector-toc-list"> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Properties</span> </div> </a> <ul id="toc-Properties-sublist" class="vector-toc-list"> </ul> </li> </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-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">7</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">8</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">Frobenius pseudoprime</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 2 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-2" 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">2 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/N%C3%BAmero_pseudoprimo_de_Frobenius" title="Número pseudoprimo de Frobenius – Spanish" lang="es" hreflang="es" data-title="Número pseudoprimo de Frobenius" 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-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE_%D0%A4%D1%80%D0%BE%D0%B1%D0%B5%D0%BD%D0%B8%D1%83%D1%81%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> </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/Q5505102#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/Frobenius_pseudoprime" 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:Frobenius_pseudoprime" 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/Frobenius_pseudoprime"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Frobenius_pseudoprime&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=Frobenius_pseudoprime&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/Frobenius_pseudoprime"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Frobenius_pseudoprime&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=Frobenius_pseudoprime&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/Frobenius_pseudoprime" 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/Frobenius_pseudoprime" 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=Frobenius_pseudoprime&oldid=1214574423" 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=Frobenius_pseudoprime&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=Frobenius_pseudoprime&id=1214574423&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%2FFrobenius_pseudoprime"><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%2FFrobenius_pseudoprime"><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=Frobenius_pseudoprime&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=Frobenius_pseudoprime&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/Q5505102" 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"><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-Technical plainlinks metadata ambox ambox-style ambox-technical" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may be too technical for most readers to understand</b>.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Frobenius_pseudoprime&action=edit">help improve it</a> to <a href="/wiki/Wikipedia:Make_technical_articles_understandable" title="Wikipedia:Make technical articles understandable">make it understandable to non-experts</a>, without removing the technical details.</span> <span class="date-container"><i>(<span class="date">August 2021</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>In <a href="/wiki/Number_theory" title="Number theory">number theory</a>, a <b>Frobenius pseudoprime</b> is a <a href="/wiki/Pseudoprime" title="Pseudoprime">pseudoprime</a>, whose definition was inspired by the <a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">quadratic Frobenius test</a> described by Jon Grantham in a 1998 preprint and published in 2000.<sup id="cite_ref-Grantham98_1-0" class="reference"><a href="#cite_note-Grantham98-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Grantham01_2-0" class="reference"><a href="#cite_note-Grantham01-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Frobenius pseudoprimes can be defined with respect to <a href="/wiki/Polynomial" title="Polynomial">polynomials</a> of degree at least 2, but they have been most extensively studied in the case of <a href="/wiki/Quadratic_polynomial" class="mw-redirect" title="Quadratic polynomial">quadratic polynomials</a>.<sup id="cite_ref-CP05_3-0" class="reference"><a href="#cite_note-CP05-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Loebenberger08_4-0" class="reference"><a href="#cite_note-Loebenberger08-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Frobenius_pseudoprimes_w.r.t._quadratic_polynomials">Frobenius pseudoprimes w.r.t. quadratic polynomials</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=1" title="Edit section: Frobenius pseudoprimes w.r.t. quadratic polynomials"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The definition of Frobenius pseudoprimes with respect to a monic quadratic polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-Px+Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>P</mi> <mi>x</mi> <mo>+</mo> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-Px+Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed3a7fc86c19d60634b959fda5027ca962a0485" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.978ex; height:3.009ex;" alt="{\displaystyle x^{2}-Px+Q}"></span>, where the <a href="/wiki/Discriminant" title="Discriminant">discriminant</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 D=P^{2}-4Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mo>=</mo> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>4</mn> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D=P^{2}-4Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab28c050150ad67de72802cc6e9decdac0aec5bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.74ex; height:3.009ex;" alt="{\displaystyle D=P^{2}-4Q}"></span> is not a square, can be expressed in terms of <a href="/wiki/Lucas_sequence" title="Lucas sequence">Lucas sequences</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 U_{n}(P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>U</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U_{n}(P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9acf94bbc2c8e51474c0b61e79469aa6049fcf0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.233ex; height:2.843ex;" alt="{\displaystyle U_{n}(P,Q)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{n}(P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{n}(P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/40dfdb812d2de843618bac1786e8887494aba43e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.001ex; height:2.843ex;" alt="{\displaystyle V_{n}(P,Q)}"></span> as follows. </p><p>A <a href="/wiki/Composite_number" title="Composite number">composite number</a> <i>n</i> is a Frobenius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span> pseudoprime if and only if </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 (1)\qquad \gcd(n,2QD)=1,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mspace width="2em" /> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <mi>Q</mi> <mi>D</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1)\qquad \gcd(n,2QD)=1,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb2e420dd8c3a9d1a97b6ceef31ba7fe25f1481e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.562ex; height:2.843ex;" alt="{\displaystyle (1)\qquad \gcd(n,2QD)=1,}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mspace width="2em" /> <msub> <mi>U</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mi>δ</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>≡</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/912529fd621f5a963f0612131ff815175d7e336b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.856ex; height:2.843ex;" alt="{\displaystyle (2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},}"></span> and</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mspace width="2em" /> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mi>δ</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>≡</mo> <mn>2</mn> <msup> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>δ</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9df1fa998ff408f3ba4074273a576bc942fcf6d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.46ex; height:3.343ex;" alt="{\displaystyle (3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},}"></span></dd></dl> <p>where <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 \delta =\left({\tfrac {D}{n}}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>D</mi> <mi>n</mi> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta =\left({\tfrac {D}{n}}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a6f74ee36052e5a3789accd0ce13639c3cce2c67" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.119ex; height:4.843ex;" alt="{\displaystyle \delta =\left({\tfrac {D}{n}}\right)}"></span> is the <a href="/wiki/Jacobi_symbol" title="Jacobi symbol">Jacobi symbol</a>. </p><p>When condition (2) is satisfied, condition (3) becomes equivalent to </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 (3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msup> <mn>3</mn> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mspace width="2em" /> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>≡</mo> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9045ec1984e77d06b90be06b44351b5410d3c48d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.872ex; height:3.009ex;" alt="{\displaystyle (3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.}"></span></dd></dl> <p>Therefore, a Frobenius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span> pseudoprime <span class="texhtml mvar" style="font-style:italic;">n</span> can be equivalently defined by conditions (1-2) and (3), or by conditions (1-2) and (3′). </p><p>Since conditions (2) and (3) hold for all primes which satisfy the simple condition (1), they can be used as a <a href="/wiki/Probable_prime" title="Probable prime">probable primality</a> test. (If condition (1) fails, then either the <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> is less than <span class="texhtml mvar" style="font-style:italic;">n</span>, in which case it is a non-trivial factor and <span class="texhtml mvar" style="font-style:italic;">n</span> is composite, or the GCD equals <span class="texhtml mvar" style="font-style:italic;">n</span>, in which case one should try different parameters <span class="texhtml mvar" style="font-style:italic;">P</span> and <span class="texhtml mvar" style="font-style:italic;">Q</span> which are not multiples of <span class="texhtml mvar" style="font-style:italic;">n</span>.) </p> <div class="mw-heading mw-heading2"><h2 id="Relations_to_other_pseudoprimes">Relations to other pseudoprimes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=2" title="Edit section: Relations to other pseudoprimes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Every Frobenius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span> pseudoprime is also </p> <ul><li>a <a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a> with parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, since it is defined by conditions (1) and (2);<sup id="cite_ref-Grantham01_2-1" class="reference"><a href="#cite_note-Grantham01-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-CP05_3-1" class="reference"><a href="#cite_note-CP05-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Rotkiewicz03_5-0" class="reference"><a href="#cite_note-Rotkiewicz03-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li> <li>a <a href="/w/index.php?title=Dickson_pseudoprime&action=edit&redlink=1" class="new" title="Dickson pseudoprime (page does not exist)">Dickson pseudoprime</a> with parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, since it is defined by conditions (1) and (3');<sup id="cite_ref-Rotkiewicz03_5-1" class="reference"><a href="#cite_note-Rotkiewicz03-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li> <li>a <a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a> base <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |Q|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |Q|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9c07422812bf98ca7757bdbe3effbd2d37b3929" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.132ex; height:2.843ex;" alt="{\displaystyle |Q|}"></span> when <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 |Q|>1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |Q|>1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/849149e7d8cff53517b3509b96aeadedfb18b039" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.393ex; height:2.843ex;" alt="{\displaystyle |Q|>1}"></span>.</li></ul> <p>The converse of none of these statements is true, making the Frobenius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span> pseudoprimes a proper subset of each of the sets of Lucas pseudoprimes and Dickson pseudoprimes with parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, and Fermat pseudoprimes to base <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |Q|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |Q|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9c07422812bf98ca7757bdbe3effbd2d37b3929" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.132ex; height:2.843ex;" alt="{\displaystyle |Q|}"></span> when <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 |Q|>1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |Q|>1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/849149e7d8cff53517b3509b96aeadedfb18b039" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.393ex; height:2.843ex;" alt="{\displaystyle |Q|>1}"></span>. Furthermore, it follows that for the same parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, a composite number is a Frobenius pseudoprime if and only if it is both a Lucas and Dickson pseudoprime. In other words, for every fixed pair of parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, the set of Frobenius pseudoprimes equals the intersection of the sets of Lucas and Dickson pseudoprimes. </p><p>While each Frobenius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span> pseudoprime is a Lucas pseudoprime, it is not necessarily a <a href="/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes" title="Lucas pseudoprime">strong Lucas pseudoprime</a>. For example, 6721 is the first Frobenius pseudoprime for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)=(1,-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)=(1,-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/134ce72476e4c4a34572f383c43a76858a053712" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.502ex; height:2.843ex;" alt="{\displaystyle (P,Q)=(1,-1)}"></span>, which is not a strong Lucas pseudoprime. </p><p>Every Frobenius pseudoprime to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{3}-x-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>−</mo> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{3}-x-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa65123eda4efe4577f20f38f36efbb61d3f17f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.557ex; height:2.843ex;" alt="{\displaystyle x^{3}-x-1}"></span> is also a <a href="/wiki/Perrin_number#Perrin_primality_test" title="Perrin number">restricted Perrin pseudoprime</a>. Analogous statements hold for other cubic polynomials of the form <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{3}-rx^{2}+sx-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>−</mo> <mi>r</mi> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mi>s</mi> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{3}-rx^{2}+sx-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d68f7453270a6da52d3f037a09aa3ad117e2f6ef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:17.92ex; height:2.843ex;" alt="{\displaystyle x^{3}-rx^{2}+sx-1}"></span>.<sup id="cite_ref-Grantham01_2-2" class="reference"><a href="#cite_note-Grantham01-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=3" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Frobenius pseudoprimes with respect to the Fibonacci polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-x-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-x-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9a6454bbe84939273de34c70735b86dfcbc88e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.557ex; height:2.843ex;" alt="{\displaystyle x^{2}-x-1}"></span> are determined in terms of the <a href="/wiki/Fibonacci_numbers" class="mw-redirect" title="Fibonacci numbers">Fibonacci numbers</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{n}=U_{n}(1,-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>U</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{n}=U_{n}(1,-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f62dd65d54d501fe5a6237b88785e3da12e9975d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.594ex; height:2.843ex;" alt="{\displaystyle F_{n}=U_{n}(1,-1)}"></span> and <a href="/wiki/Lucas_numbers" class="mw-redirect" title="Lucas numbers">Lucas numbers</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 L_{n}=V_{n}(1,-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{n}=V_{n}(1,-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66bf0247e739da63c1115fd9cca17a16ffca54e7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.45ex; height:2.843ex;" alt="{\displaystyle L_{n}=V_{n}(1,-1)}"></span>. Such Frobenius pseudoprimes form the sequence: </p> <dl><dd>4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 75077, 90061, 96049, 97921, 100127, 113573, 118441, 146611, 161027, 162133, 163081, 186961, 197209, 219781, 231703, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 330929, 399001, 430127, 433621, 438751, 489601, ... (sequence <span class="nowrap external"><a href="//oeis.org/A212424" class="extiw" title="oeis:A212424">A212424</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</dd></dl> <p>While 323 is the first <a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a> with respect to the Fibonacci polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-x-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-x-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9a6454bbe84939273de34c70735b86dfcbc88e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.557ex; height:2.843ex;" alt="{\displaystyle x^{2}-x-1}"></span>, the first Frobenius pseudoprime with respect to the same polynomial is 4181 (Grantham stated it as 5777<sup id="cite_ref-Grantham01_2-3" class="reference"><a href="#cite_note-Grantham01-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> but multiple authors have noted this is incorrect and is instead the first pseudoprime 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 \left({\tfrac {5}{n}}\right)=-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>5</mn> <mi>n</mi> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\tfrac {5}{n}}\right)=-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dba770630107bd2a982cd5c0a4cfcf178692bb87" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.667ex; height:4.843ex;" alt="{\displaystyle \left({\tfrac {5}{n}}\right)=-1}"></span> for this polynomial<sup id="cite_ref-CP05_3-2" class="reference"><a href="#cite_note-CP05-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>). </p><p>Another case, Frobenius pseudoprimes with respect to the quadratic polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-3x-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>3</mn> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-3x-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aaf74a9ce99a4109a400bf6579df42e25a9f0d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.719ex; height:2.843ex;" alt="{\displaystyle x^{2}-3x-1}"></span> can be determined using the Lucas <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 (3,-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (3,-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f95a95e8b0c8668e349921a139cdddf73569b143" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.976ex; height:2.843ex;" alt="{\displaystyle (3,-1)}"></span> sequence and are: </p> <dl><dd>119, 649, 1189, 4187, 12871, 14041, 16109, 23479, 24769, 28421, 31631, 34997, 38503, 41441, 48577, 50545, 56279, 58081, 59081, 61447, 75077, 91187, 95761, 96139, 116821, 127937, 146329, 148943, 150281, 157693, 170039, 180517, 188501, 207761, 208349, 244649, 281017, 311579, 316409, 349441, 350173, 363091, 371399, 397927, 423721, 440833, 459191, 473801, 479119, 493697, ... (sequence <span class="nowrap external"><a href="//oeis.org/A327655" class="extiw" title="oeis:A327655">A327655</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <p>In this case, the first Frobenius pseudoprime with respect to the quadratic polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-3x-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>3</mn> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-3x-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aaf74a9ce99a4109a400bf6579df42e25a9f0d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.719ex; height:2.843ex;" alt="{\displaystyle x^{2}-3x-1}"></span> is 119, which is also the first Lucas pseudoprime with respect to the same polynomial. Besides, <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({\tfrac {13}{119}}\right)=-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>13</mn> <mn>119</mn> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\tfrac {13}{119}}\right)=-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9fa6dd435b62981d4d7b924ba746ca374e3f452" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.147ex; height:4.843ex;" alt="{\displaystyle \left({\tfrac {13}{119}}\right)=-1}"></span>. </p><p>The quadratic polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}-3x-5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>3</mn> <mi>x</mi> <mo>−</mo> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-3x-5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1af16b6a63ff6362210a2975138b899806c6a3c0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.719ex; height:2.843ex;" alt="{\displaystyle x^{2}-3x-5}"></span>, i.e. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)=(3,-5)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mo>−</mo> <mn>5</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)=(3,-5)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a406be395687d8d2c00d61e0a72419c716cc160" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.502ex; height:2.843ex;" alt="{\displaystyle (P,Q)=(3,-5)}"></span>, has sparser pseudoprimes as compared to many other simple quadratics. Using the same process as above, we get the sequence: </p> <dl><dd>13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781, ….</dd></dl> <p>Notice there are only 3 such pseudoprimes below 500,000, while there are many Frobenius (1, −1) and (3, −1) pseudoprimes below 500,000. </p><p>Every entry in this sequence is a <a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a> to base 5 as well as a Lucas (3, −5) pseudoprime, but the converse is not true: 642,001 is both a psp-5 and a Lucas (3,-5) pseudoprime, but is not a Frobenius (3, −5) pseudoprime. (Note that <a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a> for a <span class="texhtml">(<i>P</i>, <i>Q</i>)</span> pair need not to be a <a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a> for base |<span class="texhtml"><i>Q</i></span>|, e.g. 14209 is a Lucas (1, −3) pseudoprime, but not a Fermat pseudoprime for base 3.) </p> <div class="mw-heading mw-heading2"><h2 id="Strong_Frobenius_pseudoprimes">Strong Frobenius pseudoprimes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=4" title="Edit section: Strong Frobenius pseudoprimes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Strong Frobenius pseudoprimes are also defined.<sup id="cite_ref-Grantham01_2-4" class="reference"><a href="#cite_note-Grantham01-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Details on implementation for quadratic polynomials can be found in Crandall and Pomerance.<sup id="cite_ref-CP05_3-3" class="reference"><a href="#cite_note-CP05-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>By imposing the restrictions 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 \delta =-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta =-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/76bff9c958592b8a867d6db5bb18742122bbfcdb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.118ex; height:2.509ex;" alt="{\displaystyle \delta =-1}"></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 Q\neq \pm 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>≠</mo> <mo>±</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q\neq \pm 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4179a56883cddb4b902b380b0f856d813a4fcb28" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.907ex; height:2.676ex;" alt="{\displaystyle Q\neq \pm 1}"></span>, the authors of <sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> show how to choose <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></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 Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}"></span> such that there are only <i>five</i> odd, composite numbers 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 10^{15}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>10</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>15</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 10^{15}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f50f542aca44501ae585479ee4e36e60b11646f7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.201ex; height:2.676ex;" alt="{\displaystyle 10^{15}}"></span> for which (3) holds, that is, for which <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_{n+1}\equiv 2Q{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>≡</mo> <mn>2</mn> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4206fb2a4bf45537e39909663b41bff25064fe61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.852ex; height:2.843ex;" alt="{\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Pseudoprimality_tests">Pseudoprimality tests</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=5" title="Edit section: Pseudoprimality tests"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The conditions defining Frobenius pseudoprime can be used for testing a given number <i>n</i> for <a href="/wiki/Probable_prime" title="Probable prime">probable primality</a>. Often such tests do not rely on fixed parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.427ex; height:2.843ex;" alt="{\displaystyle (P,Q)}"></span>, but rather select them in a certain way depending on the input number <i>n</i> in order to decrease the proportion of <a href="/wiki/False_positive" class="mw-redirect" title="False positive">false positives</a>, i.e., composite numbers that pass the test. Sometimes such composite numbers are commonly called Frobenius pseudoprimes, although they may correspond to different parameters. </p><p>Using parameter selection ideas first laid out in Baillie and Wagstaff (1980)<sup id="cite_ref-lpsp_7-0" class="reference"><a href="#cite_note-lpsp-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> as part of the <a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW primality test</a> and used by Grantham in his <a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">quadratic Frobenius test</a>,<sup id="cite_ref-QFT_8-0" class="reference"><a href="#cite_note-QFT-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> one can create even better quadratic tests. In particular, it was shown that choosing parameters from <a href="/wiki/Quadratic_non-residue" class="mw-redirect" title="Quadratic non-residue">quadratic non-residues</a> modulo <i>n</i> (based on the <a href="/wiki/Jacobi_symbol" title="Jacobi symbol">Jacobi symbol</a>) makes far stronger tests, and is one reason for the success of the <a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW primality test</a>. For instance, for the parameters (<i>P</i>,2), where <i>P</i> is the first odd integer that satisfies <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({\tfrac {D}{n}}\right)=-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>D</mi> <mi>n</mi> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\tfrac {D}{n}}\right)=-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c0cd9e988f839530bccab25126e9f3e7a2389d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:11.041ex; height:4.843ex;" alt="{\displaystyle \left({\tfrac {D}{n}}\right)=-1}"></span>, there are no pseudoprimes below 2<sup>64</sup>. </p><p>Yet another test is proposed by Khashin.<sup id="cite_ref-Khashin13_9-0" class="reference"><a href="#cite_note-Khashin13-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> For a given <a href="/wiki/Square_number" title="Square number">non-square</a> number <i>n</i>, it first computes a parameter <i>c</i> as the smallest odd prime having Jacobi symbol <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({\tfrac {c}{n}}\right)=-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>c</mi> <mi>n</mi> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\tfrac {c}{n}}\right)=-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/24d93615b6f1deb447b3161aaf7637d01032d150" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.021ex; height:3.176ex;" alt="{\displaystyle \left({\tfrac {c}{n}}\right)=-1}"></span>, and then verifies the congruence: </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 (1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>c</mi> </msqrt> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>≡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>c</mi> </msqrt> </mrow> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b923edee8da1ed0db234da4e94679df9046739d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.905ex; height:3.009ex;" alt="{\displaystyle (1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}}"></span>.</dd></dl> <p>While all prime <i>n</i> pass this test, a composite <i>n</i> passes it if and only if <i>n</i> is a Frobenius pseudoprime for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,Q)=(2,1-c)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>1</mn> <mo>−</mo> <mi>c</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P,Q)=(2,1-c)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f9fc91038b85c61e3310c62bb0618b6781b0c459" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.541ex; height:2.843ex;" alt="{\displaystyle (P,Q)=(2,1-c)}"></span>. Similar to the above example, Khashin notes that no pseudoprime has been found for his test. He further shows that any that exist under 2<sup>60</sup> must have a factor less than 19 or have <i>c</i> > 128. </p> <div class="mw-heading mw-heading3"><h3 id="Properties">Properties</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=6" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The computational cost of the Frobenius pseudoprimality test with respect to quadratic polynomials is roughly three times the cost of a <a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">strong pseudoprimality</a> test (i.e. a single round of the <a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin primality test</a>), 1.5 times that of a <a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprimality</a> test, and slightly more than a <a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW primality test</a>. </p><p>Note that the quadratic Frobenius test is stronger than the Lucas test. For example, 1763 is a Lucas pseudoprime to (<i>P</i>, <i>Q</i>) = (3, –1) since <i>U</i><sub>1764</sub>(3,–1) ≡ 0 (mod 1763) (<i>U</i>(3,–1) is given in <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A006190" class="extiw" title="oeis:A006190">A006190</a></span>), and it also passes the Jacobi step since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\tfrac {13}{1763}}\right)=-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>13</mn> <mn>1763</mn> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\tfrac {13}{1763}}\right)=-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfaa802b6158db8a8f4bb52a12853fa00893213b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.969ex; height:4.843ex;" alt="{\displaystyle \left({\tfrac {13}{1763}}\right)=-1}"></span>, but it fails the Frobenius test to <i>x</i><sup>2</sup> – 3<i>x</i> – 1. This property can be clearly seen when the algorithm is formulated as shown in Crandall and Pomerance Algorithm 3.6.9<sup id="cite_ref-CP05_3-4" class="reference"><a href="#cite_note-CP05-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> or as shown by Loebenberger,<sup id="cite_ref-Loebenberger08_4-1" class="reference"><a href="#cite_note-Loebenberger08-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> as the algorithm does a Lucas test followed by an additional check for the Frobenius condition. </p><p>While the quadratic Frobenius test does not have formal error bounds beyond that of the Lucas test, it can be used as the basis for methods with much smaller error bounds. Note that these have more steps, additional requirements, and non-negligible additional computation beyond what is described on this page. It is important to note that the error bounds for these methods <b>do not apply</b> to the standard or strong Frobenius tests with fixed values of (P,Q) described on this page. </p><p>Based on this idea of pseudoprimes, algorithms with strong worst-case error bounds can be built. The <a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">quadratic Frobenius test</a>,<sup id="cite_ref-QFT_8-1" class="reference"><a href="#cite_note-QFT-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> using a quadratic Frobenius test plus other conditions, has a bound 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 {\tfrac {1}{7710}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mn>7710</mn> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{7710}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b17877547fa492ec564364b3a62b01375a760c2d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:4.124ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{7710}}}"></span>. Müller in 2001 proposed the MQFT test with bounds of essentially <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 {\tfrac {1}{131040^{t}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <msup> <mn>131040</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{131040^{t}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/873c689cad3524ca5dac7454201eec53226098c5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:6.414ex; height:4.009ex;" alt="{\displaystyle {\tfrac {1}{131040^{t}}}}"></span>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially <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 {\tfrac {256}{{331776}^{t}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>256</mn> <msup> <mrow class="MJX-TeXAtom-ORD"> <mn>331776</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {256}{{331776}^{t}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f523dea7cd27ddb288bfa7c2ee0829d30c4446f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:6.414ex; height:4.009ex;" alt="{\displaystyle {\tfrac {256}{{331776}^{t}}}}"></span>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Seysen in 2005 proposed the SQFT test with a bound 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 {\tfrac {1}{{4096}^{t}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <msup> <mrow class="MJX-TeXAtom-ORD"> <mn>4096</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{{4096}^{t}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b3c42bf9c83d8262d74faf2500c068d73790e5c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:4.77ex; height:4.009ex;" alt="{\displaystyle {\tfrac {1}{{4096}^{t}}}}"></span> and a SQFT3 test with a bound 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 {\tfrac {16}{336442^{t}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>16</mn> <msup> <mn>336442</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {16}{336442^{t}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/380a09ac3cbf749d852ff9a9797d736a9a58bf41" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:6.414ex; height:4.009ex;" alt="{\displaystyle {\tfrac {16}{336442^{t}}}}"></span>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p><p>Given the same computational effort, these offer better worst-case bounds than the commonly used <a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin primality test</a>. </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=Frobenius_pseudoprime&action=edit&section=7" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Pseudoprime" title="Pseudoprime">Pseudoprime</a></li> <li><a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a></li> <li><a href="/wiki/Ferdinand_Georg_Frobenius" title="Ferdinand Georg Frobenius">Ferdinand Georg Frobenius</a></li> <li><a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius test</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=8" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-Grantham98-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Grantham98_1-0">^</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="CITEREFGrantham1998" class="citation report cs1">Grantham, Jon (1998). <a rel="nofollow" class="external text" href="http://www.pseudoprime.com/pseudo1.ps">Frobenius pseudoprimes</a> (Report). preprint.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=Frobenius+pseudoprimes&rft.pub=preprint&rft.date=1998&rft.aulast=Grantham&rft.aufirst=Jon&rft_id=http%3A%2F%2Fwww.pseudoprime.com%2Fpseudo1.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-Grantham01-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Grantham01_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Grantham01_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Grantham01_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Grantham01_2-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Grantham01_2-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGrantham2001" class="citation journal cs1">Grantham, Jon (2001). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-00-01197-2">"Frobenius pseudoprimes"</a>. <i>Mathematics of Computation</i>. <b>70</b> (234): 873–891. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1903.06820">1903.06820</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2001MaCom..70..873G">2001MaCom..70..873G</a>. <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-00-01197-2">10.1090/S0025-5718-00-01197-2</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=Frobenius+pseudoprimes&rft.volume=70&rft.issue=234&rft.pages=873-891&rft.date=2001&rft_id=info%3Aarxiv%2F1903.06820&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-00-01197-2&rft_id=info%3Abibcode%2F2001MaCom..70..873G&rft.aulast=Grantham&rft.aufirst=Jon&rft_id=https%3A%2F%2Fdoi.org%2F10.1090%252FS0025-5718-00-01197-2&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-CP05-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-CP05_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CP05_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-CP05_3-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-CP05_3-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-CP05_3-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCrandallPomerance2005" class="citation book cs1"><a href="/wiki/Richard_Crandall" title="Richard Crandall">Crandall, Richard</a>; <a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (2005). <i>Prime numbers: A computational perspective</i> (2nd ed.). <a href="/wiki/Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-25282-7" title="Special:BookSources/978-0-387-25282-7"><bdi>978-0-387-25282-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Prime+numbers%3A+A+computational+perspective&rft.edition=2nd&rft.pub=Springer-Verlag&rft.date=2005&rft.isbn=978-0-387-25282-7&rft.aulast=Crandall&rft.aufirst=Richard&rft.au=Pomerance%2C+Carl&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-Loebenberger08-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-Loebenberger08_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Loebenberger08_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLoebenberger2008" class="citation journal cs1">Loebenberger, Daniel (2008). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2008/124.pdf">"A Simple Derivation for the Frobenius Pseudoprime Test"</a> <span class="cs1-format">(PDF)</span>. <i>IACR Cryptology ePrint Archive</i>. <b>2008</b>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IACR+Cryptology+ePrint+Archive&rft.atitle=A+Simple+Derivation+for+the+Frobenius+Pseudoprime+Test&rft.volume=2008&rft.date=2008&rft.aulast=Loebenberger&rft.aufirst=Daniel&rft_id=https%3A%2F%2Feprint.iacr.org%2F2008%2F124.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-Rotkiewicz03-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-Rotkiewicz03_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Rotkiewicz03_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRotkiewicz2003" class="citation journal cs1">Rotkiewicz, Andrzej (2003). <a rel="nofollow" class="external text" href="http://www.sbc.org.pl/Content/33711/2003_03.pdf">"Lucas and Frobenius pseudoprimes"</a> <span class="cs1-format">(PDF)</span>. <i>Annales Mathematicae Silesianae</i>. <b>17</b>. Wydawnictwo Uniwersytetu Śląskiego: 17–39.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annales+Mathematicae+Silesianae&rft.atitle=Lucas+and+Frobenius+pseudoprimes&rft.volume=17&rft.pages=17-39&rft.date=2003&rft.aulast=Rotkiewicz&rft.aufirst=Andrzej&rft_id=http%3A%2F%2Fwww.sbc.org.pl%2FContent%2F33711%2F2003_03.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRobert_BaillieAndrew_FioriSamuel_S._Wagstaff,_Jr.2021" class="citation journal cs1">Robert Baillie; Andrew Fiori; <a href="/wiki/Samuel_S._Wagstaff,_Jr." class="mw-redirect" title="Samuel S. Wagstaff, Jr.">Samuel S. Wagstaff, Jr.</a> (July 2021). "Strengthening the Baillie-PSW Primality Test". <i>Mathematics of Computation</i>. <b>90</b> (330): 1931–1955. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2006.14425">2006.14425</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fmcom%2F3616">10.1090/mcom/3616</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5718">0025-5718</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:220055722">220055722</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=Strengthening+the+Baillie-PSW+Primality+Test&rft.volume=90&rft.issue=330&rft.pages=1931-1955&rft.date=2021-07&rft_id=info%3Aarxiv%2F2006.14425&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A220055722%23id-name%3DS2CID&rft.issn=0025-5718&rft_id=info%3Adoi%2F10.1090%2Fmcom%2F3616&rft.au=Robert+Baillie&rft.au=Andrew+Fiori&rft.au=Samuel+S.+Wagstaff%2C+Jr.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-lpsp-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-lpsp_7-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBaillieWagstaff1980" class="citation journal cs1">Baillie, Robert; <a href="/wiki/Samuel_S._Wagstaff_Jr." title="Samuel S. Wagstaff Jr.">Wagstaff, Samuel S. Jr.</a> (October 1980). <a rel="nofollow" class="external text" href="http://mpqs.free.fr/LucasPseudoprimes.pdf">"Lucas Pseudoprimes"</a> <span class="cs1-format">(PDF)</span>. <i>Mathematics of Computation</i>. <b>35</b> (152): 1391–1417. <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-1980-0583518-6">10.1090/S0025-5718-1980-0583518-6</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0583518">0583518</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=Lucas+Pseudoprimes&rft.volume=35&rft.issue=152&rft.pages=1391-1417&rft.date=1980-10&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-1980-0583518-6&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D583518%23id-name%3DMR&rft.aulast=Baillie&rft.aufirst=Robert&rft.au=Wagstaff%2C+Samuel+S.+Jr.&rft_id=http%3A%2F%2Fmpqs.free.fr%2FLucasPseudoprimes.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-QFT-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-QFT_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-QFT_8-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGrantham1998" class="citation journal cs1">Grantham, Jon (1998). "A Probable Prime Test With High Confidence". <i>Journal of Number Theory</i>. <b>72</b> (1): 32–47. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1903.06823">1903.06823</a></span>. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.8827">10.1.1.56.8827</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjnth.1998.2247">10.1006/jnth.1998.2247</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119640473">119640473</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Number+Theory&rft.atitle=A+Probable+Prime+Test+With+High+Confidence&rft.volume=72&rft.issue=1&rft.pages=32-47&rft.date=1998&rft_id=info%3Aarxiv%2F1903.06823&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A119640473%23id-name%3DS2CID&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.56.8827%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1006%2Fjnth.1998.2247&rft.aulast=Grantham&rft.aufirst=Jon&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-Khashin13-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Khashin13_9-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKhashin2013" class="citation arxiv cs1">Khashin, Sergey (July 2013). "Counterexamples for Frobenius primality test". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1307.7920">1307.7920</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.NT">math.NT</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Counterexamples+for+Frobenius+primality+test&rft.date=2013-07&rft_id=info%3Aarxiv%2F1307.7920&rft.aulast=Khashin&rft.aufirst=Sergey&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMüller2001" class="citation conference cs1">Müller, Siguna (2001). "A Probable Prime Test with Very High Confidence for N Equiv 1 Mod 4". <i>Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology</i>. ASIACRYPT. pp. 87–106. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45682-1_6">10.1007/3-540-45682-1_6</a></span>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-42987-5" title="Special:BookSources/3-540-42987-5"><bdi>3-540-42987-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Probable+Prime+Test+with+Very+High+Confidence+for+N+Equiv+1+Mod+4&rft.btitle=Proceedings+of+the+7th+International+Conference+on+the+Theory+and+Application+of+Cryptology+and+Information+Security%3A+Advances+in+Cryptology&rft.pages=87-106&rft.date=2001&rft_id=info%3Adoi%2F10.1007%2F3-540-45682-1_6&rft.isbn=3-540-42987-5&rft.aulast=M%C3%BCller&rft.aufirst=Siguna&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDamgårdFrandsen2006" class="citation journal cs1"><a href="/wiki/Ivan_Damg%C3%A5rd" title="Ivan Damgård">Damgård, Ivan Bjerre</a>; Frandsen, Gudmund Skovbjerg (October 2006). <a rel="nofollow" class="external text" href="http://www.brics.dk/RS/03/9/BRICS-RS-03-9.pdf">"An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Cryptology</i>. <b>19</b> (4): 489–520. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00145-006-0332-x">10.1007/s00145-006-0332-x</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:34417193">34417193</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Cryptology&rft.atitle=An+Extended+Quadratic+Frobenius+Primality+Test+with+Average-+and+Worst-Case+Error+Estimate&rft.volume=19&rft.issue=4&rft.pages=489-520&rft.date=2006-10&rft_id=info%3Adoi%2F10.1007%2Fs00145-006-0332-x&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A34417193%23id-name%3DS2CID&rft.aulast=Damg%C3%A5rd&rft.aufirst=Ivan+Bjerre&rft.au=Frandsen%2C+Gudmund+Skovbjerg&rft_id=http%3A%2F%2Fwww.brics.dk%2FRS%2F03%2F9%2FBRICS-RS-03-9.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">Seysen, Martin. <a rel="nofollow" class="external text" href="http://eprint.iacr.org/2005/462">A Simplified Quadratic Frobenius Primality Test</a>, 2005.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Frobenius_pseudoprime&action=edit&section=9" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="citation mathworld" id="Reference-Mathworld-Frobenius_Pseudoprime"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/FrobeniusPseudoprime.html">"Frobenius Pseudoprime"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Frobenius+Pseudoprime&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FFrobeniusPseudoprime.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span></li> <li><span class="citation mathworld" id="Reference-Mathworld-Strong_Frobenius_Pseudoprime"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/StrongFrobeniusPseudoprime.html">"Strong Frobenius Pseudoprime"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Strong+Frobenius+Pseudoprime&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FStrongFrobeniusPseudoprime.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFrobenius+pseudoprime" class="Z3988"></span></span></li> <li>Jacobsen, Dana <a rel="nofollow" class="external text" href="http://ntheory.org/pseudoprimes.html">Pseudoprime Statistics, Tables, and Data</a> (data for Frobenius (1,-1) and (3,-5) pseudoprimes)</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="Classes_of_natural_numbers" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed 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:Classes_of_natural_numbers" title="Template:Classes of natural numbers"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Classes_of_natural_numbers" title="Template talk:Classes of natural numbers"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Classes_of_natural_numbers" title="Special:EditPage/Template:Classes of natural numbers"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Classes_of_natural_numbers" style="font-size:114%;margin:0 4em">Classes of <a href="/wiki/Natural_number" title="Natural number">natural numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Powers_and_related_numbers" style="font-size:114%;margin:0 4em"><a href="/wiki/Exponentiation" title="Exponentiation">Powers</a> and related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Achilles_number" title="Achilles number">Achilles</a></li> <li><a href="/wiki/Power_of_two" title="Power of two">Power of 2</a></li> <li><a href="/wiki/Power_of_three" title="Power of three">Power of 3</a></li> <li><a href="/wiki/Power_of_10" title="Power of 10">Power of 10</a></li> <li><a href="/wiki/Square_number" title="Square number">Square</a></li> <li><a href="/wiki/Cube_(algebra)" title="Cube (algebra)">Cube</a></li> <li><a href="/wiki/Fourth_power" title="Fourth power">Fourth power</a></li> <li><a href="/wiki/Fifth_power_(algebra)" title="Fifth power (algebra)">Fifth power</a></li> <li><a href="/wiki/Sixth_power" title="Sixth power">Sixth power</a></li> <li><a href="/wiki/Seventh_power" title="Seventh power">Seventh power</a></li> <li><a href="/wiki/Eighth_power" title="Eighth power">Eighth power</a></li> <li><a href="/wiki/Perfect_power" title="Perfect power">Perfect power</a></li> <li><a href="/wiki/Powerful_number" title="Powerful number">Powerful</a></li> <li><a href="/wiki/Prime_power" title="Prime power">Prime power</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Of_the_form_a_×_2b_±_1" style="font-size:114%;margin:0 4em">Of the form <i>a</i> × 2<sup><i>b</i></sup> ± 1</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cullen_number" title="Cullen number">Cullen</a></li> <li><a href="/wiki/Double_Mersenne_number" title="Double Mersenne number">Double Mersenne</a></li> <li><a href="/wiki/Fermat_number" title="Fermat number">Fermat</a></li> <li><a href="/wiki/Mersenne_prime" title="Mersenne prime">Mersenne</a></li> <li><a href="/wiki/Proth_number" class="mw-redirect" title="Proth number">Proth</a></li> <li><a href="/wiki/Thabit_number" title="Thabit number">Thabit</a></li> <li><a href="/wiki/Woodall_number" title="Woodall number">Woodall</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Other_polynomial_numbers" style="font-size:114%;margin:0 4em">Other polynomial numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Hilbert_number" title="Hilbert number">Hilbert</a></li> <li><a href="/wiki/Idoneal_number" title="Idoneal number">Idoneal</a></li> <li><a href="/wiki/Leyland_number" title="Leyland number">Leyland</a></li> <li><a href="/wiki/Loeschian_number" class="mw-redirect" title="Loeschian number">Loeschian</a></li> <li><a href="/wiki/Lucky_numbers_of_Euler" title="Lucky numbers of Euler">Lucky numbers of Euler</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Recursively_defined_numbers" style="font-size:114%;margin:0 4em"><a href="/wiki/Recursion" title="Recursion">Recursively</a> defined numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fibonacci_sequence" title="Fibonacci sequence">Fibonacci</a></li> <li><a href="/wiki/Jacobsthal_number" title="Jacobsthal number">Jacobsthal</a></li> <li><a href="/wiki/Leonardo_number" title="Leonardo number">Leonardo</a></li> <li><a href="/wiki/Lucas_number" title="Lucas number">Lucas</a></li> <li><a href="/wiki/Supergolden_ratio#Narayana_sequence" title="Supergolden ratio">Narayana</a></li> <li><a href="/wiki/Padovan_sequence" title="Padovan sequence">Padovan</a></li> <li><a href="/wiki/Pell_number" title="Pell number">Pell</a></li> <li><a href="/wiki/Perrin_number" title="Perrin number">Perrin</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Possessing_a_specific_set_of_other_numbers" style="font-size:114%;margin:0 4em">Possessing a specific set of other numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Amenable_number" title="Amenable number">Amenable</a></li> <li><a href="/wiki/Congruent_number" title="Congruent number">Congruent</a></li> <li><a href="/wiki/Kn%C3%B6del_number" title="Knödel number">Knödel</a></li> <li><a href="/wiki/Riesel_number" title="Riesel number">Riesel</a></li> <li><a href="/wiki/Sierpi%C5%84ski_number" title="Sierpiński number">Sierpiński</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Expressible_via_specific_sums" style="font-size:114%;margin:0 4em">Expressible via specific sums</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Nonhypotenuse_number" title="Nonhypotenuse number">Nonhypotenuse</a></li> <li><a href="/wiki/Polite_number" title="Polite number">Polite</a></li> <li><a href="/wiki/Practical_number" title="Practical number">Practical</a></li> <li><a href="/wiki/Primary_pseudoperfect_number" title="Primary pseudoperfect number">Primary pseudoperfect</a></li> <li><a href="/wiki/Ulam_number" title="Ulam number">Ulam</a></li> <li><a href="/wiki/Wolstenholme_number" title="Wolstenholme number">Wolstenholme</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Figurate_numbers" style="font-size:114%;margin:0 4em"><a href="/wiki/Figurate_number" title="Figurate number">Figurate numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Plane_(mathematics)" title="Plane (mathematics)">2-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Centered_polygonal_number" title="Centered polygonal number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Centered_triangular_number" title="Centered triangular number">Centered triangular</a></li> <li><a href="/wiki/Centered_square_number" title="Centered square number">Centered square</a></li> <li><a href="/wiki/Centered_pentagonal_number" title="Centered pentagonal number">Centered pentagonal</a></li> <li><a href="/wiki/Centered_hexagonal_number" title="Centered hexagonal number">Centered hexagonal</a></li> <li><a href="/wiki/Centered_heptagonal_number" title="Centered heptagonal number">Centered heptagonal</a></li> <li><a href="/wiki/Centered_octagonal_number" title="Centered octagonal number">Centered octagonal</a></li> <li><a href="/wiki/Centered_nonagonal_number" title="Centered nonagonal number">Centered nonagonal</a></li> <li><a href="/wiki/Centered_decagonal_number" title="Centered decagonal number">Centered decagonal</a></li> <li><a href="/wiki/Star_number" title="Star number">Star</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Polygonal_number" title="Polygonal number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Triangular_number" title="Triangular number">Triangular</a></li> <li><a href="/wiki/Square_number" title="Square number">Square</a></li> <li><a href="/wiki/Square_triangular_number" title="Square triangular number">Square triangular</a></li> <li><a href="/wiki/Pentagonal_number" title="Pentagonal number">Pentagonal</a></li> <li><a href="/wiki/Hexagonal_number" title="Hexagonal number">Hexagonal</a></li> <li><a href="/wiki/Heptagonal_number" title="Heptagonal number">Heptagonal</a></li> <li><a href="/wiki/Octagonal_number" title="Octagonal number">Octagonal</a></li> <li><a href="/wiki/Nonagonal_number" title="Nonagonal number">Nonagonal</a></li> <li><a href="/wiki/Decagonal_number" title="Decagonal number">Decagonal</a></li> <li><a href="/wiki/Dodecagonal_number" title="Dodecagonal number">Dodecagonal</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Three-dimensional_space" title="Three-dimensional space">3-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Centered_polyhedral_number" title="Centered polyhedral number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Centered_tetrahedral_number" title="Centered tetrahedral number">Centered tetrahedral</a></li> <li><a href="/wiki/Centered_cube_number" title="Centered cube number">Centered cube</a></li> <li><a href="/wiki/Centered_octahedral_number" title="Centered octahedral number">Centered octahedral</a></li> <li><a href="/wiki/Centered_dodecahedral_number" title="Centered dodecahedral number">Centered dodecahedral</a></li> <li><a href="/wiki/Centered_icosahedral_number" title="Centered icosahedral number">Centered icosahedral</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Polyhedral_number" class="mw-redirect" title="Polyhedral number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Tetrahedral_number" title="Tetrahedral number">Tetrahedral</a></li> <li><a href="/wiki/Cube_(algebra)" title="Cube (algebra)">Cubic</a></li> <li><a href="/wiki/Octahedral_number" title="Octahedral number">Octahedral</a></li> <li><a href="/wiki/Dodecahedral_number" title="Dodecahedral number">Dodecahedral</a></li> <li><a href="/wiki/Icosahedral_number" title="Icosahedral number">Icosahedral</a></li> <li><a href="/wiki/Stella_octangula_number" title="Stella octangula number">Stella octangula</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Pyramidal_number" title="Pyramidal number">pyramidal</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Square_pyramidal_number" title="Square pyramidal number">Square pyramidal</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Four-dimensional_space" title="Four-dimensional space">4-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">non-centered</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Pentatope_number" title="Pentatope number">Pentatope</a></li> <li><a href="/wiki/Squared_triangular_number" title="Squared triangular number">Squared triangular</a></li> <li><a href="/wiki/Fourth_power" title="Fourth power">Tesseractic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial_numbers" style="font-size:114%;margin:0 4em">Combinatorial numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bell_number" title="Bell number">Bell</a></li> <li><a href="/wiki/Cake_number" title="Cake number">Cake</a></li> <li><a href="/wiki/Catalan_number" title="Catalan number">Catalan</a></li> <li><a href="/wiki/Dedekind_number" title="Dedekind number">Dedekind</a></li> <li><a href="/wiki/Delannoy_number" title="Delannoy number">Delannoy</a></li> <li><a href="/wiki/Euler_number" class="mw-redirect" title="Euler number">Euler</a></li> <li><a href="/wiki/Eulerian_number" title="Eulerian number">Eulerian</a></li> <li><a href="/wiki/Fuss%E2%80%93Catalan_number" title="Fuss–Catalan number">Fuss–Catalan</a></li> <li><a href="/wiki/Lah_number" title="Lah number">Lah</a></li> <li><a href="/wiki/Lazy_caterer%27s_sequence" title="Lazy caterer's sequence">Lazy caterer's sequence</a></li> <li><a href="/wiki/Lobb_number" title="Lobb number">Lobb</a></li> <li><a href="/wiki/Motzkin_number" title="Motzkin number">Motzkin</a></li> <li><a href="/wiki/Narayana_number" title="Narayana number">Narayana</a></li> <li><a href="/wiki/Ordered_Bell_number" title="Ordered Bell number">Ordered Bell</a></li> <li><a href="/wiki/Schr%C3%B6der_number" title="Schröder number">Schröder</a></li> <li><a href="/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number" title="Schröder–Hipparchus number">Schröder–Hipparchus</a></li> <li><a href="/wiki/Stirling_numbers_of_the_first_kind" title="Stirling numbers of the first kind">Stirling first</a></li> <li><a href="/wiki/Stirling_numbers_of_the_second_kind" title="Stirling numbers of the second kind">Stirling second</a></li> <li><a href="/wiki/Telephone_number_(mathematics)" title="Telephone number (mathematics)">Telephone number</a></li> <li><a href="/wiki/Wedderburn%E2%80%93Etherington_number" title="Wedderburn–Etherington number">Wedderburn–Etherington</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Primes" style="font-size:114%;margin:0 4em"><a href="/wiki/Prime_number" title="Prime number">Primes</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Wieferich_prime#Wieferich_numbers" title="Wieferich prime">Wieferich</a></li> <li><a href="/wiki/Wall%E2%80%93Sun%E2%80%93Sun_prime" title="Wall–Sun–Sun prime">Wall–Sun–Sun</a></li> <li><a href="/wiki/Wolstenholme_prime" title="Wolstenholme prime">Wolstenholme prime</a></li> <li><a href="/wiki/Wilson_prime#Wilson_numbers" title="Wilson prime">Wilson</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Pseudoprimes" style="font-size:114%;margin:0 4em"><a href="/wiki/Pseudoprime" title="Pseudoprime">Pseudoprimes</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a></li> <li><a href="/wiki/Catalan_pseudoprime" title="Catalan pseudoprime">Catalan pseudoprime</a></li> <li><a href="/wiki/Elliptic_pseudoprime" title="Elliptic pseudoprime">Elliptic pseudoprime</a></li> <li><a href="/wiki/Euler_pseudoprime" title="Euler pseudoprime">Euler pseudoprime</a></li> <li><a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprime</a></li> <li><a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a></li> <li><a class="mw-selflink selflink">Frobenius pseudoprime</a></li> <li><a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a></li> <li><a href="/wiki/Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael number</a></li> <li><a href="/wiki/Perrin_number#Perrin_primality_test" title="Perrin number">Perrin pseudoprime</a></li> <li><a href="/wiki/Somer%E2%80%93Lucas_pseudoprime" title="Somer–Lucas pseudoprime">Somer–Lucas pseudoprime</a></li> <li><a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">Strong pseudoprime</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Arithmetic_functions_and_dynamics" style="font-size:114%;margin:0 4em"><a href="/wiki/Arithmetic_function" title="Arithmetic function">Arithmetic functions</a> and <a href="/wiki/Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Divisor_function" title="Divisor function">Divisor functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abundant_number" title="Abundant number">Abundant</a></li> <li><a href="/wiki/Almost_perfect_number" title="Almost perfect number">Almost perfect</a></li> <li><a href="/wiki/Arithmetic_number" title="Arithmetic number">Arithmetic</a></li> <li><a href="/wiki/Betrothed_numbers" title="Betrothed numbers">Betrothed</a></li> <li><a href="/wiki/Colossally_abundant_number" title="Colossally abundant number">Colossally abundant</a></li> <li><a href="/wiki/Deficient_number" title="Deficient number">Deficient</a></li> <li><a href="/wiki/Descartes_number" title="Descartes number">Descartes</a></li> <li><a href="/wiki/Hemiperfect_number" title="Hemiperfect number">Hemiperfect</a></li> <li><a href="/wiki/Highly_abundant_number" title="Highly abundant number">Highly abundant</a></li> <li><a href="/wiki/Highly_composite_number" title="Highly composite number">Highly composite</a></li> <li><a href="/wiki/Hyperperfect_number" title="Hyperperfect number">Hyperperfect</a></li> <li><a href="/wiki/Multiply_perfect_number" title="Multiply perfect number">Multiply perfect</a></li> <li><a href="/wiki/Perfect_number" title="Perfect number">Perfect</a></li> <li><a href="/wiki/Practical_number" title="Practical number">Practical</a></li> <li><a href="/wiki/Primitive_abundant_number" title="Primitive abundant number">Primitive abundant</a></li> <li><a href="/wiki/Quasiperfect_number" title="Quasiperfect number">Quasiperfect</a></li> <li><a href="/wiki/Refactorable_number" title="Refactorable number">Refactorable</a></li> <li><a href="/wiki/Semiperfect_number" title="Semiperfect number">Semiperfect</a></li> <li><a href="/wiki/Sublime_number" title="Sublime number">Sublime</a></li> <li><a href="/wiki/Superabundant_number" title="Superabundant number">Superabundant</a></li> <li><a href="/wiki/Superior_highly_composite_number" title="Superior highly composite number">Superior highly composite</a></li> <li><a href="/wiki/Superperfect_number" title="Superperfect number">Superperfect</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Prime_omega_function" title="Prime omega function">Prime omega functions</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Almost_prime" title="Almost prime">Almost prime</a></li> <li><a href="/wiki/Semiprime" title="Semiprime">Semiprime</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Euler%27s_totient_function" title="Euler's totient function">Euler's totient function</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Highly_cototient_number" title="Highly cototient number">Highly cototient</a></li> <li><a href="/wiki/Highly_totient_number" title="Highly totient number">Highly totient</a></li> <li><a href="/wiki/Noncototient" title="Noncototient">Noncototient</a></li> <li><a href="/wiki/Nontotient" title="Nontotient">Nontotient</a></li> <li><a href="/wiki/Perfect_totient_number" title="Perfect totient number">Perfect totient</a></li> <li><a href="/wiki/Sparsely_totient_number" title="Sparsely totient number">Sparsely totient</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Aliquot_sequence" title="Aliquot sequence">Aliquot sequences</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Amicable_numbers" title="Amicable numbers">Amicable</a></li> <li><a href="/wiki/Perfect_number" title="Perfect number">Perfect</a></li> <li><a href="/wiki/Sociable_numbers" class="mw-redirect" title="Sociable numbers">Sociable</a></li> <li><a href="/wiki/Untouchable_number" title="Untouchable number">Untouchable</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Primorial" title="Primorial">Primorial</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Euclid_number" title="Euclid number">Euclid</a></li> <li><a href="/wiki/Fortunate_number" title="Fortunate number">Fortunate</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Other_prime_factor_or_divisor_related_numbers" style="font-size:114%;margin:0 4em">Other <a href="/wiki/Prime_factor" class="mw-redirect" title="Prime factor">prime factor</a> or <a href="/wiki/Divisor" title="Divisor">divisor</a> related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Blum_integer" title="Blum integer">Blum</a></li> <li><a href="/wiki/Cyclic_number_(group_theory)" title="Cyclic number (group theory)">Cyclic</a></li> <li><a href="/wiki/Erd%C5%91s%E2%80%93Nicolas_number" title="Erdős–Nicolas number">Erdős–Nicolas</a></li> <li><a href="/wiki/Erd%C5%91s%E2%80%93Woods_number" title="Erdős–Woods number">Erdős–Woods</a></li> <li><a href="/wiki/Friendly_number" title="Friendly number">Friendly</a></li> <li><a href="/wiki/Giuga_number" title="Giuga number">Giuga</a></li> <li><a href="/wiki/Harmonic_divisor_number" title="Harmonic divisor number">Harmonic divisor</a></li> <li><a href="/wiki/Jordan%E2%80%93P%C3%B3lya_number" title="Jordan–Pólya number">Jordan–Pólya</a></li> <li><a href="/wiki/Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael</a></li> <li><a href="/wiki/Pronic_number" title="Pronic number">Pronic</a></li> <li><a href="/wiki/Regular_number" title="Regular number">Regular</a></li> <li><a href="/wiki/Rough_number" title="Rough number">Rough</a></li> <li><a href="/wiki/Smooth_number" title="Smooth number">Smooth</a></li> <li><a href="/wiki/Sphenic_number" title="Sphenic number">Sphenic</a></li> <li><a href="/wiki/St%C3%B8rmer_number" title="Størmer number">Størmer</a></li> <li><a href="/wiki/Super-Poulet_number" title="Super-Poulet number">Super-Poulet</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Numeral_system-dependent_numbers" style="font-size:114%;margin:0 4em"><a href="/wiki/Numeral_system" title="Numeral system">Numeral system</a>-dependent numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Arithmetic_function" title="Arithmetic function">Arithmetic functions</a> <br />and <a href="/wiki/Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Persistence_of_a_number" title="Persistence of a number">Persistence</a> <ul><li><a href="/wiki/Additive_persistence" class="mw-redirect" title="Additive persistence">Additive</a></li> <li><a href="/wiki/Multiplicative_persistence" class="mw-redirect" title="Multiplicative persistence">Multiplicative</a></li></ul></li></ul> </div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Digit_sum" title="Digit sum">Digit sum</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Digit_sum" title="Digit sum">Digit sum</a></li> <li><a href="/wiki/Digital_root" title="Digital root">Digital root</a></li> <li><a href="/wiki/Self_number" title="Self number">Self</a></li> <li><a href="/wiki/Sum-product_number" title="Sum-product number">Sum-product</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit product</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Multiplicative_digital_root" title="Multiplicative digital root">Multiplicative digital root</a></li> <li><a href="/wiki/Sum-product_number" title="Sum-product number">Sum-product</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coding-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Meertens_number" title="Meertens number">Meertens</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Dudeney_number" title="Dudeney number">Dudeney</a></li> <li><a href="/wiki/Factorion" title="Factorion">Factorion</a></li> <li><a href="/wiki/Kaprekar_number" title="Kaprekar number">Kaprekar</a></li> <li><a href="/wiki/Kaprekar%27s_routine" title="Kaprekar's routine">Kaprekar's constant</a></li> <li><a href="/wiki/Keith_number" title="Keith number">Keith</a></li> <li><a href="/wiki/Lychrel_number" title="Lychrel number">Lychrel</a></li> <li><a href="/wiki/Narcissistic_number" title="Narcissistic number">Narcissistic</a></li> <li><a href="/wiki/Perfect_digit-to-digit_invariant" title="Perfect digit-to-digit invariant">Perfect digit-to-digit invariant</a></li> <li><a href="/wiki/Perfect_digital_invariant" title="Perfect digital invariant">Perfect digital invariant</a> <ul><li><a href="/wiki/Happy_number" title="Happy number">Happy</a></li></ul></li></ul> </div></td></tr></tbody></table><div> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/P-adic_numbers" class="mw-redirect" title="P-adic numbers">P-adic numbers</a>-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Automorphic_number" title="Automorphic number">Automorphic</a> <ul><li><a href="/wiki/Trimorphic_number" class="mw-redirect" title="Trimorphic number">Trimorphic</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Numerical_digit" title="Numerical digit">Digit</a>-composition related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Palindromic_number" title="Palindromic number">Palindromic</a></li> <li><a href="/wiki/Pandigital_number" title="Pandigital number">Pandigital</a></li> <li><a href="/wiki/Repdigit" title="Repdigit">Repdigit</a></li> <li><a href="/wiki/Repunit" title="Repunit">Repunit</a></li> <li><a href="/wiki/Self-descriptive_number" title="Self-descriptive number">Self-descriptive</a></li> <li><a href="/wiki/Smarandache%E2%80%93Wellin_number" title="Smarandache–Wellin number">Smarandache–Wellin</a></li> <li><a href="/wiki/Undulating_number" title="Undulating number">Undulating</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit-<a href="/wiki/Permutation" title="Permutation">permutation</a> related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cyclic_number" title="Cyclic number">Cyclic</a></li> <li><a href="/wiki/Digit-reassembly_number" title="Digit-reassembly number">Digit-reassembly</a></li> <li><a href="/wiki/Parasitic_number" title="Parasitic number">Parasitic</a></li> <li><a href="/wiki/Primeval_number" title="Primeval number">Primeval</a></li> <li><a href="/wiki/Transposable_integer" title="Transposable integer">Transposable</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Divisor-related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Equidigital_number" title="Equidigital number">Equidigital</a></li> <li><a href="/wiki/Extravagant_number" title="Extravagant number">Extravagant</a></li> <li><a href="/wiki/Frugal_number" title="Frugal number">Frugal</a></li> <li><a href="/wiki/Harshad_number" title="Harshad number">Harshad</a></li> <li><a href="/wiki/Polydivisible_number" title="Polydivisible number">Polydivisible</a></li> <li><a href="/wiki/Smith_number" title="Smith number">Smith</a></li> <li><a href="/wiki/Vampire_number" title="Vampire number">Vampire</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Friedman_number" title="Friedman number">Friedman</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Binary_numbers" style="font-size:114%;margin:0 4em"><a href="/wiki/Binary_number" title="Binary number">Binary numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Evil_number" title="Evil number">Evil</a></li> <li><a href="/wiki/Odious_number" title="Odious number">Odious</a></li> <li><a href="/wiki/Pernicious_number" title="Pernicious number">Pernicious</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Generated_via_a_sieve" style="font-size:114%;margin:0 4em">Generated via a <a href="/wiki/Sieve_theory" title="Sieve theory">sieve</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Lucky_number" title="Lucky number">Lucky</a></li> <li><a href="/wiki/Generation_of_primes" title="Generation of primes">Prime</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Sorting_related" style="font-size:114%;margin:0 4em"><a href="/wiki/Sorting_algorithm" title="Sorting algorithm">Sorting</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Pancake_sorting" title="Pancake sorting">Pancake number</a></li> <li><a href="/wiki/Sorting_number" title="Sorting number">Sorting number</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Natural_language_related" style="font-size:114%;margin:0 4em"><a href="/wiki/Natural_language" title="Natural language">Natural language</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aronson%27s_sequence" title="Aronson's sequence">Aronson's sequence</a></li> <li><a href="/wiki/Ban_number" title="Ban number">Ban</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Graphemics_related" style="font-size:114%;margin:0 4em"><a href="/wiki/Graphemics" title="Graphemics">Graphemics</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Strobogrammatic_number" title="Strobogrammatic number">Strobogrammatic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2" style="font-weight:bold;"><div> <ul><li><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Symbol_portal_class.svg" class="mw-file-description" title="Portal"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/16px-Symbol_portal_class.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/23px-Symbol_portal_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/31px-Symbol_portal_class.svg.png 2x" data-file-width="180" data-file-height="185" /></a></span> <a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></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=Frobenius_pseudoprime&oldid=1214574423">https://en.wikipedia.org/w/index.php?title=Frobenius_pseudoprime&oldid=1214574423</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:Pseudoprimes" title="Category:Pseudoprimes">Pseudoprimes</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:Wikipedia_articles_that_are_too_technical_from_August_2021" title="Category:Wikipedia articles that are too technical from August 2021">Wikipedia articles that are too technical from August 2021</a></li><li><a href="/wiki/Category:All_articles_that_are_too_technical" title="Category:All articles that are too technical">All articles that are too technical</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 19 March 2024, at 20:00<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=Frobenius_pseudoprime&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-6b7f745dd4-8kfr9","wgBackendResponseTime":144,"wgPageParseReport":{"limitreport":{"cputime":"0.481","walltime":"0.712","ppvisitednodes":{"value":1878,"limit":1000000},"postexpandincludesize":{"value":137192,"limit":2097152},"templateargumentsize":{"value":543,"limit":2097152},"expansiondepth":{"value":8,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":60841,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 459.416 1 -total"," 35.97% 165.270 1 Template:Reflist"," 31.05% 142.658 1 Template:Classes_of_natural_numbers"," 30.45% 139.875 1 Template:Navbox_with_collapsible_groups"," 18.35% 84.322 1 Template:Cite_report"," 15.02% 68.995 1 Template:Technical"," 11.53% 52.965 1 Template:Ambox"," 8.18% 37.597 2 Template:MathWorld"," 8.01% 36.788 7 Template:Cite_journal"," 4.01% 18.418 7 Template:Navbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.258","limit":"10.000"},"limitreport-memusage":{"value":4827288,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-k62c7","timestamp":"20241123165956","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Frobenius pseudoprime","url":"https:\/\/en.wikipedia.org\/wiki\/Frobenius_pseudoprime","sameAs":"http:\/\/www.wikidata.org\/entity\/Q5505102","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q5505102","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-07-16T14:38:50Z","dateModified":"2024-03-19T20:00:11Z"}</script> </body> </html>