Die natürliche Zahl $ n $ wird durch $ O (n ^ {\ frac {1} {4}}) $ faktorisiert.
Wenn eine natürliche Zahl $ n $ in Primfaktoren zerlegt wird, besteht eine naive Implementierung darin, sie nacheinander bis zur Quadratwurzel von $ n $ zu teilen. Diese Methode erfordert einen Rechenbetrag von $ O (\ sqrt {n}) $ und ist für große $ n $ ineffizient.
Betrachten wir zunächst die Primzahlbeurteilung einer natürlichen Zahl mit hoher Geschwindigkeit. Hier verwenden wir die sogenannte Miller-Rabin-Methode. Lassen Sie uns zunächst den Satz von Fermat überprüfen.
Nach dem Satz von Fermat gilt das Folgende für die Primzahl $ p $ und die natürliche Zahl $ a $, die sich gegenseitig mit $ p $ primieren.
Ein Paar nehmen, ungefähr ein bestimmtes $ a $
Wenn dies nicht der Fall ist, ist $ p $ keine Primzahl. Wenn wir umgekehrt sicherstellen, dass dies bei vielen $ a $ nicht der Fall ist, können wir dann sagen, dass $ p $ eine Primzahl ist? Tatsächlich gibt es leider ein Gegenbeispiel für die (?) Carmichael-Zahl. Die Carmichael-Zahl $ n $ gilt für alle natürlichen Zahlen $ a $, die synthetisch sind, aber $ (2) $ schließen sich mit $ n $ gegenseitig aus. Wir wissen, dass es unendlich viele Carmichael-Zahlen gibt.
Für eine Primzahl von $ p $ über $ 3 $ gibt es in der Welt von $ \ mathbb {Z} / p \ mathbb {Z} $ genau $ 2 $ Quadratwurzeln von $ 1 $ und $ -1 $. .. Dies ist daran zu erkennen, dass der Restring $ \ mathbb {Z} / p \ mathbb {Z} $ zum Feld wird. Wenn $ n $ eine Primzahl größer oder gleich $ 3 $ ist, ist der Index $ n-1 $ auf der linken Seite von $ (2) $ gerade. Ab $ a ^ {n-1} \ equiv 1 $ sollte $ a ^ {\ frac {n-1} {2}} \ equiv \ pm1 $ gelten. Wenn umgekehrt $ a ^ {\ frac {n-1} {2}} \ equiv \ pm1 $ nicht gilt, ist $ n $ eine zusammengesetzte Zahl. Wenn Sie den Index von $ a $ halbieren, sollte er kurz vor $ 1 $ $ \ pm1 $ sein. Wenn Sie plötzlich von einer anderen Zahl als $ \ pm1 $ zu $ 1 $ wechseln, wissen Sie, dass $ n $ eine zusammengesetzte Zahl ist. Wenn es jedoch von hinten betrachtet zu $ -1 $ wird, kann nicht festgestellt werden, ob $ n $ eine Primzahl oder eine zusammengesetzte Zahl für sich ist, unabhängig von der Vorderseite. Die Wahrscheinlichkeit, eine solche Zahl zu wählen, die unbekannt ist oder nicht, beträgt höchstens $ \ frac {1} {4} $. Mit anderen Worten, bei vielen Versuchen nähert sich die Wahrscheinlichkeit, eine richtige Entscheidung zu treffen, 1 $.
Beachten Sie, dass es ausreicht, wenn $ n <2 ^ {32} $ ist, $ 2, \ 3, \ 61 $ als $ a $ zu betrachten. Wenn $ n <2 ^ {64} $ ist, suchen Sie nach $ 2, \ 3, \ 5, \ 7, \ 11, \ 13, \ 17, \ 19, \ 23, \ 29, \ 31, \ 37 $ genug. Details zum Zustand der Suffizienz finden Sie in der englischen Version von Wikipedia.
(Japanisch) https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
(Englisch) https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
Lassen Sie uns nun endlich die Primfaktorisierung erklären. Zunächst werde ich die Zirkulationserkennungsmethode von Floyd vorstellen.
Betrachten Sie für eine endliche Menge von $ A $, die aus $ n $ Elementen besteht, eine Zuordnung $ f: A \ rightarrow A $. Für $ a \ in A $ zirkuliert dies irgendwo, wenn man $ a, \ f (a), \ f (f (a)), \ ... $ berücksichtigt. Ich möchte die Größe dieses kreisförmigen Knotens ermitteln. Sie können dies auf folgende Arten tun: Zuerst
Nehmen wir zur Vereinfachung an, $ n $ wird als $ n = pq $ als Produkt von $ 2 $ Primfaktoren dargestellt. Durch Teilen der kleinen Primfaktoren im Voraus können $ p $ und $ q $ auch relativ groß sein (z. B. 100 $ oder mehr). $ F: \ mathbb {Z} / n \ mathbb {Z} \ rightarrow \ mathbb {Z} / n \ mathbb {Z} $ als Pseudozufallszahl ist
Bei der obigen Methode war die Einnahme von $ \ rm GCD $ ein Engpass bei der Berechnung. Daher werden wir eine Beschleunigung in Betracht ziehen, indem wir mehrere Werte gleichzeitig beurteilen. Insbesondere wird $ m $ angemessen entschieden, die Anzahl der zu nehmenden $ \ rm GCD $ wird mit allen $ m $ Stücken multipliziert und das Produkt wird mit $ n $ von $ \ rm GCD multipliziert. Sie können sofort beurteilen, indem Sie $ nehmen. Wenn Sie $ p $ und $ q $ gleichzeitig finden, können Sie ein Stück zurückgehen und um $ 1 $ vorwärts gehen. Wenn Sie Pech haben und es gleichzeitig erkannt wird, ändern Sie die Pseudozufallszahl und versuchen Sie es erneut. Insbesondere können Sie versuchen, $ c $ von $ (3) $ entsprechend zu ändern.
Wenn $ m $ auf ungefähr $ m = n ^ {\ frac {1} {8}} $ gesetzt ist, beträgt die Häufigkeit, mit der $ \ log $ genommen wird, $ O (n ^ {\ frac {1} {8}} ) $, Und die Anzahl der Multiplikationen und Divisionen ist $ O (n ^ {\ frac {1} {4}}) $, also $ O (n ^ {\ frac {1} {4}} + n ^ als Ganzes Sie können die Primfaktorisierung mit {\ frac {1} {8}} \ log n) = O (n ^ {\ frac {1} {4}}) $ durchführen.
factorize.py
def gcd(a, b):
while b: a, b = b, a % b
return a
def isPrimeMR(n):
d = n - 1
d = d // (d & -d)
L = [2]
for a in L:
t = d
y = pow(a, t, n)
if y == 1: continue
while y != n - 1:
y = (y * y) % n
if y == 1 or t == n - 1: return 0
t <<= 1
return 1
def findFactorRho(n):
m = 1 << n.bit_length() // 8
for c in range(1, 99):
f = lambda x: (x * x + c) % n
y, r, q, g = 2, 1, 1, 1
while g == 1:
x = y
for i in range(r):
y = f(y)
k = 0
while k < r and g == 1:
ys = y
for i in range(min(m, r - k)):
y = f(y)
q = q * abs(x - y) % n
g = gcd(q, n)
k += m
r <<= 1
if g == n:
g = 1
while g == 1:
ys = f(ys)
g = gcd(abs(x - ys), n)
if g < n:
if isPrimeMR(g): return g
elif isPrimeMR(n // g): return n // g
return findFactorRho(g)
def primeFactor(n):
i = 2
ret = {}
rhoFlg = 0
while i*i <= n:
k = 0
while n % i == 0:
n //= i
k += 1
if k: ret[i] = k
i += 1 + i % 2
if i == 101 and n >= 2 ** 20:
while n > 1:
if isPrimeMR(n):
ret[n], n = 1, 1
else:
rhoFlg = 1
j = findFactorRho(n)
k = 0
while n % j == 0:
n //= j
k += 1
ret[j] = k
if n > 1: ret[n] = 1
if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
return ret
Recommended Posts