Trouver l'inverse d'un nombre dans z/pz

Commenter

Contenu du snippet

Il s'agit d'un programme purement de math : soit n et p deux entiers. Le programme cherche à detreminer un entier m tel que n*m = 1 mod p.

Source / Exemple : 


#include <stdio.h>
#include <stdlib.h>

long int minimum(long int  a0,long int  b0)
{
  if (a0<b0) 
	{return a0;}
  else 
	return b0;
}

long int maximum(long int  a1,long int  b1)
{
  if (a1>b1)
	{return a1;}
  else
	return b1;
}

long int premier_entre_eux(long int  a2,long int  b2)
{
  long int r1, r2,rt;
  r1=minimum(a2,b2);
  r2=maximum(a2,b2);
  while(rt>1)
  {
	rt=r1 % r2;
	if (rt<0) 
	rt+=r2;
	r1=r2;
	r2=rt;
  }
  if (rt==1) 
	{return 1;}
  else
  	return 0;
}

long int bezout(long int  a3, long int  b3)
{
  long int coeffs1, coeffs2, coeffst,  r1, r2, rt;
  if (premier_entre_eux(a3,b3)==0) 
	{return 0;}
  else
  {
  coeffs1=1; coeffs2=0;
  r1=minimum(a3,b3);
  r2=maximum(a3,b3);
  rt=r1 % r2;
  while (rt>1)
      {
	rt=r1 % r2;
	if (rt<0) 
	rt+=r2;
	coeffst=coeffs1-(r1/r2)*coeffs2;
	coeffs1=coeffs2;
	coeffs2=coeffst;
	r1=r2;
	r2=rt;
      }
  }
  return(coeffs2);
}

long int inverse(long int  a4,long int  m)
{
  long int  result, a5;
  a5= a4 % m;
  result=bezout(a5,m);
  result=result % m;
  if (result<0) 
	result+=m;
  return result;
}

void main()
{
  long int  nb, p;
  printf("\nNombre a inverser : ");
  scanf("%d",&nb);
  printf("Le modulo: ");
  scanf("%d",&p);
  if (inverse(nb,p)==0) 
	{printf("Probléme : %d et %d ne sont pas premiers entre eux.\n", nb,p);}
  else 
	printf("\n\nL'inverse de %d modulo %d est %d.\n", nb,p,inverse(nb,p));
  system("pause");
}

Conclusion :


Eviter les nombres supérieurs à 2^31.

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_Thanatos)