Pourquoi la factorisation de grands nombres entiers est-elle difficile?

17

J'ai lu quelque part que le plus algorithme efficace trouvé peut calculer les facteurs le temps, mais le code que j'ai écrit est O ( n ) ou éventuellement O ( n log n ) en fonction de la rapidité de la division et du module. Je suis sûr que j'ai mal compris quelque chose, mais je ne sais pas où. Voici ce que j'ai écrit sous forme de pseudo-code.O(exp((64/9b)1/3(logb)2/3)O(n)O(nlogn)

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors
EnderShadow
la source
3
Google "pseudo polynôme".
Raphael
Cet algorithme est en fait très lent - si nombre est un nombre premier, la boucle est itérée (nombre) fois. Il existe un argument très simple qui vous permet de vous en sortir avec les itérations sqrt (nombre).
gnasher729

Réponses:

26

Vous confondez le nombre avec le nombre de bits nécessaires pour représenter n . Ici b = le nombre de bits nécessaires pour représenter n (donc b lg n ). Cela fait une énorme différence. Un algorithme à temps O ( n ) est un algorithme à temps O ( 2 b ) - exponentiel en nombre de bits. En comparaison, l'algorithme "efficace" que vous avez trouvé a un temps d'exécution sous-exponentiel en b .nnb=nblgnO(n)O(2b)b

Exemple: Considérons (2 M). Alors b = 21 bits suffisent pour représenter le nombre n . Ainsi, un algorithme O ( 2 b 1 / 3 ) sera beaucoup plus rapide qu'un algorithme est O ( 2 b ) . Un algorithme O ( n ) appartient à cette dernière catégorie, c'est-à-dire qu'il est très lent.n=2,000,000b=21nO(2b1/3)O(2b)O(n)

Voir https://en.wikipedia.org/wiki/Integer_factorization

DW
la source
1
Je savais que c'était quelque chose de simple comme ça.
EnderShadow
3
b>1,000n>21,000O(n)n21,000
1

vous avez environ deux questions ici, une générale et une spécifique à propos de votre code. le spécifique est traité dans l'autre réponse. la question générale du titre sur la complexité de l'affacturage est très profonde. malheureusement, il n'y a pas de preuves scientifiques solides que l'affacturage est en dehors de P autre que (le plus souvent circonstanciel) "beaucoup d'experts ont essayé et échoué" et certains experts pensent que c'est à l'intérieur de P; Son considéré comme l'un des problèmes ouverts les plus importants (et très difficiles à résoudre) de la théorie de la complexité. après des décennies «d'attaque lourde», les meilleurs algorithmes sont exponentiels. la complexité de l'affacturage est l'un des "quelques problèmes exceptionnels" connus pour se situer "entre" P et NP complets mais n'a pas été classé comme tel jusqu'à présent.

comme on l'a souligné, la complexité n'était pas vraiment un problème jusqu'à ce qu'elle soit utilisée ("à peu près") dans les cryptosystèmes RSA au milieu des années 1980 où la sécurité cryptographique dépend de l' hypothèse. (Deux autres points de données liés "pas exactement encourageants": l' algorithme Shors pour l'affacturage quantique du temps P et les tests de primalité s'est avéré être en P au début des années 2000 dans le célèbre / célèbre algorithme AKS .) un résultat positif possible serait que son temps quasipolynomial , qui est plus faible que NP complet (en supposant que P ≠ NP et NP complet a une limite inférieure de temps exponentielle ) mais reste techniquement "dur".

n'ont pas trouvé une grande enquête sur ce sujet clé jusqu'à présent. mais voir aussi

vzn
la source
un autre scénario quelque peu "apparent" possible est que l'affacturage pourrait être en P mais il n'y a toujours pas d'algorithme réalisable. alias algorithmes galactiques
vzn
Il convient de mentionner que RSA consiste à factoriser le produit de deux grands nombres premiers (où quelqu'un connaît les nombres premiers et les multiplie, et quelqu'un d'autre reçoit le produit et est censé trouver les nombres premiers). Il est concevable qu'il puisse y avoir un algorithme qui peut factoriser les produits de deux grands nombres premiers, mais pas les produits de plus de deux grands nombres premiers. Tout comme la factorisation de nombres qui sont de grands nombres premiers (mais qui n'étaient pas connus auparavant comme étant de grands nombres premiers) peut être fait en temps polynomial.
gnasher729