プログラマ専用SNS ミクプラ

C言語でフェルマーの小定理を用いて正の整数の逆元を求めようとしたのですが、
なぜかもとの整数と掛けても1にならない数が出てくることがあります。

コード:

#include <stdio.h>
 
/* this is prime */
#define MOD_BY 100000007
 
int getInv(int x) {
    int nowzyou=MOD_BY-2;
    long long now=x;
    long long result=1;
    while(nowzyou>0) {
        if(nowzyou & 2)result=(result*now)%MOD_BY;
        now=(now*now)%MOD_BY;
        nowzyou>>=1;
        }
    return (int)result;
}
 
int main(void) {
    int i;
    for(i=1;i<100;i++) {
        printf("%10d %10d %10d\n",i,getInv(i),(int)(((long long)i*getInv(i))%MOD_BY));
    }
    return 0;
}

出力の最初がもとの整数、2番目が求めた逆元、3番目がもとの整数と逆元を掛けた結果です。
3番目が全て1になってほしいのですが、100000006が混ざってしまいます。

フェルマーの小定理についてはここを参考にしました。
http://www2.cc.niigata-u.ac.jp/~takeuch ... ermat.html

やっぱり整数の逆元を求めるには、拡張ユークリッドの互除法を用いなければならないのでしょうか？
よろしくお願いします。

まず、言及が無いですが逆元というのは p=MOD_BY の有限体Fp上で、演算は乗法を考えるということだと思うのでそれを仮定します。

今、xの逆元yが求まったとしたら x*y = 1 となるはずですが、今の場合は MOD_BY-1が求まっています。
ゆえに x*y = -1 となっているのでこれを適当に変形して x*(-y) = x*(MOD_BY - y) = 1 としてやれば求めたい逆元 (MOD_BY - y) が得られるのではないですか？

getInv函数が何をしているのかは知りませんが、要は1になるものを出しているか-1になるものを出しているかの区別がなされていないので、
後者の場合はMOD_BYで引いてあげればよいのでは、と思います。
(アルゴリズムの指摘では無いのでみけCATさんの期待する回答ではないかもしれません。すみません)

このようにしたら1～1000までの整数についてきちんと逆元が求まったようです。

コード:

#include <stdio.h>
#include <assert.h> 
 
/* this is prime */
#define MOD_BY 100000007
 
int getInv(int x) {
    int nowzyou=MOD_BY-2;
        long long now=x;
        long long result=1;
        while(nowzyou>0) {
                if(nowzyou & 2)result=(result*now)%MOD_BY;
                now=(now*now)%MOD_BY;
                nowzyou>>=1;
        }
        if((result*x)%MOD_BY!=1)result=MOD_BY-result;
        return (int)result;
}
 
int main(void) {
    int i;
    for(i=1;i<1000;i++) {
        printf("%10d %10d %10d\n",i,getInv(i),(int)(((long long)i*getInv(i))%MOD_BY));
        assert((int)(((long long)i*getInv(i))%MOD_BY)==1);
    }
    return 0;
}

しかし、参考サイトのフェルマーの小定理によると、必ずx^(p-1) （xのp-1乗）をpで割ったあまりは1になりそうなのに、
なぜMOD_BY-1が混ざるのでしょうか？

12行目で、

コード:

                if(nowzyou & 2)result=(result*now)%MOD_BY;

とされていますが"&2"ではなく"&1"ではないでしょうか？

「一番右端のビットが1の時はシフトして情報が落ちる前にnowをresultにかけておく」
という処理ならば1だと思います。
実際そうするとresultは(最初の方のコードで)全て1が出力されました。

myuon_myon さんが書きました:12行目で、
コード:
                if(nowzyou & 2)result=(result*now)%MOD_BY;
とされていますが"&2"ではなく"&1"ではないでしょうか？

「一番右端のビットが1の時はシフトして情報が落ちる前にnowをresultにかけておく」
という処理ならば1だと思います。
実際そうするとresultは(最初の方のコードで)全て1が出力されました。

あああああ…そうでした。
%2と混ざってしまったようです。
ありがとうございました。

コード:

#include <stdio.h>
#include <assert.h> 
 
/* this is prime */
#define MOD_BY 100000007
 
int getInv(int x) {
    int nowzyou=MOD_BY-2;
	long long now=x;
	long long result=1;
	while(nowzyou>0) {
		if(nowzyou & 1)result=(result*now)%MOD_BY;
		now=(now*now)%MOD_BY;
		nowzyou>>=1;
	}
	return (int)result;
}

int main(void) {
    int i;
    for(i=1;i<1000000;i++) {
        if(i<=1000)printf("%10d %10d %10d\n",i,getInv(i),(int)(((long long)i*getInv(i))%MOD_BY));
        assert((int)(((long long)i*getInv(i))%MOD_BY)==1);
    }
    puts("OK");
    return 0;
}

プログラマ専用SNS ミクプラ

フェルマーの小定理

フェルマーの小定理

Re: フェルマーの小定理

Re: フェルマーの小定理

Re: フェルマーの小定理

Re: フェルマーの小定理