Résidus biquadratiques

Soyez le premier à donner votre avis sur cette source.

Vue 4 338 fois - Téléchargée 169 fois

Description

Il s'agit d'une fonction permettant de calculer un résidu biquadratique (quartic in english) . L'intérêt de cette fonction se retrouve en cryptographie: il s'agit d'un homomorphisme

Source / Exemple :


// **********************************************
//	  Algorithme de résolution de Quartiques 
//
//	 par malik@hammoutene.com, septembre 2004
//
// **********************************************

// ce code est accompagné d'un PDF expliquant "grossièrement" l'algorithme

#include "gmp.h"
#pragma comment(lib, "gmp.lib")

#define _WIN32_WINNT 0x0501

#include <stdio.h>
#include <windows.h>
#include <wincrypt.h>

struct resChar{	
	
// structure permettant la reconstruction de la réponse

	int real_plus;
	int real_moins;
	int imag_plus;
	int imag_moins;
};

struct cornAlgo{	
	
// structure pour définir les nombres complexes
// (elle porte ce nom simplement parce qu'elle
// apparaît pour la première fois dans Cornacchia

	mpz_t x_sol;
	mpz_t y_sol;
};

struct cornAlgo powerComplex(struct cornAlgo x, int a){

// calcul (a+ib)^c
// la réponse est un nombre complexe, c est positif ou nul

	int i;
	struct cornAlgo reponse;
	mpz_t temp1,temp2,tempX,tempY;

	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(tempX);
	mpz_init(tempY);
	mpz_init(reponse.x_sol);
	mpz_init(reponse.y_sol);

	mpz_set(reponse.x_sol,x.x_sol);
	mpz_set(reponse.y_sol,x.y_sol);

	if (a==0){
		mpz_set_ui(reponse.x_sol,1);
		mpz_set_ui(reponse.y_sol,0);}

	if (a==1){}

	if (a>1){
		for(i=1;i<a;i++){
		
		mpz_set(temp1,reponse.x_sol);
		mpz_mul(temp1,temp1,x.x_sol);
		mpz_set(temp2,reponse.y_sol);
		mpz_mul(temp2,temp2,x.y_sol);
		mpz_neg(temp2,temp2);
		mpz_add(temp1,temp1,temp2);
		mpz_set(tempX,temp1);

		mpz_set(temp1,reponse.x_sol);
		mpz_mul(temp1,temp1,x.y_sol);
		mpz_set(temp2,reponse.y_sol);
		mpz_mul(temp2,temp2,x.x_sol);
		mpz_add(temp1,temp1,temp2);
		mpz_set(tempY,temp1);

		mpz_set(reponse.x_sol,tempX);
		mpz_set(reponse.y_sol,tempY);

		}
	}
	mpz_clear(temp1);
	mpz_clear(temp2);
	mpz_clear(tempX);
	mpz_clear(tempY);	
	
	return reponse;
}

struct cornAlgo multComplex(struct cornAlgo x, struct cornAlgo y){

// calcul (a+bi)*(c+di)
// la réponse est un nombre complexe

	struct cornAlgo reponse;
	mpz_t temp1,temp2;

	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(reponse.x_sol);
	mpz_init(reponse.y_sol);

	mpz_set(temp1,x.x_sol);
	mpz_mul(temp1,temp1,y.x_sol);
	mpz_set(temp2,x.y_sol);
	mpz_mul(temp2,temp2,y.y_sol);
	mpz_neg(temp2,temp2);
	mpz_add(reponse.x_sol,temp1,temp2);

	mpz_set(temp1,x.x_sol);
	mpz_mul(temp1,temp1,y.y_sol);
	mpz_set(temp2,x.y_sol);
	mpz_mul(temp2,temp2,y.x_sol);
	mpz_add(reponse.y_sol,temp1,temp2);

	mpz_clear(temp1);
	mpz_clear(temp2);

	return reponse;
}

struct cornAlgo moduloGauss(struct cornAlgo x, struct cornAlgo y){ 

// calcul (a+bi)modulo(c+di)
// la réponse est un complexe

	struct cornAlgo tempXY;
	mpz_t temp1,temp2,temp3,normY,yReal_q,yImag_q;

	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(temp3);

	mpz_mul(temp1,y.x_sol,y.x_sol); // c^2 + d^2
	mpz_mul(temp2,y.y_sol,y.y_sol);

