Math: Factorisation

Question

Omettre les détails des méthodes de calcul des nombres premiers et des méthodes de factorisation.

Pourquoi prendre la peine de factoriser?

Quelles sont ses applications?

Answer 1

Wow, tant de bagarres dans ce fil.

Ironiquement, cette question a une réponse valable majeure.

La factorisation est en réalité très utilisée dans les algorithmes de cryptage / décryptage, à tel point que la RSA organise régulièrement des compétitions dans lesquelles la tâche est de factoriser certains grands nombres qui sont des multiples de très grands nombres premiers.

En effet, plusieurs algorithmes de cryptage / décryptage reposent sur le principe selon lequel la factorisation prend beaucoup de temps, ce qui (prétendument) rend difficile et / ou peu pratique de casser certains algorithmes de cryptage / décryptage étant donné que le pirate / pirate n'a pas accès aux clés publiques / privées.

Les algorithmes de factorisation peuvent ensuite être utilisés pour vérifier la force d’un algorithme de cryptage / décryptage donné.

Answer 2

Le cryptage asymétrique basé sur RSA / DAS, la factorisation est une chose très difficile. Si je vous attribue un nombre, celui-ci, lorsqu’il est imprimé, est aussi gros que la page d’un journal et vous indique "Ce nombre a été généré en multipliant deux nombres premiers. Maintenant, factorisez-le "... pensez-vous pouvoir le faire?" Croyez-moi, tout moyen connu de le faire prendra une éternité. Il n’existe aucun moyen efficace de le faire sans recourir à des tonnes de temps de calcul (des siècles) ou de beaucoup de mémoire (plus de stockage que tous les serveurs Internet du monde). Si vous trouvez un moyen simple de factoriser des nombres aussi importants, vous cassez la signature de courrier électronique et le protocole SSL (HTTPS), par exemple.

Cependant, il existe d'autres tâches liées à la factorisation. La factorisation ne concerne pas seulement le nombre. Parfois, il s'agit de "pourquoi les polynômes sont des facteurs d'un autre polynôme". Ainsi, les tâches mathématiques peuvent dépendre de la factorisation et permettre ainsi de résoudre de nombreux problèmes. La factorisation effective est donc d'une grande valeur. Même les matrices peuvent être factorisées.

Answer 3

Il peut être utilisé pour déchiffrer certains types de chiffrement (si la clé est suffisamment petite).

Vous en auriez également besoin pour certains types de logiciels scientifiques.

Une autre application consiste à répondre aux Questions sur ProjectEuler .