問題タブ [modular-arithmetic]

x^y mod z の計算方法を知りたいです。x と y は非常に大きく (64 ビット整数に収まりません)、z は 64 ビット整数に収まります。x^y mod z は (x mod z)^y mod z と同じです。

そんなこと知ってる、

しかし、オーバーフローの可能性があります。簡単にするために、整数のサイズが 2 ビットであると仮定します。a = 2 (つまり 10 ₂ ) かつ b = 2 (つまり 10 ₂ )、m = 3 (つまり 11 ₂ ) の場合、a%m と b%m は 2 になり、乗算後の答えは 4 (つまり100) は整数サイズに収まりません。2-lsb を 4 から考えると、最終的な答えは 0 になります。しかし、実際の答えは 1 です。

この状況を回避するにはどうすればよいですか?

これはPythonによって行われます

累乗演算のコレクションの合計をタプルのリストとして表すとします。各タプルには、基数と指数の 2 つの整数が含まれます。たとえば、リストは2 ⁴ + 3 ⁵ + (−6) ³[(2,4),(3,5),(-6,3)]のべき乗の合計を表します。

sumOfPowers(nes, ps)1 つ以上のタプルのリストnes(つまりnesの形式[(a1,n1),...,(ak,nk)]) を最初の引数として取り、1 つ以上の素数のリストps(つまり の形式[p1,...,pm]) を 2 番目の引数として取る関数を実装します。この関数は、次の条件が満たされている限り、べき乗の合計の正しい結果を返す必要があります (たとえば、メモリと時間が無制限のコンピューターの場合)。

0 ≤ a1 ⁿ¹ + ... + ak ^nk < p1 ⋅ ... ⋅ pm

2 番目のリストには別個の素数が含まれていると想定できます。最初の入力リストの数値に特定のパターンや関係があるとは思わないかもしれません。それらは任意の順序、任意のサイズにすることができ、因子を共有する場合と共有しない場合があります。実装は、非常に大きな入力に対して効率的に機能する必要があります

^1111..n mod Mの値を効率的に求める方法はありますか? 10 ⁰ mod M + 10 ¹ mod M + 10 ² mod M + 10 ³ mod M + ...10 ⁿ mod M
を見つけるために、繰り返し 2 乗をいつでも使用できます 。これよりも高速な方法はありますか?

私の短いスポーツプログラミングのキャリアの中で、私は何度も遭遇しました

私はいくつかの調査を行いましたが、フォームの数値のmodの計算しか見つけることができませんでした

最初の例のような数値の mod を計算する方法を誰か説明できますか?