	mpz_init(normY);
	mpz_add(normY,temp1,temp2);
	mpz_init(yReal_q);				// calcul du quotient réel

	mpz_set(yReal_q,x.x_sol);
	mpz_mul(yReal_q,yReal_q,y.x_sol);
	mpz_set(temp3,x.y_sol);
	mpz_mul(temp3,temp3,y.y_sol);
	mpz_add(yReal_q,yReal_q,temp3);

	if(mpz_sgn(yReal_q) == -1){
		mpz_neg(yReal_q,yReal_q);
		mpz_mod(temp1,yReal_q,normY);
		mpz_add(temp2,temp1,temp1);
		if (mpz_cmp(temp2,normY) > 0){
			mpz_cdiv_q(yReal_q,yReal_q,normY);
		}
		
		else{
			mpz_fdiv_q(yReal_q,yReal_q,normY);
		}

		mpz_neg(yReal_q,yReal_q);
	}
	else{
		mpz_mod(temp1,yReal_q,normY);
		mpz_add(temp2,temp1,temp1);
		if (mpz_cmp(temp2,normY) > 0){
			mpz_cdiv_q(yReal_q,yReal_q,normY);
		}
		
		else{
			mpz_fdiv_q(yReal_q,yReal_q,normY);
		}
	}

	mpz_init(yImag_q);				// calcul du quotient imaginaire
	mpz_set(yImag_q,x.x_sol);
	mpz_mul(yImag_q,yImag_q,y.y_sol);
	mpz_neg(yImag_q,yImag_q);
	mpz_set(temp3,x.y_sol);
	mpz_mul(temp3,temp3,y.x_sol);
	mpz_add(yImag_q,yImag_q,temp3);

	if(mpz_sgn(yImag_q) == -1){
		mpz_neg(yImag_q,yImag_q);
		mpz_mod(temp1,yImag_q,normY);
		mpz_add(temp2,temp1,temp1);
		if (mpz_cmp(temp2,normY) > 0){

			mpz_cdiv_q(yImag_q,yImag_q,normY);	
		}
		else{
			mpz_fdiv_q(yImag_q,yImag_q,normY);
		}
		mpz_neg(yImag_q,yImag_q);
	}
	else{
		mpz_mod(temp1,yImag_q,normY);
		mpz_add(temp2,temp1,temp1);
		if (mpz_cmp(temp2,normY) > 0){
			mpz_cdiv_q(yImag_q,yImag_q,normY);
		}
		
		else{
			mpz_fdiv_q(yImag_q,yImag_q,normY);
		}
	}

	mpz_init(tempXY.x_sol);
	mpz_init(tempXY.y_sol);
	mpz_set(tempXY.x_sol,yReal_q);
	mpz_set(tempXY.y_sol,yImag_q);

	tempXY = multComplex(tempXY,y); // e+fi = (yReal_q+iYImag_q)(c+di)

	mpz_set(temp1, tempXY.x_sol);
	mpz_set(temp2, tempXY.y_sol);

	mpz_neg(temp1,temp1);
	mpz_neg(temp2,temp2);
	mpz_add(temp1,x.x_sol,temp1);	// calcul du reste
	mpz_add(temp2,x.y_sol,temp2);	// réel et imaginaire

	mpz_set(tempXY.x_sol,temp1);
	mpz_set(tempXY.y_sol,temp2);	// on a x/y = bq + r, donc xmody = r

	mpz_clear(temp1);
	mpz_clear(temp2);
	mpz_clear(temp3);
	mpz_clear(yReal_q);
	mpz_clear(yImag_q);
	mpz_clear(normY);

	return tempXY;					// la réponse est le reste, c'est un complexe

}

struct cornAlgo divExactComplex(struct cornAlgo x, struct cornAlgo y){

// calcul (a+bi)/(c+di) sachant que l'on sait d'avance que la division ne donnera pas de reste
// la réponse est un nombre complexe

	struct cornAlgo reponse;
	mpz_t temp1,temp2,temp3;

	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(temp3);
	mpz_init(reponse.x_sol);
	mpz_init(reponse.y_sol);

	mpz_set(temp1,y.x_sol);			// méthode classique: x/y = (x*conj(y))/norme(y)
	mpz_mul(temp1,temp1,y.x_sol);	// x = a + bi, y = c + di
	mpz_set(temp2,y.y_sol);
	mpz_mul(temp2,temp2,y.y_sol);
	mpz_add(temp1,temp1,temp2);		// temp1 = c^2 + d^2 = norme de y
	
