Espaces Quotients

espacesQuotients.c

#include<stdio.h>
#include<gmp.h>

/*---------------------------------------------------------------------*/

/*
  Calcule u et v tels que au + bv = pgcd, ou pgcd est le pgcd de a et b. 
  Toutes les variables doivent etre initialisees.
 */

void bezout(mpz_t a, mpz_t b, mpz_t u, mpz_t v, mpz_t pgcd)
{
  if (!mpz_cmp_ui(b, 0))
    {
      mpz_set(pgcd, a);
      mpz_set_ui(u, 1);
      mpz_set_ui(v, 0);
    }
  else
    {
      mpz_t quotient;
      mpz_t reste;
      mpz_t uRec;
      mpz_t vRec;
      mpz_t vFoisQuotient;
      mpz_init(quotient);
      mpz_init(reste);
      mpz_init(uRec);
      mpz_init(vRec);
      mpz_init(vFoisQuotient);
      mpz_tdiv_qr(quotient, reste, a, b);
      bezout(b, reste, uRec, vRec, pgcd);
      mpz_set(u, vRec);
      mpz_mul(vFoisQuotient, vRec, quotient);
      mpz_sub(v, uRec, vFoisQuotient);
      mpz_clear(quotient);
      mpz_clear(reste);
      mpz_clear(uRec);
      mpz_clear(vRec);
      mpz_clear(vFoisQuotient);
    }
}

/*---------------------------------------------------------------------*/

int trouveInverse(mpz_t valeur, mpz_t module, mpz_t inverse)
{
  mpz_t u, v, pgcd;
  int res = 1;
  mpz_init(u);
  mpz_init(v);
  mpz_init(pgcd);
  bezout(valeur, module, u, v, pgcd);
  if (!mpz_cmp_ui(pgcd, 1))
      mpz_set(inverse, u);
  else
      res = 0;
  mpz_clear(u);
  mpz_clear(v);
  mpz_clear(pgcd);
  return res;
}

/*---------------------------------------------------------------------*/

void etudieEspaceQuotient(mpz_t n)
{
  mpz_t i, phi, inverseI;
  mpz_init(i);
  mpz_init(phi);
  mpz_init(inverseI);
  mpz_set_ui(i, 0);
  mpz_set_ui(phi, 0);
  printf("Z/");
  mpz_out_str(NULL, 10, n);
  printf("Z : ");
  while(mpz_cmp(i, n))
    {
      printf("\n");
      mpz_out_str(NULL, 10, i);
      if (trouveInverse(i, n, inverseI))
	{
	  printf(" a pour inverse ");
	  mpz_add_ui(phi, phi, 1);
	  mpz_mod(inverseI, inverseI, n);
	  mpz_out_str(NULL, 10, inverseI);
	}
      else
	printf(" (non inversible) ");
      mpz_add_ui(i, i, 1);
    }
  printf("\nOn a phi(");
  mpz_out_str(NULL, 10, n);
  printf(") = ");
  mpz_out_str(NULL, 10, phi);
  printf("\n");
  mpz_add_ui(phi, phi, 1);
  if (!mpz_cmp(n, phi))
    printf("Cet ensemble est un corps\n");
  else
    printf("Cet ensemble n est pas un corps\n");
}

/*---------------------------------------------------------------------*/

int main(int argc, char* argv[])
{
  mpz_t test;
  mpz_init(test);
  if (argc > 1)
    mpz_set_str(test, argv[1], 10);
  else
    mpz_init_set_ui(test, 15);
  etudieEspaceQuotient(test);
  mpz_clear(test);
  return 0;
}