Existe-t-il un moyen facile de trouver deux valeurs qui, lorsqu'elles sont multipliées, produisent un motif de bits exact?

Question

À des fins de test, je dois trouver deux valeurs entières de 64 bits qui se multiplient exactement en une valeur intermédiaire de 128 bits avec un modèle de bits spécifique. Évidemment, je peux générer la valeur intermédiaire souhaitée et diviser par des valeurs aléatoires jusqu'à ce que je trouve une combinaison qui fonctionne, mais existe-t-il un moyen plus efficace?

Answer 1

Ce problème ressemble à une une factorisation d'entiers . Malheureusement, aucun algorithme rapide n’est connu, mais en regardant cette page de Wikipedia, certains algorithmes (peut-être délicats) sont plus rapides que la division d'essai.

Answer 2

J'étais sur le point de publier la même chose que j_random_hacker. J'ajouterai simplement que si le nombre 128 bits est primordial ou s'il a un facteur premier supérieur à 64 bits, il n'y aura pas de solution à votre problème.

Answer 3

Et j'ajouterai simplement au commentaire précédent: si le nombre 128 bits a un facteur premier supérieur à 64 bits, alors il a certainement un facteur inférieur à 64 bits:)