3riko tachibana

In der Mathematik ist das rationales Sieb ein allgemeiner Algorithmus zum Faktorisieren von Ganzzahlen in Primfaktoren. Es ist ein Sonderfall des allgemeinen Nummernfeldsiebs. Obwohl es weniger effizient ist als der allgemeine Algorithmus, ist es konzeptionell einfacher. Es ist ein hilfreicher erster Schritt, um zu verstehen, wie das allgemeine Zahlenfeldsieb funktioniert.

Nehmen wir an, wir versuchen, die zusammengesetzte Zahl n zu berücksichtigen. Wir wählen eine gebundene B und identifizieren die -Faktorbasis (die wir P ) nennen, die Menge aller Primzahlen kleiner oder gleich . B . Als nächstes suchen wir nach positiven ganzen Zahlen z so dass sowohl z als auch z + n B B glätten - dh alle ihre Primzahlen Faktoren sind in P . Wir können daher für geeignete Exponenten schreiben ${ displaystyle a_ {k}}$ ,

${displaystyle z=prod _{p_{i}in P}p_{i}^{a_{i}}}$ $z = prod _ {{p_ {i} in P}} p_ {i} ^ {{a_ {i}}}$

und für geeignete ${ displaystyle b_ {k}}$ haben wir

$p p p p p p p ] i { displaystyle z + n = prod _ {p_ {i} in P} p_ {i} ^ {b_ {i}}}$ .

Aber ${displaystyle z}$ und ${1945Start z + n} [19659052] z + n "/>$

{displaystyle prod _{p_{i}in P}p_{i}^{a_{i}}equiv prod _{p_{i}in P}p_{i}^{b_{i}}{pmod {n}}}

(wobei a _i und b _i sind nicht negative ganze Zahlen.)

Wenn wir genug von diesen Beziehungen erzeugt haben (es reicht im Allgemeinen aus, dass die Anzahl der Beziehungen ein paar mehr ist als P ), können wir die Methoden der linearen Algebra verwenden, um diese verschiedenen Faktoren miteinander zu multiplizieren Beziehungen so, dass die Exponenten der Primzahlen alle gleich sind. Dies gibt uns eine Übereinstimmung der Quadrate der Form a ² ]b ² (mod n ), die in eine Faktorisierung von umgewandelt werden können. n n = gcd ( a - b n ) × gcd ( a + b n ). Diese Faktorisierung könnte sich als trivial herausstellen (d. H. n = n × 1). In diesem Fall müssen wir es erneut mit einer anderen Kombination von Beziehungen versuchen; aber mit etwas Glück werden wir ein nicht-triviales Paar von Faktoren von n erhalten, und der Algorithmus wird enden.

Beispiel [ edit ]

Wir werden die ganze Zahl n = 187 unter Verwendung des rationalen Siebes einkalkulieren. Wir versuchen willkürlich den Wert B = 7, wobei wir die Faktorbasis P = {2,3,5,7} angeben. Der erste Schritt besteht darin, n auf Teilbarkeit durch jedes der Mitglieder von P zu testen; Wenn n durch eine dieser Primzahlen teilbar ist, sind wir bereits fertig. 187 ist jedoch nicht teilbar durch 2, 3, 5 oder 7. Als nächstes suchen wir nach geeigneten Werten für z ; Die ersten sind 2, 5, 9 und 56. Die vier geeigneten Werte von z ergeben vier multiplikative Beziehungen (Mod 187):

2 ¹ 3 ⁰ 5 ⁰ 7 ⁰ = 2 ≡ 189 = 2 ⁰ 3 3 ³ 5 ⁰ 7 ¹ ............. (1)

2 ⁰ 3 ⁰ 5 ¹ 7 ⁰ = 5 ≡ 192 = 2 ⁶ 3 ¹ 5 ⁰ 7 ⁰ ............. (2)

2 ⁰ 3 ² 5 ⁰ 7 ⁰ = 9 ≡ 196 = 2 ² 3 ⁰ 5 ⁰ 7 ² .. ........... (3)

