モジュラス剰余で除算を行うにはどうすればよいですか?
例: 9^2012 を 11 で割った余りを求めます。
剰余演算を使用すると、9 == 1(mod 4) となるため、9^2012 == 1^2012(mod 4) となります。したがって、9^2012 == 1(mod 4) です。また、11 == 3(mod 4) です。質問に答えるために、私は 1(mod 4)/3(mod 4) をしようとしています。これを行う方法はありますか?
モジュラス剰余で除算を行うにはどうすればよいですか?
例: 9^2012 を 11 で割った余りを求めます。
剰余演算を使用すると、9 == 1(mod 4) となるため、9^2012 == 1^2012(mod 4) となります。したがって、9^2012 == 1(mod 4) です。また、11 == 3(mod 4) です。質問に答えるために、私は 1(mod 4)/3(mod 4) をしようとしています。これを行う方法はありますか?
この問題を解決するのに役立つ2つの重要な理論があります:-
剰余累乗 :- この単純な再帰式を理解してもらう:-
(a^n)%p = ((a^(n-1))%p*a)%p
上記の式は、a^n が大きい場合に発生するオーバーフローを防ぐのに役立ちます。さらに、O(logn)を使用して高速指数を実行できます
フェルマーの小定理 :- p が素数の場合、11 が素数である場合、p に互いに素(a^(p-1))%p = 1
な任意の a について(a^n)%p = (a^(n%(p-1)))%p
あなたの例:-
9^2012 % 11 = ?
11 is prime and 9 is co-prime to 11 then using fermat's theorem
9^2012 % 11 = (9^(2012%10)) % 11
2012%10 = 2
9^2012 % 11 = 9^2 % 11 = 4