	mpz_set(temp2,y.x_sol);	
	mpz_mul(temp2,temp2,x.x_sol);
	mpz_set(temp3,y.y_sol);
	mpz_mul(temp3,temp3,x.y_sol);
	mpz_add(temp2,temp2,temp3);		// temp2 = ac + bd
	mpz_div(reponse.x_sol,temp2,temp1);

	mpz_set(temp2,y.x_sol);
	mpz_mul(temp2,temp2,x.y_sol);
	mpz_set(temp3,y.y_sol);
	mpz_mul(temp3,temp3,x.x_sol);
	mpz_neg(temp3,temp3);
	mpz_add(temp2,temp2,temp3);		// temp2 = bc - ad
	mpz_div(reponse.y_sol,temp2,temp1);

	mpz_clear(temp1);
	mpz_clear(temp2);
	mpz_clear(temp3);

	return reponse;
}

struct cornAlgo transformPrimary(mpz_t inX, mpz_t inY){

// test de PRIMARITY
// il s'agit de vérifier qu'un nombre complexe a+bi respecte les deux règles suivantes:
// b = 0 mod 2
// a+b = 1 mod 4

	mpz_t tempX1,tempX2,tempY1,tempY2,temp1,temp2;
	struct cornAlgo nbrXY;

	mpz_init(tempX1);
	mpz_init(tempX2);
	mpz_init(tempY1);
	mpz_init(tempY2);
	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(nbrXY.x_sol);
	mpz_init(nbrXY.y_sol);

	mpz_set(nbrXY.x_sol,inX);
	mpz_set(nbrXY.y_sol,inY);	// au cas où le test n'est pas réussi

	mpz_set(tempX1,inX);		//  a
	mpz_neg(tempX2,tempX1);		// -a
	mpz_set(tempY1,inY);		//  b
	mpz_set(tempY2,tempY1);
	mpz_neg(tempY2,tempY2);		// -b

	// si le nombre c = a+bi ne passe pas le test, on cherche à le modifier pour
	// trouver un nombre qui passe le test.
	// Les nombres possibles sont:
	// a+bi = 1*c, -b+ai = i*c, -a-bi = -1*c, b-ai = -i*c

	mpz_mod_ui(temp1,tempY1,2);
	mpz_add(temp2,tempX1,tempY1);
	mpz_mod_ui(temp2,temp2,4);

	if ((mpz_cmp_si(temp1,0)==0) && (mpz_cmp_si(temp2,1)==0)){ // fois 1
				mpz_set(nbrXY.x_sol,tempX1);
				mpz_set(nbrXY.y_sol,tempY1);
	}
	else{
		mpz_mod_ui(temp1,tempY2,2);
		mpz_add(temp2,tempX2,tempY2);
		mpz_mod_ui(temp2,temp2,4);

		if ((mpz_cmp_si(temp1,0)==0) && (mpz_cmp_si(temp2,1)==0)){ // fois -1
					mpz_set(nbrXY.x_sol,tempX2);
					mpz_set(nbrXY.y_sol,tempY2); 
		}
		else{		
			mpz_mod_ui(temp1,tempX1,2);
			mpz_add(temp2,tempY2,tempX1);
			mpz_mod_ui(temp2,temp2,4);

			if ((mpz_cmp_si(temp1,0)==0) && (mpz_cmp_si(temp2,1)==0)){ // fois  i
						mpz_set(nbrXY.x_sol,tempY2);
						mpz_set(nbrXY.y_sol,tempX1);
			}
			else{
				mpz_mod_ui(temp1,tempX2,2);
				mpz_add(temp2,tempY1,tempX2);
				mpz_mod_ui(temp2,temp2,4);

				if ((mpz_cmp_si(temp1,0)==0) && (mpz_cmp_si(temp2,1)==0)){ // fois -i
							mpz_set(nbrXY.x_sol,tempY1);
							mpz_set(nbrXY.y_sol,tempX2);
				}
			}
		}
	}
	mpz_clear(tempX1);
	mpz_clear(tempX2);
	mpz_clear(tempY1);
	mpz_clear(tempY2);
	mpz_clear(temp1);
	mpz_clear(temp2);

	// si ce n'est pas transformable ou si c'est inutile de transformer,
	// on ne change rien
	
	return nbrXY;
}

