[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

# 29. Number Theory

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

## 29.1 Functions and Variables for Number Theory

関数: bern (n)

  整数 nについて n番目の Bernoulli数を返します。 もし `zerobern`が `false`ならゼロに等しい Bernoulli数は抑制されます。

  `burn`も参照してください。

      (%i1) zerobern: true$
      (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
                            1  1       1      1        1
      (%o2)           [1, - -, -, 0, - --, 0, --, 0, - --]
                            2  6       30     42       30
      (%i3) zerobern: false$
      (%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
                            1  1    1   1     1   5     691   7
      (%o4)           [1, - -, -, - --, --, - --, --, - ----, -]
                            2  6    30  42    30  66    2730  6

  Categories: Number theory

関数: bernpoly (x, n)

  変数 xに関する n番目の Bernoulli多項式を返します。

  Categories: Number theory

関数: bfzeta (s, n)

  引数 sに関する Riemannのゼータ関数を返します。 戻り値は多倍長浮動小数点です; nは戻り値の小数点以下の桁数です。

  Categories: Number theory · Numerical evaluation

関数: bfhzeta (s, h, n)

  引数 sと hに関する Hurwitzのゼータ関数を返します。 戻り値は多倍長浮動小数点です; nは戻り値の小数点以下の桁数です。

  Hurwitzゼータ関数は以下のように定義されます。

                              inf
                              ====
                              \        1
               zeta (s,h)  =   >    --------
                              /            s
                              ====  (k + h)
                              k = 0

  `load ("bffac")`でこの関数をロードします。

  Categories: Number theory · Numerical evaluation

関数: burn (n)

  n番目の Bernoulli数の近似の有理数をを返します。 `burn`は(有理) Bernoulli数が まあまあの効率で(超越的)ゼータによって近似できるという観察を利用します。

                         n - 1  1 - 2 n
                    (- 1)      2        zeta(2 n) (2 n)!
           B(2 n) = ------------------------------------
                                      2 n
                                   %pi

  `bern`は返す前にインデックス nまでの Bernoulli数すべてを計算するので、 `burn`は大きな、孤立した n(たぶん 105以上の n)に対しては `bern`より効率的かもしれません。 `burn`は 255よりおおきな偶数 nに対しては近似を呼び出します。 奇数と 255以下の nに対しては関数 `bern`が呼び出されます。

  `load ("bffac")`でこの関数をロードします。 `bern`も参照してください。

  Categories: Number theory

関数: chinese ([r_1, …, r_n], [m_1, …, m_n])

  連立合同式 `x = r_1 mod m_1`, …, `x = r_n mod m_n`を解きます。 剰余 r_nは任意の整数が可能である一方、 法 m_nは正の互いに素な整数でなければいけません。

      (%i1) mods : [1000, 1001, 1003, 1007];
      (%o1)                   [1000, 1001, 1003, 1007]
      (%i2) lreduce('gcd, mods);
      (%o2)                               1
      (%i3) x : random(apply("*", mods));
      (%o3)                         685124877004
      (%i4) rems : map(lambda([z], mod(x, z)), mods);
      (%o4)                       [4, 568, 54, 624]
      (%i5) chinese(rems, mods);
      (%o5)                         685124877004
      (%i6) chinese([1, 2], [3, n]);
      (%o6)                    chinese([1, 2], [3, n])
      (%i7) %, n = 4;
      (%o7)                              10

  Categories: Number theory

関数: cf (expr)

  連分数近似を計算します。 exprは連分数と整数の平方根と実数リテラル(整数、有理数、通常の浮動小数点や多倍長浮動小数点)から構成される式です。 `cf`は有理数に関して厳密な展開を計算しますが、 通常の浮動小数点に関して展開は `ratepsilon`で丸められ、 多倍長小数点に関して `10^(-fpprec)`で丸められます。

  式の中のオペランドは代数演算子を組み合わせられます。 Maximaは `cf`の外側で連分数に関する演算について知りません。

  `cf`は、 `listarith`を `false`にバインドした後、引数を評価します。 `cf`はリストとして表現された連分数を返します。

  連分数 `a + 1/(b + 1/(c + ...))`はリスト `[a, b, c, ...]`で表現されます。 リストの要素 `a`, `b`, `c`, ...は整数に評価されなければいけません。 exprは `sqrt (n)`も含むかもしれません。 `n`は整数です。 この場合、`cf`は変数 `cflength`の値掛ける周期と同じ数の連分数の項を与えます。

  `cfdisrep`が返す代数表現を評価することで、連分数は数に評価することができます。 連分数を評価する別の方法に関しては `cfexpand`も参照してください。

  `cfdisrep`, `cfexpand`, `cflength`も参照してください。

  例:

  - exprは連分数と整数の平方根から成る式です。

        (%i1) cf ([5, 3, 1]*[11, 9, 7] + [3, 7]/[4, 3, 2]);
        (%o1)               [59, 17, 2, 1, 1, 1, 27]
        (%i2) cf ((3/17)*[1, -2, 5]/sqrt(11) + (8/13));
        (%o2)        [0, 1, 1, 1, 3, 2, 1, 4, 1, 9, 1, 9, 2]

  - `cflength`は連分数の何周期を代数的無理数のために計算するかを制御します。

        (%i1) cflength: 1$
        (%i2) cf ((1 + sqrt(5))/2);
        (%o2)                    [1, 1, 1, 1, 2]
        (%i3) cflength: 2$
        (%i4) cf ((1 + sqrt(5))/2);
        (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
        (%i5) cflength: 3$
        (%i6) cf ((1 + sqrt(5))/2);
        (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

  - `cfdisrep`が返す代数的表現を評価することによって連分数を評価することができます。

        (%i1) cflength: 3$
        (%i2) cfdisrep (cf (sqrt (3)))$
        (%i3) ev (%, numer);
        (%o3)                   1.731707317073171

  - Maximaは `cf`の外側で連分数に関する演算について知りません。

        (%i1) cf ([1,1,1,1,1,2] * 3);
        (%o1)                     [4, 1, 5, 2]
        (%i2) cf ([1,1,1,1,1,2]) * 3;
        (%o2)                  [3, 3, 3, 3, 3, 6]

  Categories: Continued fractions

関数: cfdisrep (list)

  連分数 `[a, b, c, ...]`のリスト表現から形式 `a + 1/(b + 1/(c + ...))`の通常の代数式を構成し返します。

      (%i1) cf ([1, 2, -3] + [1, -2, 1]);
      (%o1)                     [1, 1, 1, 2]
      (%i2) cfdisrep (%);
                                        1
      (%o2)                     1 + ---------
                                          1
                                    1 + -----
                                            1
                                        1 + -
                                            2

  Categories: Continued fractions

関数: cfexpand (x)

  連分数 xのコンバージェントの最後(列1)とその１つ前(列2)の分子と分母の行列を返します。

      (%i1) cf (rat (ev (%pi, numer)));

      `rat' replaced 3.141592653589793 by 103993/33102 =3.141592653011902
      (%o1)                  [3, 7, 15, 1, 292]
      (%i2) cfexpand (%);
                               [ 103993  355 ]
      (%o2)                    [             ]
                               [ 33102   113 ]
      (%i3) %[1,1]/%[2,1], numer;
      (%o3)                   3.141592653011902

  Categories: Continued fractions

オプション変数: cflength

  デフォルト値: 1

  `cflength`は、値 `cflength`掛ける周期として関数 `cf`が与える連分数の項の数を制御します。 従って、デフォルトは 1周期を与えます。

      (%i1) cflength: 1$
      (%i2) cf ((1 + sqrt(5))/2);
      (%o2)                    [1, 1, 1, 1, 2]
      (%i3) cflength: 2$
      (%i4) cf ((1 + sqrt(5))/2);
      (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
      (%i5) cflength: 3$
      (%i6) cf ((1 + sqrt(5))/2);
      (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

  Categories: Continued fractions

関数: divsum
`divsum` (n, k)
`divsum` (n)

  `divsum (n, k)`は nの約数の k乗した和を返します。

  `divsum (n)`は nの約数の和を返します。

      (%i1) divsum (12);
      (%o1)                          28
      (%i2) 1 + 2 + 3 + 4 + 6 + 12;
      (%o2)                          28
      (%i3) divsum (12, 2);
      (%o3)                          210
      (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
      (%o4)                          210

  Categories: Number theory

関数: euler (n)

  非負の整数 nに対して n番目のEuler数を返します。 もし `zerobern`が `false`なら、 0のEuler数は抑制されます。

  Euler-Mascheroni定数に関しては `%gamma`を参照してください。

      (%i1) zerobern: true$
      (%i2) map (euler, [0, 1, 2, 3, 4, 5, 6]);
      (%o2)               [1, 0, - 1, 0, 5, 0, - 61]
      (%i3) zerobern: false$
      (%i4) map (euler, [0, 1, 2, 3, 4, 5, 6]);
      (%o4)               [1, - 1, 5, - 61, 1385, - 50521, 2702765]

  Categories: Number theory

オプション変数: factors_only

  デフォルト値: `false`

  `ifactors`が返す値を制御します。 デフォルトの `false`の時、 `ifactors`は計算された素因数の多重性について情報を提供するようになります。 もし `factors_only`が `true`に設定されているなら、 `ifactors`は素因数のリスト以外なにも返しません。

  例: `ifactors`を参照してください。

  Categories: Number theory

関数: fib (n)

  第 n項の Fibonacci数を返します。 `fib(0)`は 0に等しく、 `fib(1)`は 1に等しく、 `fib (-n)`は `(-1)^(n + 1) * fib(n)`に等しいです。

  `fib`をコールした後， `prevfib`は 最後に計算された１つ前の Fibonacci数 `fib (x - 1)`に等しいです。

      (%i1) map (fib, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o1)           [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21]

  Categories: Number theory

関数: fibtophi (expr)

  exprに関する Fibonacci数を定数 `%phi`を使って表現します。 `%phi`は `(1 + sqrt(5))/2`, 近似的に1.61803399です。

  例:

      (%i1) fibtophi (fib (n));
                                 n             n
                             %phi  - (1 - %phi)
      (%o1)                  -------------------
                                 2 %phi - 1
      (%i2) fib (n-1) + fib (n) - fib (n+1);
      (%o2)          - fib(n + 1) + fib(n) + fib(n - 1)
      (%i3) fibtophi (%);
                  n + 1             n + 1       n             n
              %phi      - (1 - %phi)        %phi  - (1 - %phi)
      (%o3) - --------------------------- + -------------------
                      2 %phi - 1                2 %phi - 1
                                                n - 1             n - 1
                                            %phi      - (1 - %phi)
                                          + ---------------------------
                                                    2 %phi - 1
      (%i4) ratsimp (%);
      (%o4)                           0

  Categories: Number theory

関数: ifactors (n)

  正の整数 nに対して nの素因数分解を返します。 もし `n=p1^e1..pk^nk`が nの素因数への分解なら、 ifactorsは `[[p1, e1], ... , [pk, ek]]`を返します。

  使われる素因数分解法は 9973までの素数による試行除算と、 Pollardのローとp-1法と、楕円曲線法です。

  `ifactors`が返す値はオプション変数 `factors_only`によって制御されます。 デフォルトの `false`の時、 `ifactors`は計算された素因数の多重性について情報を提供するようになります。 もし `factors_only`が `true`に設定されているなら、 `ifactors`は単に素因数のリストを返します。

      (%i1) ifactors(51575319651600);
      (%o1)     [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]]
      (%i2) apply("*", map(lambda([u], u[1]^u[2]), %));
      (%o2)                        51575319651600
      (%i3) ifactors(51575319651600), factors_only : true;
      (%o3)                   [2, 3, 5, 1583, 9050207]

  Categories: Number theory

関数: igcdex (n, k)

  リスト `[a, b, u]`を返します。 ここで、 uは nと kの最大公約数で、 uは `a n + b k`に等しいです。 引数 nと kは整数でなければいけません。

  `igcdex`はユークリッドのアルゴリズムを実装します。 `gcdex`.も参照してください。

  コマンド `load(gcdex)`でこの関数をロードします。

  例:

      (%i1) load(gcdex)$

      (%i2) igcdex(30,18);
      (%o2)                      [- 1, 2, 6]
      (%i3) igcdex(1526757668, 7835626735736);
      (%o3)            [845922341123, - 164826435, 4]
      (%i4) igcdex(fib(20), fib(21));
      (%o4)                   [4181, - 2584, 1]

  Categories: Number theory

関数: inrt (x, n)

  xの絶対値の整数 n乗根を返します。

      (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
      (%i2) map (lambda ([a], inrt (10^a, 3)), l);
      (%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]

  Categories: Number theory

関数: inv_mod (n, m)

  mを法とする nの逆元を計算します。 もし nが mを法とするゼロ因子なら、 `inv_mod (n,m)`は `false`を返します。

      (%i1) inv_mod(3, 41);
      (%o1)                           14
      (%i2) ratsimp(3^-1), modulus = 41;
      (%o2)                           14
      (%i3) inv_mod(3, 42);
      (%o3)                          false

  Categories: Number theory

関数: isqrt (x)

  整数 xの絶対値の「整数平方根」を返します。

  Categories: Mathematical functions

関数: jacobi (p, q)

  pと qの Jacobi記号を返します。

      (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
      (%i2) map (lambda ([a], jacobi (a, 9)), l);
      (%o2)         [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]

  Categories: Number theory

関数: lcm (expr_1, ..., expr_n)

  引数の最小公倍数を返します。 引数は、整数はもちろん一般式を取り得ます。

  `load ("functs")`でこの関数をロードします。

  Categories: Number theory

関数: lucas (n)

  n番目の Lucas数を返します。 `lucas(0)`は 2に等しく、 `lucas(1)`は 1に等しく、 `lucas(-n)`は `(-1)^(-n) * lucas(n)`に等しいです。

      (%i1) map (lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o1)             [7, - 4, 3, - 1, 2, 1, 3, 4, 7, 11, 18, 29, 47]

  After calling `lucas`を呼び出した後には、グローバル変数 `next_lucas`は 最後の戻り値に続く Lucas数 `lucas (n + 1)`に等しいです。 例は、どのようにして Fibonacci数が `lucas`と `next_lucas`を使って計算可能かを示します。

      (%i1) fib_via_lucas(n) :=
               block([lucas : lucas(n)],
               signum(n) * (2*next_lucas - lucas)/5 )$
      (%i2) map (fib_via_lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o2)             [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21]

  Categories: Number theory

関数: mod (x, y)

  もし xと yが実数で、 yがゼロでないなら、 `x - y * floor(x / y)`を返します。 さらにすべての実数 xに関して `mod (x, 0) = x`が成り立ちます。 定義 `mod (x, 0) = x`の議論に関しては、 Graham, Knuth, Patashnik著の「コンピュータの数学」の3.4節を参照してください。 関数 `mod (x, 1)` は周期が 1で `mod (1, 1) = 0`、`mod (0, 1) = 0`ののこぎり波関数です。

  複素数の偏角の主値（区間 `(-%pi, %pi]`での数）を見つけるためには、 関数 `x |-> %pi - mod (%pi - x, 2*%pi)`を使います。 xは引数です。

  xと yが定数式(例えば `10 * %pi`)の時、 `mod`は `floor`や `ceiling`が使うのと同じ多倍長浮動小数点評価スキームを使います。 同様に、まれですが そんな場合には`mod`は間違った値を返すことがありえます。

  数値でない引数 xや yに関して `mod`はいくつかの式整理規則を知っています:

      (%i1) mod (x, 0);
      (%o1)                           x
      (%i2) mod (a*x, a*y);
      (%o2)                      a mod(x, y)
      (%i3) mod (0, x);
      (%o3)                           0

  Categories: Mathematical functions

関数: next_prime (n)

  nよりも大きな最も小さな素数を返します。

      (%i1) next_prime(27);
      (%o1)                       29

  Categories: Number theory

関数: partfrac (expr, var)

  主変数 varに関する部分分数式 exprを展開します。 `partfrac`は完全な部分分数分解を行います。 利用したアルゴリズムは 部分分数展開(元の分母の因子)の分母は互いに素であるという事実に基づいています。 分子は分母の線形結合として書けて、結果は展開されたものになります。

      (%i1) 1/(1+x)^2 - 2/(1+x) + 2/(2+x);
                            2       2        1
      (%o1)               ----- - ----- + --------
                          x + 2   x + 1          2
                                          (x + 1)
      (%i2) ratsimp (%);
                                       x
      (%o2)                 - -------------------
                               3      2
                              x  + 4 x  + 5 x + 2
      (%i3) partfrac (%, x);
                            2       2        1
      (%o3)               ----- - ----- + --------
                          x + 2   x + 1          2
                                          (x + 1)

関数: power_mod (a, n, m)

  `a^n mod m`を計算するために剰余アルゴリズムを使います。 ここで、 aと nは整数で、 mは正の整数です。 もし nが負なら `inv_mod`が剰余逆元を見つけるために使われます。

      (%i1) power_mod(3, 15, 5);
      (%o1)                          2
      <(%i2) mod(3^15,5);
      (%o2)                          2
      (%i3) power_mod(2, -1, 5);
      (%o3)                          3
      (%i4) inv_mod(2,5);
      (%o4)                          3

  Categories: Number theory

関数: primep (n)

  素数テスト。 もし `primep (n)`が `false`を返すなら、 nは合成数であり、 もし `true`を返すなら、 nは非常に高い確率で素数です。

  341550071728321より小さな nに対しては Miller-Rabinのテストの決定的バージョンが使われます。 もし `primep (n)`が `true`を返すなら、 nは素数です。

  341550071728321よりの大きな nに対して、 `primep`は、 `primep_number_of_tests`個の Miller-Rabinの疑似素数テストと 1つの Lucasの疑似素数テストを使います。 合成数の nが Miller-Rabinのテスト１つを通過する確率は 1/4より小さいです。 `primep_number_of_tests`に関してデフォルト値 25を使うと、 通過した nが合成である確率は 10^-15よりもはるかに小さいです。

  Categories: Predicate functions · Number theory

オプション変数: primep_number_of_tests

  デフォルト値: 25

  `primep`の中で使われる Miller-Rabinのテストの回数。

  Categories: Number theory

関数: prev_prime (n)

  nよりも小さな最大の素数を返します。

      (%i1) prev_prime(27);
      (%o1)                       23

  Categories: Number theory

関数: qunit (n)

  実二次数体 `sqrt (n)`の基本単数、すなわちノルムが 1の要素を返します。 ここで nは整数です。 これは結果的にペル方程式 `a^2 - n b^2 = 1`を解くことになります。

      (%i1) qunit (17);
      (%o1)                     sqrt(17) + 4
      (%i2) expand (% * (sqrt(17) - 4));
      (%o2)                           1

  Categories: Number theory

関数: totient (n)

  n以下の nと互いに素な整数の数を返します。

  Categories: Number theory

オプション変数: zerobern

  デフォルト値: `true`

  `zerobern`が `false`の時、 `bern`は Bernoulli数を除外し、 `euler`はゼロに等しい Euler数を除外します。 `bern`と `euler`を参照してください。

  Categories: Number theory

関数: zeta (n)

  Riemannのゼータ関数を返します。 もし xが負の整数か, 0, 1,または正の偶数なら、 Reimannのゼータ関数は厳密な値に整理されます。 正の偶数に対してはオプション変数 `zeta%pi`は `true`であることも必要です。 (`zeta%pi`を参照してください。) 浮動小数点または多倍長浮動小数点数に対しては Reimannゼータ関数は数値的に評価されます。 Maximaは、 有理非整数、浮動小数点数、複素数の引数を含む他の引数すべてに対して、 また、 `zeta%pi`が値 `false`なら偶数に対しても 名詞形 `zeta (n)`を返します。

  `zeta(1)`は未定義ですが、 Maximaは上からと下からの極限 `limit(zeta(x), x, ,1)`を知っています。

  `bfzeta`と `zeta%pi`も参照してください。

  例：

      (%i1) zeta([-2, -1, 0, 0.5, 2, 3, 1+%i]);
                                                   2
                  1     1                       %pi
      (%o1) [0, - --, - -, - 1.460354508809586, ----, zeta(3),
                  12    2                        6
                                                          zeta(%i + 1)]
      (%i2) limit(zeta(x),x,1,plus);
      (%o2)                          inf
      (%i3) limit(zeta(x),x,1,minus);
      (%o3)                         minf

  Categories: Number theory

オプション変数: zeta%pi

  デフォルト値: `true`

  `zeta%pi`が `true`の時、 偶数 `n`に対して `zeta`は `%pi^n`に比例する式を返します。 そうでないなら、 偶数 `n`に対して `zeta`は名詞形 `zeta (n)`を返します。

  例:

      (%i1) zeta%pi: true$
      (%i2) zeta (4);
                                       4
                                    %pi
      (%o2)                         ----
                                     90
      (%i3) zeta%pi: false$
      (%i4) zeta (4);
      (%o4)                        zeta(4)

  Categories: Number theory

関数: zn_add_table (n)

  (Z/nZ)のすべての要素の加算表を表示します。

  `zn_mult_table`, `zn_power_table`も参照してください。

  Categories: Number theory

関数: zn_determinant (matrix, p)

  LU分解の技法を使って、 (Z/pZ)上の matrixの行列式を計算します。 pは素数でなければいけません。

  行列式がゼロに等しい場合、LU分解が失敗するかもしれません。 この場合、 `zn_determinant`はモジュラーでない行列式を計算し、その後整理します。

  `zn_invert_by_lu`も参照してください。

  例:

      (%i1) m : matrix([1,3],[2,4]);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 2  4 ]
      (%i2) zn_determinant(m, 5);
      (%o2)                               3
      (%i3) m : matrix([2,4,1],[3,1,4],[4,3,2]);
                                     [ 2  4  1 ]
                                     [         ]
      (%o3)                          [ 3  1  4 ]
                                     [         ]
                                     [ 4  3  2 ]
      (%i4) zn_determinant(m, 5);
      (%o4)                               0

  Categories: Number theory

関数: zn_invert_by_lu (matrix, p)

  LU分解の技法を使って、 (Z/pZ)上で matrixのモジュラー逆元を計算します。 pは素数、 matrixは可逆でなければいけません。 matrixが可逆でないなら、 `zn_invert_by_lu`は `false`を返します。

  `zn_determinant`も参照してください。

  例:

      (%i1) m : matrix([1,3],[2,4]);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 2  4 ]
      (%i2) zn_determinant(m, 5);
      (%o2)                               3
      (%i3) mi : zn_invert_by_lu(m, 5);
                                      [ 3  4 ]
      (%o3)                           [      ]
                                      [ 1  2 ]
      (%i4) matrixmap(lambda([a], mod(a, 5)), m . mi);
                                      [ 1  0 ]
      (%o4)                           [      ]
                                      [ 0  1 ]

  Categories: Number theory

関数: zn_log
`zn_log` (a, g, n)
`zn_log` (a, g, n, [[p1, e1], …, [pk, ek]])

  離散対数を計算します。 (Z/nZ)* が巡回群、 gが nを法とする原始根とし、 aがこの群の要素とします。 そのとき、`zn_log (a, g, n)`は合同式 `g^x = a mod n`を解きます。

  採用したアルゴリズムは `totient(n)`の素因数分解を必要とします。 この素因数分解はその上時間を消費するかもしれず、いくつかの場合、 最初に素因数分解してそれから因数のリストを 4番目の引数として `zn_log`に渡すのが実用的かもしれません。 リストは、デフォルトオプション `factors_only : false`を使って `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

  離散対数のために、アルゴリズムは Pohlig-Hellman-縮約と Pollardのロー法を使います。 `zn_log`の実行時間は主にtotientの最大素因数のビット長に依存します。

  `zn_primroot`, `zn_order`, `ifactors`, `totient`も参照して下さい。

  例:

  `zn_log (a, g, n)`は合同式 `g^x = a mod n`を解きます。

      (%i1) n : 22$
      (%i2) g : zn_primroot(n);
      (%o2)                               7
      (%i3) ord_7 : zn_order(7, n);
      (%o3)                              10
      (%i4) powers_7 : makelist(power_mod(g, x, n), x, 0, ord_7 - 1);
      (%o4)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
      (%i5) zn_log(21, g, n);
      (%o5)                               5
      (%i6) map(lambda([x], zn_log(x, g, n)), powers_7);
      (%o6)                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  オプションの4番目の引数は `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。 実行時間は主にtotientの最大素因数のビット長に依存します。

      (%i1) (p : 2^127-1, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors(p - 1)$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                              43
      (%i4) a : power_mod(g, 1234567890, p)$
      (%i5) zn_log(a, g, p, ifs);
      (%o5)                          1234567890
      (%i6) time(%o5);
      (%o6)                            [1.204]
      (%i7) f_max : last(ifs);
      (%o7)                       [77158673929, 1]
      (%i8) slength( printf(false, "~b", f_max[1]) );
      (%o8)                              37

  Categories: Number theory

関数: zn_mult_table
`zn_mult_table` (n)
`zn_mult_table` (n, all)

  オプション引数 allがない時、 `zn_mult_table(n)`は、 nを法として可逆な (Z/nZ)*のすべての要素の乗算表を表示します。

  オプション引数 allを付けると、ゼロでない要素すべてに関して表示します。

  `zn_add_table`, `zn_power_table`も参照してください。

  例:

      (%i1) zn_mult_table(4);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 3  1 ]
      (%i2) zn_mult_table(4, all);
                                     [ 1  2  3 ]
                                     [         ]
      (%o2)                          [ 2  0  2 ]
                                     [         ]
                                     [ 3  2  1 ]

  Categories: Number theory

関数: zn_order
`zn_order` (x, n)
`zn_order` (x, n, [[p1, e1], …, [pk, ek]])

  xが 有限群 (Z/nZ)*の単位元ならその次数を返し、そうでないなら `false`を返します。 xは nと互いに素なら nを法とする単位元です。

  採用したアルゴリズムは `totient(n)`の素因数分解を必要とします。 この素因数分解はその上時間を消費するかもしれず、いくつかの場合、 最初に素因数分解してそれから因数のリストを 3番目の引数として `zn_order`に渡すのが実用的かもしれません。 リストは、デフォルトオプション `factors_only : false`を使って `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

  `zn_primroot`, `ifactors`, `totient`も参照して下さい。

  例:

  `zn_order`は (Z/nZ)*の単位元 xの次数を計算します。

      (%i1) n : 22$
      (%i2) g : zn_primroot(n);
      (%o2)                               7
      (%i3) units_22 : sublist(makelist(i,i,1,21), lambda([x], gcd(x, n) = 1));
      (%o3)              [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
      (%i4) (ord_7 : zn_order(7, n)) = totient(n);
      (%o4)                            10 = 10
      (%i5) powers_7 : makelist(power_mod(g,i,n), i,0,ord_7 - 1);
      (%o5)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
      (%i6) map(lambda([x], zn_order(x, n)), powers_7);
      (%o6)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
      (%i7) map(lambda([x], ord_7/gcd(x, ord_7)), makelist(i, i,0,ord_7 - 1));
      (%o7)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
      (%i8) totient(totient(n));
      (%o8)                               4

  オプションの三番目の引数は `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                               3
      (%i4) is( (ord_3 : zn_order(g, p, ifs)) = totient(p) );
      (%o4)                             true
      (%i5) map(lambda([x], ord_3/zn_order(x, p, ifs)), makelist(i,i,2,15));
      (%o5)        [22, 1, 44, 10, 5, 2, 22, 2, 8, 2, 1, 1, 20, 1]

  Categories: Number theory

関数: zn_power_table
`zn_power_table` (n)
`zn_power_table` (n, all)

  オプション引数 allなしの場合、 `zn_power_table(n)`は nを法として可逆な (Z/nZ)*のすべての要素のべき表を表示します。 指数は `1`から `totient(n)`の最大特性因子までループし、表は右側1の列で終わります。

  オプション引数 allを付けると、ゼロでない要素すべてに関して表示します。 指数は `1`から `totient(n) + 1`までループし、 モジュラスが異なる素数に因素分解される場合、最後の列は最初の列に等しくなります。

  `zn_add_table`, `zn_mult_table`も参照してください。

  例:

      (%i1) zn_power_table(6);
                                      [ 1  1 ]
      (%o1)                           [      ]
                                      [ 5  1 ]
      (%i2) zn_power_table(6, all);
                                     [ 1  1  1 ]
                                     [         ]
                                     [ 2  4  2 ]
                                     [         ]
      (%o2)                          [ 3  3  3 ]
                                     [         ]
                                     [ 4  4  4 ]
                                     [         ]
                                     [ 5  1  5 ]

  Categories: Number theory

関数: zn_primroot
`zn_primroot` (n)
`zn_primroot` (n, [[p1, e1], …, [pk, ek]])

  もし乗法群 (Z/nZ)*が巡回的なら、 `zn_primroot`は nを法とする最小の原始根を計算します。 もし nが `2`, `4`, `p^k` または `2*p^k`に等しいなら (Z/nZ)* は巡回的です。 ここで `p`は素数で `2`より大きく `k`は自然数です。 もしオプション変数 `zn_primroot_pretest` (デフォルト: `false`)が `true`に設定されているなら `zn_primroot`は条件付き事前テスト(according pretest)を実行します。 どんな場合でも計算は上限 `zn_primroot_limit`で制限されます。

  もし (Z/nZ)*が巡回的でないか `zn_primroot_limit`まで原始根がないなら、 `zn_primroot`は `false`を返します。

  採用したアルゴリズムは `totient(n)`の素因数分解を必要とします。 この素因数分解はその上時間を消費するかもしれず、いくつかの場合、 最初に素因数分解してそれから因数のリストを 3番目の引数として `zn_primroot`に渡すのが実用的かもしれません。

  リストは、デフォルトオプション `factors_only : false`を使って `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

  `zn_primroot_p`, `zn_order`, `ifactors`, `totient`も参照してください。

  例:

  `zn_primroot`は nを法とする最小原始根を計算するか、 `false`を返します。

      (%i1) n : 14$
      (%i2) g : zn_primroot(n);
      (%o2)                               3
      (%i3) zn_order(g, n) = totient(n);
      (%o3)                             6 = 6
      (%i4) n : 15$
      (%i5) zn_primroot(n);
      (%o5)                             false

  オプションの二番目の引数は`ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                               3
      (%i4) [time(%o2), time(%o3)];
      (%o4)                    [[15.556972], [0.004]]
      (%i5) is(zn_order(g, p, ifs) = p - 1);
      (%o5)                             true
      (%i6) n : 2^142 + 216$
      (%i7) ifs : ifactors(totient(n))$
      (%i8) zn_primroot(n, ifs),
            zn_primroot_limit : 200, zn_primroot_verbose : true;
      `zn_primroot' stopped at zn_primroot_limit = 200
      (%o8)                             false

  Categories: Number theory

オプション変数: zn_primroot_limit

  デフォルト値: `1000`

  もし `zn_primroot`が原始根をみつけられないなら、 上限でやめます。 もしオプション変数 `zn_primroot_verbose` (デフォルト: `false`)が `true`に設定されているなら、 `zn_primroot_limit`に到達した時メッセージが表示されます。

  Categories: Number theory

関数: zn_primroot_p
`zn_primroot_p` (x, n)
`zn_primroot_p` (x, n, [[p1, e1], …, [pk, ek]])

  xが乗法群 (Z/nZ)*の原始根かチェックします。

  採用したアルゴリズムは `totient(n)`の素因数分解を必要とします。 この素因数分解はその上時間を消費するかもしれず、いくつかの場合、 最初に素因数分解してそれから因数のリストを 3番目の引数として `zn_primroot_p`に渡すのが実用的かもしれません。 リストは、デフォルトオプション `factors_only : false`を使って `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

  `zn_primroot`, `zn_order`, `ifactors`, `totient`も参照して下さい。

  例:

  述語論理関数としての `zn_primroot_p`。

      (%i1) n : 14$
      (%i2) units_14 : sublist(makelist(i,i,1,13), lambda([i], gcd(i, n) = 1));
      (%o2)                     [1, 3, 5, 9, 11, 13]
      (%i3) zn_primroot_p(13, n);
      (%o3)                            false
      (%i4) sublist(units_14, lambda([x], zn_primroot_p(x, n)));
      (%o4)                            [3, 5]
      (%i5) map(lambda([x], zn_order(x, n)), units_14);
      (%o5)                      [1, 6, 6, 3, 3, 2]

  オプションの三番目の引数は `ifactors(totient(n))`が返すリストと同じ形式でなければいけません。

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) sublist(makelist(i,i,1,50), lambda([x], zn_primroot_p(x, p, ifs)));
      (%o3)      [3, 12, 13, 15, 21, 24, 26, 27, 29, 33, 38, 42, 48]
      (%i4) [time(%o2), time(%o3)];
      (%o4)                   [[7.748484], [0.036002]]

  Categories: Predicate functions · Number theory

オプション変数: zn_primroot_pretest

  デフォルト値: `false`

  もし nが `2`, `4`, `p^k`か `2*p^k`なら 乗法群 (Z/nZ)*は巡回的です。 ここで `p`は素数で `2`より大きく、 `k`は自然数です。

  `zn_primroot_pretest`は `zn_primroot`が 最小原始根を計算する前にこれらの場合の１つが起こるかどうかチェックするかどうか制御します。 `zn_primroot_pretest`が `true`に設定されているときだけ、 これの事前テストが実行されます。

  Categories: Number theory

オプション変数: zn_primroot_verbose

  デフォルト値: `false`

  `zn_primroot_limit`に達したとき、 `zn_primroot`がメッセージを表示するかどうか制御します。

  Categories: Number theory

[ << ] | [ >> ] |  |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

この文書は市川 雄二によって1月, 7 2015にtexi2html 1.76を用いて生成されました。