Le nombre naturel $ n $ est factorisé par $ O (n ^ {\ frac {1} {4}}) $.
Lors de la factorisation d'un nombre naturel $ n $ en facteurs premiers, une implémentation naïve consiste à le diviser séquentiellement jusqu'à la racine carrée de $ n $. Cette méthode nécessite un montant de calcul de $ O (\ sqrt {n}) $ et est inefficace pour les gros $ n $.
Tout d'abord, considérons d'effectuer le jugement de nombre premier d'un nombre naturel à grande vitesse. Ici, nous utilisons ce qu'on appelle la méthode Miller-Rabin. Tout d'abord, passons en revue le théorème de Fermat.
Selon le théorème de Fermat, ce qui suit est vrai pour le nombre premier $ p $ et le nombre naturel $ a $ qui est mutuellement premier avec $ p
Prendre une paire, environ un certain $ a $
Si ce n'est pas vrai, alors $ p $ n'est pas un nombre premier. A l'inverse, si on s'assure que ce n'est pas le cas pour beaucoup de $ a $, peut-on dire que $ p $ est un nombre premier? Pour dire la vérité, malheureusement, il existe un contre-exemple du nombre (?) De Carmichael. Le nombre de Carmichael $ n $ est valable pour tous les nombres naturels $ a $ qui sont synthétiques mais $ (2) $ sont mutuellement exclusifs avec $ n $. Nous savons qu'il existe un nombre infini de nombres de Carmichael.
Maintenant, pour un $ p $ premier sur $ 3 $, dans le monde de $ \ mathbb {Z} / p \ mathbb {Z} $, il y a exactement $ 2 $ racines carrées de $ 1 $ et $ -1 $. .. Ceci peut être vu du fait que l'anneau de reste $ \ mathbb {Z} / p \ mathbb {Z} $ devient le champ. Si $ n $ est un nombre premier supérieur ou égal à $ 3 $, l'indice $ n-1 $ sur le côté gauche de $ (2) $ est pair. A partir de $ a ^ {n-1} \ equiv 1 $, $ a ^ {\ frac {n-1} {2}} \ equiv \ pm1 $ devrait tenir. Inversement, si $ a ^ {\ frac {n-1} {2}} \ equiv \ pm1 $ ne tient pas, alors $ n $ est un nombre composé. En divisant encore par deux l'indice de $ a $, il devrait être $ \ pm1 $ juste avant $ 1 $. Si un nombre autre que $ \ pm1 $ devient soudainement $ 1 $, vous savez que $ n $ est un nombre composé. Cependant, s'il devient $ -1 $ vu de l'arrière, il ne peut pas être déterminé si $ n $ est un nombre premier ou un nombre composé par lui-même, quel que soit le front. La probabilité de choisir un tel nombre inconnu ou non est au plus $ \ frac {1} {4} $. En d'autres termes, avec de nombreux essais, la probabilité de prendre une décision correcte approche 1 $.
Notez que si $ n <2 ^ {32} $, il suffit de regarder $ 2, \ 3, \ 61 $ comme $ a $. Si $ n <2 ^ {64} $, recherchez $ 2, \ 3, \ 5, \ 7, \ 11, \ 13, \ 17, \ 19, \ 23, \ 29, \ 31, \ 37 $ est assez. Les détails de la condition de suffisance peuvent être trouvés dans la version anglaise de Wikipedia.
(Japonais) 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
(Anglais) https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
Maintenant, expliquons enfin la factorisation première. Tout d'abord, je présenterai la méthode de détection de circulation de floyd.
Considérons un mapping $ f: A \ rightarrow A $ pour un ensemble fini de $ A $ composé de $ n $ éléments. Pour $ a \ dans A $, en considérant $ a, \ f (a), \ f (f (a)), \ ...
Pour simplifier, disons que $ n $ est représenté par $ n = pq $ comme le produit de $ 2 $ facteurs premiers. De plus, en divisant les petits facteurs premiers à l'avance, $ p $ et $ q $ peuvent être raisonnablement grands (par exemple, 100 $ ou plus). $ F: \ mathbb {Z} / n \ mathbb {Z} \ rightarrow \ mathbb {Z} / n \ mathbb {Z} $ en tant que nombre pseudo aléatoire est
Dans la méthode ci-dessus, prendre $ \ rm GCD $ était un goulot d'étranglement dans la quantité de calcul. Par conséquent, nous envisagerons d'accélérer en jugeant plusieurs valeurs en même temps. Plus précisément, $ m $ est décidé de manière appropriée, le nombre de $ \ rm GCD $ à prendre est multiplié par tous les $ m $ pièces, et le produit est multiplié par $ n $ de $ \ rm GCD. Vous pouvez juger immédiatement en prenant $. Si vous trouvez $ p $ et $ q $ en même temps, vous pouvez revenir un peu en arrière et avancer de 1 $. Si vous n'êtes pas chanceux et qu'il est détecté en même temps, modifiez le nombre pseudo aléatoire et réessayez. Plus précisément, vous pouvez essayer de changer $ c $ de $ (3) $ de manière appropriée.
Si $ m $ vaut environ $ m = n ^ {\ frac {1} {8}} $, le nombre de fois pour prendre $ \ log $ est $ O (n ^ {\ frac {1} {8}} ) $, Et le nombre de multiplications et de divisions est $ O (n ^ {\ frac {1} {4}}) $, donc $ O (n ^ {\ frac {1} {4}} + n ^ dans son ensemble Vous pouvez effectuer une factorisation premier avec {\ frac {1} {8}} \ log n) = O (n ^ {\ frac {1} {4}}) $.
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