Discussion :

[selmagsi]

Salut les développeurs help !!!
Je réalise une petite application java qui sert à générer la clé de cryptage dans le cas du protocole ECC.
je commence par la multiplication scalaire tout d'abord
L’algorithme que j’implémente est ci-joint.

Et voila ce que j’ai implémenté

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Point  multiScalaire(Point p, int a, int k){
//p point a additionner
//k combien de fois l'aditionner      
//Q point resultant  
 Point Q; 
         int j = 0,n;
        String S;
        ConvertDecimal c=new ConvertDecimal();
      S=c.convert(k, 2);
 
      double inf=Double.POSITIVE_INFINITY;
       Q=new Point(inf, inf);
 
       for(int i=0;i<S.length();i++){
          if(S.charAt(i)=='1'){
//addition de deux point définie a part testée et fiable          
    Q= addition(p, Q);
 
          } 
//addition de deux point égaux définie a part testée et fiable           
p=doublement(p, a);       return Q;}
       }

Le problème c’est que j’ai des valeur du x et y de mon point Q indéfini parce que dans mon implémentation l’infini n’est pas considéré comme l’élément neutre par rapport à l’addition.
j'ai trouvé pour solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Point  multiScalaire(Point p, int a, int k){
//p point a additionner
//k combien de fois l'aditionner      
//Q point resultant  
 Point Q; 
         int j = 0,n;
        String S;
        ConvertDecimal c=new ConvertDecimal();
      S=c.convert(k, 2);
 
      double inf=Double.POSITIVE_INFINITY;
       Q=new Point(inf, inf);
 
       for(int i=0;i<S.length();i++){
   if(S.charAt(i)=='1' && Q.getX=Infinity && Q.getY=Infinity){
Q=p; //premiére addition de l'algorithme donne comme résultat p puisque Q=p+Q; ET Q et infini et l'infini et l'element neutre par rapport a l'addition
 
          }        
   if(S.charAt(i)=='1' && Q.getX!=Infinity && Q.getY!=Infinity){
//addition de deux point définie a part testée et fiable          
    Q= addition(p, Q);
 
          } 
//addition de deux point égaux définie a part testée et fiable           
p=doublement(p, a);       return Q;}
       }

mais toujours le même problème des valeurs indéfinies à cause du fameux infini .
quelqu'un aurait une idée sur la solution de mon probléme??
merci d'avance de l'aide

[joel.drigo]

Salut,

