Don_Angelo 27 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 Bonjour à tous, Une petite question qui va paraître bizzare, comment est-il possible de prévoir avec une relative précision le temps moyen d'execution d'un programme compilé en tenant compte du fait qu'il tourne sous un OS genre Windows ou Linux? Je m'explique, il faut que j'écrive un programme qui soit capable de calculer toutes les solutions d'une équation dont j'estime qu'elle a environ 4,5 millions de milliard de solutions. Et je cherche à savoir combien de temps metterait un PC moyen pour faire tout ces calculs. D'avance Merci. [edit] Pardon, je corrige, l'équation a beaucoup de solutions (peu importe le nombre) mais j'estime qu'il faudrait que le programme effectue environ 4.5 millions de milliard de calculs pour arriver à la solution qui m'interesse. Lien à poster
LapinGarou 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 C'est un peu difficile je pense, ça va dépendre de beaucoup de choses : l'algorithme utilisé, le temps demandé au processeur pour chaque instruction, le compilateur, l'optimisation du code, etc... Par exemple : en assembleur, pour multiplier par 30, il est plus rapide(en temps bien sûr, pas en ligne de codes) de faire un shift <<5 et de soustraire 2 ... que de faire directement une multiplication par 30. Lien à poster
Don_Angelo 27 Posté(e) le 6 mai 2006 Auteur Partager Posté(e) le 6 mai 2006 Merci de ta réponse. En fait le problème c'est que je sais pas exactement à quoi va ressembler l'algorithme, pour schématiser ce devrait être quelque chose de ce type, il y aurait deux tableaux contenant des entiers naturels. Il y aurait 76 entiers premiers dans le premier et 600 entiers dans le second. En fait le programme devra essayer d'ecrire les 600 entiers du tableaux 2 avec chacun des 76 entiers premiers multiplié par un entier ajouté à un entier appelé c. J'estime qu'un tel programme devra écrire au maximimum 4.5 millions de milliards d'égalitées de ce type et enregistrer tous les c différents dans un troisième tableau. je sais que ces calculs ont à prioris aucun intêret mais c'est pour vérifier une conjecture. Lien à poster
thev 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 Ben comme c'est dit, il faut voir le temps mis par l'algorithme (à déterminer) utilisé pour écrire une équation type sur un CPU donné, puis multiplier. Je pense qu'il n'est pas utile de prendre en compte l'OS. D'autant que ton programme aura sûrement "l'exclusivité" sur la machine (genre seul à vraiment travailler, avec éventuellement un haut niveau d'exécution). @+ Lien à poster
rjds 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 ceci ne verifiera pas ta conjecture. Ca ne fera que repousser l'apparition eventuelle du contre exemple qui fera que la conjecture est fausse. Lien à poster
akira 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 Sinon tu peux estimer le pire temps d'execution que ton programme peut donner. Je crois que c'est utilisé pour l'embarqué. Le nom anglais de cette méthode est WCET (Worst Case Execution Time) qui te donnes un majorant pour ton temps d'execution. Voilou Lien à poster
Don_Angelo 27 Posté(e) le 6 mai 2006 Auteur Partager Posté(e) le 6 mai 2006 Sinon tu peux estimer le pire temps d'execution que ton programme peut donner. Je crois que c'est utilisé pour l'embarqué. Le nom anglais de cette méthode est WCET (Worst Case Execution Time) qui te donnes un majorant pour ton temps d'execution. Voilou Akira en fait c'est que j'aimerais, merci de m'avoir filé le nom. Il faudrait que j'explique un peu l'embrouille. En maths je ne suis pas une grosse tête c'est pour ça que j'ai fait appel à des amis de terminale pour me filer un coup de pouce. L'idée c'est de créer notre propre système de cryptage pour l'utiliser sur nos données personnelles. On cherche pas à recréer RSA bien sur mais à faire un truc avec un niveau de sécuritée convenable. On a l'expression du cryptage et celle du décryptage. Ce qu'on aimerait savoir en fait c'est combien de temps faudrait-il à un PC pour le casser. On y réfléchit depuis plusieurs semaines et on est presque sur que c'est suffisement fiable pour ce qu'on souhaite en faire. L'idée c'est de faire un test, d'ou l'idée de cet algorithme. Lien à poster
akira 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 arf ok je vois. Je crois que RSA se base sur le fait que l'on ne peut pas trouver les plus petit diviseur commun pour deux grands nombres pour un problème de complétude (à vérifer ). A mon avis, tu va être obligé de calculer le nombre de combinaisons possibles. Enjoy . Lien à poster
lhurgoyf 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 En même temps, en ce qui concerne le cryptage un des meilleurs algorithmes reste celui de Vigenère. En effet, il n'y a aucune méthode mathématique pour le casser sans avoir un indice sur le contenu du message de base, et avec une clé assez longue (genre une 20aine de caractères, c'est déjà pas mal), le PC d'un éventuel pirate rendra l'âme avant d'avoir fini son attaque brute force. Le seul problème de cet algo, c'est qu'il nécessite de transmettre la clé en clair, et c'est à ce moment qu'elle peut être interceptée par un pirate, c'est pour ça que ce cryptage ne peut pas être utilisé sur Internet. Mais comme vous êtes entre potes, il n'y a aucun risque à ce niveau. Lien à poster
akira 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 Hum, il me semble que pour les certificats sur Internet la crypto est utilisée. Lien à poster
lhurgoyf 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 La crypto, oui, mais l'algo de Vigenère, ça m'étonnerait, l'échange de clés n'est pas assez (voire pas du tout) sûr. Si quelqu'un peut confirmer cela dit, parce que bon, je peux me tromper, et j'avoue ne pas avoir fait la moindre recherche. Lien à poster
akira 0 Posté(e) le 6 mai 2006 Partager Posté(e) le 6 mai 2006 Ben ca dépends s'il sagit d'un système clé privée / clé plublique. Lien à poster
lhurgoyf 0 Posté(e) le 7 mai 2006 Partager Posté(e) le 7 mai 2006 Je parle de ce code là : http://www.apprendre-en-ligne.net/crypto/vigenere/index.html ou http://fr.wikipedia.org/wiki/Carré_de_Vigenère Bon, sur la page, il y a effectivement une méthode de décryptage, mais elle est basée sur la statistique, et donc, relativement peu évidente à mettre en place. De plus, elle est très facile à coder, et on peut même en gardant la même sécurité, remplacer le système de décalage par un XOR du texte à crypter avec la clé, ce qui fait que l'on utilise exactement le même algorithme pour crypter et pour décrypter le message. Enfin, l'analyse statistique devient impossible si l'on utilise une clé de même longueur (ou plus longue) que le message. Lien à poster
Don_Angelo 27 Posté(e) le 7 mai 2006 Auteur Partager Posté(e) le 7 mai 2006 arf ok je vois. Je crois que RSA se base sur le fait que l'on ne peut pas trouver les plus petit diviseur commun pour deux grands nombres pour un problème de complétude (à vérifier ). A mon avis, tu va être obligé de calculer le nombre de combinaisons possibles. Enjoy . RSA si je me rappelle bien utilise de très grands nombres premiers et de l'algèbre modulaire. Toute la difficulté réside dans le fait que même pour un ordinateur, il est difficile de dire si un très grand nombre est premier ou non. Vignère est très bien, on pensait s'en servir comme surcouche de sécurité. Comme on utilise des clés privés on pensait utiliser un système d'échange entre un serveur web et le programme. Le serveur attribuerait et conserverait toutes les clés. En fait l'idée est la suivante: On génére pour chaque chiffre et lettre un nombre premier que l'on multiplie par sa position dans le mot, on ajoute un entier quelquonque (la clée), on mélange tout les nombres obtenus et on s'arrange pour que dans le résultat final on obtienne une série de chiffres et de lettres en vrac, pour pouvoir y appliquer vignère. Voici un exemple tout bête d'une phrase codée avec un tel système (ici on a pas appliqué Vignère à la fin et la clée est très petite): 1dL3K dy1œ1 dL3Kd yæ1dL 3Kdy@ 1dL3K dyù1d L3Kdy 0è1dL 3Kdy0 ë1dL3 Kdy-1 dL3Kd y!1dL 3Kdyè 1dL3K dyæ1d L3Kdy 0æ Est-ce que ça vous paraît suffisement retord? En tout cas merci de vos réponses Lien à poster
thev 0 Posté(e) le 8 mai 2006 Partager Posté(e) le 8 mai 2006 Pas vraiment, rien qu'en l'apercevant, j'ai pû déchiffrer le message. @+ Lien à poster
Don_Angelo 27 Posté(e) le 9 mai 2006 Auteur Partager Posté(e) le 9 mai 2006 Pas vraiment, rien qu'en l'apercevant, j'ai pû déchiffrer le message. @+ Heu comment tu as fait et c'est quoi le message stp? Lien à poster
PoP 0 Posté(e) le 10 mai 2006 Partager Posté(e) le 10 mai 2006 On cherche pas à recréer RSA bien sur mais à faire un truc avec un niveau de sécuritée convenable Qu'est-ce que tu appeles un niveau de sécurité convenable? Si c'est juste t'assurer que ta mère va pas pouvoir lire tes mails de fion écrit à ta cousine, t'as qu'à les écrire en l33t. :devil Lien à poster
Don_Angelo 27 Posté(e) le 11 mai 2006 Auteur Partager Posté(e) le 11 mai 2006 On cherche pas à recréer RSA bien sur mais à faire un truc avec un niveau de sécuritée convenable-ce que tu appeles un niveau de sécurité convenable? Si c'est juste t'assurer que ta mère va pas pouvoir lire tes mails de fion écrit à ta cousine, t'as qu'à les écrire en l33t.:devil [/quote1147349134] J'ai pas très bien compris l'appelation mail de fion, mais j'ai pas de cousine. Pop, c'est pas uniquement pour notre usage (sinon on utiliserait un algorithme existant bien sûr) mais surtout pour le plaisir de se creuser le chou sur un problème interessant, pour dépasser le cadre un peu ennuyeux des maths au lycée, surtout avec notre prof de maths qui est un peu une tâche et avec qui on ne fait rien. Lien à poster
frisco2000 0 Posté(e) le 13 août 2006 Partager Posté(e) le 13 août 2006 attention : pour bien programmer un algo de cryptage, il faut que le temps d'execution ne depende pas de la cle ni des donneés. Lien à poster
Messages recommandés