Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
3170 connectés 

  FORUM HardWare.fr
  Programmation

  [blabla@olympe] Le topic du modo, dieu de la fibre et du monde

 
 


Sujet auquel vous répondez
Sujet : [blabla@olympe] Le topic du modo, dieu de la fibre et du monde
leo++

nraynaud a écrit :


ça se fait en O(log(puissance))


 

uriel a écrit :


ben c'est ce que je dis, tu mets pas tout en une fois [:paysan]


 
Ha mais j'y connais rien à la crypto moi, pourquoi j'arrive encore à l'ouvrir ?  :o


Votre réponse
Nom d'utilisateur    Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !
Le ton de votre message                        
                       
Votre réponse
[b][i][u][strike][spoiler][fixed][cpp][url][email][img][*]   
 
   [quote]
 
Options

 
Vous avez perdu votre mot de passe ?


Vue Rapide de la discussion
tontonbud

sligor a écrit :


C'est pour un TPE ?  :??:

 

:lol:

 

Si on commence à voir RSA en detail en TPE, on peut tous aller se coucher !
nraynaud

uriel a écrit :


ça depend comment modpow est fait en dessous


Code :
  1. public BigInteger modPow(BigInteger exponent, BigInteger m) {
  2. if (m.signum <= 0)
  3.     throw new ArithmeticException("BigInteger: modulus not positive" );
  5. // Trivial cases
  6. if (exponent.signum == 0)
  7.             return (m.equals(ONE) ? ZERO : ONE);
  9.         if (this.equals(ONE))
  10.             return (m.equals(ONE) ? ZERO : ONE);
  12.         if (this.equals(ZERO) && exponent.signum >= 0)
  13.             return ZERO;
  15.         if (this.equals(negConst[1]) && (!exponent.testBit(0)))
  16.             return (m.equals(ONE) ? ZERO : ONE);
  17.            
  18. boolean invertResult;
  19. if ((invertResult = (exponent.signum < 0)))
  20.     exponent = exponent.negate();
  22. BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
  23.      ? this.mod(m) : this);
  24. BigInteger result;
  25. if (m.testBit(0)) { // odd modulus
  26.     result = base.oddModPow(exponent, m);
  27. } else {
  28.     /*
  29.      * Even modulus.  Tear it into an "odd part" (m1) and power of two
  30.              * (m2), exponentiate mod m1, manually exponentiate mod m2, and
  31.              * use Chinese Remainder Theorem to combine results.
  32.      */
  34.     // Tear m apart into odd part (m1) and power of 2 (m2)
  35.     int p = m.getLowestSetBit();   // Max pow of 2 that divides m
  37.     BigInteger m1 = m.shiftRight(p);  // m/2**p
  38.     BigInteger m2 = ONE.shiftLeft(p); // 2**p
  40.             // Calculate new base from m1
  41.             BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
  42.                                 ? this.mod(m1) : this);
  44.             // Caculate (base ** exponent) mod m1.
  45.             BigInteger a1 = (m1.equals(ONE) ? ZERO :
  46.                              base2.oddModPow(exponent, m1));
  48.     // Calculate (this ** exponent) mod m2
  49.     BigInteger a2 = base.modPow2(exponent, p);
  51.     // Combine results using Chinese Remainder Theorem
  52.     BigInteger y1 = m2.modInverse(m1);
  53.     BigInteger y2 = m1.modInverse(m2);
  55.     result = a1.multiply(m2).multiply(y1).add
  56.       (a2.multiply(m1).multiply(y2)).mod(m);
  57. }
  59. return (invertResult ? result.modInverse(m) : result);
  60.     }
uriel

flo850 a écrit :


sauf qu'il y aun maniere bcp plus inteligente de le faire , avec expomod , sans consommer trop de memoire , ni trop de temps
 


ça depend comment modpow est fait en dessous
flo850

tontonbud a écrit :


 
Non mais moi je voulais faire  
997593903573^889364620183 mod 1037594094337
 
et en 2 lignes en java ca se fait avec BigInteger
 
BigInteger msg = new BigInteger("997593903573" );
msg.modPow(889364620183,1037594094337);
 
c'est tout !


sauf qu'il y aun maniere bcp plus inteligente de le faire , avec expomod , sans consommer trop de memoire , ni trop de temps
 
sligor

tontonbud a écrit :


 
Non mais moi je voulais faire  
997593903573^889364620183 mod 1037594094337
 
et en 2 lignes en java ca se fait avec BigInteger
 
BigInteger msg = new BigInteger("997593903573" );
msg.modPow(889364620183,1037594094337);
 
