CINXE.COM

<!DOCTYPE html> <html class="client-nojs" lang="de" dir="ltr"> <head> <meta charset="UTF-8"> <title>Kettenbruchmethode – Wikipedia</title> <script>(function(){var className="client-js";var cookie=document.cookie.match(/(?:^|; )dewikimwclientpreferences=([^;]+)/);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":[",\t.",".\t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","Januar","Februar","März","April","Mai","Juni","Juli","August","September","Oktober","November","Dezember"],"wgRequestId":"5e16b7d7-e807-4e3e-8370-79b2e22beda7","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Kettenbruchmethode","wgTitle":"Kettenbruchmethode","wgCurRevisionId":201780070,"wgRevisionId":201780070,"wgArticleId":981713,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"], "wgCategories":["Faktorbasisverfahren"],"wgPageViewLanguage":"de","wgPageContentLanguage":"de","wgPageContentModel":"wikitext","wgRelevantPageName":"Kettenbruchmethode","wgRelevantArticleId":981713,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgFlaggedRevsParams":{"tags":{"accuracy":{"levels":1}}},"wgStableRevisionId":201780070,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"de","pageLanguageDir":"ltr","pageVariantFallbacks":"de"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":8000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgVector2022LanguageInHeader":false, "wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1739928","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.citeRef":"ready","ext.gadget.defaultPlainlinks":"ready","ext.gadget.dewikiCommonHide":"ready","ext.gadget.dewikiCommonLayout":"ready","ext.gadget.dewikiCommonStyle":"ready","ext.gadget.NavFrame":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","skins.vector.styles.legacy":"ready","ext.flaggedRevs.basic":"ready","mediawiki.codex.messagebox.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","codex-search-styles":"ready", "ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","mediawiki.toc","skins.vector.legacy.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.createNewSection","ext.gadget.WikiMiniAtlas","ext.gadget.OpenStreetMap","ext.gadget.CommonsDirekt","ext.gadget.donateLink","ext.urlShortener.toolbar","ext.centralauth.centralautologin","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.compactlinks","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.checkUser.clientHints","ext.quicksurveys.init","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=de&modules=codex-search-styles%7Cext.flaggedRevs.basic%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cmediawiki.codex.messagebox.styles%7Cskins.vector.styles.legacy%7Cwikibase.client.init&only=styles&skin=vector"> <script async="" src="/w/load.php?lang=de&modules=startup&only=scripts&raw=1&skin=vector"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=de&modules=ext.gadget.NavFrame%2CciteRef%2CdefaultPlainlinks%2CdewikiCommonHide%2CdewikiCommonLayout%2CdewikiCommonStyle&only=styles&skin=vector"> <link rel="stylesheet" href="/w/load.php?lang=de&modules=site.styles&only=styles&skin=vector"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <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="Kettenbruchmethode – Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//de.m.wikipedia.org/wiki/Kettenbruchmethode"> <link rel="alternate" type="application/x-wiki" title="Seite bearbeiten" href="/w/index.php?title=Kettenbruchmethode&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 (de)"> <link rel="EditURI" type="application/rsd+xml" href="//de.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://de.wikipedia.org/wiki/Kettenbruchmethode"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de"> <link rel="alternate" type="application/atom+xml" title="Atom-Feed für „Wikipedia“" href="/w/index.php?title=Spezial:Letzte_%C3%84nderungen&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin-vector-legacy mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Kettenbruchmethode rootpage-Kettenbruchmethode skin-vector action-view"><div id="mw-page-base" class="noprint"></div> <div id="mw-head-base" class="noprint"></div> <div id="content" class="mw-body" role="main"> <a id="top"></a> <div id="siteNotice"></div> <div class="mw-indicators"> </div> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Kettenbruchmethode</span></h1> <div id="bodyContent" class="vector-body"> <div id="siteSub" class="noprint">aus Wikipedia, der freien Enzyklopädie</div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="contentSub2"></div> <div id="jump-to-nav"></div> <a class="mw-jump-link" href="#mw-head">Zur Navigation springen</a> <a class="mw-jump-link" href="#searchInput">Zur Suche springen</a> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Die <b>Kettenbruchmethode</b> (Abk.: <b>CFRAC</b>) berechnet zwei <a href="/wiki/Teilbarkeit" title="Teilbarkeit">Teiler</a> einer <a href="/wiki/Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahl</a>, die keine <a href="/wiki/Primzahl" title="Primzahl">Primzahl</a> ist. Durch wiederholte Anwendung lässt sich so die <a href="/wiki/Primfaktorzerlegung" title="Primfaktorzerlegung">Primfaktorzerlegung</a> dieser Zahl ermitteln. </p><p>Die Kettenbruchmethode wurde 1931 von <a href="/wiki/Derrick_Henry_Lehmer" title="Derrick Henry Lehmer">Derrick Henry Lehmer</a> und dem Mathematik-Liebhaber <a href="/w/index.php?title=Ralph_Ernest_Powers&action=edit&redlink=1" class="new" title="Ralph Ernest Powers (Seite nicht vorhanden)">Ralph Ernest Powers</a> veröffentlicht, der auch durch zahlentheoretische Rechenergebnisse bekannt ist. Über Jahrzehnte hinweg wurde sie kaum verwendet, da sie auf den zur Verfügung stehenden Rechenmaschinen häufig nach mehreren Stunden noch keine Faktorisierung fand. Im Jahr 1970 programmierten Michael Morrison und <a href="/wiki/John_Brillhart" title="John Brillhart">John Brillhart</a> die Kettenbruchmethode auf einem <a href="/wiki/Gro%C3%9Frechner" title="Großrechner">Großrechner</a> und berechneten damit die Faktorisierung der siebten <a href="/wiki/Fermat-Zahl" title="Fermat-Zahl">Fermat-Zahl</a>. In den achtziger Jahren war die Kettenbruchmethode das Standardverfahren für die Faktorisierung großer Zahlen. Das waren damals Zahlen mit bis zu fünfzig Dezimalstellen. 1990 wurde mit dem <a href="/wiki/Quadratisches_Sieb" title="Quadratisches Sieb">quadratischen Sieb</a> ein neuer Algorithmus vorgestellt, der die Nachfolge der Kettenbruchmethode antrat. Die <a href="/wiki/Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> der Kettenbruchmethode in <a href="/wiki/Landau-Symbole" title="Landau-Symbole">O-Notation</a> ist <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mrow> <mo>(</mo> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> </msqrt> </mrow> </msup> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/189bb7e25c87a1690084dbb548ba93cf16a34332" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:19.875ex; height:4.843ex;" alt="{\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}"></span>, wobei <i>N</i> die zu faktorisierende Zahl ist. </p> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="de" dir="ltr"><h2 id="mw-toc-heading">Inhaltsverzeichnis</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Funktionsweise"><span class="tocnumber">1</span> <span class="toctext">Funktionsweise</span></a></li> <li class="toclevel-1 tocsection-2"><a href="#Algorithmus_nach_Morrison_und_Brillhart"><span class="tocnumber">2</span> <span class="toctext">Algorithmus nach Morrison und Brillhart</span></a> <ul> <li class="toclevel-2 tocsection-3"><a href="#Schritt_A"><span class="tocnumber">2.1</span> <span class="toctext">Schritt A</span></a></li> <li class="toclevel-2 tocsection-4"><a href="#Schritt_B"><span class="tocnumber">2.2</span> <span class="toctext">Schritt B</span></a></li> <li class="toclevel-2 tocsection-5"><a href="#Schritt_C"><span class="tocnumber">2.3</span> <span class="toctext">Schritt C</span></a></li> </ul> </li> <li class="toclevel-1 tocsection-6"><a href="#Geschichte"><span class="tocnumber">3</span> <span class="toctext">Geschichte</span></a></li> <li class="toclevel-1 tocsection-7"><a href="#Literatur"><span class="tocnumber">4</span> <span class="toctext">Literatur</span></a></li> </ul> </div> <div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=1" title="Abschnitt bearbeiten: Funktionsweise" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=1" title="Quellcode des Abschnitts bearbeiten: Funktionsweise"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Der Algorithmus sucht eine <a href="/wiki/Kongruenz_(Zahlentheorie)" title="Kongruenz (Zahlentheorie)">Kongruenz</a> der Form <i>x</i><sup>2</sup> ≡ <i>y</i><sup>2</sup> (mod <i>N</i>). Um diese zu finden, multipliziert er geeignete Kongruenzen der Form <i>x</i><sup>2</sup> ≡ <i>y</i> (mod <i>N</i>). Solche Kongruenzen führen zu einer Faktorisierung von <i>N</i> (genauer beschrieben im Artikel <a href="/wiki/Dixons_Faktorisierungsmethode" title="Dixons Faktorisierungsmethode">Dixons Faktorisierungsmethode</a>.) </p><p>Bei der Kettenbruchmethode nutzt man die Kettenbruchentwicklung von <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3d8948b2c154ccc7f7523b035ae7e254e04190" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}"></span>, um solche Kongruenzen zu finden. Die Kettenbruchentwicklung liefert <a href="/wiki/Kettenbruch#Beste_Näherungen" title="Kettenbruch">beste Näherungen</a> der Wurzel von <i>N</i> als Brüche der 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 {\frac {p}{q}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>p</mi> <mi>q</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {p}{q}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e9903bc1de26879e5fc4c7f78b54b952bcbb800f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:2.006ex; height:5.343ex;" alt="{\displaystyle {\frac {p}{q}}}"></span>. Jede Näherung liefert eine Kongruenz <i>x</i><sup>2</sup> ≡ <i>y</i> (mod <i>N</i>) für <i>x</i> = <i>p</i> und <i>y</i> = <i>x</i><sup>2</sup> − <i>q</i><sup>2</sup> · <i>N.</i> Da der Bruch eine beste Näherung für <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {N}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3d8948b2c154ccc7f7523b035ae7e254e04190" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}"></span> ist, ist <i>y</i> klein und mit hoher Wahrscheinlichkeit <a href="/wiki/Glatte_Zahl" title="Glatte Zahl">glatt</a> und man braucht nur wenige solcher Kongruenzen. </p> <div class="mw-heading mw-heading2"><h2 id="Algorithmus_nach_Morrison_und_Brillhart">Algorithmus nach Morrison und Brillhart</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=2" title="Abschnitt bearbeiten: Algorithmus nach Morrison und Brillhart" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=2" title="Quellcode des Abschnitts bearbeiten: Algorithmus nach Morrison und Brillhart"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Die hier beschriebene Variante der Kettenbruchmethode entspricht derjenigen, die von Morrison und Brillhart in ihrem Aufsatz „A Method of Factoring and the Factorization 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 F_{7}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>7</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{7}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3d649c0c1ff6141f1db35d5efe5ad244ea1199c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{7}}"></span>“ veröffentlicht wurde. Der <a href="/wiki/Algorithmus" title="Algorithmus">Algorithmus</a> besteht aus drei wesentlichen Schritten. Die zu faktorisierende Zahl wird im Weiteren mit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> bezeichnet. </p> <div class="mw-heading mw-heading3"><h3 id="Schritt_A">Schritt A</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=3" title="Abschnitt bearbeiten: Schritt A" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=3" title="Quellcode des Abschnitts bearbeiten: Schritt A"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Wähle eine natürliche Zahl <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≥</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\geq 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d30d7dcf305b7bce39d36df72fe3985b47aa9961" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 1}"></span> und berechne die <a href="/wiki/Kettenbruch" title="Kettenbruch">Kettenbruchentwicklung</a> von <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {kN}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>k</mi> <mi>N</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {kN}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/40f8f0d08c4ba2074cd7e14bf87342b2ab24ef93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.211ex; height:3.009ex;" alt="{\displaystyle {\sqrt {kN}}}"></span>. Die Kettenbruchentwicklung kann an einer beliebigen Stelle <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}"></span> abgebrochen werden, sodass man einen Kettenbruch der Form </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 [q_{0};q_{1},q_{2},\ldots ,q_{n-1},{\frac {{\sqrt {kN}}+P_{n}}{Q_{n}}}]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>;</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>k</mi> <mi>N</mi> </msqrt> </mrow> <mo>+</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mrow> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mfrac> </mrow> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [q_{0};q_{1},q_{2},\ldots ,q_{n-1},{\frac {{\sqrt {kN}}+P_{n}}{Q_{n}}}]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b075b82ebc1634818930986a278b5266c4ce46f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:31.802ex; height:6.343ex;" alt="{\displaystyle [q_{0};q_{1},q_{2},\ldots ,q_{n-1},{\frac {{\sqrt {kN}}+P_{n}}{Q_{n}}}]}"></span></dd></dl> <p>erhält. Man berechnet nun die Paare <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A_{i-1},Q_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (A_{i-1},Q_{i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6af15535e406ad7bd4945516b5a475e4cae93a12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.125ex; height:2.843ex;" alt="{\displaystyle (A_{i-1},Q_{i})}"></span>, wobei <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1aed3b5def921afbe6cc48aaf8f9b11c6f1c1e2d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.543ex; height:2.509ex;" alt="{\displaystyle A_{i}}"></span> der Zähler und <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/82cda0578ec6b48774c541ecb9bee4a90176e62f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle B_{i}}"></span> der Nenner der <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 i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>-ten <a href="/wiki/Kettenbruch#Endliche_Kettenbrüche_und_ihre_Näherungsbrüche" title="Kettenbruch">Konvergente</a> sind und sich <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_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9f7193081d440425e522698e80817b5d558df03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.638ex; height:2.509ex;" alt="{\displaystyle Q_{i}}"></span> nach der Formel </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 Q_{i}=(-1)^{i}\cdot (A_{i-1}^{2}-kNB_{i-1}^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>⋅</mo> <mo stretchy="false">(</mo> <msubsup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> <mo>−</mo> <mi>k</mi> <mi>N</mi> <msubsup> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q_{i}=(-1)^{i}\cdot (A_{i-1}^{2}-kNB_{i-1}^{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1de72130b5e545d5543cfb4ad366e934d169b7a3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:30.227ex; height:3.509ex;" alt="{\displaystyle Q_{i}=(-1)^{i}\cdot (A_{i-1}^{2}-kNB_{i-1}^{2})}"></span></dd></dl> <p>berechnet. </p> <div class="mw-heading mw-heading3"><h3 id="Schritt_B">Schritt B</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=4" title="Abschnitt bearbeiten: Schritt B" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=4" title="Quellcode des Abschnitts bearbeiten: Schritt B"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Aus den in Schritt A erzeugten <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>A</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (A,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85ee54a2d069df3b1b65565ce1e3685295c2dffe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.425ex; height:2.843ex;" alt="{\displaystyle (A,Q)}"></span>-Paaren werden diejenigen ausgewählt, bei denen alle Primfaktoren von <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> einer vorher festgelegten Faktorbasis entstammen. Die Faktorbasis enthält üblicherweise die Zahl −1 und alle Primzahlen, die Teiler von <i>Q</i> sein können, bis zu einer bestimmten Schranke. Man braucht nur die Primzahlen <i>p</i> mit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d62e4100b94c1939c67f2d4b8580d26c78106c44" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.52ex; height:2.509ex;" alt="{\displaystyle p=2}"></span> oder <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 (kN)^{(p-1)/2}\,{\bmod {\;}}p\leq 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>k</mi> <mi>N</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mspace width="thinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mo lspace="thickmathspace" rspace="thickmathspace">mod</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="thickmathspace" /> </mrow> </mrow> <mi>p</mi> <mo>≤</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (kN)^{(p-1)/2}\,{\bmod {\;}}p\leq 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ceec9bb0dbc01e1d41f077fcc96949fc338f8c0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.311ex; height:3.343ex;" alt="{\displaystyle (kN)^{(p-1)/2}\,{\bmod {\;}}p\leq 1}"></span> in die Faktorbasis aufzunehmen, denn <i>Q</i> kann nur durch diese <i>p</i> teilbar sein. </p><p>Durch mehrfache <a href="/wiki/Probedivision" title="Probedivision">Probedivision</a> lässt sich feststellen, ob das jeweilige <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> ein Produkt von Zahlen aus der Faktorbasis ist, und nebenbei erhält man die Primfaktorzerlegung von <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>. </p><p>Mit den ausgewählten <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,Q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>A</mi> <mo>,</mo> <mi>Q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (A,Q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85ee54a2d069df3b1b65565ce1e3685295c2dffe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.425ex; height:2.843ex;" alt="{\displaystyle (A,Q)}"></span>-Paaren füllt man eine Tabelle. Diese Tabelle enthält eine Spalte für jede Zahl der Faktorbasis. In die Faktorbasisspalten wird die Zahl 1 eingetragen, wenn der jeweilige Faktor in der Primzahlzerlegung von <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> ungerade oft vorkommt. Andernfalls trägt man 0 ein. Der Tabelleneintrag für das Paar <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 (375,-220=-1\cdot 2^{2}\cdot 5\cdot 11)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>375</mn> <mo>,</mo> <mo>−</mo> <mn>220</mn> <mo>=</mo> <mo>−</mo> <mn>1</mn> <mo>⋅</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <mn>5</mn> <mo>⋅</mo> <mn>11</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (375,-220=-1\cdot 2^{2}\cdot 5\cdot 11)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b8ba18366bb991c72748ab1f032a10eb21f523e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.437ex; height:3.176ex;" alt="{\displaystyle (375,-220=-1\cdot 2^{2}\cdot 5\cdot 11)}"></span> und die Faktorbasis <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,2,3,5,7,11,13\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mo>−</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>,</mo> <mn>11</mn> <mo>,</mo> <mn>13</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{-1,2,3,5,7,11,13\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b8c6c7356695d508c657d33b75757c65c8b5a50" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.799ex; height:2.843ex;" alt="{\displaystyle \{-1,2,3,5,7,11,13\}}"></span> sieht beispielsweise wie folgt aus: </p> <table class="wikitable"> <tbody><tr class="hintergrundfarbe5"> <th></th> <th>−1</th> <th>2</th> <th>3</th> <th>5</th> <th>7</th> <th>11</th> <th>13 </th></tr> <tr> <td class="hintergrundfarbe5">(375, −220)</td> <td>1</td> <td>0</td> <td>0</td> <td>1</td> <td>0</td> <td>1</td> <td>0 </td></tr></tbody></table> <p>Dann bestimmt man eine Auswahl von Tabellenzeilen, für die die Summe der Einträge in jeder Tabellenspalte gerade ist, sodass das Produkt der <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> der ausgewählten Zeilen jeden Faktor mit einer geraden Potenz enthält und somit eine Quadratzahl ist. Das ist sicher dann möglich, wenn die Zahl der Tabellenzeilen mindestens um eins größer ist als die Zahl der Faktoren in der Faktorbasis und damit der Tabellenspalten. </p> <div class="mw-heading mw-heading3"><h3 id="Schritt_C">Schritt C</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=5" title="Abschnitt bearbeiten: Schritt C" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=5" title="Quellcode des Abschnitts bearbeiten: Schritt C"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Man multipliziert die A aller Paare und die Q aller Paare der ausgewählten Tabellenzeilen. So erhält man die <a href="/wiki/Legendre-Kongruenz" title="Legendre-Kongruenz">Legendre-Kongruenz</a> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}=\prod A^{2}\equiv \prod Q=y^{2}\;({\bmod {\,}}N)}"> <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> <mo>∏</mo> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mo>∏</mo> <mi>Q</mi> <mo>=</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo lspace="thickmathspace" rspace="thickmathspace">mod</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="thinmathspace" /> </mrow> </mrow> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}=\prod A^{2}\equiv \prod Q=y^{2}\;({\bmod {\,}}N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44c5d50233f19c6985fd403e1d1eabc137b91395" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:35.829ex; height:3.843ex;" alt="{\displaystyle x^{2}=\prod A^{2}\equiv \prod Q=y^{2}\;({\bmod {\,}}N)}"></span>.</dd></dl> <p>Man berechnet dann <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_{1}=\operatorname {ggT} (x-y,N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>ggT</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <mi>y</mi> <mo>,</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d_{1}=\operatorname {ggT} (x-y,N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/77ecc847a08138dc2e20f34344b230c71882d8b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.597ex; height:2.843ex;" alt="{\displaystyle d_{1}=\operatorname {ggT} (x-y,N)}"></span> und <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_{2}=\operatorname {ggT} (x+y,N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mi>ggT</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mi>y</mi> <mo>,</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d_{2}=\operatorname {ggT} (x+y,N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b6077b9532b39acbcba38ab33885717e2b2b22cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.597ex; height:2.843ex;" alt="{\displaystyle d_{2}=\operatorname {ggT} (x+y,N)}"></span>. </p><p>Wenn <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\not \equiv y\;({\bmod {\,}}N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>≢</mo> <mi>y</mi> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo lspace="thickmathspace" rspace="thickmathspace">mod</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="thinmathspace" /> </mrow> </mrow> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\not \equiv y\;({\bmod {\,}}N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2420ed73eaa21b36d9612fc7f52bb8cb5beb0c57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.171ex; height:2.843ex;" alt="{\displaystyle x\not \equiv y\;({\bmod {\,}}N)}"></span> und <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\not \equiv -y\;({\bmod {\,}}N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>≢</mo> <mo>−</mo> <mi>y</mi> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo lspace="thickmathspace" rspace="thickmathspace">mod</mo> <mrow class="MJX-TeXAtom-ORD"> <mspace width="thinmathspace" /> </mrow> </mrow> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\not \equiv -y\;({\bmod {\,}}N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea478c51b28a2bebe1a85cc5ec95f03179bd51e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.979ex; height:2.843ex;" alt="{\displaystyle x\not \equiv -y\;({\bmod {\,}}N)}"></span>, dann sind <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cccb5a6a2f1acab4ca255e0be86c224ed82282a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.263ex; height:2.509ex;" alt="{\displaystyle d_{1}}"></span> und <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9276f8f68c5c23329de74ad76e69f6801358fb1f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.263ex; height:2.509ex;" alt="{\displaystyle d_{2}}"></span> echte Teiler von <i>N.</i> Anderenfalls kann eine andere Auswahl von Tabellenzeilen erfolgreich sein. Ggfs. muss man noch weitere Zeilen berechnen. </p> <div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=6" title="Abschnitt bearbeiten: Geschichte" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=6" title="Quellcode des Abschnitts bearbeiten: Geschichte"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Der erste Schritt auf dem Weg zur Kettenbruchmethode war die 1643 von <a href="/wiki/Pierre_de_Fermat" title="Pierre de Fermat">Pierre de Fermat</a> beschriebene <a href="/wiki/Faktorisierungsmethode_von_Fermat" title="Faktorisierungsmethode von Fermat">Faktorisierungsmethode von Fermat</a>. Dieses Rechenverfahren findet zwei Quadratzahlen <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}}"> <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> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf0bf28fd28f45d07e1ceb909ce333c18c558c93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}"></span> und <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/888453430f9613fcab7a4ec7a3dfd75260d51427" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.215ex; height:3.009ex;" alt="{\displaystyle y^{2}}"></span>, sodass <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}-y^{2}=N}"> <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> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-y^{2}=N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/900c951fe9fbe54ffab480043052c9f1522007ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.601ex; height:3.009ex;" alt="{\displaystyle x^{2}-y^{2}=N}"></span> gilt. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> ist auch hier wieder die zu faktorisierende Zahl. Aufgrund der <a href="/wiki/Binomische_Formeln" title="Binomische Formeln">3. Binomischen Formel</a> gilt </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/749f08332768b2f27c0ca018b7d9455f339cb73e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.969ex; height:3.176ex;" alt="{\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}"></span></dd></dl> <p>und <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+y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>+</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x+y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffb4441dccedb5ede51a213408b17cf83eec9a27" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.326ex; height:2.343ex;" alt="{\displaystyle x+y}"></span> und <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-y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>−</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x-y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3129cb3620bd9f38d0304a0fca719644d7d2d265" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.326ex; height:2.343ex;" alt="{\displaystyle x-y}"></span> sind deshalb Teiler von <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>. </p><p>1798 veröffentlichte <a href="/wiki/Adrien-Marie_Legendre" title="Adrien-Marie Legendre">Adrien-Marie Legendre</a> sein Buch „Essai sur la théorie des nombres“. In diesem findet sich mit den <i>Legendre-Kongruenzen</i> eine Weiterentwicklung der Methode von Fermat. Die Differenz der Quadratzahlen <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}}"> <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> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf0bf28fd28f45d07e1ceb909ce333c18c558c93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}"></span> und <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/888453430f9613fcab7a4ec7a3dfd75260d51427" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.215ex; height:3.009ex;" alt="{\displaystyle y^{2}}"></span> muss nicht mehr gleich <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> sein, sondern kann ein beliebiges Vielfaches von <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> sein. Die Wurzeln <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span> und <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}"></span> der Quadratzahlen müssen zudem drei Bedingungen erfüllen: <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 0<x,y<N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo><</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo><</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0<x,y<N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a375b1e313d2b1ffe9900652335a63e06a1c6428" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.942ex; height:2.509ex;" alt="{\displaystyle 0<x,y<N}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\neq y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>≠</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\neq y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f51b711ca7f932963cdb268b0817dc72d6258733" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.584ex; height:2.676ex;" alt="{\displaystyle x\neq y}"></span> und <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+y\neq N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>+</mo> <mi>y</mi> <mo>≠</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x+y\neq N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a4995d7a1264760d63c0ec0b3afd7f18953eeda" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.488ex; height:2.676ex;" alt="{\displaystyle x+y\neq N}"></span>. Unter diesen Voraussetzungen ist <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> ein Teiler von <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}-y^{2}=(x+y)(x-y)}"> <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> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{2}-y^{2}=(x+y)(x-y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6364fdb9e9d31860302d0d4dd231cc4f06e992c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.807ex; height:3.176ex;" alt="{\displaystyle x^{2}-y^{2}=(x+y)(x-y)}"></span> und sowohl der größte gemeinsame Teiler <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 \operatorname {ggT} (N,x+y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ggT</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>,</mo> <mi>x</mi> <mo>+</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \operatorname {ggT} (N,x+y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/114adedbaf11ec4924656493221318ba0ac7f879" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.235ex; height:2.843ex;" alt="{\displaystyle \operatorname {ggT} (N,x+y)}"></span> als auch <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 \operatorname {ggT} (N,x-y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ggT</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>,</mo> <mi>x</mi> <mo>−</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \operatorname {ggT} (N,x-y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f19642b411fdecacbdca0830059ef5e7d36cbb61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.235ex; height:2.843ex;" alt="{\displaystyle \operatorname {ggT} (N,x-y)}"></span> sind Faktoren von <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit&section=7" title="Abschnitt bearbeiten: Literatur" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Kettenbruchmethode&action=edit&section=7" title="Quellcode des Abschnitts bearbeiten: Literatur"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a>: <a rel="nofollow" class="external text" href="http://www.ams.org/notices/199612/pomerance.pdf"><i>A Tale of Two Sieves.</i></a> (PDF; 275 kB) In: <i>Notices of the AMS.</i> Bd. 43, Nr. 12, 1996, S. 1473–1485.</li> <li><a href="/wiki/Derrick_Henry_Lehmer" title="Derrick Henry Lehmer">D. H. Lehmer</a>, R. E. Powers: <i>On Factoring Large Numbers.</i> In: <i>Bulletin of the American Mathematical Society.</i> Bd. 37, 1931, S. 770–776 (<a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1090/S0002-9904-1931-05271-X">10.1090/S0002-9904-1931-05271-X</a></span>).</li> <li>Michael A. Morrison, <a href="/wiki/John_Brillhart" title="John Brillhart">John Brillhart</a>: <i>A Method of Factoring and the Factorization 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 F_{7}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>7</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{7}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3d649c0c1ff6141f1db35d5efe5ad244ea1199c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{7}}"></span>.</i> In: <i>Mathematics of Computation.</i> Bd. 29, Nr. 129, 1975, S. 183–205 (<a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.2307/2005475">10.2307/2005475</a></span>).</li></ul></div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Abgerufen von „<a dir="ltr" href="https://de.wikipedia.org/w/index.php?title=Kettenbruchmethode&oldid=201780070">https://de.wikipedia.org/w/index.php?title=Kettenbruchmethode&oldid=201780070</a>“</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Wikipedia:Kategorien" title="Wikipedia:Kategorien">Kategorie</a>: <ul><li><a href="/wiki/Kategorie:Faktorbasisverfahren" title="Kategorie:Faktorbasisverfahren">Faktorbasisverfahren</a></li></ul></div></div> </div> </div> <div id="mw-navigation"> <h2>Navigationsmenü</h2> <div id="mw-head"> <nav id="p-personal" class="mw-portlet mw-portlet-personal vector-user-menu-legacy vector-menu" aria-labelledby="p-personal-label" > <h3 id="p-personal-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Meine Werkzeuge</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anonuserpage" class="mw-list-item"><span title="Benutzerseite der IP-Adresse, von der aus du Änderungen durchführst">Nicht angemeldet</span></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Spezial:Meine_Diskussionsseite" title="Diskussion über Änderungen von dieser IP-Adresse [n]" accesskey="n"><span>Diskussionsseite</span></a></li><li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Spezial:Meine_Beitr%C3%A4ge" title="Eine Liste der Bearbeitungen, die von dieser IP-Adresse gemacht wurden [y]" accesskey="y"><span>Beiträge</span></a></li><li id="pt-createaccount" class="mw-list-item"><a href="/w/index.php?title=Spezial:Benutzerkonto_anlegen&returnto=Kettenbruchmethode" title="Wir ermutigen dich dazu, ein Benutzerkonto zu erstellen und dich anzumelden. Es ist jedoch nicht zwingend erforderlich."><span>Benutzerkonto erstellen</span></a></li><li id="pt-login" class="mw-list-item"><a href="/w/index.php?title=Spezial:Anmelden&returnto=Kettenbruchmethode" title="Anmelden ist zwar keine Pflicht, wird aber gerne gesehen. [o]" accesskey="o"><span>Anmelden</span></a></li> </ul> </div> </nav> <div id="left-navigation"> <nav id="p-namespaces" class="mw-portlet mw-portlet-namespaces vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-namespaces-label" > <h3 id="p-namespaces-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Namensräume</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected mw-list-item"><a href="/wiki/Kettenbruchmethode" title="Seiteninhalt anzeigen [c]" accesskey="c"><span>Artikel</span></a></li><li id="ca-talk" class="mw-list-item"><a href="/wiki/Diskussion:Kettenbruchmethode" rel="discussion" title="Diskussion zum Seiteninhalt [t]" accesskey="t"><span>Diskussion</span></a></li> </ul> </div> </nav> <nav id="p-variants" class="mw-portlet mw-portlet-variants emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-variants-label" > <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-menu-checkbox" aria-labelledby="p-variants-label" > <label id="p-variants-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Deutsch</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> </div> <div id="right-navigation"> <nav id="p-views" class="mw-portlet mw-portlet-views vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-views-label" > <h3 id="p-views-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Ansichten</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected mw-list-item"><a href="/wiki/Kettenbruchmethode"><span>Lesen</span></a></li><li id="ca-ve-edit" class="mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&veaction=edit" title="Diese Seite mit dem VisualEditor bearbeiten [v]" accesskey="v"><span>Bearbeiten</span></a></li><li id="ca-edit" class="collapsible mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&action=edit" title="Den Quelltext dieser Seite bearbeiten [e]" accesskey="e"><span>Quelltext bearbeiten</span></a></li><li id="ca-history" class="mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&action=history" title="Frühere Versionen dieser Seite [h]" accesskey="h"><span>Versionsgeschichte</span></a></li> </ul> </div> </nav> <nav id="p-cactions" class="mw-portlet mw-portlet-cactions emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-cactions-label" title="Weitere Optionen" > <input type="checkbox" id="p-cactions-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-cactions" class="vector-menu-checkbox" aria-labelledby="p-cactions-label" > <label id="p-cactions-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Weitere</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <h3 >Suche</h3> <form action="/w/index.php" id="searchform" class="vector-search-box-form"> <div id="simpleSearch" class="vector-search-box-inner" data-search-loc="header-navigation"> <input class="vector-search-box-input" type="search" name="search" placeholder="Wikipedia durchsuchen" aria-label="Wikipedia durchsuchen" autocapitalize="sentences" title="Durchsuche die Wikipedia [f]" accesskey="f" id="searchInput" > <input type="hidden" name="title" value="Spezial:Suche"> <input id="mw-searchButton" class="searchButton mw-fallbackSearchButton" type="submit" name="fulltext" title="Suche nach Seiten, die diesen Text enthalten" value="Suchen"> <input id="searchButton" class="searchButton" type="submit" name="go" title="Gehe direkt zu der Seite mit genau diesem Namen, falls sie vorhanden ist." value="Artikel"> </div> </form> </div> </div> </div> <div id="mw-panel" class="vector-legacy-sidebar"> <div id="p-logo" role="banner"> <a class="mw-wiki-logo" href="/wiki/Wikipedia:Hauptseite" title="Hauptseite"></a> </div> <nav id="p-navigation" class="mw-portlet mw-portlet-navigation vector-menu-portal portal vector-menu" aria-labelledby="p-navigation-label" > <h3 id="p-navigation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Navigation</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikipedia:Hauptseite" title="Hauptseite besuchen [z]" accesskey="z"><span>Hauptseite</span></a></li><li id="n-topics" class="mw-list-item"><a href="/wiki/Portal:Wikipedia_nach_Themen"><span>Themenportale</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Spezial:Zuf%C3%A4llige_Seite" title="Zufällige Seite aufrufen [x]" accesskey="x"><span>Zufälliger Artikel</span></a></li> </ul> </div> </nav> <nav id="p-Mitmachen" class="mw-portlet mw-portlet-Mitmachen vector-menu-portal portal vector-menu" aria-labelledby="p-Mitmachen-label" > <h3 id="p-Mitmachen-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Mitmachen</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-Artikel-verbessern" class="mw-list-item"><a href="/wiki/Wikipedia:Beteiligen"><span>Artikel verbessern</span></a></li><li id="n-Neuerartikel" class="mw-list-item"><a href="/wiki/Hilfe:Neuen_Artikel_anlegen"><span>Neuen Artikel anlegen</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Autorenportal" title="Info-Zentrum über Beteiligungsmöglichkeiten"><span>Autorenportal</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Hilfe:%C3%9Cbersicht" title="Übersicht über Hilfeseiten"><span>Hilfe</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Spezial:Letzte_%C3%84nderungen" title="Liste der letzten Änderungen in Wikipedia [r]" accesskey="r"><span>Letzte Änderungen</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikipedia:Kontakt" title="Kontaktmöglichkeiten"><span>Kontakt</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_de.wikipedia.org&uselang=de" title="Unterstütze uns"><span>Spenden</span></a></li> </ul> </div> </nav> <nav id="p-tb" class="mw-portlet mw-portlet-tb vector-menu-portal portal vector-menu" aria-labelledby="p-tb-label" > <h3 id="p-tb-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Werkzeuge</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Spezial:Linkliste/Kettenbruchmethode" title="Liste aller Seiten, die hierher verlinken [j]" accesskey="j"><span>Links auf diese Seite</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Spezial:%C3%84nderungen_an_verlinkten_Seiten/Kettenbruchmethode" rel="nofollow" title="Letzte Änderungen an Seiten, die von hier verlinkt sind [k]" accesskey="k"><span>Änderungen an verlinkten Seiten</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Spezial:Spezialseiten" title="Liste aller Spezialseiten [q]" accesskey="q"><span>Spezialseiten</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&oldid=201780070" title="Dauerhafter Link zu dieser Seitenversion"><span>Permanenter Link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&action=info" title="Weitere Informationen über diese Seite"><span>Seiteninformationen</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Spezial:Zitierhilfe&page=Kettenbruchmethode&id=201780070&wpFormIdentifier=titleform" title="Hinweise, wie diese Seite zitiert werden kann"><span>Artikel zitieren</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Spezial:URL-K%C3%BCrzung&url=https%3A%2F%2Fde.wikipedia.org%2Fwiki%2FKettenbruchmethode"><span>Kurzlink</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Spezial:QrCode&url=https%3A%2F%2Fde.wikipedia.org%2Fwiki%2FKettenbruchmethode"><span>QR-Code herunterladen</span></a></li> </ul> </div> </nav> <nav id="p-coll-print_export" class="mw-portlet mw-portlet-coll-print_export vector-menu-portal portal vector-menu" aria-labelledby="p-coll-print_export-label" > <h3 id="p-coll-print_export-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Drucken/exportieren</span> </h3> <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=Spezial:DownloadAsPdf&page=Kettenbruchmethode&action=show-download-screen"><span>Als PDF herunterladen</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Kettenbruchmethode&printable=yes" title="Druckansicht dieser Seite [p]" accesskey="p"><span>Druckversion</span></a></li> </ul> </div> </nav> <nav id="p-wikibase-otherprojects" class="mw-portlet mw-portlet-wikibase-otherprojects vector-menu-portal portal vector-menu" aria-labelledby="p-wikibase-otherprojects-label" > <h3 id="p-wikibase-otherprojects-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">In anderen Projekten</span> </h3> <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/Q1739928" title="Link zum verbundenen Objekt im Datenrepositorium [g]" accesskey="g"><span>Wikidata-Datenobjekt</span></a></li> </ul> </div> </nav> <nav id="p-lang" class="mw-portlet mw-portlet-lang vector-menu-portal portal vector-menu" aria-labelledby="p-lang-label" > <h3 id="p-lang-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">In anderen Sprachen</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Continued_fraction_factorization" title="Continued fraction factorization – Englisch" lang="en" hreflang="en" data-title="Continued fraction factorization" data-language-autonym="English" data-language-local-name="Englisch" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Factorizaci%C3%B3n_con_fracciones_continuas" title="Factorización con fracciones continuas – Spanisch" lang="es" hreflang="es" data-title="Factorización con fracciones continuas" data-language-autonym="Español" data-language-local-name="Spanisch" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Factorisation_par_fraction_continue" title="Factorisation par fraction continue – Französisch" lang="fr" hreflang="fr" data-title="Factorisation par fraction continue" data-language-autonym="Français" data-language-local-name="Französisch" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%97%B0%EB%B6%84%EC%88%98_%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98" title="연분수 소인수분해 알고리즘 – Koreanisch" lang="ko" hreflang="ko" data-title="연분수 소인수분해 알고리즘" data-language-autonym="한국어" data-language-local-name="Koreanisch" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-ru badge-Q17559452 badge-recommendedarticle mw-list-item" title="empfohlener Artikel"><a href="https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%BD%D0%B5%D0%BF%D1%80%D0%B5%D1%80%D1%8B%D0%B2%D0%BD%D1%8B%D1%85_%D0%B4%D1%80%D0%BE%D0%B1%D0%B5%D0%B9" title="Факторизация методом непрерывных дробей – Russisch" lang="ru" hreflang="ru" data-title="Факторизация методом непрерывных дробей" data-language-autonym="Русский" data-language-local-name="Russisch" 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/Q1739928#sitelinks-wikipedia" title="Links auf Artikel in anderen Sprachen bearbeiten" class="wbc-editpage">Links bearbeiten</a></span></div> </div> </nav> </div> </div> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Diese Seite wurde zuletzt am 11. Juli 2020 um 14:06 Uhr bearbeitet.</li> <li id="footer-info-copyright"><div id="footer-info-copyright-stats" class="noprint"><a rel="nofollow" class="external text" href="https://pageviews.wmcloud.org/?pages=Kettenbruchmethode&project=de.wikipedia.org">Abrufstatistik</a> · <a rel="nofollow" class="external text" href="https://xtools.wmcloud.org/authorship/de.wikipedia.org/Kettenbruchmethode?uselang=de">Autoren</a> </div><div id="footer-info-copyright-separator"><br /></div><div id="footer-info-copyright-info"> <p>Der Text ist unter der Lizenz <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">„Creative-Commons Namensnennung – Weitergabe unter gleichen Bedingungen“</a> verfügbar; Informationen zu den Urhebern und zum Lizenzstatus eingebundener Mediendateien (etwa Bilder oder Videos) können im Regelfall durch Anklicken dieser abgerufen werden. Möglicherweise unterliegen die Inhalte jeweils zusätzlichen Bedingungen. Durch die Nutzung dieser Website erklären Sie sich mit den <span class="plainlinks"><a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/de">Nutzungsbedingungen</a> und der <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Privacy_policy/de">Datenschutzrichtlinie</a></span> einverstanden.<br /> </p> Wikipedia® ist eine eingetragene Marke der Wikimedia Foundation Inc.</div></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/de">Datenschutz</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:%C3%9Cber_Wikipedia">Über Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Impressum">Impressum</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Verhaltenskodex</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Entwickler</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/de.wikipedia.org">Statistiken</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Stellungnahme zu Cookies</a></li> <li id="footer-places-mobileview"><a href="//de.m.wikipedia.org/w/index.php?title=Kettenbruchmethode&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile Ansicht</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> <script>(RLQ=window.RLQ||[]).push(function(){mw.log.warn("This page is using the deprecated ResourceLoader module \"codex-search-styles\".\n[1.43] Use a CodexModule with codexComponents to set your specific components used: https://www.mediawiki.org/wiki/Codex#Using_a_limited_subset_of_components");mw.config.set({"wgHostname":"mw-web.codfw.main-5c59558b9d-6lpvq","wgBackendResponseTime":130,"wgPageParseReport":{"limitreport":{"cputime":"0.067","walltime":"0.188","ppvisitednodes":{"value":365,"limit":1000000},"postexpandincludesize":{"value":632,"limit":2097152},"templateargumentsize":{"value":0,"limit":2097152},"expansiondepth":{"value":3,"limit":100},"expensivefunctioncount":{"value":0,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":2052,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 24.614 1 -total"," 99.35% 24.453 2 Vorlage:DOI"]},"scribunto":{"limitreport-timeusage":{"value":"0.007","limit":"10.000"},"limitreport-memusage":{"value":917851,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-587f7d4878-nc9fq","timestamp":"20241120100855","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Kettenbruchmethode","url":"https:\/\/de.wikipedia.org\/wiki\/Kettenbruchmethode","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1739928","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1739928","author":{"@type":"Organization","name":"Autoren der Wikimedia-Projekte"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2005-10-11T16:49:32Z"}</script> </body> </html>