Depuis quand l'infini est-il l'élément neutre de l'addition ? Ce n'est pas 0, l'élément neutre de l'addition ? (Remarque : au début de l'algorithme, on voit P ← 0)

[selmagsi]

O est le symbole de l'infini dans les courbe elliptique et oué c'est la vie dans les courbe elliptique l'élément neutre est bel et bien l'infini ,j'ai beau essayé la démontrer mais sans succès

[joel.drigo]

Il n'est pas question de courbes elliptiques mais de double, type Java. Ta méthode addition doit implémenter l'addition de 2 points au sens courbe elliptique (sens mathématique), ce qui ne peut être directement appliqué avec des doubles. Déjà, il y a une infinité de réels, mais pas une infinité de double, et Double.POSITIVE_INFINITY-Double.POSITIVE_INFINITY donne Double.NaN. Donc les formules d'addition de points ne pourront jamais fonctionner directement (somme de 2 points infinis par exemple) avec des doubles.
Tes tests sur "Infinity" devraient être dans la méthode addition. Quel est le code de ton addition (le vrai code Java, pas cette espèce de pseudo java que tu as mis — d'ailleurs cette méthode devrait être une méthode de la classe Point) ? Par ailleurs, tu n'es pas obligé d'utiliser Double.POSITIVE_INFINITY pour représenter une coordonnée de point à l'infini, tu peux aussi bien le faire avec un attribut qui signifie que ton point est à l'infini, en codant toutes les méthodes utiles pour que leur comportements soient conforme à cet état (comme P+0 = P).

[selmagsi]

voila comment effectuer l'addition de deux point:


voila le code java de l'addition

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static Point addition(Point p1, Point p2){
 
        Point p3;
 
        double x1,x2,x3,y1,y2,y3;
        double a1,a2;
        double fra1;
 
        x1=p1.getX();
        x2=p2.getX();
 
        y1=p1.getY();
        y2=p2.getY();
 
 
 
        a1=y2-y1;
        a2=x2-x1;
 
        fra1=a1/a2;
 
 
        x3=(Math.pow(fra1, 2)-x1-x2)%11;
 
        y3=(Math.pow(fra1, 2)*(x1-x3)-y1)%11;
 
        p3=new Point(x3,y3);
 
 
        return p3;
    }

voila doublement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
static Point doublement(Point p, int a){
        double a1,a2;
        double fra1,fra2,fra3;
        double x,y,x1,y1;
        x=p.getX();
        y=p.getY();
        Point Q = null;
 
 
        a1=3* Math.pow(x, 2)+a;
        fra1=a1/(2*y);
        fra2=Math.pow(fra1, 2);
 
        fra3=fra2-(2*x);
 
        x1=fra3%11;
        y1=(fra1*(x-x1)-y)%11;
 
 
      Q=new Point(x1,y1);
 
        return Q;
    }

certainement j'ai la classe point.

[joel.drigo]

C'est bien ce que je te dis : tu ne peux pas appliquer des formules de calcul sur des doubles telles quelles, sans traiter le cas du O à part.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Point {
 
    private final double x;
    private final double y;
    private final boolean infinity;
 
    public Point(double x, double y) {
         infinity = ( x==Double.POSITIVE_INFINITY || y==Double.POSITIVE_INFINITY );
         this.x=x;
         this.y=y;
    }
 
    public double getX() {
        return x;
    }
 
    public double getY() {
        return y;
    }
 
    public boolean isInfinity() {
        return infinity;
    }
 
    public Point add(Point p) {
        if ( this.isInfinity() ) {
             return p;
        }
        else if ( p.isInfinity() ) {
             return this;
        }
        else { 
              // ... ici l'application des formules qui peuvent fonctionner avec des doubles
        }
    }
 
}

Attention également à l'égalité entre doubles : tu ne peux pas toujours écrire if ( d1==d2 ), il vaut mieux comparer la valeur absolue de la différence avec un EPSILON (un double proche de 0).

Je vois un autre problème dans ton programme par rapport à l'algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p=doublement(p, a);       return Q;}

Le return Q est en dehors du for dans l’algorithme.

[selmagsi]

bonne solution pour le point à l'infinie merci infiniment.
normalement pas de probléme avec le RETURN et je crois etre obligée de passer en résolu la parce que je vois que mon problème est avec l’arithmétique modulaire,par exemple j'ai pas compris pourquoi (5/20)mod 23= 6 et pourquoi -34 mod 23= 12 et non pas 11 !!!!

[joel.drigo]

pourquoi (5/20)mod 23= 6 et pourquoi -34 mod 23= 12 et non pas 11 !!!!

De quoi tu parles ? De -34 % 23 ? çà fait -11 (ni 12 ni 11 donc). Quand à (5/20)% 23, ça fait 0. Si mod a une signification particulière dans ton contexte autre que "reste de la division entière par", il faut le dire)

[Flodelarab]

Bonjour

Le reste de la division est positive! Donc si on divise par b, le reste est entre 0 (inclus) et b (exclu).

-34+23=-11
-11+23=12

-34 = 12 [23]

[selmagsi]

