Petitverse

コミュニティアイコン プチコン 非公式コミュニティ トピック

アバター
こういち ◆ou0jbJnEJ0Kb
2023/11/29 21:26
情報交換
続:A*B MOD Pの計算方法(モンゴメリ乗算)
タイトルの通り
Pを2×5進法で10桁程度の素数として
A*B MOD Pを計算する方法について考えるトピックです。

以前はGarnerのアルゴリズムを使った方法を検討しましたが、どうもより高速なモンゴメリ乗算と呼ばれる方法があるらしいので、それを使うことにします。

ちなみに、一体何故突然A*B MOD Pを求めようと思ったのかは謎です。(特に必要になったとかではない)
通報

コメント

アバター
こういち 2023/11/29 21:28 ◆ou0jbJnEJ0Kb
探したら過去の自分がモンゴメリ乗算についての資料を作ってたので、とりあえずこれを載せときます。(作りかけだった記憶ある)
アバター
こういち 2023/11/29 21:34 ◆ou0jbJnEJ0Kb
確か記憶が正しければ、モンゴメリ乗算とGarnerのアルゴリズムって本質的には同じだった気がするんですよね。
アバター
こういち 2023/11/29 21:35 ◆ou0jbJnEJ0Kb
やっぱり中途半端ですね。
ここから先は考える必要があるんですけど、睡魔が限界なのでまた後日。

コメントを書く

  • こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
  • プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
  • こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
  • ユーザー登録なしで書き込みができます
  • 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
  • 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
  • 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります

- WEB PATIO -