Discussion :

[Noteirak]

Bonjour !
Je suis face à un problème assez épineux qui demande un algorithme pour être régler, mais malheureusement je n'ai pas encore assez de compétences pour montrer ce genre d'algorithme (ou pas assez de logique, la suite vous le dira ).

J'aimerai monter un alogorithme de conversion capable de transformer n'importe quel chaine de caractère d'une longeur de 16 octets (répondant au standart ASCII) pouvant avoir n'importe quel caractère ASCII, en une chaine de maximum 24 caractères ne contenant que [0-9,a-f].
L'ordre, l'emplacement, ou n'importe quoi d'autre des différents elléments devra permetre de retrouver la chaine originel.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Ex : ChaineDe16Elemen
->    af5cd129e3ac59be[...]
      --> Cette chaine devra permetre via un algorithme de retrouver la chaine originelle (ChaineDe16Elemen)

Moins il y a des caractères pour la seconde chaine, mieux c'est !
Si il existe un algorithme de cryptographie me permetant la meme chose, je suis prenneur !
Si vous avez des suggestions ou des idées pour programmer ce genre d'algorithme, votre aide est la bienvenue ! Merci d'avance.

[Luc Hermitte]

Ca rentre pas.
ASCII -> 7 bits par caractères.
16 * 7 = 112 bits
112 / 4 -> 28 quartets (nombre sur 4 bits -> de 0 à 15 (15 == f en hexa) pour stocker ta chaine.

28 > 24 => bug dans les énoncés.

Ou alors il faut une compression qui assure qu'il y aura toujours une réduction. Je ne suis pas un pro du domaine, mais je pense que ce n'est pas possible (avoir une correspondance exacte sur 127^16 valeurs dinstinctes possibles qui tienne toujours en 24 quartets). Quelque soit l'ago de compression, je pense que l'on pourra toujours trouver une chaine contre-exemple qui dépasse.

Quant au cryptage, en général on augmente par rapport à la taille de la chaine originale.

[Médiat]

>>Luc, je confirme tout le début de ta démonstration, mais

Ou alors il faut une compression qui assure qu'il y aura toujours une réduction.

Quelque soit la compression il y a quand même 128^16 (5*10^33) chaînes possibles au départ et 16^24 (8*10^28) à l'arrivée, donc pas d'injection possible (donc il n'y a pas toujours réduction (sinon tous les fichiers pourraient se comprimer en un seul caractère ))!

[Luc Hermitte]

A défaut de relacher la contrainte sur le 24, il faudrait éliminer des caractères. p.ex. le code ASCII 0 sert à définir une fin de chaine (si mes souvenirs sont bons).
En l'éliminant, la taille de l'ensemble de départ se reduit à \sigma_0^{15} 127^i , soit \frac^{127^16-1}_{127-1}.

C'est toujours trop gros mais ça donne l'idée -- virer les 32 premiers caractères est toujours insuffisant. Une fois cet ensemble réduit, il est très facile de l'ordonner. Le résultat à générer correspondrait à la position (en hexa) de l'élément de départ dans son ensemble trié.

[Médiat]

64^16 = 16^24, donc il faut réduire l'alphabet de départ à 64 signes !

[gangsoleil]

64^16 = 16^24, donc il faut réduire l'alphabet de départ à 64 signes !

26 minuscules + 26 majuscules + 10 chiffres = 62 caracteres... reste pas beucoup de place !

[Noteirak]

Les lettres peuvent servir à plus que bettement dire la position d'une autre !
Ex : si a en première position, ac b en second, 3 en troisième, etc...
ou bien utiliser le code hexa de ces valeurs ou le code binaire pour programmer des instructions.
Je pense sérieusement qu'il y a moyen de cette facon, mais dite moi ce que vous en pensez.

J'aimerai que les lettres soient des instructions ! Et si besoin est avec un tableau de départ ou quelque chose... vous voyez ce que je veux dire ?

[Médiat]

vous voyez ce que je veux dire ?

Euhh Non

Ta question de départ est :

transformer n'importe quel chaine de caractère d'une longeur de 16 octets (répondant au standart ASCII) pouvant avoir n'importe quel caractère ASCII, en une chaine de maximum 24 caractères ne contenant que [0-9,a-f].
L'ordre, l'emplacement, ou n'importe quoi d'autre des différents elléments devra permetre de retrouver la chaine originel.

Si cela n'a pas changé, il n'y a qu'une réponse : impossible ! Il te faut une injection et ce n'est pas possible si l'ensemble de départ est plus grand que l'ensemble d'arrivée.

[Noteirak]

c'est n'es pas un algo en soit, enfin si mais non

Je veux considérer la chaine [0-9,a-f] comme un script si vous voulez, un code source pour permetre d'exécuter des instructions pour retrouver la chaine original !

[Nemerle]

Précise, car j'ai l'impression qu'un script ne change rien au problème.

A moins d'utiliser tes 24 octets pour faire une machine de turing...