algorithm - 素数を使用した非常に大きな数の剰余

Question

素数を使用して非常に大きな数の残りを見つける必要があるという問題に悩まされています。実際の問題は、その数がかなり大きく、約10^100. したがって、変数に格納することはできず、唯一のオプションは配列に格納することです。

次に、素数 を使用して、この数の残りを見つける必要があります(10^9)+7。

アイデアが思い浮かびません、何か提案はありますか？

PS: プログラミング言語は C++ です。

Answer 1

10進数（1234など）は、次の方法でその数字から作成できます。

x=1;
x=x*10+2;
x=x*10+3;
x=x*10+4;//x=1234

（最上位桁から始めて、毎回次の桁を取ります）。

加算と乗算により、モジュラス演算をそれらに移動できるため、すべてのステップでモジュラス（7など）を適用するだけで済みます。

x=1;
x=(x*10+2)%7;
x=(x*10+3)%7;
x=(x*10+4)%7;//x=1234%7

プライムが約10^9の場合、32ビット整数では不十分ですが、64ビットで十分です。

Answer 2

一般的に、私はその事実を利用します

a^n mod b == (a mod b)^n mod b

したがって、この例では、次のように計算できます。

= 10^100 mod 10^9 + 7 = (10^10 mod 10^9 + 7)^10  mod 10^9 + 7

= (999999937) ^ 10 mod 10^9 + 7
= ((999999937) ^ 2 mod 10^9 + 7) ^ 5 mod 10^9 + 7
= 4900 ^ 5 mod 10^9 +7
= 226732710

等

Answer 3

何のプログラミング言語？C/C++、Java、PHP、Perl、JavaScript... はすべて、null で終わる文字列の最大長までの整数を持つことができる Big Integer の形式を持っています。実際の構文は言語によって異なりますが、次のようになります。

$num = new BigInt("1234567891234567912346579865432165498765462132165498765431");
$prime = new BigInt("54657613216846346874321638743");
$mod = $num.mod($prime);