c'est tout !


C'est pour un TPE ?  :??:

nraynaud

tontonbud a écrit :


 
Non mais moi je voulais faire  
997593903573^889364620183 mod 1037594094337
 
et en 2 lignes en java ca se fait avec BigInteger
 
BigInteger msg = new BigInteger("997593903573" );
msg.modPow(889364620183,1037594094337);
 
c'est tout !


ok, super.
tontonbud

nraynaud a écrit :


va voir le lien wikipedia que j'ai fait passer (en fait c'est pas exactement cet algo en java, mais presque)

 

Non mais moi je voulais faire
997593903573^889364620183 mod 1037594094337

 

et en 2 lignes en java ca se fait avec BigInteger

 

BigInteger msg = new BigInteger("997593903573" );
msg.modPow(889364620183,1037594094337);

 

c'est tout !
nraynaud

tontonbud a écrit :


 
 
développe je comprend pas là !


va voir le lien wikipedia que j'ai fait passer (en fait c'est pas exactement cet algo en java, mais presque)
tontonbud

nraynaud a écrit :


bah si vous utilisez modpow, alors vous développez pas la puissance.


 
 
développe je comprend pas là !
nraynaud http://www.liberation.fr/actualite [...] 919.FR.php  
'tain mais je rêve quoi ! soit ils soutiennent et ils minimisent la crise actuelle (rien ne dit qu'il va pas remonter dans les sondages) soit il fallait pas beugler avec les veaux après l'élection ...
leo++

nraynaud a écrit :


ça se fait en O(log(puissance))


 

uriel a écrit :


ben c'est ce que je dis, tu mets pas tout en une fois [:paysan]


 
Ha mais j'y connais rien à la crypto moi, pourquoi j'arrive encore à l'ouvrir ?  :o

sligor La méthode est trés clairement expliquée dans le lien wikipedia qui vient de passer
uriel

leo++ a écrit :


 
Bah c'est juste que tu découpe ta puissance en plusieurs multiplications et tu applique le modulo entre chaque operation.
En choisissant correctement les coefficients, tu peux régler ca en 10000 operations à mon avis.


ben c'est ce que je dis, tu mets pas tout en une fois [:paysan]
nraynaud

leo++ a écrit :


 
Bah c'est juste que tu découpe ta puissance en plusieurs multiplications et tu applique le modulo entre chaque operation.
En choisissant correctement les coefficients, tu peux régler ca en 10000 operations à mon avis.


ça se fait en O(log(puissance))

nraynaud

tontonbud a écrit :


 
On a été tout aussi étonné avec mon binome ! On y croyait pas de trop en plus ca marchait pas au debut mais j'avais inversé les paramétres  dans modpow


bah si vous utilisez modpow, alors vous développez pas la puissance.
leo++

uriel a écrit :


je suis impressionné je dois dire. faudrait que j'essaye vite fait en fortran pour voir  [:robert de niro]


 
Bah c'est juste que tu découpe ta puissance en plusieurs multiplications et tu applique le modulo entre chaque operation.
En choisissant correctement les coefficients, tu peux régler ca en 10000 operations à mon avis.
 

vapeur_cochonne a écrit :

leo++ tu peux faire de grandes choses si tu choisis les bon topics [:leo++]
 
t'a un compte sur doctissiomo ? [:cupra]


 
 :jap: Venant d'un grand maitre du troll je suis flatté  [:shadowblade]  
 
J'ai pas de compte chez doctissimo, est-ce que j'ai a gagné à m'en ouvrir un ?  
 
Doctissimo, c'est le discu santé de hfr, c'est ca ?  [:cupra_yvele]

nraynaud

tontonbud a écrit :


Je crois tu comprends pas là !


non, j'ai un peu de mal à comprendre, tu veux faire une puissance modulo, sur des grands nombres, typiques de RSA. Ce calcul ne se fait jamais en faisant l'exponentielle direct, mais toujours par la méthode rapide modulaire, qui ne fait jamais apparaitre explicitement le grand nombre intermédiaire.
tontonbud

uriel a écrit :


je suis impressionné je dois dire. faudrait que j'essaye vite fait en fortran pour voir  [:robert de niro]


 
On a été tout aussi étonné avec mon binome ! On y croyait pas de trop en plus ca marchait pas au debut mais j'avais inversé les paramétres  dans modpow
vapeur_cochonne leo++ tu peux faire de grandes choses si tu choisis les bon topics [:leo++]
 
t'a un compte sur doctissiomo ? [:cupra]
uriel

