位数を求めるプログラム

質問

a^e≡1(mod n)を満たす最小の正の整数eを
法nに関するaの位数です。
これを法３１における１、２,...、３０の位数を求めるプログラムを以下のように作ったのですが
位数は３１が素数なので３０の約数であるはずなのですが１１とか１２などが出てきてしまいます。
問題のある箇所を教えてください。

#include <stdio.h>

int main(void)
{
int h,i,j,k,n;

//法３１
n=31;
//1の位数は１
printf("1:1\n");

for(j=2;j<n;j++){
k=1;
for(i=1;i<=(n-1)/2;i++){
//j^iを求める。
k=j*k;
for(h=2;h*n<k;h++);
//余りが１になるものを位数とする。
if(!((k-1)%((h-1)*n))){
printf("%d:%d\n",j,i);
break;
}
}
//i<=（n-1）/2までに余りが1あまるものがなければn-1（３０）を位数とする。
if(i>(n-1)/2)printf("%d:%d\n",j,n-1);
}

return 0;
}

回答No.1

Tacosan · ベストアンサー

k の値がどうなっているか調べてみましたか?

合同式の性質をうまく使って, 途中に現れる数値が
大きくなりすぎないようにしましょう.

お礼

アドバイス有難うございます。

ｋの値がたまに－になったりしてました。
数が大きくなりすぎているようですね。

余りを使ってやってみます。

補足

出来ました。有難うございました。
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int h,i,j,k,n;
int *ptr;
char ch[5];

while(1){
for(i=0;i<1;i++){
printf("1:法ｎそれぞれの位数を求める\n");
printf("2:終了する。\n");
if(!(n=atoi(gets(ch)))||n<1||n>2){
printf("入力にに誤りがあります\n");
i--;
}
}
if(n==2)break;

for(i=0;i<1;i++){
printf("法：");
if(!(n=atoi(gets(ch)))||n<1||n>100){
printf("入力に誤りがあります。\n");
i--;
}
}
ptr=(int *)malloc(n*sizeof(int));
printf("法%2d\n",n);

//1の位数は１
printf(" 1:1\n");

for(j=2;j<n;j++){
k=1;
for(i=1;i<=(n-1)/2;i++){
//j^iを求める。
k=j*k;
for(h=2;h*n<k;h++);
//余りが１になるものを位数とする。
k=k%((h-1)*n);
if(k==1){
printf("%2d:%2d\t\n",j,i);
ptr[j-2]=i;
break;
}
}
//i<=（n-1）/2までに余りが1あまるものがなければn-1を位数とする。
if(i>(n-1)/2){
printf("%2d:%2d\n",j,n-1);
ptr[j-2]=n-1;
}
}

printf("原始根：");
for(i=0;ptr[i];i++)
if(ptr[i]==n-1)printf("[%d] ",i+2);
free(ptr);
printf("\n");

}
return 0;
}