int power(int val, int pow){ 
	
// a^b       
	
	int ret_val = 1;
    int i;

    for(i = 0; i < pow; i++) ret_val *= val;

    return(ret_val);
}

// ***** L'algorithme en lui-même

struct cornAlgo quartic(struct cornAlgo x, struct cornAlgo y){

	struct cornAlgo temp,tempX,tempY,unPlusI,tempNeg;
	mpz_t temp1,temp2,temp3;
	int r,s,s2,total_result;
	struct resChar resultat;

	mpz_init(tempX.x_sol);
	mpz_init(tempX.y_sol);
	mpz_init(tempY.x_sol);
	mpz_init(tempY.y_sol);
	mpz_init(temp.x_sol);
	mpz_init(temp.y_sol);

	mpz_set(tempX.x_sol,x.x_sol);
	mpz_set(tempX.y_sol,x.y_sol);

	mpz_set(tempY.x_sol,y.x_sol);
	mpz_set(tempY.y_sol,y.y_sol);
	
	mpz_init(temp1);
	mpz_init(temp2);
	mpz_init(temp3);

	mpz_init(tempNeg.x_sol);
	mpz_init(tempNeg.y_sol);
	mpz_set(tempNeg.x_sol,tempX.x_sol);
	mpz_neg(tempNeg.x_sol,tempNeg.x_sol);
	mpz_set(tempNeg.y_sol,tempX.y_sol);
	mpz_neg(tempNeg.y_sol,tempNeg.y_sol);

	mpz_init(unPlusI.x_sol);
	mpz_init(unPlusI.y_sol);

	resultat.real_plus = 0;
	resultat.real_moins = 0;
	resultat.imag_plus = 0;
	resultat.imag_moins = 0;

	if (((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))){
		printf("Entrées non conformes...alpha est nulle!\n");
		_beep(200,300);
		exit(1);
	}

	mpz_set(temp1,moduloGauss(tempX,tempY).x_sol);
	mpz_set(temp2,moduloGauss(tempX,tempY).y_sol);

	if (((mpz_cmp_ui(temp1,0) == 0) && (mpz_cmp_ui(temp2,0) == 0))){
		printf("Entrees non conformes...alpha est un multiple de delta!\n");
		_beep(200,300);
		exit(1);
	}

// 0, PRIMARY test sur le delta. On effectue une transformation si nécessaire
// IL EST ESSENTIEL QUE DELTA SORTE DU TEST EN ETANT PRIMARY POUR QUE L'ALGO FONCTIONNE!

	tempY= transformPrimary(tempY.x_sol,tempY.y_sol); 

