CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 27 18:23:04

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

RÉSIDUS BIQUADRATIQUES

Information sur la source

Note :
Aucune note

Catégorie :Sécurité & Cryptage Niveau :Initié Date de création :01/09/2004 Date de mise à jour :13/09/2004 20:28:38 Vu / téléchargé :3 427 / 136

Auteur : malik7934

Ecrire un message privé

Commentaire sur cette source (4)

Ajouter un commentaire et/ou une note

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

// **********************************************
// 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;
}

// **********************************************
//	  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...

Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

quart.pdf33 481 octets

Télécharger le zip

Historique

02 septembre 2004 16:39:43 :: Voilà une version épurée de tout code inutile (j'avais laissé traîner pas mal de fonctions) et qui a l'avantage d'être JUSTE, contrairement à la dernière version. Si vous exécutez ce code, vous aurez comme réponse: [code] Le residu biquadratique de 11031818020696571597239620808834075942982696691282491597775427449726988070342010 653465971096325346914408067426660421091050705936 par 38325763174536450848974858388463913870523833963235457447192624452697978016299073 08083454639275083186765047040749133298990036687667255119307215103120892708551446 085 +i* 40156513646433533491396592918378956357462487576188199306144054757048528555017576 76390789196753936154073212813023829126072036075439456769468035845385170838862547 576 est: 1 (oh la surprise!) [/code]
02 septembre 2004 17:13:31 :: J'ai oublié de mettre le PDF qui explique en gros l'algo! C'est chose faite maintenant ;o)
06 septembre 2004 11:10:05 :: oops, il y avait un bug mathématique dans la manière de faire le modulo gaussien! C'est corrigé. Prochaine étape: optimiser la vitesse...
06 septembre 2004 11:47:39 :: avec le bon code, c'est mieux ;o)
08 septembre 2004 17:08:20 :: correction d'une erreur possible due à un manque de rigueur dans la sortie du test de primarysation
10 septembre 2004 15:38:36 :: arg! Encore un bug de détecté: la construction de la réponse contenait une erreur... c'est corrigé!
13 septembre 2004 20:28:38 :: une déclaration manquante...

Sources du même auteur

AFFICHER LA XEME LIGNE D'UN TEXTE

FENÊTRE AVEC OU SANS BOUTON

CORNACCHIA ALGORITHM

Toutes les sources de malik7934

Sources de la même categorie

PROJET DE CRYPTOGRAPHIE: RSA À JEU REDUIT D'INSTRUCTION par samatarahmed

CRYPTOSYSTÈME ELGAMAL LIBRAIRIE GMP par louelh95

NOUVEL ALGORITHME D'ENCRYPTION-DÉSENCRYPTION DYNAMIQUE (INFA... par vletktol

A2DCRYPT - CRYPTAGE 2048 BITS par darkor

CRYPTEUR-DÉCRYPTEUR-IP par antho974

Toutes les sources de la catégorie Sécurité & Cryptage

Commentaires et avis

Commentaire de Inekman le 02/09/2004 23:44:28

je sais pas à quoi ça sert, mais c'est impressionnant. :-)

Commentaire de malik7934 le 03/09/2004 09:22:30

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))

Commentaire de TeLeTUbIz le 03/09/2004 18:35:11

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 ?

Commentaire de malik7934 le 04/09/2004 10:40:05

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!

Ajouter un commentaire

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

MATRICE TEMPLATE par hjr2610

SUPERVISION DE LA BATTERIE par romanticgirl

RE : OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par buno

RE : SAC A DOS par hadjkaddour

OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par ssaif

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Realisation d-une version 2 d-un site e-commerce existant sous prestashop-REPUBLICATION
Budget : 5 000€
Recherche Infogerance Serveur Debian Linux
Budget : 1 800€
Creation d-un site vitrine avec MagentO
Budget : 2 000€

Logiciels

sDEVIS-FACTURES vlPRO (8.1.0.3)
SDEVIS-FACTURES VLPRO (8.1.0.3)

sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa...

Cliquez pour télécharger sDEVIS-FACTURES vlPRO
974 Application Server (12.2.4.6)
974 APPLICATION SERVER (12.2.4.6)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP