Problème de dénombrement ....

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 13:38

seb69 a écrit:Le C serait effectivement une bonne chose, ma boite ne l'utilises pas, et ne veut pas en entendre parler .... faut faire avec les contraintes ....

Par contre si tu pouvais, ou les autres lecteur de ce post, m'éclairer plus sur le traitement, je suis preneur ...

J'ai posté le code en PHP un peu plus haut. L'algorithme:

- Tableau a 20 éléments: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- Boucle: tant que le premier élément est différent de 128 {
-- Incrémentation du dernier élément
-- Définition de l'élément de travail pour une boucle dynamique: c = 20 (dernier élément)
-- Tant que le c-ieme élément du tableau est égal a 128, remettre celui-ci a zéro, décrémenter c de 1, et augmenter le nouveau c-ieme élément du tableau de 1
-- Lister la possibilité
- }



bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 13:47

On peut quand même faire beaucoup plus simple !
on sait le nombre de codes possibles en tout, nomons le N.
On convertit tous les nombres entre 0 et N en base 128, et c'est terminé :p
on a tous les codes possibles en 0 et 20 caractères, en considérant qu'un code du genre
00000000001111111111 est en fait un code à 10 charactères.

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 13:48

bruce.ml a écrit:On peut quand même faire beaucoup plus simple !
on sait le nombre de codes possibles en tout, nomons le N.
On convertit tous les nombres entre 0 et N en base 128, et c'est terminé :p
on a tous les codes possibles en 0 et 20 caractères, en considérant qu'un code du genre
00000000001111111111 est en fait un code à 10 charactères.

:doh:
Et je n'y avais meme pas pensé!

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 13:52

Bah l'informatique c'est la science du paresseux :P fais en un peu et ça viendra vite :pc: :lol5:

seb69
Messages: 8
Enregistré le: 09 Aoû 2007, 12:30

par seb69 » 09 Aoû 2007, 13:53

bruce.ml a écrit:On peut quand même faire beaucoup plus simple !
on sait le nombre de codes possibles en tout, nomons le N.
On convertit tous les nombres entre 0 et N en base 128, et c'est terminé :p
on a tous les codes possibles en 0 et 20 caractères, en considérant qu'un code du genre
00000000001111111111 est en fait un code à 10 charactères.



Bonne idée, mais je ne traite pas que des nombres, mais tout type de caractères Alpha-numériques ....

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 13:57

seb69 a écrit:Bonne idée, mais je ne traite pas que des nombres, mais tout type de caractères Alpha-numériques ....

Base 128 = 128 possibilités différentes. Donc, en convertissant tous les nombres entre 1 et 128^20, tout nombre sera divisé jusqu'a ce qu'il puisse s'exprimer dans la base 128 (pense au binaire: 2^0, 2^1, 2^2 etc... Sauf qu'ici, 2 est remplacé par 128)...

Apres, si un nombre de 1 a 128 te gene, prends donc l'équivalent ASCII. (Ah lala, ces ingénieurs sécurité. Un poil au creux de la main serait un euphémisme parfois... :mur: )

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 13:58

Oui bien sûr, une fois que tu as généré tes nombres, tu les convertis en chaines de caratères par la table ASCII.
exemple :
000000000000000 56 23 47 105 8
est un nombre de 20 chiffres écrit en base 128, il donne la chaine de caratères
ASCII(56) ASCII(23) ASCII(47) ASCII(105) ASCII (8)

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 14:00

J'ai mis 128 car mon collègue Anima l'avait mis, mais il faut remplacer par le nombre de caractères que tu souhaites utiliser, puis tu établis une bijection entre [1,ce_nombre] et ton ensemble de charactères :)

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 14:02

bruce.ml a écrit:J'ai mis 128 car mon collègue Anima l'avait mis, mais il faut remplacer par le nombre de caractères que tu souhaites utiliser, puis tu établis une bijection entre [1,ce_nombre] et ton ensemble de charactères :)

Arrete, il va y avoir des fusibles a remplacer :we: de plus, l'ASCII n'est pas bijectif. En effet, l'ASCII a une période de 256! :ptdr:

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 14:13

que veux tu dire par "l'ASCII est périodique" ?
que les fonctions de conversion le sont souvent ? ;)

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 14:15

bruce.ml a écrit:que veux tu dire par "l'ASCII est périodique" ?
que les fonctions de conversion le sont souvent ? ;)

Valeur ASCII (256), ca te dit quelque chose? En binaire, pour l'ASCII, on parle d'un octet, non?

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 14:18

Oui, mais qu'appelles tu "l'ASCII" ?

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 14:20

