hey william, I'm trying to find the inverse of a(X) mod 32, after running the first 31 lines of the algorithm for the polynomial a(X)=[-1,1,1,0,-1,0,1,0,0,1,-1] my program returns: b(X)=[1,1,0,0,0,1] and c(X)=[0,0,0,0,0,0,0,0,1,1] and k=11; I already know from the NTRU tutorial that the inverse of a(X) mod 32 is [5,9,6,16,4,15,16,22,20,18,30] however when I continue with the rest of the code i get a different answer. I was wondering if you could check whether my value for b(X) that I get after the first 31 lines is correct? If you could do that I would be extremely grateful.
k=0;
do
{
while(f[0]==0)
{
printf("\nEntering in while loop");
printf("--------\n");
for(i=1;i<=N;i++)
{
f[i-1]=f[i];
f[N]=0;
c[N+1-i]=c[N-i];
}
for(i=0;i<=0;i++)
{
c[i]=0;
}
k=k+1;
}
printf("\nExiting from while loop\n");
int x=degree(f);
int y=degree(g);
for(i=0;i<N;i++)
{
printf("%d",f[i]);
}
printf("-");
for(i=0;i<N;i++)
{
printf("%d",g[i]);
}
printf("-");
for(i=0;i<N;i++)
{
printf("%d",b[i]);
}
printf("-");;
for(i=0;i<N;i++)
{
printf("%d",c[i]);
}
printf("\n");
if(x==0)
{
goto step33;
}
if(x<y)
{
printf("Entering in degree f less than g loop");
printf("------\n");
for(i=0;i<N;i++)
{
temp[i]=f[i];
f[i]=g[i];
g[i]=temp[i];
temp[i]=c[i];
c[i]=b[i];
b[i]=temp[i];
}
//printf("\npolynomial_f--");
for(i=0;i<N;i++)
{
printf("%d",f[i]);
}
printf("-");
//printf("\npolynomial_g--");
for(i=0;i<N;i++)
{
printf("%d",g[i]);
}
printf("-");
//printf("\npolynomial_b--");
for(i=0;i<N;i++)
{
printf("%d",b[i]);
}
printf("-");
//printf("\npolynomial_c--");
for(i=0;i<N;i++)
{
printf("%d",c[i]);
}
}
printf("\nExiting from degree f less than g loop");
printf("--------");
tempvar=posmodr(f[0],q);
tempvar1=extendedEuclid(g[0],q);
tempvar2=tempvar*tempvar1;
int u=posmodr(tempvar2,q);
//printf("\n%d\n%d\n%d\n%d\n",tempvar,tempvar1,tempvar2,u);
for(i=0;i<N;i++)
{
f[i]=posmodr((f[i]+g[i]),q);
b[i]=posmodr((b[i]+c[i]),q);
}
printf("\npolynomial_f--");
for(i=0;i<N;i++)
{
printf("%d",f[i]);
}
printf("\npolynomial_g--");
for(i=0;i<N;i++)
{
printf("%d",g[i]);
}
printf("\npolynomial_b--");
for(i=0;i<N;i++)
{
printf("%d",b[i]);
}
printf("\npolynomial_c--");
for(i=0;i<N;i++)
{
printf("%d",c[i]);
}
int s=degree(f);
t=s;
} while(t!=0);
step33:
j=0;
k=posmodr(k,N-1);
for(i=0;i<11;i++)
{
printf("%d",f[i]);
}
for(i=N-2;i>=0;i--)
{
j=i-k;
if(j<0)
{
j=j+N-1;
}
Fq[j]=b[i];
}
printf("Inverse of polynomial in ascending order of exponent w.r.t 2\n");
for(j=0;j<11;j++)
{
printf("%d",Fq[j]);
}
printf("\n");
int v=2;
Q=32;
n=11;
while(v<Q)
{
v=v*2;
starmultiply(a,Fq,temp,11,v);
printf("\n");
for(i=0;i<11;i++)
{
temp[i]=posmodr((2-temp[i]),v);
}
starmultiply(Fq,temp,F,11,v);
printf("\n");
for(i=0;i<11;i++)
{
Fq[i]=F[i];
}
}
for(i=0;i<11;i++)
{
if(Fq[i]<0)
{
Fq[i]=Fq[i]+Q;
}
}
printf("Inverse of polynomial in ascending order of exponent\n");
for(j=0;j<11;j++)
{
printf("%d\n",Fq[j]);
}
getch();
}
int degree(int m[])
{
int i;
int N=12;
for(i=N-1;i>=0;i--)
{
if(m[i]==0)
{
continue;
}
else
return(i);
}
}
int euclid(int a,int b)
{
if(b==0)
return a;
else
return euclid(b,a%b);
}
int extendedEuclid(int a, int b)
{
if(a<0)
{
a=posmodr(a,b);
}
int quotient, remainder1, remainder2, remainderTemp;
//r-2 variables
int r1Muxa, r1Muxb;
//r-1 variables
int r2Muxa, r2Muxb;
//Temp Variables for Switch
int tempMuxa, tempMuxb;
int pass = 0;
//Verify that a and b are coprime
int proceed = euclid(a, b);
if(proceed == 0) printf("a and b are not coprime. Will return 0.\n.");
//Set Initial Values
quotient = a/b;
remainder1 = b;
remainder2 = a % b;
r1Muxa = 1;
r1Muxb = 0;
r2Muxa = 0;
r2Muxb = 1;
while(remainder2 != 0 && proceed)
{ tempMuxa = r1Muxa;
tempMuxb = r1Muxb;
pass++;
r1Muxa = r2Muxa;
r1Muxb = r2Muxb;
r2Muxa = r2Muxa*(-quotient) + tempMuxa;
r2Muxb = r2Muxb*(-quotient) + tempMuxb;
quotient = remainder1/remainder2;
remainderTemp = remainder2;
remainder2 = remainder1 % remainder2;
remainder1 = remainderTemp;
}
return r2Muxa;
}
int posmodr(int a, int b)
{
if(a>=0)
{
int r=(a%b);
return r;
}
else
{
if(abs(a)<=b)
{
int r=((b-abs(a)));
return r;
}
else
{
int x=abs(a);
int r=modr(a,b,x);
return r;
}
}
}
int modr(int a, int b,int x)
{
a=abs(a)+1;
if(a%b==0)
{
return (a-x);
}
else
{
return (modr(a,b,x));
}
}
int starmultiply(int a[],int b[],int c[],int n,int M)
{
int k,j=0,i=0,l=0;
//int c[12];
for(k=n-1;k>=0;k--)
{
c[k]=0;
j=k+1;
for(i=n-1;i>=0;i--)
{
if(j==n)
{
j=0;
}
if(a[i]!=0&&b[j]!=0)
{
c[k]=posmodr((c[k]+(a[i]*b[j])),M);
}
j=j+1;
}
}
for(i=0;i<n;i++)
{
// c[i]=c[i]-2;
printf("%d\t",c[i]);
}
}