• 締切済み

多倍長整数同士の剰余

たとえば 321789^473289473982 % 74382478392 のような計算を計算機上で高速に行うには どのような処理をすればよいでしょうか？

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

一般論としては x^2 % n 及び xy % n を計算する関数を繰り返し適用する. 今の例の場合は (手元の電卓によると) 74382478392 = 2^3×3×29×106871377 らしいので指数を小さくしておくと楽. 「繰り返し2乗法」なんて調べておくと吉かも.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

注目のQ&A

カテゴリ

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

専門家に質問してみよう

職業から探して質問する
質問する