numération bijective en base 2 VS. numération binaire classique

[geometrodynamics_of_QFT]

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, soient un entier demi-premier (produit de deux nombres premiers).

Soit où et sont des entiers premiers et .

Soient et , 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!
-----

[geometrodynamics_of_QFT]

Dès que ce n'est pas un cas d'école, il n'y a plus personne...ce forum n'a pas changé

Je serais ravi d'expliciter des parties plus obscures pour ceux parmi les lecteurs qui ne comprendraient pas un passage dans la question...
Il s'agit ici d'un raisonnement intuitif, le but n'est pas d'être académique, mais de voir si la question que je me pose est justifiée a priori...
Je vous remercie d'avance encore une fois!

[Médiat]

Bonjour,

Dès que ce n'est pas un cas d'école, il n'y a plus personne...ce forum n'a pas changé

Dommage, j'ai failli répondre !

[geometrodynamics_of_QFT]

Dommage, j'ai failli répondre !

Haha dommage que vous soyez si susceptibles, et que vous preniez les critiques d'un forum personnellement.
Heureusement, j'ai trouvé les équations manquantes, et je peux à présent inverser la matrice (qui ne contient plus de lignes nulles contrairement au cas binaire classique...)
Merci quand même pour votre aide précieuse

*** Critique de la modération ***

[A voir en vidéo sur Futura]

[geometrodynamics_of_QFT]

Mais je suis tout de même curieux de savoir ce que vous alliez dire...

Allez, svp, ne faites pas l'enfant...je m'excuse d'avoir usé d'humour grinçant...ça vous convient?

(j'ai une personnalité impertinente, chassez le naturel il revient au galop...mais c'est de bonne guerre et pas du tout du côté de la méchanceté)

[invite23cdddab]

Je ne comprends absolument pas ce raisonnement :

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 :

Il est évident que si l'on tient compte de la retenue, on sait si 0 provient de 1+1 ou de 0+0, de même que dans le système 2-adique, on ne sait pas si 2 viens de 1+1 ou de 2+2 si on ne tiens pas compte "de la retenue"...

[geometrodynamics_of_QFT]

Salut Tryss,

Merci pour la réponse. Admettons pour l'addition.
Qu'en est-il de la multiplication? Là c'est différent non?
En fait, j'aimerais travailler avec les résultats complets, et pas uniquement sur un seul "bit"...
Donc partir du résultat, et retrouver les deux facteurs. Dans ce cas, le résultat comporte le dernier "bit" (celui du tableau) ainsi que le ou les "bits" du reste, afin de pouvoir profiter de la réduction du degré de surjectivité des tables.

[invite23cdddab]

"pouvoir profiter de la réduction du degré de surjectivité des tables"

Je ne suis absolument pas convaincu qu'il y ai une "réduction du degré de surjectivité des tables" (enfin, si j'ai compris de quoi tu parles).

Je ne vois pas en quoi

x | 1 2
----------
1 | 1 2
2 | 2 22

Est "moins surjective" que

x | 1 10
----------
1 | 1 10
10| 10 100

[geometrodynamics_of_QFT]

Hello,

les deux tables que tu donnes ont en effet pour moi le même "degré de surjectivité", mais la seconde n'est pas une table complète d'un système de numération (si c'est décimal, il manque des chiffres...)
En revanche, la table binaire :

x | 0 1
----------
0 | 0 0
1 | 0 1

a bel et bien un degré de surjectivité supérieur, on est d'accord?

On gagne nécessairement des informations...le binaire est composé d'un élément absorbant (0 pour x) et d'un élément neutre (1 pour x, et 0 pour +)...alors que le système 2-adique n'a qu'un élément neutre (1 pour x)...

[geometrodynamics_of_QFT]

Pour relancer le topic :

Imaginons que l'on veuille factoriser le nombre , et que la seule chose qu'on sache, est que c'est un produit de deux nombres premiers distincts différents de 0 : où ,

En notation binaire, on écrit où , de sorte que s'écrit en little-endian.

En notation 2-adique, on écrit où

Par exemple, si on applique la situation pour :
Il s'écrit en binaire : 1111, et en 2-adique : 1111 aussi. On a donc la taille en bits de

Supposons que la taille des deux facteurs soit deux fois moindre : soit

On doit donc résoudre, en notation 2-adique :


De sorte qu'on peut écrire:



où les sont les différents bits des restes qui émergent lors de l'addition des différents termes.


Je cherche une méthode pour résoudre ce système d'équations, qu'on sait à l'avance bien posé : en effet, on sait que la solution existe et est unique, en vertu du théorème fondamental de l'arithmétique.
Je vous remercie d'avance pour votre aide!

[geometrodynamics_of_QFT]

Je me suis gouré dans la dernière ligne du système d'équations, c'est plutôt :

[geometrodynamics_of_QFT]

Bon, je résouds pour avec inconnus (lol)

On a donc en 2-adique :

On écrit et

Comme on sait que p et q sont premiers (impairs), on sait qu'ils terminent par 1...

On doit résoudre :
(a) et on sait que

(b) donc on choisit et (puisque le sytème est complètement symétrique en p et q). On a donc

On a déterminé les facteurs, on poursuit pour vérifier :

(c) donc

(d) ok

On a donc obtenu :
et
Ce qui donne en décimal :
et

Cette méthode a-t-elle de l'avenir?

[geometrodynamics_of_QFT]

Un autre exemple, pour voir si ça tient la route: avec inconnus

On a donc en 2-adique :

On écrit et

Comme on sait que p et q sont premiers (impairs), on sait qu'ils terminent par 1...

On doit résoudre :
(a) et on sait que

(b) donc on choisit et (puisque le sytème est complètement symétrique en p et q). On a donc

(c)
Puisque doit se terminer par , alors termine forcément par , et par la table d'addition, on sait que soit , soit . Dans les duex cas, on a .

A ce stade, soit on vérifie les deux possibilités directement et on retient la bonne, soit on utilise le reste des équations pour déterminer la bonne...
Si on continue, on a :

(d) donc doit être pair.
Donc forcément, et , on a levé l'indétermination...on a donc

vérification:

(e) donc
(f) ok!


On a donc obtenu :
et
Ce qui donne en décimal :
et

Quelqu'un pourrait-il me dire pourquoi ça ne marcherait pas avec de plus grands nombres?

[geometrodynamics_of_QFT]

c'est aux étapes (c) et (d) qu'on profite de la réduction du degré du surjectivité des tables d'addition et de multiplication : en binaire classique, il aurait fallut ajouter une possibilité supplémentaire...

De plus, on voit que le système à résoudre est composé de deux matrices carrées triangulaires. En binaire classique, certaines de ses lignes sont nulles, ce qui la rend non-inversible. Tandis qu'en 2-adique, on SAIT que la matrice est inversible, puisqu'on SAIT que le système possède une solution, et qu'elle est unique (par le théorème fondamental de l'arithmétique : la décomposition d'un nombre en facteurs premiers est unique modulo l'ordre des facteurs)