bruce.ml a écrit:Oui, mais qu'appelles tu "l'ASCII" ?

La table de code associant les 8 derniers bits d'un nombre a une lettre, et inversement.

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 14:23

anima a écrit:La table de code associant les 8 derniers bits d'un nombre a une lettre, et inversement.


Dit comme ça c'est bijectif :P
Mais je comprends ce que tu as voulu dire ;)

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 14:29

bruce.ml a écrit:Dit comme ça c'est bijectif :P
Mais je comprends ce que tu as voulu dire ;)

Pas bijectif sur N. Bijectif sur [0,256] par contre, je suis d'accord.

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 18 Juin 2007, 23:54

par bruce.ml » 09 Aoû 2007, 14:34

J'ai l'impression qu'on a fait peur à Seb :S

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 15:49

bruce.ml a écrit:J'ai l'impression qu'on a fait peur à Seb :S

Blague a part, la boite en question pour qui la "question" était posée était sans doute le crédit mutuel; vive les indices.

alben
Membre Irrationnel
Messages: 1144
Enregistré le: 18 Mai 2006, 21:33

par alben » 09 Aoû 2007, 16:31

seb69 a écrit:Pour ce qui est de l'ordi, pas de problèmes, la machine est extrèment puissante (Octo processeur & 12 Go RAM ...).

Ben voyons !
soit à peine plus que
Avec une machine à 360 teraflops (genre Blue gene), il suffira de d'attendre années soit un milliard de fois l'âge de l'univers.

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 11:00

par anima » 09 Aoû 2007, 16:33

alben a écrit:Ben voyons !
soit à peine plus que
Avec une machine à 360 teraflops (genre Blue gene), il suffira de d'attendre années soit un milliard de fois l'âge de l'univers.

alben, ca, c'était la partie facile. La partie difficile consiste a lister toutes les possibilités, et établir un algorithme (fait par bruce) :ptdr:

jkevinlb
Membre Naturel
Messages: 10
Enregistré le: 08 Aoû 2007, 16:36

par jkevinlb » 11 Aoû 2007, 02:29

seb69 a écrit:Merci à tous les 2 d'intervenir aussi vite sur le sujet ....
Pour ce qui est de l'ordi, pas de problèmes, la machine est extrèment puissante (Octo processeur & 12 Go RAM ...).

Ce que je recherche, c'est une formule, qu'informaticien, je nommerai plus volontiers algorithme, qui me permette :

si l'on admet avoir 127 caractères utilisables pour composer un mot de passe, dont la taille est : au minimum de 1 caractères, et au maximum de 20 caractères, et que le même caractère peut être utilisé plusieurs fois dans la composition du mot de passe ( par un exemple : mot de passe pourrait très bien être AAAAAAA), je veux pouvoir lister tous les mots de passes possibles.

Bien à vous.


128^20 =1393796574908163946345982392040522594123776

En Go sur le disque: 1298074214633706907132624082305024

Faut pas s'étonner qu'il n'y aie pas de DB de mot de passes, la taille n'est pas réaliste et du moment qu'on sait les générer il n'y a aucun intêret à les stocker sur le disque (c'est tellement rapide à générer que ça va de toutes façon nettement plus rapidement que s'il fallait les lire sur le disque).

A part ça je te renvoie sur le thread et au programme que j'ai écrit en dernier pour que tu puisses voir comment écrire un algo récursif et qui s'adapterai facilement a ton problème de mot de passe puisque le but est de faire un calcul basé sur toutes les combinaisons possibles d'un vecteur à X position (ce vecteur pourrait contenir les lettres de tes mots de passe et mon programme les listerai tous, par contre il faudrait ajouter une boucle pour faire de 1 à X comme longueur puisque moi je faisais exactement X)
autre thread

PS: Dernier conseil, ta machine à beau avoir 8 cpu, si tu ne parallélise pas l'algorithme tu n'en utiliseras qu'un.

Si 1 cpu gènère 10'000'000'000 de mot de passes par seconde (et que tu as un algo parallélisé pour en utiliser 8), il te faudra 552462493225267926475291 ans pour les générer tous.

Bon je te l'ai fait, c'est du ruby (ça ne génère que les mots de passe avec les chiffres de 0 à 9) et ça n'écrit pas sur le disque:

Code: Tout sélectionner
def pass_l(ks, l)
    if l == 0
        puts "#{ks}"
    else
        for i in (0..9) do
            pass_l(ks + [i], l -1)
        end
    end
end

def pass(l)
    for i in (0..l) do
        pass_l([], i)
    end
end

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 51 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite