Factorisation prime avec O (n ^ (1/4))

Factorisation prime avec O (N ^ (1/4))

Le nombre naturel $ n $ est factorisé par $ O (n ^ {\ frac {1} {4}}) $.

Implémentation naïve

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 $.

Jugement du nombre premier

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.

Jugement par 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 . $ a^{p-1} \equiv 1\ ({\rm mod}\ p) \tag{1}$$

Prendre une paire, environ un certain $ a $ $ a^{n-1} \equiv 1\ ({\rm mod}\ n) \tag{2}$

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.

Méthode de jugement des nombres premiers de Rabin en miroir

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

Algorithme de décomposition des facteurs premiers

Maintenant, expliquons enfin la factorisation première. Tout d'abord, je présenterai la méthode de détection de circulation de floyd.

Méthode de détection de circulation 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)), \ ... , cela circule quelque part. Je veux détecter la taille de ce nœud circulaire. Vous pouvez le faire des manières suivantes: Premier $\ x=a,\ y=a$ Et initialisez. ensuite $\ x=f(x),\ y=f(f(y))$$ Si vous répétez, un jour $ x $ et $ y $ correspondront. L'image est que $ x $ avance de 1 $ et $ y $ avance de 2 $.

La méthode ρ de Polard

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 $ f (a) = a ^ {2} + c \ ( {\ rm mod} \ n) \ tag {3} Défini par $. De $ n = pq $, cela peut aussi être vu comme une fonction sur $ \ mathbb {Z} / p \ mathbb {Z} $ ou une fonction sur $ \ mathbb {Z} / q \ mathbb {Z} $ .. Maintenant, en utilisant la méthode de détection de circulation Floyd que j'ai mentionnée plus tôt, cela circule quelque part. D'après le paradoxe d'anniversaire, cela devrait être $ O (\ sqrt p) $ dans $ \ mathbb {Z} / p \ mathbb {Z} $ et vous devriez trouver un cycle. Il en va de même pour $ \ mathbb {Z} / q \ mathbb {Z} $. Comment puis-je savoir si j'ai circulé dans $ \ mathbb {Z} / p \ mathbb {Z} $? Cela peut être fait en utilisant $ \ rm GCD . En particulier, $\ x=a,\ y=a$ Et initialisez. ensuite $\ x=f(x),\ y=f(f(y))$$ De façon répétée, s'il circule dans $ {\ rm mod} \ p $, c'est-à-dire si $ x \ equiv y \ {\ rm mod} \ p $ est satisfait, alors $ {\ rm gcd} (xy, \ n) $ devient $ p $ (souvent juste $ p $). À moins que les cycles de $ {\ rm mod} \ p $ et $ {\ rm mod} \ q $ ne correspondent, soit $ p $ ou $ q $ peuvent être récupérés en premier, et la factorisation des nombres premiers est terminée. Dans ce cas, $ n $ était supposé être le produit de $ 2 $ facteurs premiers, mais s'il existe une possibilité d'un produit de 3 $ $ ou plus de facteurs premiers, le nombre détecté est-il un nombre premier? Ou vous devez vérifier si plusieurs facteurs premiers sont détectés en même temps. Ceci peut être déterminé par la méthode miroir-rabin ci-dessus. Si le nombre naturel détecté est un nombre composé, il peut être décomposé davantage. Le montant du calcul est $ \ sqrt p $ si le facteur premier $ 2 $ le plus grand de $ n $ prend $ n $ à détecter, donc $ O en considérant le $ \ log $ qui coûte $ \ rm GCD $. (n ^ {\ frac {1} {4}} \ log n) Cela devient $.

Une variante de Richard Brent

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}}) $.

code

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

Factorisation prime avec O (n ^ (1/4))
Tri sélectif O (n ^ 2)
Benchmarks langage C, Java, Python avec factorisation prime
[Python 3] Décomposition des facteurs premiers en 14 lignes
Juger les nombres premiers avec python
Résolution des problèmes N + 1 avec les chargeurs de données
Revive Frame Reader avec Quartus Prime 18.1
Factorisation matricielle non négative (NMF) avec scikit-learn
Résolution avec Ruby et Python AtCoder ABC057 C Décomposition du facteur premier Recherche complète de bits
Résolution avec Ruby, Perl, Java et Python AtCoder CADDi 2018 C factorisation premier