	while (!(
		((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
		((mpz_cmp_ui(tempX.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
		((mpz_cmp_ui(tempNeg.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))||
		((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,1) == 0))  ||
		((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempNeg.y_sol,1) == 0))
		)){

		tempX = moduloGauss(tempX,tempY); // on réduit si c'est possible

		mpz_set(tempNeg.x_sol,tempX.x_sol);
		mpz_neg(tempNeg.x_sol,tempNeg.x_sol);
		mpz_set(tempNeg.y_sol,tempX.y_sol);
		mpz_neg(tempNeg.y_sol,tempNeg.y_sol);
		
	// 2, LE PARASITE 1+i
		if (!(
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempNeg.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,1) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempNeg.y_sol,1) == 0))
			)){

			mpz_set(temp1,tempX.x_sol);
			mpz_mul(temp1,temp1,tempX.x_sol);
			mpz_set(temp2,tempX.y_sol);
			mpz_mul(temp2,temp2,tempX.y_sol);
			mpz_add(temp1,temp1,temp2);
		
			mpz_mod_ui(temp2,temp1,2);
			r=0;
			
			if (mpz_cmp_ui(temp2,0) == 0){
			
			while((mpz_cmp_ui(temp2,0) == 0) && (!(mpz_cmp_ui(temp1,0) == 0)))
				{
				mpz_div_ui(temp1, temp1, 2);
				mpz_mod_ui(temp2,temp1,2);
				r = r+1;
				}
			}

			mpz_set(temp3,tempY.y_sol);
			mpz_mul(temp3,temp3,tempY.y_sol);
			mpz_add(temp3,temp3,tempY.y_sol);
			mpz_add_ui(temp3,temp3,1);
			mpz_neg(temp3,temp3);
			mpz_add(temp3,temp3,tempY.x_sol);
			mpz_div_ui(temp3,temp3,4); // a-b-b^2-1 / 4
			mpz_mul_ui(temp3,temp3,r); // * r

			if (mpz_sgn(temp3) == -1){

				mpz_neg(temp3,temp3);
				mpz_mod_ui(temp3,temp3,4);

				if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
				if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
				if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
				if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
				}

			else{
				mpz_mod_ui(temp3,temp3,4); 

				if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
				if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
				if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
				if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
			}

			mpz_set_ui(unPlusI.x_sol,1);
			mpz_set_ui(unPlusI.y_sol,1);
			unPlusI = powerComplex(unPlusI,r);

			tempX = divExactComplex(tempX,unPlusI);

			mpz_set(tempNeg.x_sol,tempX.x_sol);
			mpz_neg(tempNeg.x_sol,tempNeg.x_sol);
			mpz_set(tempNeg.y_sol,tempX.y_sol);
			mpz_neg(tempNeg.y_sol,tempNeg.y_sol);
		}

		if (!(
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempNeg.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,1) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempNeg.y_sol,1) == 0)))){

	// 3, PRIMARIYsation
			temp = transformPrimary(tempX.x_sol,tempX.y_sol);

			if ((mpz_cmp(tempX.x_sol,temp.x_sol) == 0) && (mpz_cmp(tempX.y_sol,temp.y_sol) == 0)){
				s=0;} // *1
			if ((mpz_cmp(tempNeg.y_sol,temp.x_sol) == 0) && (mpz_cmp(tempX.x_sol,temp.y_sol) == 0)){
				s=1;} // *i
			if ((mpz_cmp(tempNeg.x_sol,temp.x_sol) == 0) && (mpz_cmp(tempNeg.y_sol,temp.y_sol) == 0)){
				s=2;} // *-1
			if ((mpz_cmp(tempX.y_sol,temp.x_sol) == 0) && (mpz_cmp(tempNeg.x_sol,temp.y_sol) == 0)){
				s=3;} // *-i

	// calcul de i/delta:
			mpz_set(temp2,tempY.x_sol);
			mpz_mul(temp2,temp2,tempY.x_sol);// a^2
			mpz_set(temp3,tempY.y_sol);
			mpz_mul(temp3,temp3,tempY.y_sol); // b^2
			mpz_add(temp3,temp3,temp2); // a^2+b^2
			mpz_neg(temp3,temp3); // -(a^2+b-2)
			mpz_add_ui(temp3,temp3,1); // 1-(a^2+b^2)
			mpz_neg(temp3,temp3); // a^2+b^2-1
			mpz_div_ui(temp3,temp3,4); 
			s=3*s; // (-i)^s = i^3s
			mpz_mul_ui(temp3,temp3,s);

			if (mpz_sgn(temp3) == -1){

				mpz_neg(temp3,temp3);
				mpz_mod_ui(temp3,temp3,4);

				if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
				if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
				if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
				if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
				}

			else{
				mpz_mod_ui(temp3,temp3,4); 

				if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
				if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
				if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
				if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
			}
	// mise à jour de x
			mpz_set(tempX.x_sol,temp.x_sol);
			mpz_set(tempX.y_sol,temp.y_sol);
		}

	// A ce stade, les deux éléments de l'équations sont PRIMARY
	// On peut donc appliquer la loi de réciprocité:
	// 4, Loi de réciprocité

		mpz_set(tempNeg.x_sol,tempX.x_sol);
		mpz_neg(tempNeg.x_sol,tempNeg.x_sol);
		mpz_set(tempNeg.y_sol,tempX.y_sol);
		mpz_neg(tempNeg.y_sol,tempNeg.y_sol);

		if (!(
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))  ||
			((mpz_cmp_ui(tempNeg.x_sol,1) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0))||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,1) == 0))  ||
			((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempNeg.y_sol,1) == 0)))){

			mpz_set(temp1,tempY.x_sol);
			mpz_mul(temp1,temp1,tempY.x_sol);
			mpz_set(temp2,tempY.y_sol);
			mpz_mul(temp2,temp2,tempY.y_sol);
			mpz_add(temp1,temp1,temp2); // norme de delta
			mpz_neg(temp1,temp1);
			mpz_add_ui(temp1,temp1,1);
			mpz_neg(temp1,temp1); // a^2 + b^2 - 1
			mpz_set(temp2,tempX.x_sol);
			mpz_mul(temp2,temp2,tempX.x_sol);
			mpz_set(temp3,tempX.y_sol);
			mpz_mul(temp3,temp3,tempX.y_sol);
			mpz_add(temp2,temp2,temp3); // norme de alpha
			mpz_neg(temp2,temp2);
			mpz_add_ui(temp2,temp2,1);
			mpz_neg(temp2,temp2);

			mpz_mul(temp1,temp1,temp2);
			mpz_div_ui(temp1,temp1,16);
			mpz_mod_ui(temp1,temp1,2);

			if (mpz_cmp_ui(temp1,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
			else{resultat.real_moins = resultat.real_moins + 1;}
				
			// mise à jour
			mpz_set(tempX.x_sol,tempY.x_sol);
			mpz_set(tempX.y_sol,tempY.y_sol);
			mpz_set(tempY.x_sol,temp.x_sol);
			mpz_set(tempY.y_sol,temp.y_sol);

			mpz_set(tempNeg.x_sol,tempX.x_sol);
			mpz_neg(tempNeg.x_sol,tempNeg.x_sol);
			mpz_set(tempNeg.y_sol,tempX.y_sol);
			mpz_neg(tempNeg.y_sol,tempNeg.y_sol);
		}

	} // le grand while 

	if (!(((mpz_cmp_ui(tempX.x_sol,0) == 0) && (mpz_cmp_ui(tempX.y_sol,0) == 0)))){
		

		if (mpz_cmp_ui(tempX.x_sol,1)  == 0) {r=0;}//4;}
		if (mpz_cmp_ui(tempNeg.x_sol,1) == 0) {r=2;}
		if (mpz_cmp_ui(tempX.y_sol,1)  == 0) {r=1;}
		if (mpz_cmp_ui(tempNeg.y_sol,1) == 0) {r=3;}

		mpz_set(temp2,tempY.x_sol);
		mpz_mul(temp2,temp2,tempY.x_sol);
		mpz_set(temp3,tempY.y_sol);
		mpz_mul(temp3,temp3,tempY.y_sol);
		mpz_add(temp3,temp3,temp2);
		mpz_neg(temp3,temp3);
		mpz_add_ui(temp3,temp3,1);
		mpz_neg(temp3,temp3);
		mpz_div_ui(temp3,temp3,4);
		mpz_mul_ui(temp3,temp3,r);

		if (mpz_sgn(temp3) == -1){

			mpz_neg(temp3,temp3);
			mpz_mod_ui(temp3,temp3,4);

			if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
			if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
			if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
			if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
			}

		else{
			mpz_mod_ui(temp3,temp3,4); 

			if (mpz_cmp_ui(temp3,0) == 0){resultat.real_plus = resultat.real_plus + 1;}
			if (mpz_cmp_ui(temp3,1) == 0){resultat.imag_plus = resultat.imag_plus + 1;}
			if (mpz_cmp_ui(temp3,2) == 0){resultat.real_moins = resultat.real_moins + 1;}
			if (mpz_cmp_ui(temp3,3) == 0){resultat.imag_moins = resultat.imag_moins + 1;}
		}
	total_result = (resultat.imag_plus + 2*resultat.real_moins + 3*resultat.imag_moins);
		total_result = total_result&3;

		if (total_result == 0){
			mpz_set_ui(temp.x_sol,1);mpz_set_ui(temp.y_sol,0);}

		if (total_result == 1){
			mpz_set_ui(temp.x_sol,0);mpz_set_ui(temp.y_sol,1);}

		if (total_result == 2){
			mpz_set_ui(temp.x_sol,1);mpz_neg(temp.x_sol,temp.x_sol);mpz_set_ui(temp.y_sol,0);}

		if (total_result == 3){
			mpz_set_ui(temp.x_sol,0);mpz_set_ui(temp.y_sol,1);mpz_neg(temp.y_sol,temp.y_sol);}

		mpz_clear(temp1);
		mpz_clear(temp2);
		mpz_clear(temp3);
		mpz_clear(tempX.x_sol);
		mpz_clear(tempX.y_sol);
		mpz_clear(tempY.x_sol);
		mpz_clear(tempY.y_sol);
		mpz_clear(unPlusI.x_sol);
		mpz_clear(unPlusI.y_sol);
		
	}

	return temp;

}
// ************** MAIN
int main(void){ 

	struct cornAlgo alpha, beta,rep;
	char* temp;
	char* xc;
	char* yc;

	int i=0;
	int j=0;
	int x,d;

	mpz_init(alpha.x_sol);
	mpz_init(alpha.y_sol);	
	mpz_init(beta.x_sol);
	mpz_init(beta.y_sol);

temp="9597668719801313988353738782261942599237752791575575420305761876265862544120836660192534558602409686683221737492858517289954867335315347603241921121591118028788431";
mpz_set_str(beta.x_sol,temp,10);

temp = "7134218987249387452935521903085170868478923749563132505189587382998736190082683718437654496904227932765368206087058195930178336671583541109383813675309120173445286";
mpz_set_str(beta.y_sol,temp,10);

temp="65393499616376627213311765836983432094485601390446446046903536352321392401533010099408897626166269386893170657896791098596307378766343040741986965582444045508798898568987294062486469194850048286632545854773437261004632922514498569984869453174631956626177073535373106348062654701579175382979290343211456351672644502006230877984";	
mpz_set_str(alpha.x_sol,temp,10);
	
mpz_set_ui(alpha.y_sol,0);
rep = quartic(alpha,beta);

printf("quartic: ");

				if ((mpz_cmp_ui(rep.y_sol, 0) == 0) && (mpz_cmp_ui(rep.x_sol, 0) == 0)){printf("0");} //return FALSE;}
					else{
			if (mpz_cmp_ui(rep.y_sol, 0) == 0){// s'il n'y a pas de i ou -i
				if (mpz_cmp_ui(rep.x_sol, 1) == 0){printf("1");}

				else{
					mpz_neg(rep.x_sol,rep.x_sol);
					if (mpz_cmp_ui(rep.x_sol, 1) == 0){printf("-1");}
				}
			}
				
			else{// s'il n'y a pas de 1 ou -1
				if (mpz_cmp_ui(rep.y_sol, 1) == 0){printf("i");}
				else{printf("-i");}
			}
		}

printf("\n\n");

return 0;
}

