SHANK Algoritması

#include<stdio.h>
#include<math.h> //ceil ve sqrt için
#define M 1000

int hizli(int,int,int);//üslü sayıların modunu almak için hızlı modüler üs algoritmasını kullandım
int modInverse(int , int ); //bi sayının moda göre tersini alır
int L1[M];//1. liste
int L2[M];//2. liste
int dizi_i[M];
int dizi_j[M];

int main(){

printf("\n a^x = b mod p isleminde verilen a, b ve p degerleri icin ");
printf("x' in hesaplanmasi\n\n");

int a,b,p,i,j,m,sayac=0;

printf("\na degerini giriniz:");//taban(alfa)
scanf("%d",&a);
printf("\nb degerini giriniz:");//(beta)
scanf("%d",&b);
printf("\np degerini giriniz:");//mod
scanf("%d",&p);

m=(int)ceil(sqrt(p-1));

for(j=0;j<m;j++) //a^(m*j)
L1[j]=hizli(a,m*j,p);

for(i=0;i<m;i++) //önce a^i hesaplanır,daha sonra bunun mod p' ye göre tersi alınır
L2[i]=(b*modInverse(hizli(a,i,p),p))%p; //b ile çarpılır ve mod p yapılır

for(i=0;i<m;i++) //iki listeyi karşılaştırıyor
for(j=0;j<m;j++)
if(L2[i]==L1[j]){
dizi_i[sayac]=i;
dizi_j[sayac]=j;
sayac++;
}

printf("\nj=%d i=%d\n",dizi_j[0],dizi_i[0]);
//for(i=0;i<m;i++)
printf("\nx=%d\n",(m*dizi_j[0]+dizi_i[0])%(p-1));

return 0;
}


int modInverse(int a, int n) {

int mod = n; //son adımda mod bize lazım olacak
int ters = 0, d = 1; //eğer tersi yoksa 0 döndürecek

while (a>0) { //pozitif olmalı tersi bulunması için
int bolum = mod/a, sayi = a;
a = mod % sayi; //kalanı atıyoruz
mod = sayi;
sayi = d;
d = ters - bolum*sayi;
ters = sayi;
}
ters %= n;
if (ters<0) //eğer negatifse o moda göre pozitif eşitini buluyor
ters = (ters+n)%n;
return ters;
}


int hizli(int a,int b,int m){//taban , üs ve mod değişkeni

int c=0, d=1, i, k=0;//k sayaç
int on;
int binary[100];//üssün ikili karşılığı

on=b; //b yi ikiliye çevir binary[] dizisine ata,rakam sayısını k ya ata
while (on>0)
{
binary[k]=on % 2;
on = on / 2;
k++;
}

for(i=0;i<k;i++){//hızlı üs alma algoritması

c=2*c;
d=(d*d)%m;

if(binary[k-1-i]==1){
c++;
d=(d*a)%m;
}
}
return d;
}