2 ³ 3 ⁰ 5 ⁰ 7 ¹ = 56 243 = 2 ⁰ 3 ⁵ 5 ⁰ 7 ⁰ ............. ( 4)

Es gibt jetzt mehrere verschiedene Möglichkeiten, diese zu kombinieren und sogar Exponenten zu erhalten. Zum Beispiel,

(1) × (4): Nachdem diese multipliziert und der gemeinsame Faktor von 7 aufgehoben wurde (was wir seit 7 tun können, da er Mitglied von P ist, ist bereits festgelegt worden, dass er mithelfen kann n ^[1]) reduziert sich dies auf 2 ⁴ ≡ 3 ⁸ (mod n ) oder 4 ² 2 81 ² (mod n ). Die resultierende Faktorisierung beträgt 187 = gcd (81-4.187) × gcd (81 + 4.187) = 11 x 17.

Alternativ ist Gleichung (3) bereits in der richtigen Form:

(3): Dies sagt 3 ² ≡ 14 ² (mod n ), was die Faktorisierung 187 = gcd (14-3.187) × ergibt gcd (14 + 3,187) = 11 × 17.

Einschränkungen des Algorithmus [ edit ]

Das rationale Sieb kann, wie das allgemeine Zahlenfeldsieb, keine Zahlen der Form beeinflussen p ^mwobei p eine Primzahl und m eine ganze Zahl ist. Dies ist jedoch kein großes Problem - solche Zahlen sind statistisch selten, und außerdem gibt es einen einfachen und schnellen Prozess, um zu prüfen, ob eine bestimmte Anzahl diese Form hat. Die wohl eleganteste Methode ist die Überprüfung, ob ${displaystyle lfloor n^{1/b}rfloor ^{b}=n}$ gilt für jedes 1 <b <log (n) unter Verwendung einer ganzzahligen Version der Newton-Methode zur Wurzelextraktion ^[2]

Das größte Problem ist, eine ausreichende Anzahl von z zu finden beide z und z + n sind B -glatt. Für jedes gegebene B nimmt der Anteil der Zahlen, die B sind, mit der Größe der Anzahl rasch ab. Wenn also n groß ist (etwa hundert Stellen), wird es schwierig oder unmöglich sein, z ausreichend zu finden, damit der Algorithmus funktioniert. Der Vorteil des allgemeinen Zahlenfeldsiebs besteht darin, dass man nur nach glatten Ordnungszahlen suchen muss n ^{1 / d} für eine positive ganze Zahl d d (19459008) 5) und nicht wie hier gefordert n .

Referenzen [ edit ]

A. K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse und J.M. Pollard, Die Faktorisierung der neunten Fermat-Zahl, Math. Comp. 61 (1993), 319-349. Ein Entwurf ist unter www.std.org/~msm/common/f9paper.ps verfügbar. K. Lenstra, HW Lenstra, Jr. (Hrsg.) Die Entwicklung des Zahlenfeldsiebs, Vorlesungsunterlagen in Mathematics 1554, Springer-Verlag, New York, 1993.

Anmerkung dass gemeinsame Faktoren nicht allgemein in einer Kongruenz aufgehoben werden können, aber sie können in diesem Fall da die Primzahlen der Faktorbasis alle bis n müssen. wie oben erwähnt. Siehe modulares multiplikatives Inverses.

^ R. Crandall und J. Papadopoulos, Zur Durchführung von Primalitätstests der AKS-Klasse, verfügbar unter [1]

[1] Anmerkung dass gemeinsame Faktoren nicht allgemein in einer Kongruenz aufgehoben werden können, aber sie können in diesem Fall da die Primzahlen der Faktorbasis alle bis n müssen. wie oben erwähnt. Siehe modulares multiplikatives Inverses.

[2] R. Crandall und J. Papadopoulos, Zur Durchführung von Primalitätstests der AKS-Klasse, verfügbar unter [1]

3riko tachibana

Wednesday, February 20, 2019

Rationales Sieb - Wikipedia

Beispiel [ edit ]

Einschränkungen des Algorithmus [ edit ]

Referenzen [ edit ]

No comments:

Post a Comment