Conclusion :


Homomorphisme pour les protocoles de signature...

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
Hello! Non, ce n'est pas du cryptage... ni du hashage en fait. C'est pour SIGNER. SI jamais regarde l'URL que j'ai mis pour les détails.

En quelques mots: je prends comme entrée le hashage d'un fichier à signer. Préalablement j'ai générer une clé secrète de la forme a+bi (c'est le delta), telle que Norme(a+bi) = p*q, p et q étant des premiers 1 mod 4. A parit de cela, si je fait quartic(a,b), j'aurai une réponse sur deux bits: 1, -1, i, -i. Si je décide que 1->00, -1->01, i->10, -i->11 et qu'ensuite je comprime 1,-i -> 0 et -1,i->1, j'aurai qqchose du type 11100110001011001010 et ensuite je peux regarder dans un dico. Ca devient une signature... A côté de ça il faut biensûr une clé publlique, mais plutôt que de partir dans des explications je te conseille à nouveau l'url http://lasecwww.epfl.ch/movaMemo.html ;o)

Si t'as d'autres questions, hésite pas!
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010
-
En gros, si j'ai bien compris, tu utilises la fonction de résolution de quartique pour transformer un condensé ?
A quoi cela sert il ? Est ce que cette transformation est réversible ?
En fait, est ce que ca correspond à du cryptage ou à du hashage ?
malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
A quoi ça sert? Un petit exemple: imagine que tu veux crypter un fichier pour le signer. Une manière de faire: tu hash le fichier avec SHA-1 ou MD5 par exemple, tu récupères les bits de sortie et tu passes ça dans la fonction de résidus quartiques (après avoir judicieusement choisi un z = a+ bi pour faire le delta, c'est la clé secrète). Tu sors de la X bits (si tu associes 1 à -1 et i et 0 à 1 et -i par exemple), disons 20, que tu peux utiliser avec un dictionnaire de mot: 011 -> 3 -> cf 3e mot du dico. Et ainsi tu as une clé secrète et une signature "intelligible"... etc... pour plus d'info, regarde http://lasecwww.epfl.ch/movaMemo.html, c'est le protocole que je suis en train d'implémenter (enfin... j'essaie ;o))
Inekman
Messages postés
291
Date d'inscription
dimanche 2 février 2003
Statut
Membre
Dernière intervention
30 juin 2006
-
je sais pas à quoi ça sert, mais c'est impressionnant. :-)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.