
エントリーの編集

エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Tonelli-Shanks アルゴリズムの理解と実装(2) - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています

- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Tonelli-Shanks アルゴリズムの理解と実装(2) - Qiita
はじめに 前回の記事はこちらです。 実装 まず、今回仮定する条件をもう一度しておきます。 Input: $p$ ... はじめに 前回の記事はこちらです。 実装 まず、今回仮定する条件をもう一度しておきます。 Input: $p$ : 奇素数 $n$ : 整数, ただし$n$は$p$の倍数ではない Output: $x$ : $x^2 \equiv n\ {\rm mod}\ p$, かつ $0 < x < n$を満たす1 $n$が$p$の倍数なら、$n \equiv 0\ {\rm mod}\ p$で剰余とは言いづらいので今回は除外します(例外としてコード中に組み込みます)。 Legendre記号 $$\left(\begin{array} nn\ p \end{array}\right) := n^{\frac{p-1}{2}} \equiv \begin{cases} 1\ {\rm mod}\ p\Leftrightarrow n は平方剰余\ -1\ {\rm mod}\ p \Leftright