tontonbud a écrit :


SI !
 
Et le resultat est instantané !


je suis impressionné je dois dire. faudrait que j'essaye vite fait en fortran pour voir  [:robert de niro]

tontonbud

nraynaud a écrit :


en RSA on le fait jamais en direct, toujours en modulaire.


 
Je crois tu comprends pas là !
vapeur_cochonne /o\ j'ai oublié l'euromiyard :/
nraynaud

uriel a écrit :


l'operation theorique ok, mais tu le fais en une seule fois (sur une seule ligne sans rien limiter) dans ton code? :??:


il utilise un algo qui calcule pas la puissance intermédiaire.
nraynaud

tontonbud a écrit :


 
Non pas du tout , c'est typique de RSA
 
msg 997593903573 d 889364620183 n 1037594094337 res 6682658679 ascii : BRAVO


en RSA on le fait jamais en direct, toujours en modulaire.
tontonbud

uriel a écrit :


l'operation theorique ok, mais tu le fais en une seule fois dans ton code? :??:


 
 
SI !
 
Et le resultat est instantané !
uriel

tontonbud a écrit :


Non pas du tout , c'est typique de RSA
msg 997593903573 d 889364620183 n 1037594094337 res 6682658679 ascii : BRAVO


l'operation theorique ok, mais tu le fais en une seule fois (sur une seule ligne sans rien limiter) dans ton code? :??:
leo++

tontonbud a écrit :

En java c'est possible de gerer cette operation 3456756987654^345678987657 mod 4567890987654
 
Car BigInteger me tronque le résultat


 
 
 [:cmshadow]  
 
Un Biginteger peut contenir 4567890987654, il peut donc contenir tout nombre inférieur à 4567890987654.
 
Par contre il est probable que tu doive utiliser une petite manip pour limiter la taille de ton exposant. Je suppose qu'il s'agit de nombres premiers ?!
 
 Edit: [:grilled]

tontonbud

uriel a écrit :


surtout idiot.
 tu fais pas une operation comme ça en une seule fois.

 

Non pas du tout , c'est typique de RSA

 

msg 997593903573 d 889364620183 n 1037594094337 res 6682658679 ascii : BRAVO
tontonbud Oui c'est bon ca marche, je sais pas pourquoi je disais ça marchais pas
 
(c'etait pour decrypté un message RSA) donc avec biginteger et la methode modpow ca a bien fonctionné !
uriel

ratibus a écrit :


Il est joueur le monsieur :D


surtout idiot.
 tu fais pas une operation comme ça en une seule fois.
nraynaud

tontonbud a écrit :

En java c'est possible de gerer cette operation 3456756987654^345678987657 mod 4567890987654

 

Car BigInteger me tronque le résultat


heu, il faut pas effectuer cette opération comme ça, il faut utiliser l'algèbre modulaire, comme en cryptographie.

 

edit : http://fr.wikipedia.org/wiki/Exponentiation_modulaire
ratibus

tontonbud a écrit :

En java c'est possible de gerer cette operation 3456756987654^345678987657 mod 4567890987654
 
Car BigInteger me tronque le résultat


Il est joueur le monsieur :D
sligor

tontonbud a écrit :

En java c'est possible de gerer cette operation 3456756987654^345678987657 mod 4567890987654
 
Car BigInteger me tronque le résultat


il faut juste 13TO de mémoire vive pour stocker le résultat avant le mod
 [:cerveau kneu]
tontonbud En java c'est possible de gerer cette operation 3456756987654^345678987657 mod 4567890987654
 
Car BigInteger me tronque le résultat
ratibus

nraynaud a écrit :

'tain mais si je me plante dans toute cette daube de web, je vais rentrer des données à la con :(


Tu veux mettre des contraintes sur des données saisies par les utilisateurs ?
Si oui faut faire les vérifs coté serveur d'application :spamafote:
uriel http://compbiol.plosjournals.org/p [...] bi.0040023 [:vapeur_cochonne]
nraynaud 'tain mais si je me plante dans toute cette daube de web, je vais rentrer des données à la con :(
ratibus

nraynaud a écrit :

bon, on peut pas mettre de contrainte arbitraire dans Mysql ?


[:hahaguy]

Spoiler :

Non mais tu te crois sous Oracle ? :o
Oublie ce que tu as pu apprendre :D
nraynaud bon, on peut pas mettre de contrainte arbitraire dans Mysql ?
sligor http://www.enregistrersous.com/ima [...] 200036.jpg
Shinuza http://masklinn.skyrock.com/ :o

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)