J'ai besoin d'obtenir tous les principaux facteurs de grands nombres pouvant facilement accéder à 1k bits. Les chiffres sont pratiquement aléatoires de sorte que cela ne devrait pas être difficile. Comment puis-je le faire efficacement? J'utilise C ++ avec la bibliothèque GMP.
EDIT:
Je suppose que vous m'avez mal compris.
Ce que je veux dire par premier, un nombre est d'obtenir tous les facteurs principaux du nombre.
Désolé pour mon anglais, dans ma langue prime et facteur sont les mêmes :)
Clarification (de l'autre post de OP):
Ce dont j'ai besoin, c'est un moyen de facturer efficacement (trouver des facteurs premiers d'un nombre) de grands nombres (peut atteindre 2048 bits) en utilisant C ++ et GMP (GNU Plus de précesession de la précession) ou moins de préférence toute autre manière. Les numéros sont pratiquement aléatoires, il y a peu de chance qu'il sera difficile de facturer, et même si le nombre est difficile à facteur, je peux repousser le numéro (ne peut pas choisir cependant).
4 Réponses :
Un bon démarrage serait un peu de pré-filtrage avec de petits nombres premiers, par exemple de tous les nombres premiers inférieurs à 100 000 environ. Essayez simplement de diviser par chacune d'elles (créez une table que vous chargez ensuite au moment de l'exécution ou faites-la en tant que données statiques dans votre code). Cela peut sembler lent et stupide, mais si le nombre est totalement aléatoire, cela vous donnera des facteurs très rapidement avec une énorme probabilité. Ensuite, regardez le numéro restant et décidez de quoi faire ensuite. Si c'est assez petit (ce que "petit" signifie à vous), vous pouvez essayer un test de primalité (il y a quelque chose dans GMP, je pense) et si cela le donne est un premier, vous pouvez dans la plupart des cas de confiance. Sinon, vous devez le prendre en compte.
Si vos chiffres sont vraiment énormes et que vous vous souciez de la performance, vous devez certainement mettre en œuvre quelque chose de plus sophistiqué qu'une division stupide. Regardez le tamis quadratique (essayez Wikipedia). C'est assez simple mais très puissant. Si vous êtes au chalenge, essayez MPQs, une variante de l'algorithme de tamis quadratique. Ce forum est une bonne source d'information. Il existe même des implémentations existantes d'un outil dont vous avez besoin - Voir par exemple ce .
Notez que ce nombre avec 1k bits sont énormes par tous les moyens. L'affacturage d'un tel nombre (même avec les MPQ ou d'autres) pourrait prendre des années si vous avez de la chance et à jamais sinon. Je pense que ce MPQS fonctionne bien avec des nombres d'environ 100 à 400 bits (s'ils sont composés de deux nombres premiers presque également importants, ce qui est le plus difficile du parcours).
Pour des chiffres avec plus d'environ 100 chiffres, le tamis quadratique commence à être battu par le tamis de champ de numéro général (GNFS).
@Chris carte - 100 chiffres dans quelle base? Veuillez préciser.
Dans la base décimale bien sûr. Chris a raison pour de tels nombres importants, QS (ou plus claire, MPQ, puisque Qs est de bien plus lent avec de tels chiffres) commence à devenir plus lent que GNFS.
La factorisation enregistrée actuelle est RSA768 ( Crypto-world.com/factorrecords.html ). a pris une quantité massive de travail. Il est possible de contester des numéros avec environ 150 chiffres à l'aide de GNFS sur un PC moderne standard, mais 1k bits est hors de portée à l'heure actuelle des meilleurs chercheurs.
Oui, et toutes les tentatives d'affacturage d'énormes numéros sont la plupart du temps effectuées sur des systèmes informatiques distribués où chaque nœud contribue au résultat avec une petite partie. Même alors, il faut des mois ou même des années pour terminer la tâche.
Vous n'avez pas besoin de diviser individuellement par de petits nombres premiers pour les éliminer. Prenez simplement le produit de tous les petits nombres premiers (cette pièce est prétraitée), puis calculez un GCD.
ci-dessous est un exemple d'algorithme en Java (ce n'est pas C ++ avec GMP, mais la conversion doit être assez simple) que:
x de bitlength nbits
- essaie de prendre en compte tous les facteurs principaux <100, en gardant une liste de facteurs primaires qui divisent X.
- TESTS Pour voir si le facteur restant est primordial à l'aide de Java
isprobableprime méthode
- Si le produit facteur restant est primordial avec une probabilité suffisante, nous avons réussi à affacer x. (
Stop )
- Sinon, le produit facteur restant est définitivement composite (voir les documents ISPROBABABIREPRAME).
- pendant que nous avons toujours le temps, nous courons le Pollard Rho Algorithm jusqu'à ce que nous trouvions un Diviseur d.
- Si nous manquons de temps, nous avons échoué. (
Stop )
- Nous avons trouvé un diviseur d. Nous facturons donc d, ajoutons les facteurs premiers de D à la liste des facteurs premiers de X et d'aller à l'étape 4.
Tous les paramètres de cet algorithme sont au début de la liste des programmes. J'ai cherché des nombres aléatoires de 1024 bits, avec un délai d'attente de 250 millisecondes, et je continue à exécuter le programme jusqu'à ce que je reçoive un numéro X avec au moins 4 facteurs premiers (parfois, le programme trouve un nombre avec 1, 2 ou 3 facteurs premiers première). Avec ce paramètre défini, il faut généralement environ 15-20 secondes sur mon iMac de 2,66 GHz.
Rho Algorithme de Pollard n'est pas vraiment si efficace, mais c'est simple, par rapport au tamis quadratique (qs) ou le Numéro général Tamis de champ (GNFS) - Je voulais juste voir comment l'algorithme simple a fonctionné.
pourquoi cela fonctionne: ( Malgré la réclamation de nombreux d'entre vous que c'est un problème difficile) Le fait clair est, c'est-à-dire Les nombres premiers ne sont pas si rares . Pour les nombres 1024 bits, le théorème de nombres premiers indique qu'environ 1 dans toutes les 1024 ln 2 (= environ 710)
Les chiffres sont premiers. Donc, si je génère un nombre aléatoire X qui est prime et que j'accepte la détection de prime probabiliste, j'ai correctement factorisé x.
si ce n'est pas premier, mais je prends rapidement en compte rapidement Quelques petits facteurs et le facteur restant sont (probabilistes) primordiaux, alors j'ai correctement factorisé x.
sinon je viens d'abandonner et de générer un nouveau nombre aléatoire. (que l'OP dit est acceptable)
La plupart des chiffres facturés avec succès auront 1 gros facteur premier et quelques petits facteurs premiers.
Les chiffres difficiles à facteurs sont le plus difficile à facteur. ceux qui n'ont pas de petits facteurs premiers et au moins 2 grands facteurs premiers (celles-ci incluent les clés cryptographiques qui sont le produit de deux grands nombres; l'OP n'a rien dit sur la cryptographie), et je peux simplement les sauter lorsque je manque de temps. xxx
Pour le moment, vous ne pouvez pas factoriser un Bigint avec GMP. Vous pouvez convertir votre Bigint en d'autres bibliothèques et utiliser leurs algorithmes d'affacturage. Notez que l'affacturage des entiers avec >> 20 chiffres nécessite des algorithmes spécialisés et est presque exponentiellement lente.
Départ:
Vous pouvez utiliser l'algorithme de factorisation Pollard P-1 si le nombre que vous souhaitez facteur a de petits facteurs premiers. Il a pris en charge un facteur prime de 30 chiffres du nombre 2 ^ 740 + 1. ECM est un algorithme similaire mais sous-exponétial, mais la mise en œuvre est plus difficile. Le temps que l'algorithme est basé sur ce que la liaison B est définie comme. Il factimera n'importe quel nombre qui a un facteur p où p - 1 est b-lisse. sorties - 7465647
Temps d'exécution - 0.003 secondes Un autre algorithme d'affacturage créé par J.Pollard était le polard rho algorithme qui n'est pas si rapide mais nécessite très peu d'espace. Leurs façons aussi de la parréliser. Sa complexité est O (n ^ 1/4) sorties - 353
Heure d'exécution - 0.003S
Qu'entendez-vous par premier dans ce contexte? Essayez-vous de générer de grands nombres premiers? Ou voulez-vous dire préparer les chiffres à l'avance pour une utilisation particulière?
Vous appuyez sur la petite touche Squishy sur le côté du nombre pour le grimper sur quelques-quelques encoches. C'est donc prime et le moteur commence à fonctionner correctement.
Je suis d'accord, l'anglais à ce sujet est assez mauvais pour que je puisse deviner ce que l'OP voulait dire, mais ce n'est certainement pas clair.
La probabilité du cas difficile de nombres composites avec deux facteurs premiers n'est pas négligeable IMHO (mon estimation rapide donne de l'ordre de 1 en 100 000 numéros aléatoires avec 1024 bits).
@starBlue: Intéressant! Pourriez-vous expliquer vos calculs plus en détail?
Fondamentalement, j'utilise qu'il existe environ
n / journal n des nombres premiersn pour approcher le nombre de nombres premiers 512 bits. Le carré est approximativement le nombre de paires dures avec 1024 bits (la plupart de ces nombres premiers ont près de 512 bits).Notez que cela estime simplement une limite inférieure pour être pratiquement impossible à facteur. Il existe de nombreux autres numéros qui peuvent toujours être trop difficiles à prendre en compte rapidement.
BTW, pourquoi avez-vous besoin de prendre en compte ces chiffres?