Résidus biquadratiques
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
Homomorphisme pour les protocoles de signature...
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...
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.