Y a-t-il une relation entre les bits des nombres quand l'un est divisible par un autre? Quelle est la relation entre les bits de 36 et les séquences de bits de 9 ou 4 ou 12, ou entre 10 (1010) et 5 (101), ou 21 (10101) et 7 (00111)?Question sur les relations entre deux nombres
Merci. Je suis désolé si une phrase n'est pas correcte, mais j'espère que vous comprenez ce que je veux.
Prenons l'exemple de 36.
36 = 0010 0100
36 est 4 * 9, qui est
4 = 0100
9 = 1001
Si vous les multipliez (comme vous le feriez sur une multiplication normale), vous aurez
0100 x
1001
--------
0100
0000
0000
0100
-------
0100100
Donc essentiellement 0100 x 1001 = 0010 0100 (vous pouvez répéter Maintenant, y a-t-il une relation spéciale qui vous permettra d'obtenir tous les diviseurs de 36 simplement en regardant ses bits? La réponse, hélas, est non :)
EDIT: il n'y a pas de relation CONNUE au moins mais, qui sait, dans le futur peut-être qu'un mathématicien intelligent en trouvera un. À partir d'aujourd'hui, la réponse est toujours non.
Qu'est-ce qui vous fait penser que la réponse est "NON"? Avez-vous une preuve qui traîne quelque part? –
Il existe un monde de la littérature mathématique sur la complexité de la factorisation d'entiers. Il a été prouvé qu'il n'y a pas de "raccourci" pour obtenir les diviseurs d'un nombre en l'écrivant en binaire. http://en.wikipedia.org/wiki/Integer_factorization – dmazzoni
@Dmazzoni. Il n'a pas encore été montré. Les gens pensent que la factorisation d'entiers se situe entre P et NP-Complète, semblable à l'isomorphisme de graphique, mais c'est tout. Il n'y a aucune preuve pour le dire avec conviction. –
Donc, vous voulez savoir si vous pouvez «rapidement» faire Integer Factorization en regardant simplement les bits?
Bonne chance avec ça!
+1 La réponse est correcte et tout aussi légitime (sinon plus) que la question à laquelle elle répond. – andand
De toute évidence, ce a est un multiple de b SUFFISAMMENT étant donné les representions binaires de a et b (c'est ce que fait le matériel lors de l'exécution du code suivant
boolean isMultiple = a % b == 0;
) et donc il y a une telle relation .
Poser une question plus précise pour obtenir une réponse plus précise ...
je sais que ce n'est pas exactement ce que vous demandez, mais il peut être utile. Il existe de nombreuses astuces pour établir la divisibilité des nombres binaires par manipulation de bits. Par exemple, un nombre binaire est divisible par trois si la somme de ses bits binaires pairs moins la somme de ses bits binaires impairs tout le module 3 est zéro. Voici un lien sur binary divisibility.
Le plus facile à voir est le nombre de 0 consécutif dans les chiffres les moins significatifs qui désigne la plus grande puissance de deux qui est un facteur de votre nombre n. Il y a apparemment d'autres tests, comme l'a souligné DonnyD (je ne le savais pas), mais je suppose qu'ils ne vont pas très bien à l'échelle. Si c'était le cas, la cryptographie à clé publique, telle qu'elle est généralement mise en œuvre, deviendrait rapidement une chose du passé. Cela ne veut pas dire que de telles méthodes ne peuvent être découvertes/inventées. Par exemple, il a été montré que des nombres arbitrairement grands peuvent être facilement factorisés using quantum methods, mais personne n'a jamais été en mesure de mettre en œuvre un système de travail.En fin de compte, nous avons confié notre système financier et notre système de sécurité nationale aux méthodes basées sur l'ICP, principalement parce que nous supposons que les numéros d'affacturage sont difficiles à obtenir pour des nombres arbitrairement élevés. Mais comme Moron semblait l'impliquer dans sa réponse, vous êtes invités à lui donner un tourbillon.
Je n'ai aucune idée. –
vous voulez savoir s'il existe une relation entre la représentation binaire d'un nombre et ses facteurs? –
@Paul: C'est ce que j'ai compris aussi. –