Checksum : challenge

Bonjour,

Dans beaucoup de challenge javascript on peut voir ce genre de script:

Code:

---

1 2 3 4 5 6

var password = prompt("Enter password",""); var sum = 1.0; for (i = 0; i<password.length; i++) { sum *= password.charCodeAt(i); } if (sum == 2476409006188517400) {Good}

---

Comme vous l'aurez surement deviner le but de ce challenge est de trouver le mot de passe !

Quel est la meilleur solution pour le résoudre ?
- Faire un brute force ?
- Esseyer de s'approcher assez près de la valeur 2476409006188517400 et ensuite esseyer quelques combinaisons pour esseyé d'arriver au bon chiffre ?
- Autre solution....

Merci d'avance...

Salut,

Deja je ne pense pas que la solution a ce probleme soit unique, il doit probablement y avoir plusieurs password dont la somme va correspondre au chiffre.

deja le password peut etre ecrit dans n'importe quel ordre et ca va fonctionner pareil, a moins que charCodeAt(i) tienne compte de la position i.

ensuite tu peux decomposer ton chiffre en facteurs premiers et tu trouveras une solution.

XXiemeciel

Je n'y avait pas dutout pensé à décomposer se nombre en facteur premier: pas bête dutout :)

Je n'y ait pas pensé sur le coup mais la décomposition en facteur premier n'est pas si pratique que ça :
- Je vais me retrouver avec des nombres du genre: 3,5,7,11,13 et re-traduire ces nombres en code ascii : c'est pas évident...

Il faudrai que le password ne soit formé que de chiffres et de lettres (pour simplifier le problème :)).

Rappel du code ascii: 48-57 (0-9), 65-90 (A-Z), 97-122 (a-z)

Donc il faudrait diviser le nombre 2476409006188517400 par les différents nombres cité ci-dessus mais à un certain moment de la division, je risque de ne plus savoir diviser mon nombre par un des nombres ci-dessus.
Et donc il faudrait tout recommencer à diviser avec d'autres diviseurs !

Comment résoudre ce problème ?

si 2476409006188517400 est donné alors
2476409006188517400 =
2^3 * 3^6 * 5^2 * 7 * 11^4 * 13 * 29 * 37 * 109^2

par chance, le nombre de facteurs premiers distincts est limité ( 9 différents )

Il suffit alors de decider arbitairement que certains alphanumériques correspondent à 2 ou 3 ou 5 ou... et de réaliser en consequence la multiplication en fonction des caracteres entrés.
Attention ce chiffre necessite un codage entier 64 bits!

ben je trouve que ça limite déjà pas mal:
- il faut des entiers compris entre les char code "typiques"
- ça donne une borne sur la longueur maxi et mini du password
- il "reste" à trouver les combinaisons utilisant tous les nombres de la décomposition, avec une longueur bornée et un total connu

=> je tenterais pê une résolution de contrainte pour ça

Formellement:
- soit n la longueur du password avec b_inf <= n <= b_sup (les bornes sont faciles à trouver à partir de la décomposition)
- Vj les valeurs de la décomposition en facteurs premiers en conservant les doublons
- Xi les nombres cherchés (ou charactères) sont tels ques Xi >= 0 et Prod(Xi) = Total
- Bij un indice boolean déterminant si la Valeur Vj est utilisée pour l'inconnue Xi
- contrainte sur l'utilisation unique de chaque Vj : sum_i(Bij) = 1
- et ne pas oublier: Xi = Bij * Vj (avec un léger abus de notation ;) )
- il faut aussi tenir compte du fait que tous les Xi ne doivent pas etre utilisé étant donné que b_inf <= i <=b_sup et donc rajouter des variables binaires similaires à Bij

je pense que c'est tout pour la formalisation mais ça vaudrait le coup d'essayer non ? ou j'ai pê omis qqch dans la complexité ?