| problème mathématique à optimiser | |
|
|
Auteur | Message |
---|
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: problème mathématique à optimiser Dim 27 Avr 2008, 16:48 | |
| Bonjour,
Tous les nombres sont des entiers p = premier (impair) q = premier (impair) t = (p-1)(q-1) (non premier)(pair) e = premier PGCD(e;t)=1 (en clair, e et t sont premier entre eux) e>t d = pair (d*e-1) multiple de t
Trouver la valeur de d, en fonction de e, p et q.
Merci d'avance, Prog.Val
PS: les plus perspicaces auront compris que je travaille sur un système de cryptage RSA...
Dernière édition par ProgVal le Mar 29 Avr 2008, 17:45, édité 1 fois (Raison : mise à jour des données) |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 17:56 | |
| Tu fais RSA sans avoir fait d'arithmetique? Sans avoir vu les congruences, machin truc et bidule (j'retrouve pas les noms des theoremes ^^)? Bonne chance. |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 18:00 | |
| |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 20:33 | |
| Tu remplaces entier par 0 dans ton equation, tu trouves d = 1/e, avec d entier, d'ou d=1 ou -1 et c'est fini. (pas sur que ca t'avances a quelque chose, mais j'ai eu l'impression d'etre utile pendant quelques secondes). |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 20:50 | |
| - ProgVal a écrit:
Trouver la valeur de d, en fonction de e, p et q.
|
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 20:58 | |
| Hum... Dans la cas hypothetique ou entier = 0,
d = (-1)^rand + 0*e + 0*p + 0*q d = (-1)^rand + 0*(e+p+q) |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Dim 27 Avr 2008, 21:03 | |
| euh pourquoi tu fais intervenir des nombres aléatoires ? |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Lun 28 Avr 2008, 20:25 | |
| Ca me fait plaisir Non c'est surtout que la solution de mon cas particulier est -1 et 1, donc au choix dans ma reponse. |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Lun 28 Avr 2008, 20:31 | |
| ok, mais rand sort des nombres entre 0 (inclus ?) et 1 (exclu !) non ? |
|
| |
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: Re: problème mathématique à optimiser Mar 29 Avr 2008, 17:42 | |
| Bon, bah pendant que vous discutiez, j'ai réussit à trouver que d est pair... Car: (d*e-1) multiple de (p-1)(q-1) (d*premier-1) multiple de (premier-1)(premier-1) bon, ok, j'ai oublié de dire que e est premier. (d*impair-1) multiple de (impair-1)(impair-1) (d*impair-1) multiple de (pair)(pair) (d*impair-1) multiple de (pair) (d*impair) multiple de impair et donc d est pair. EDIT: Je viens de trouver ça: - Citation :
- l'exposant inverse de E (modulo t)(calcul a l'aide de l'algorithme d'Euclide etendu).
Quelqu'un peut m'expliquer? |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Mar 29 Avr 2008, 18:24 | |
| bah justement c'est du programme de terminale ça ... si je ne me trompe pas, l'algorithme d'Euclide étendu sert à trouver 2 entiers relatifs u et v tels que u*a+v*b=1, une solution particulière pour ensuite résoudre l'équation et trouver tous les couples (u;v) qui vérifient l'équation donnée (équation dionphantienne (ou un truc du genre)) Après ça fait appel aux théorèmes de Bezout et de Gauss, mais je ne suis pas sûr que ça ait un rapport avec le problème actuel A mon avis, le mieux que tu aies à faire, c'est soit attendre quelques années avant de pouvoir résoudre le problème, soit chercher directement la solution et essayer de comprendre éventuellement... (sinon, je ne savais pas qu'on optimisait un problème mathématique ... ) |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Mer 30 Avr 2008, 19:40 | |
| - tama a écrit:
- ok, mais rand sort des nombres entre 0 (inclus ?) et 1 (exclu !) non ?
Ouais , mais la c'est pour 1 alors quoi qu'il arrive ca donnera toujours -1 ou 1 |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Mer 30 Avr 2008, 19:41 | |
| ok mais -1^(0.621564897) donnera ni -1 ni 1 |
|
| |
Ver2guerre chasseur en chef
Nombre de messages : 3145 Age : 113 Localisation : Partout en même temps (V2g quantique) Loisirs : #pkill boulet Humeur : Happy :) items : Personalized field : 12 jetons Réputation : 8 Points : 7495 Date d'inscription : 15/09/2007
Profil TI: (TI-89Tita)^2+TI83Plus TO: 50 [2380 - 2%] {54} Spécialité: Autres
| Sujet: Re: problème mathématique à optimiser Mer 30 Avr 2008, 20:53 | |
| ça donnera -sin(121564897pi/(10^9))+cos(121564897pi/(10^9))i
Na ! |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Mer 30 Avr 2008, 21:26 | |
| - tama a écrit:
- ok mais -1^(0.621564897) donnera ni -1 ni 1
Si! Essaie sur ta calculette -1^(0.6215) ca te donnera -1 ou 1. Reflechis: - une puissance blablabla (nombre entier) te donne un, tu es d'accord. Farpait. -une puissance -blablabla (nbr relatif) te donne 1/1^(blablabla) , ce qui equivaut a la ligne precedente. - une puissance 1/2 correspond a une racine carre, donc -1/2 correspond a 1/racine carre de 1, ce qui fait toujours 1. - de meme puissance 1/3 correspond a racine cubique etc. donc au final t'aura toujours une racine quelconque de 1 ou de -1, ce qui te donnera toujours l'un ou l'autre (sauf dans le cas de racine carree ou cubique [ou meme quatrieme], ou cela generera une erreur. Les autres cas sont acceptes. 3 cas ou cela ne fonctionne pas avec rand sur 10^9 au moins, c'est pas enorme ). -le seul cas ou je ne saurais pas exactement te dire ce que cela represente, c'est une puissance fractionnelle plus grande que 1. Il n'y en a pas avec rand. |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Mer 30 Avr 2008, 21:50 | |
| |
|
| |
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 14:00 | |
| Si nous revenions à nos moutons? J'ai trouvé ça: // Ce programme ne fonctionne qu'avec des entiers naturels // demande les données à l'utilisateur et convertit les chaînes de caractères en entiers var a = parseInt(prompt("Entrer un entier naturel a",0)) var b = parseInt(prompt("Entrer un entier naturel b",0)) // On sauvegarde les valeurs de a et b. a0 = a; b0 = b; // Initialisations. On laisse invariant p*a0 + q*b0 = a et r*a0 + s*b0 = b. p = 1; q = 0; r = 0; s = 1; // La boucle principale: while (b != 0) { c = a % b; //Modulo quotient = Math.floor(a/b); //Javascript n'a pas d'opération de division entière. a = b; b = c; nouveau_r = p - quotient * r; nouveau_s = q - quotient * s; p = r; q = s; r = nouveau_r; s = nouveau_s; } // Affiche le résultat. alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a) |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 14:21 | |
| |
|
| |
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 14:52 | |
| Bah je sais pas trop quoi en faire... |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 15:14 | |
| ça a l'air d'être du javascript... il te reste à adapter |
|
| |
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 15:26 | |
| T'es fort... - ProgVal a écrit:
- quotient = Math.floor(a/b); //Javascript n'a pas d'opération de division entière.
Je l'ai fait. Mais quelles sont les valeurs initiales de a et b? |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 17:58 | |
| bah on t'les demande au début du programme |
|
| |
Syfo Pokémophile
Nombre de messages : 1978 Age : 33 Localisation : IYA items :
Personalized field : 26 jetons Réputation : 8 Points : 6728 Date d'inscription : 09/08/2007
Profil TI: 80, 82, 83, 83+, 84+ TO: 2 945 [GAIN * 1.1] Spécialité: Basic z80
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 20:31 | |
| Hum...
Tu es sur que ton prog sert a resoudre ton probleme exposé initialement?
Parce que la j'ai surtout l'impression qu'il sert a trouver le plus petit pgcd entre quotient et reste (je sais plus le nom du theoreme, du programme de spe math) |
|
| |
tama Admin
Nombre de messages : 12376 Age : 32 Localisation : DTC ? :triso: Humeur : =) items : o Personalized field : huh ? oO Réputation : 3 Points : 9406 Date d'inscription : 08/08/2007
Profil TI: 84+, 89 tita, 89 tita TO: infini :p Spécialité: C 68k
| Sujet: Re: problème mathématique à optimiser Jeu 01 Mai 2008, 20:54 | |
| ça sert à trouver le PGCD oui, avec l'algorithme d'Euclide (dernier reste non nul) |
|
| |
ProgVal modérateur
Nombre de messages : 4107 Age : 173 Localisation : In da cloud items : o Personalized field : Réputation : -4 Points : 6687 Date d'inscription : 09/08/2007
Profil TI: V200 - NSpire TO: 120 [2352 - 2%] Spécialité: Programmation web
| Sujet: Re: problème mathématique à optimiser Sam 03 Mai 2008, 17:01 | |
| Euh? T'as pas du tout suivre... - ProgVal a écrit:
- Je viens de trouver ça:
- Citation :
- l'exposant inverse de E (modulo t)(calcul a l'aide de l'algorithme d'Euclide étendu).
- ProgVal a écrit:
// Ce programme ne fonctionne qu'avec des entiers naturels // demande les données à l'utilisateur et convertit les chaînes de caractères en entiers var a = parseInt(prompt("Entrer un entier naturel a",0)) var b = parseInt(prompt("Entrer un entier naturel b",0)) // On sauvegarde les valeurs de a et b. a0 = a; b0 = b; // Initialisations. On laisse invariant p*a0 + q*b0 = a et r*a0 + s*b0 = b. p = 1; q = 0; r = 0; s = 1; // La boucle principale: while (b != 0) { c = a % b; //Modulo quotient = Math.floor(a/b); //Javascript n'a pas d'opération de division entière. a = b; b = c; nouveau_r = p - quotient * r; nouveau_s = q - quotient * s; p = r; q = s; r = nouveau_r; s = nouveau_s; } // Affiche le résultat. alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a) |
|
| |
Contenu sponsorisé
| Sujet: Re: problème mathématique à optimiser | |
| |
|
| |
| problème mathématique à optimiser | |
|