j'ai jamais étudié les courbes elliptiques j'ai juste pris les notions de base juste pour le ECC ,dans chaque opération sur les courbe on fait mod p (tel que p est l'ordre du corps sur lequel est défini la courbe) au début mod p j'ai compris que c'était le reste de la division entiére mais la quand j'ai tiré des exemple j'ai trouvé que c'était pas ca,voila je vous ci joint un petit exemple(cas du doublement ,en utilisant les formule que j'ai laissé dans un autre poste avec mod p dans l'exemple p=23)



merci

[selmagsi]

@Flodelarab merci mais je n'ai rien compris de ce que vous avez dit

[Flodelarab]

58 = 23 * 2 + 12 donc 58 = 12 modulo 23
35 = 23 * 1 + 12 donc 35 = 12 modulo 23
12 = 23 * 0 + 12 donc 12 = 12 modulo 23
-11 = 23 * (-1) + 12 donc -11 = 12 modulo 23
-34 = 23 * (-2) + 12 donc -34 = 12 modulo 23

La division de -34 par 23 donne -2 et il reste 12.


Pareil pour l'inverse de 4. Quel est le nombre qui multiplié par 4 donne 1 ? Réponse: 6. Pourquoi ?
Car :
6*4=24=23+1=23*1+1 Donc 6*4=1 modulo 23. Et l'inverse de 4 est égal à 6 modulo 23.


Il est très important de comprendre qu'on tourne en rond. Si on comptait modulo 23, on dirait:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Là où classiquement 5 fois 7 fait 35, ici le résultat fait 12, à cause du modulo

[selmagsi]

je commence à voir clair maintenant grace à vous,merci
maintenant est ce que qu'il y a des méthode de modulo pour le negatif et l'inverse en java ou bien je dois les définir moi mem??
merci bcp

[joel.drigo]

maintenant est ce que qu'il y a des méthode de modulo pour le negatif et l'inverse en java ou bien je dois les définir moi mem??

En Java 8, il Math.floorMod(), pour des int ou des longs. Dont pour Java<=7 l'équivalent serait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
public static int modulo(int a, int b) {
    final int reste = a % b;
    if ( (b < 0 && reste > 0) || (b > 0 && reste < 0)) {
	    return reste + b;
    }
    else {
	  return reste;
    }
}

Pour le modulo sur un rationnel, je dirais ça (mais je suis moins sûr de moi) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static float modulo(int a1, int a2, int b) {
	  if( a2>a1 && a2%a1==0 ) {
 
		  float q = ((float)a2)/a1;
 
		  q = (b+1)/q;
 
		  final float reste = q % b;
		  if ( (b < 0 && reste > 0) || (b > 0 && reste < 0)) {
		    return reste + b;
		  }
		  else {
			  return reste;
		  }
 
	  }
	  throw new IllegalArgumentException();
	}

[selmagsi]

merci Joel merci bcp ,cette méthode Math.floorMod(long,long) marche super bien avec les nombre négatif mais avec l'inverse ca me donne des zero a chaque fois!!!

[joel.drigo]

merci Joel merci bcp ,cette méthode Math.floorMod(long,long) marche super bien avec les nombre négatif mais avec l'inverse ca me donne des zero a chaque fois!!!

Avec l'inverse ? Tu veux dire 5/20 (4^-1) ? C'est normal : on ne peut pas utiliser cette méthode pour ce cas. Parce que, en Java, un int divisé par un int, donne un int. 5/20 vaut donc 0, et donc après le modulo vaut 0. Et si tu calcules 5/20 en float, donc 0.25f, tu ne peux plus utiliser Math.floor(), parce qu'elle n'est prévu que pour int et long.

[selmagsi]

merci Joel,donc il faut que je teste la méthode que vous m'avez donnée si non je l’implémente merci infiniment

[selmagsi]

Joel et Flodelarab vous m'avez sauvée,je vous remercie infiniment!!!!

[selmagsi]

Comment calculer a/b mod p en java sachant que b%a!=0 exemple 3/5 mod p ?

[Flodelarab]

Je ne sais pas quoi te dire d'autre que de trouver une bibliothèque java qui donne le résultat de l'algorithme d'Euclide étendu, ou de coder cet algorithme toi-même.

Le point d'entrée est dans Wikipedia:
https://fr.wikipedia.org/wiki/Inverse_modulaire