Bonjour à tous et bonne année première,
J'ai récemment découvert l'existence du système de numération bijective en base k.
Je me demandais de quelle manière se manifestaient les contraintes supplémentaires obtenues par rapport au système classique. Je parle essentiellement de la base 2.
En effet, en binaire classique, les tables d'addition et de multiplication sont "plus" surjectives que celles en base 2-adique. Par "plus", je veux dire que le nombre configurations en input donnant le même output est plus élevé. Par conséquent, lors de l'opération inverse, l'indétermination est plus grande.
Je me demande où se manifeste cette réduction d'indétermination lorsqu'on utilise le système 2-adique. Notamment, pour l'opération de multiplication inverse.
En effet, soientun entier demi-premier (produit de deux nombres premiers).
Soitoù
et
sont des entiers premiers et
.
Soientet
, où
et
, de sorte qu'ils s'écrivent en base 2-adique :
et
.
de même pour:
.
Si on désire retrouver les deux facteurs non-triviaux de, on obtient un système de N équations à 2N inconnues (2*(N/2)=N ~ P+Q inconnues pour les facteurs, et N inconnues pour le vecteur des restes (reports).
Un méthode utilisée avec le système binaire classique est exponentielle en la taille N du nombre à factoriser, étant donné que chaque équation fournit deux possibilités avec lesquelles il faut tester le reste de "l'arbre binaire" engendré.
Cela provient du fait que les tables d'addition et de multiplication sont surjectives en binaire classique (par exemple, si le résultat d'une multiplication est 0, on ne sait pas si ça provient de 0*0 ou 0*1, ou par exemple si le résultat d'une addition est 0, on ne sait pas si ça provient de 0+0 ou de 1+1 (modulo le reste))
Tandis que les tables pour le système 2-adique lèvent cette ambiguité, si l'on tient compte du reste :
x | 1 2
----------
1 | 1 2
2 | 2 22
+ | 1 2
-----------
1 | 2 11
2 | 11 22
Ma question est : comment se matérialise ce gain d'information par rapport au système binaire classique? En terme de complexité d'un tel algorithme de factorisation qui, si le raisonnement est correct, devrait être plus petit que O(2^N)...
Je vous remercie d'avance pour vos réponses!
-----