En gros, si , on a :



Avec le vecteur des restes mal défini.
On voit bien que la matrice est inversible, puisqu'aucun des p_i n'est nul...
Et ce n'est que la moitié des équations!!!
Donc la connaissance de la moitié des bits de N permet a priori de déterminer complètement les facteurs! (avec ces fichus restes qui viennent tout compliquer...)

[geometrodynamics_of_QFT]

Je crois qu'on pourrait remplacer dans l'équation précédente par quelque chose du genre:



où et


De façon à ce que le i-ème élément du membre de droite ressemble à ...

[invite23cdddab]

Sauf que ta matrice n'est pas inversible : si elle était inversible, tout les nombres se décomposeraient de façon unique en un produit de deux facteurs de même taille, ce qui est grossièrement faux.

Quand tu dis "Tandis qu'en 2-adique, on SAIT que la matrice est inversible, puisqu'on SAIT que le système possède une solution, et qu'elle est unique (par le théorème fondamental de l'arithmétique : la décomposition d'un nombre en facteurs premiers est unique modulo l'ordre des facteurs)", il y a un problème. En effet, si l'existence et l'unicité d'une solution à ton problème ne dépend pas de l'écriture du nombre. On pourrait donc, si il était correct, employer le même raisonnement pour la matrice binaire :

"En binaire/décimal/unaire/base42, on SAIT que la matrice est inversible, puisqu'on SAIT que le système possède une solution, et qu'elle est unique (par le théorème fondamental de l'arithmétique : la décomposition d'un nombre en facteurs premiers est unique modulo l'ordre des facteurs)"

[geometrodynamics_of_QFT]

Salut,

Merci pour ta réponse.
Mais, n'y a-t-il pas une différence fondamentale entre un système de numération qui contient un élément absorbant pour la multiplication (comme le binaire, le décimal, la base 42) et un système de numération où il n'y en a pas (comme le n-adique)?
Pareil pour l'addition : pas d'élément neutre pour le n-adique, et un élément neutre pour les systèmes classiques...

Ca change forcément quelque chose en termes d'indéterminations de systèmes algébriques non?


Dans un système classique, si on a l'équation x=0.y, il y a une infinité de solutions pour y.
(Si 'y' est un chiffre dans une base n, il y a n solutions pour 'y')
Ce type d'équations n'arrive pas en n-adique, puisque le 0 n'existe pas...

[geometrodynamics_of_QFT]

Et aussi :

Concernant le nombre de bits des facteurs, il n'est évidemment pas toujours égal à la moitié du nombre de bits du nombre à factoriser.
Dans les deux exemples que j'ai fait, c'était le cas.

Mais si ce n'est pas le cas, je suppose qu'à partir d'une des équations, on arrivera à la conclusion que p_i ou q_i doit être nul...on saura alors que tous les p_i ou q_i suivants seront nuls aussi, et ne continuer qu'avec l'autre facteur...

On peut même supposer au départ que la taille des facteurs est la même que celle du nombre à factoriser, et l'algorithme détermine "on-the-run" la taille des facteurs (dès qu'un bit d'un facteur doit être nul) non?

[geometrodynamics_of_QFT]

Pour illustrer mes propos avec un nouvel exemple :


si on suppose que la taille de facteurs est plus grande que leur taille réelle, toute la série de termes à additionner, fournissant des bits au-delà de la taille de N, doivent s'annuler.

[geometrodynamics_of_QFT]

zut, j'ai loupé de fêter mon 1000ème message...
je fêterai mon 10000000000ème message en base 2 très prochainement ^^ (plus que D messages en base 16 lol)

[geometrodynamics_of_QFT]

zut, je me suis trompé c'est pas D mais F...
mais je ne sais plus modifier, alors pour que ça soit correct, j'écris

[geometrodynamics_of_QFT]

deux messages.