Euler-Fermat Teoremi

//ax=b mod m işleminin (yani modülerde ters alma işleminin)
//euler-fermat teoremine göre genişletilmesi

//Euler-Fermat Teoremi:
//a ve m aralarında asal ise
//x=b*a^(U(m)-1) mod m
//U(n)=n*(1-1/asalçarpan1)*(1-1/asalçarpan2) kaç tane asal çarpanı varsa
//örneğin U(45)=45*(1-1/5)*(1-1/3)

#include<stdio.h>

int main(){

int a,m,b,um=0,temp,x,ustel=1;

printf("\nax=b mod m isleminin Euler-Fermat Teoremine gore genisletilmesi\n\n");

printf("\nTersi alinacak sayiyi giriniz(a):");
scanf("%d",&a);

printf("\nHangi moda gore alinacak(m):");
scanf("%d",&m);

printf("\nb katsayisini giriniz:");
scanf("%d",&b);

int sayac=0,l,ks;//aralarında asla ise kontrol

if(a<m)
ks=a;
if(m<a) //küçük sayiyi bulduralım ki döngü daha az çalışsın.
ks=m;

for(l=2;l<=ks;++l)
if(a%l==0 && m%l==0) //aralarında asal mı??
sayac=1;

if (sayac==0) //------------------aralarında asal ise
{
temp=m;//mod kısmı daha sonra işimize yarayacak,geçici değişkende tutalım

int i,j=0; //asal çarpanları bulan kısım
int asalcarpan[20];

for(i=2;i<=m;i++){
if(m%i==0){
asalcarpan[j]=i;
j=j++;
m=m/i;
}}//asal çarpanları bulan kısım sonu

um=temp;//mod olan m' nin ilk halini atıyoruz

int ii,jj;

for(ii=0;ii<j;++ii) //U(m) yi buluyoruz
um=(um*asalcarpan[ii]-1)/asalcarpan[ii];
//um=um*(1-1/asalcarpan[ii]);


for(jj=1;jj<um;jj++) //a^(U(m)-1) işlemini yapıyoruz
ustel=ustel*a;

x=(b*ustel)%temp; //son olarak x' i buluyoruz

printf("\nx=%d mod %d\n",x,temp);
}//if sonu

else
printf("\nSayilar aralarinda asal degil,Fermat-Euler Teoremine gore cozulemez,baska yontem deneyin:::\n");

return 0;
}