ヤコビ記号のソースを表示
←
ヤコビ記号
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、次のグループに属する利用者のみが実行できます:
登録利用者
。
このページのソースの閲覧やコピーができます。
<div class="thumb tright"> <div class="thumbinner" style="width:500px;"> {| class="wikitable" style="width:500px; text-align:right" ! 縦 n 横 k !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 |- ! 1 |style="background:#fafa6a"| 1 || || || || || || || || || || || || || || || || |- ! 3 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 || || || || || || || || || || || || || || |- ! 5 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 || −1 ||style="background:#fafa6a"| 1 || || || || || || || || || || || || |- ! 7 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 || −1 || −1 || || || || || || || || || || |- ! 9 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 1 || || || || || || || || |- ! 11 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 || −1 || || || || || || |- ! 13 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 || || || || |- ! 15 |style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 0 ||style="background:#fafa6a"| 0 || −1 || 1 ||style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 0 || −1 || 0 || −1|| −1|| || |- ! 17 |style="background:#fafa6a"| {{0|−}}0 ||style="background:#fafa6a"| {{0|−}}1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| {{0|−}}1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| {{0|−}}1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 |} <div class="thumbcaption"> さまざまなk（列）とn（行）でのヤコビ記号 {{big|(}}{{sfrac|''k''|''n''}}{{big|)}} 。後述する規則(2)によりkはnを法として小さくすることができるため、{{nowrap|0 ≤ ''k'' < ''n''}} の場合のみ示す。[[平方剰余]]は黄色で強調される。-1のヤコビ記号となる数は平方剰余ではなく、''k'' が互いに素なnを法とする平方剰余である場合、 {{nowrap|1={{big|(}}{{sfrac|''k''|''n''}}{{big|)}} = 1}}となる。しかし、ヤコビ記号が1となる数（{{nowrap|1=''n'' = 9}} と {{nowrap|1=''n'' = 15}} の列参照）は全てが平方剰余ではないことに注意。また、''n'' または ''k'' のいずれかが平方数である場合、すべての値が非負となることに注意。 </div> </div> </div> '''ヤコビ記号'''は、[[ルジャンドル記号]]の一般化である。[[カール・グスタフ・ヤコブ・ヤコビ|ヤコビ]]により1837年に導入された<ref>{{cite journal|first=C. G. J.|last=Jacobi|title=Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie|journal=Bericht Ak. Wiss. Berlin|date=1837|page=127–136}}</ref>。[[合同算術]]や[[数論]]の他の分野で理論的に興味深いものであるが、主な用途は[[計算数論]]、特に[[素数判定]]及び[[素因数分解]]である。これらは[[暗号理論]]においても重要である。 ==定義== 任意の整数 ''a'' と任意の正の奇整数 ''n'' に対して、ヤコビ記号 {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} は ''n'' の素因数に対応する[[ルジャンドル記号]]の積として定義される。 :<math>\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k},</math> ここで :<math>n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math> は''n''の素因数分解である。 ルジャンドル記号 {{big|(}}{{sfrac|''a''|''p''}}{{big|)}} は全ての整数 ''a'' と全ての奇素数 ''p'' に対して次のように定義される。 :<math>\left(\frac{a}{p}\right) = \left\{ \begin{array}{rl} 0 & \text{if } a \equiv 0 \pmod{p},\\ 1 & \text{if } a \not\equiv 0\pmod{p} \text{ and for some integer } x\colon\;a\equiv x^2\pmod{p},\\ -1 & \text{if } a \not\equiv 0\pmod{p} \text{ and there is no such } x. \end{array} \right.</math> 空積での通常の慣例に従い、{{big|(}}{{sfrac|''a''|1}}{{big|)}} = 1とする。 下の引数が奇素数である場合、ヤコビ記号はルジャンドル記号と同じである。 ==表== ''n'' ≤ 59, ''k'' ≤ 30で ''n'' が奇数のときのヤコビ記号 {{big|(}}{{sfrac|''k''|''n''}}{{big|)}} の値の表 {|class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align: right" !縦 n 横 k !1 !2 !3 !4 !5 !6 !7 !8 !9 !10 !11 !12 !13 !14 !15 !16 !17 !18 !19 !20 !21 !22 !23 !24 !25 !26 !27 !28 !29 !30 |- !1 |{{0|−}}1 |1 |1 |{{0|−}}1 |1 |1 |1 |1 |{{0|−}}1 |1 |1 |1 |1 |1 |1 |{{0|−}}1 |1 |1 |1 |1 |1 |1 |1 |1 |{{0|−}}1 |1 |1 |1 |1 |1 |- !3 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |- !5 |1 |−1 |−1 |1 |0 |1 |−1 |−1 |1 |0 |1 |−1 |−1 |1 |0 |1 |−1 |−1 |1 |0 |1 |−1 |−1 |1 |0 |1 |−1 |−1 |1 |0 |- !7 |1 |1 |−1 |1 |−1 |−1 |0 |1 |1 |−1 |1 |−1 |−1 |0 |1 |1 |−1 |1 |−1 |−1 |0 |1 |1 |−1 |1 |−1 |−1 |0 |1 |1 |- !9 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |1 |1 |0 |- !11 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |1 |−1 |0 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |1 |−1 |0 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |- !13 |1 |−1 |1 |1 |−1 |−1 |−1 |−1 |1 |1 |−1 |1 |0 |1 |−1 |1 |1 |−1 |−1 |−1 |−1 |1 |1 |−1 |1 |0 |1 |−1 |1 |1 |- !15 |1 |1 |0 |1 |0 |0 |−1 |1 |0 |0 |−1 |0 |−1 |−1 |0 |1 |1 |0 |1 |0 |0 |−1 |1 |0 |0 |−1 |0 |−1 |−1 |0 |- !17 |1 |1 |−1 |1 |−1 |−1 |−1 |1 |1 |−1 |−1 |−1 |1 |−1 |1 |1 |0 |1 |1 |−1 |1 |−1 |−1 |−1 |1 |1 |−1 |−1 |−1 |1 |- !19 |1 |−1 |−1 |1 |1 |1 |1 |−1 |1 |−1 |1 |−1 |−1 |−1 |−1 |1 |1 |−1 |0 |1 |−1 |−1 |1 |1 |1 |1 |−1 |1 |−1 |1 |- !21 |1 |−1 |0 |1 |1 |0 |0 |−1 |0 |−1 |−1 |0 |−1 |0 |0 |1 |1 |0 |−1 |1 |0 |1 |−1 |0 |1 |1 |0 |0 |−1 |0 |- !23 |1 |1 |1 |1 |−1 |1 |−1 |1 |1 |−1 |−1 |1 |1 |−1 |−1 |1 |−1 |1 |−1 |−1 |−1 |−1 |0 |1 |1 |1 |1 |−1 |1 |−1 |- !25 |1 |1 |1 |1 |0 |1 |1 |1 |1 |0 |1 |1 |1 |1 |0 |1 |1 |1 |1 |0 |1 |1 |1 |1 |0 |1 |1 |1 |1 |0 |- !27 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |1 |−1 |0 |- !29 |1 |−1 |−1 |1 |1 |1 |1 |−1 |1 |−1 |−1 |−1 |1 |−1 |−1 |1 |−1 |−1 |−1 |1 |−1 |1 |1 |1 |1 |−1 |−1 |1 |0 |1 |- !31 |1 |1 |−1 |1 |1 |−1 |1 |1 |1 |1 |−1 |−1 |−1 |1 |−1 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |−1 |1 |−1 |−1 |1 |−1 |−1 |- !33 |1 |1 |0 |1 |−1 |0 |−1 |1 |0 |−1 |0 |0 |−1 |−1 |0 |1 |1 |0 |−1 |−1 |0 |0 |−1 |0 |1 |−1 |0 |−1 |1 |0 |- !35 |1 |−1 |1 |1 |0 |−1 |0 |−1 |1 |0 |1 |1 |1 |0 |0 |1 |1 |−1 |−1 |0 |0 |−1 |−1 |−1 |0 |−1 |1 |0 |1 |0 |- !37 |1 |−1 |1 |1 |−1 |−1 |1 |−1 |1 |1 |1 |1 |−1 |−1 |−1 |1 |−1 |−1 |−1 |−1 |1 |−1 |−1 |−1 |1 |1 |1 |1 |−1 |1 |- !39 |1 |1 |0 |1 |1 |0 |−1 |1 |0 |1 |1 |0 |0 |−1 |0 |1 |−1 |0 |−1 |1 |0 |1 |−1 |0 |1 |0 |0 |−1 |−1 |0 |- !41 |1 |1 |−1 |1 |1 |−1 |−1 |1 |1 |1 |−1 |−1 |−1 |−1 |−1 |1 |−1 |1 |−1 |1 |1 |−1 |1 |−1 |1 |−1 |−1 |−1 |−1 |−1 |- !43 |1 |−1 |−1 |1 |−1 |1 |−1 |−1 |1 |1 |1 |−1 |1 |1 |1 |1 |1 |−1 |−1 |−1 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |−1 |−1 |- !45 |1 |−1 |0 |1 |0 |0 |−1 |−1 |0 |0 |1 |0 |−1 |1 |0 |1 |−1 |0 |1 |0 |0 |−1 |−1 |0 |0 |1 |0 |−1 |1 |0 |- !47 |1 |1 |1 |1 |−1 |1 |1 |1 |1 |−1 |−1 |1 |−1 |1 |−1 |1 |1 |1 |−1 |−1 |1 |−1 |−1 |1 |1 |−1 |1 |1 |−1 |−1 |- !49 |1 |1 |1 |1 |1 |1 |0 |1 |1 |1 |1 |1 |1 |0 |1 |1 |1 |1 |1 |1 |0 |1 |1 |1 |1 |1 |1 |0 |1 |1 |- !51 |1 |−1 |0 |1 |1 |0 |−1 |−1 |0 |−1 |1 |0 |1 |1 |0 |1 |0 |0 |1 |1 |0 |−1 |1 |0 |1 |−1 |0 |−1 |1 |0 |- !53 |1 |−1 |−1 |1 |−1 |1 |1 |−1 |1 |1 |1 |−1 |1 |−1 |1 |1 |1 |−1 |−1 |−1 |−1 |−1 |−1 |1 |1 |−1 |−1 |1 |1 |−1 |- !55 |1 |1 |−1 |1 |0 |−1 |1 |1 |1 |0 |0 |−1 |1 |1 |0 |1 |1 |1 |−1 |0 |−1 |0 |−1 |−1 |0 |1 |−1 |1 |−1 |0 |- !57 |1 |1 |0 |1 |−1 |0 |1 |1 |0 |−1 |−1 |0 |−1 |1 |0 |1 |−1 |0 |0 |−1 |0 |−1 |−1 |0 |1 |−1 |0 |1 |1 |0 |- !59 |1 |−1 |1 |1 |1 |−1 |1 |−1 |1 |−1 |−1 |1 |−1 |−1 |1 |1 |1 |−1 |1 |1 |1 |1 |−1 |−1 |1 |1 |1 |1 |1 |−1 |} ==性質== 以下の事実は、ヤコビ記号の定義とルジャンドル記号の対応する性質からの直接的推論である<ref>Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10</ref>。 ヤコビ記号は上の引数（「分子」）が整数で下の引数（「分母」）が正の奇整数である場合にのみ定義される。 :1. ''n'' が（奇数の）素数の場合、ヤコビ記号 {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} は対応するルジャンドル記号と等しい（そして同じように書かれる）。 :2. {{nowrap|''a'' ≡ ''b'' (mod ''n'')}}のとき、<math>\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right) = \left(\frac{a \pm m \cdot n}{n}\right)</math> :3. <math>\left(\frac{a}{n}\right) = \begin{cases} 0 & \text{if } \gcd(a,n) \ne 1,\\ \pm1 & \text{if } \gcd(a,n) = 1. \end{cases} </math> 上または下の引数のいずれかが固定の場合、ヤコビ記号はもう一方の引数において完全乗法的関数になる。 {{explain|date=December 2020}} :4. <math>\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right),\quad\text{so } \left(\frac{a^2}{n}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ or } 0.</math> :5. <math>\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right),\quad\text{so } \left(\frac{a}{n^2}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ or } 0.</math> [[平方剰余の相互法則|平方剰余の法則]]: ''m'' と ''n'' が奇数で互いに素な正整数である場合、 :6. <math>\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\tfrac{n-1}{2}} = \begin{cases} 1 & \text{if } n \equiv 1 \pmod 4 \text{ or } m \equiv 1 \pmod 4,\\ -1 & \text{if } n\equiv m \equiv 3 \pmod 4 \end{cases} </math> であり、補足として :7. <math>\left(\frac{-1}{n}\right) = (-1)^\tfrac{n-1}{2} = \begin{cases} 1 & \text{if }n \equiv 1 \pmod 4,\\ -1 & \text{if }n \equiv 3 \pmod 4, \end{cases} </math> :8. <math>\left(\frac{2}{n}\right) = (-1)^\tfrac{n^2-1}{8} = \begin{cases} 1 & \text{if }n \equiv 1,7 \pmod 8,\\ -1 & \text{if }n \equiv 3,5\pmod 8. \end{cases} </math> 性質4と8を組み合わせると :9. <math> \left(\frac{2a}{n}\right) = \left(\frac{2}{n}\right) \left(\frac{a}{n}\right) = \begin{cases} \left(\frac{a}{n}\right) & \text{if }n \equiv 1,7 \pmod 8,\\ - \left(\frac{a}{n}\right) & \text{if }n \equiv 3,5\pmod 8. \end{cases} </math> となる。ルジャンドル記号と同様に、 *{{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = −1 の場合、''a'' は''n''を法として平方非剰余である。 *''a'' が''n''を法として[[平方剰余]]であり、[[最大公約数|gcd]](''a'',''n'') = 1 の場合、{{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = 1である。 但し、ルジャンドル記号と異なり、 :{{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = 1 である場合、''a'' は ''n'' を法として平方剰余であるかもしれないし、ないかもしれない。 これは、''a'' が ''n'' を法とする平方剰余であるためには、''n'' の全ての素因数を法とする平方剰余でなければならないためである。ただし、例えば ''a'' が ''n'' の素因数のちょうど2つを法とする非剰余である場合、ヤコビ記号は1に等しくなる。 ヤコビ記号は、平方と非平方の観点から一律に解釈することはできないが、ゾロタレフの補題([[:en:Zolotarev's lemma]])による順列の符号として一律に解釈することはできる。 ヤコビ記号{{big|(}}{{sfrac|''a''|''n''}}{{big|)}}は、法''n''に対する[[ディリクレ指標]]である。 ==ヤコビ記号の計算== 上記の式は、2つの数のgcdを見つけるために[[ユークリッドの互除法]]に似た、ヤコビ記号を計算するための効率的な{{nowrap|[[Big O notation|''O'']](log ''a'' log ''b'')}}<ref>Cohen, pp. 29–31</ref> につながる（これは規則2に照らすと驚くべきことはない）。 # 規則2を使用して「分母」を法として「分子」を減らす。 # 規則9を使用して、偶数の「分子」を抽出する。 # 「分子」が1の場合、規則3と4の結果は1になる。「分子」と「分母」が互いに素でない場合、規則3の結果は0になる。 # それ以外の場合、「分子」と「分母」は互いに素な奇数の正整数であるため、規則6を使用して記号を反転し、手順1に戻ることができる。 ===[[Lua]]での実装=== <syntaxhighlight lang="lua"> function jacobi(n, k) assert(k > 0 and k % 2 == 1) n = n % k t = 1 while n ~= 0 do while n % 2 == 0 do n = n / 2 r = k % 8 if r == 3 or r == 5 then t = -t end end n, k = k, n if n % 4 == 3 and k % 4 == 3 then t = -t end n = n % k end if k == 1 then return t else return 0 end end </syntaxhighlight> ==計算例== ルジャンドル記号{{big|(}}{{sfrac|''a''|''p''}}{{big|)}}は奇素数 ''p'' に対してのみ定義され、ヤコビ記号と同じ規則に従う（つまり、{{big|(}}{{sfrac|−1|''p''}}{{big|)}} と {{big|(}}{{sfrac|2|''p''}}{{big|)}} の相互作用と補足式、および「分子」の乗法性） 問題: 素数9907が与えられたとする。{{big|(}}{{sfrac|1001|9907}}{{big|)}}を計算せよ。 ===ルジャンドル記号を使用する=== :<math>\begin{align} \left(\frac{1001}{9907}\right) &=\left(\frac{7}{9907}\right) \left(\frac{11}{9907}\right) \left(\frac{13}{9907}\right). \\ \left(\frac{7}{9907}\right) &=-\left(\frac{9907}{7}\right) =-\left(\frac{2}{7}\right) =-1. \\ \left(\frac{11}{9907}\right) &=-\left(\frac{9907}{11}\right) =-\left(\frac{7}{11}\right) =\left(\frac{11}{7}\right) =\left(\frac{4}{7}\right) =1. \\ \left(\frac{13}{9907}\right) &=\left(\frac{9907}{13}\right) =\left(\frac{1}{13}\right) =1. \\ \left(\frac{1001}{9907}\right) &=-1. \end{align}</math> ===ヤコビ記号を使用する=== :<math>\begin{align} \left(\frac{1001}{9907}\right) &=\left(\frac{9907}{1001}\right) =\left(\frac{898}{1001}\right) =\left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right) =\left(\frac{449}{1001}\right) \\ &=\left(\frac{1001}{449}\right) =\left(\frac{103}{449}\right) =\left(\frac{449}{103}\right) =\left(\frac{37}{103}\right) =\left(\frac{103}{37}\right) \\ &=\left(\frac{29}{37}\right) =\left(\frac{37}{29}\right) =\left(\frac{8}{29}\right) =\left(\frac{2}{29}\right)^3 =-1. \end{align}</math> 2つの計算の違いは、ルジャンドル記号を使用する場合、記号を反転する前に「分子」を素数冪に因数分解する必要があることである。これにより、整数を因数分解するための既知の多項式時間アルゴリズムがないため、ルジャンドル記号を使用した計算はヤコビ記号を使用した計算よりも大幅に遅くなる<ref>The [[number field sieve]], the fastest known algorithm, requires :<math>O\left(e^{(\ln N)^\frac13(\ln\ln N)^\frac23\big(C+o(1)\big)}\right)</math> operations to factor ''n''. See Cohen, p. 495</ref>。実際、これがヤコビがこの記号を導入した理由である。 ==素数性判定== ヤコビ記号とルジャンドル記号が異なる別の方法がある。[[オイラーの規準]]の式が合成数を法として使用される場合、結果はヤコビ記号の値である場合とそうでない場合があり、実際には−1または1でさえないこともある。 :<math>\begin{align} \left(\frac{19}{45}\right) &= 1 &&\text{ and } & 19^\frac{45-1}{2} &\equiv 1\pmod{45}. \\ \left(\frac{ 8}{21}\right) &= -1 &&\text{ but } & 8^\frac{21-1}{2} &\equiv 1\pmod{21}. \\ \left(\frac{ 5}{21}\right) &= 1 &&\text{ but } & 5^\frac{21-1}{2} &\equiv 16\pmod{21}. \end{align}</math> そのため、数nが素数であるか合成数であるかが不明である場合は、乱数aを選択し、ヤコビ記号{{big|(}}{{sfrac|''a''|''n''}}{{big|)}}を計算し、オイラーの式と比較する。それらがnを法として異なる場合、nは合成数である。それらがaの多くの異なる値に対してnを法とする同じ剰余を持つ場合、nは「おそらく素数」（擬素数）である。 これは確率論的な[[ソロベイ–シュトラッセン素数判定法]]と、[[:en:Baillie–PSW primality test|Baillie-PSW primality test]]や[[ミラー–ラビン素数判定法]]などの改良の基礎である。 間接的な使用として、[[リュカ–レーマー・テストの証明|リュカ–レーマー素数判定]]の実行中のエラー検出ルーチンとして使用することができる。これは現代のコンピュータハードウェアにおいても<math>\begin{align}2^{82,589,933} - 1\end{align}</math> （既知の最大のメルセンヌ素数）を処理を完了するのに数週間かかる場合がある。In nominal cases, the Jacobi symbol: <math>\begin{align}\left(\frac{s_i - 2}{M_p}\right) &= -1 & i \ne 0\end{align}</math> これは最終的な剰余 <math>\begin{align}s_{p-2}\end{align}</math> にも当てはまるため、妥当性の検証として使用できる。ただしハードウェアでエラーが生じた場合、結果が0または1になる可能性が50%あり、これは <math>\begin{align}s\end{align}</math> の後続の項で変化しない（別のエラーが生じて-1に戻らない限り）。 ==関連項目== *{{仮リンク|クロネッカー記号|en|Kronecker symbol}} 全ての整数に対するヤコビ記号の一般化 *[[:en:Power residue symbol]] より高次の剰余に対するヤコビ記号の一般化 ==出典== {{reflist}} ==レファレンス== *{{cite book | last1 = Cohen | first1 = Henri | title = A Course in Computational Algebraic Number Theory | publisher = [[Springer Science+Business Media|Springer]] | location = Berlin | date = 1993 | isbn = 3-540-55640-0}} *{{cite book | last1 = Ireland | first1 = Kenneth | last2 = Rosen | first2 = Michael | title = A Classical Introduction to Modern Number Theory (Second edition) | publisher = [[Springer Science+Business Media|Springer]] | location = New York | date = 1990 | isbn = 0-387-97329-X}} *{{cite book | last1 = Lemmermeyer | first1 = Franz | title = Reciprocity Laws: from Euler to Eisenstein | publisher = [[Springer Science+Business Media|Springer]] | location = Berlin | date = 2000 | isbn = 3-540-66957-4}} *{{cite journal | title = On the Worst Case of Three Algorithms for Computing the Jacobi Symbol | first = Jeffrey | last = Shallit | authorlink = Jeffrey Shallit | journal = Journal of Symbolic Computation | date = December 1990 | volume = 10 | issue = 6 | pages = 593-61 | url = https://digitalcommons.dartmouth.edu/cs_tr/42/ | doi = 10.1016/S0747-7171(08)80160-5 | id = Computer science technical report PCS-TR89-140 }} *{{cite techreport | title = Average-case analyses of three algorithms for computing the Jacobi symbol | first1 = Brigitte | last1 = Vallée | authorlink1=Brigitte Vallée | first2 = Charly | last2 = Lemée | date = October 1998 | citeseerx = 10.1.1.32.3425 | url = https://vallee.users.greyc.fr/Publications/jacobi.ps }} * {{cite journal | title = Efficient Algorithms for Computing the Jacobi Symbol | first1 = Shawna Meyer | last1 = Eikenberry | first2 = Jonathan P. | last2 = Sorenson | journal = Journal of Symbolic Computation | volume = 26 | issue = 4 | pages = 509-523 | date = October 1998 | doi = 10.1006/jsco.1998.0226 | citeseerx = 10.1.1.44.2423 | url = https://doi.org/10.1006/jsco.1998.0226 }} == 外部リンク == * [http://math.fau.edu/richman/jacobi.htm Calculate Jacobi symbol] shows the steps of the calculation. {{DEFAULTSORT:やこひきこう}} [[Category:合同算術]] [[Category:数学に関する記事]]
このページで使用されているテンプレート:
テンプレート:0
(
ソースを閲覧
)
テンプレート:Big
(
ソースを閲覧
)
テンプレート:Cite book
(
ソースを閲覧
)
テンプレート:Cite journal
(
ソースを閲覧
)
テンプレート:Cite techreport
(
ソースを閲覧
)
テンプレート:Explain
(
ソースを閲覧
)
テンプレート:Nowrap
(
ソースを閲覧
)
テンプレート:Reflist
(
ソースを閲覧
)
テンプレート:Sfrac
(
ソースを閲覧
)
テンプレート:仮リンク
(
ソースを閲覧
)
ヤコビ記号
に戻る。
ナビゲーション メニュー
個人用ツール
ログイン
名前空間
ページ
議論
日本語
表示
閲覧
ソースを閲覧
履歴表示
その他
検索
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
ツール
リンク元
関連ページの更新状況
ページ情報