[ < ] | [ > ] | [ << ] | [上] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
29.1 Functions and Variables for Number Theory |
[ < ] | [ > ] | [ << ] | [上] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
整数 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
変数 xに関する n番目の Bernoulli多項式を返します。
Categories: Number theory
引数 sに関する Riemannのゼータ関数を返します。 戻り値は多倍長浮動小数点です; nは戻り値の小数点以下の桁数です。
Categories: Number theory · Numerical evaluation
引数 sと hに関する Hurwitzのゼータ関数を返します。 戻り値は多倍長浮動小数点です; nは戻り値の小数点以下の桁数です。
Hurwitzゼータ関数は以下のように定義されます。
inf ==== \ 1 zeta (s,h) = > -------- / s ==== (k + h) k = 0
load ("bffac")
でこの関数をロードします。
Categories: Number theory · Numerical evaluation
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
連立合同式 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
連分数近似を計算します。
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
も参照してください。
例:
(%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
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
連分数 [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
連分数 xのコンバージェントの最後(列1)とその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
デフォルト値: 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 (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
非負の整数 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
デフォルト値: false
ifactors
が返す値を制御します。
デフォルトの false
の時、
ifactors
は計算された素因数の多重性について情報を提供するようになります。
もし factors_only
が true
に設定されているなら、
ifactors
は素因数のリスト以外なにも返しません。
例: ifactors
を参照してください。
Categories: Number theory
第 n項の Fibonacci数を返します。
fib(0)
は 0に等しく、 fib(1)
は 1に等しく、
fib (-n)
は (-1)^(n + 1) * fib(n)
に等しいです。
fib
をコールした後,
prevfib
は 最後に計算された1つ前の 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
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
正の整数 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
リスト [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
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
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
整数 xの絶対値の「整数平方根」を返します。
Categories: Mathematical functions
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
引数の最小公倍数を返します。 引数は、整数はもちろん一般式を取り得ます。
load ("functs")
でこの関数をロードします。
Categories: Number theory
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
もし 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
nよりも大きな最も小さな素数を返します。
(%i1) next_prime(27); (%o1) 29
Categories: Number theory
主変数 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)
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)
が 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つを通過する確率は 1/4より小さいです。
primep_number_of_tests
に関してデフォルト値 25を使うと、
通過した nが合成である確率は 10^-15よりもはるかに小さいです。
Categories: Predicate functions · Number theory
デフォルト値: 25
primep
の中で使われる Miller-Rabinのテストの回数。
Categories: Number theory
startから endまでのすべての素数のリストを返します。
(%i1) primes(3, 7); (%o1) [3, 5, 7]
Categories: Number theory
nよりも小さな最大の素数を返します。
(%i1) prev_prime(27); (%o1) 23
Categories: Number theory
実二次数体 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
n以下の nと互いに素な整数の数を返します。
Categories: Number theory
デフォルト値: true
zerobern
が false
の時、
bern
は Bernoulli数を除外し、 euler
はゼロに等しい Euler数を除外します。
bern
と euler
を参照してください。
Categories: Number theory
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
デフォルト値: 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
(Z/nZ)のすべての要素の加算表を表示します。
zn_mult_table
, zn_power_table
も参照してください。
Categories: Number theory
nのトーティエントの特性因子を含むリストを返します。
特性因子を使って、 nを法とする乗法群を巡回部分群の群直積として表現できます。
群自身が巡回的の時には、リストはトーティエントのみを含み、
zn_primroot
を使って使って生成元を計算できます。
もしトーティエントが複数の特性因子に分割されるなら、
zn_factor_generators
は対応する部分群の生成元を見つけます。
リストの中の r
因子のそれぞれは"right following factors"を分割します。
最後の因子のため、 f_r
は
群の中のすべての a
に対して a^f_r = 1 (mod n)
を満たします。
もし n > 2
なら、 totient(n)/2^r
は平方剰余の数であり、
これらのそれぞれは 2^r
個の平方根を持ちます。
totient
, zn_primroot
, zn_factor_generators
も参照してください。
例:
14
を法とする乗法群は巡回的で、その 6
要素は原始根で生成できます。
(%i1) [zn_characteristic_factors(14), phi: totient(14)]; (%o1) [[6], 6] (%i2) [zn_factor_generators(14), g: zn_primroot(14)]; (%o2) [[3], 3] (%i3) M14: makelist(power_mod(g,i,14), i,0,phi-1); (%o3) [1, 3, 9, 13, 11, 5]
15
を法とする乗法群は巡回的でなかく、その 8
要素は2つの因子生成元で生成できます。
(%i1) [[f1,f2]: zn_characteristic_factors(15), totient(15)]; (%o1) [[2, 4], 8] (%i2) [[g1,g2]: zn_factor_generators(15), zn_primroot(15)]; (%o2) [[11, 7], false] (%i3) UG1: makelist(power_mod(g1,i,15), i,0,f1-1); (%o3) [1, 11] (%i4) UG2: makelist(power_mod(g2,i,15), i,0,f2-1); (%o4) [1, 7, 4, 13] (%i5) M15: create_list(mod(i*j,15), i,UG1, j,UG2); (%o5) [1, 7, 4, 13, 11, 2, 14, 8]
最後の特性因子 4
に関して、
M15
の中のすべての a
に対して a^4 = 1 (mod 15)
を満たします。
M15
は2つの特性因子と、8/2^2
平方剰余を持ち、
これらのそれぞれは 2^2
個の平方根を持ちます。
(%i6) zn_power_table(15); [ 1 1 1 1 ] [ ] [ 2 4 8 1 ] [ ] [ 4 1 4 1 ] [ ] [ 7 4 13 1 ] (%o6) [ ] [ 8 4 2 1 ] [ ] [ 11 1 11 1 ] [ ] [ 13 4 7 1 ] [ ] [ 14 1 14 1 ] (%i7) map(lambda([i], zn_nth_root(i,2,15)), [1,4]); (%o7) [[1, 4, 11, 14], [2, 7, 8, 13]]
Categories: Number theory
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
nのトーティエントの特性因子に対応する因子生成元を含むリストを返します。
コメントと例に関しては zn_characteristic_factors
を参照してください。
Categories: Number theory
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
離散対数を計算します。
(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
オプション引数 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
もし根が乗法群 (Z/mZ)* のメンバー、すなわち mと互いに素なら
そして (Z/mZ)*のメンバーの n番目のべきなら、
xの n番目の根を含むリストを返します。
そうでなければ、 zn_nth_root
は false
を返します。
zn_nth_root
は Adlemanと Manders、 Millerによるアルゴリズムを使い、
モジュラス mの素因数分解を必要とします。
mの因数分解がわかっている場合、4番目の引数として因子のリストを渡すことができます。
このオプション引数は
デフォルトオプション factors_only: false
を使った時
ifactors(m)
が返すリストと同じ形式のものでなければいけません。
例:
nが 1
から6
までの値をとる、
1
の n番目の根すべてを含むリストのリストが続く
14
を法とする乗法群のべきテーブル
(%i1) zn_power_table(14); [ 1 1 1 1 1 1 ] [ ] [ 3 9 13 11 5 1 ] [ ] [ 5 11 13 9 3 1 ] (%o1) [ ] [ 9 11 1 9 11 1 ] [ ] [ 11 9 1 11 9 1 ] [ ] [ 13 1 13 1 13 1 ] (%i2) makelist(zn_nth_root(1,n,14), n,1,6); (%o2) [[1], [1, 13], [1, 9, 11], [1, 13], [1], [1, 3, 5, 9, 11, 13]]
このRSAのような例では、モジュラスの因数分解が知られていて、 4番目の引数として渡されます。
(%i1) p: 2^107-1$ q: 2^127-1$ N: p*q$ (%i4) ibase: obase: 16$ (%i5) msg: 11223344556677889900aabbccddeeff$ (%i6) enc: power_mod(msg, 10001, N); (%o6) 1a8db7892ae588bdc2be25dd5107a425001fe9c82161abc673241c8b383 (%i7) zn_nth_root(enc, 10001, N, [[p,1],[q,1]]); (%o7) [11223344556677889900aabbccddeeff]
Categories: Number theory
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(n)
は
nを法として可逆な (Z/nZ)*のすべての要素のべき表を表示します。
指数は 1
から totient(n)
の最大特性因子までループし、表は右側1の列で終わります。
オプション引数は all
か 正の整数 i
を任意の順で与えることができます。
引数 all
を付けると、ゼロでない要素すべてに関して表示します。
もう一つ列が加えられて、モジュラスが異なる素数に因素分解される場合、
最後の列が最初の列に等しくなります。
もし追加された整数引数 i
が与えられたなら、
指数が 1
から i
までループします。
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 ] (%i3) zn_power_table(6,all,5); [ 1 1 1 1 1 ] [ ] [ 2 4 2 4 2 ] [ ] (%o3) [ 3 3 3 3 3 ] [ ] [ 4 4 4 4 4 ] [ ] [ 5 1 5 1 5 ]
Categories: Number theory
もし乗法群 (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
デフォルト値: 1000
もし zn_primroot
が原始根をみつけられないなら、 上限でやめます。
もしオプション変数 zn_primroot_verbose
(デフォルト: false
)が true
に設定されているなら、 zn_primroot_limit
に到達した時メッセージが表示されます。
Categories: Number theory
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
デフォルト値: false
もし nが 2
, 4
, p^k
か 2*p^k
なら 乗法群 (Z/nZ)*は巡回的です。
ここで p
は素数で 2
より大きく、 k
は自然数です。
zn_primroot_pretest
は zn_primroot
が 最小原始根を計算する前にこれらの場合の1つが起こるかどうかチェックするかどうか制御します。
zn_primroot_pretest
が true
に設定されているときだけ、 これの事前テストが実行されます。
Categories: Number theory
デフォルト値: false
zn_primroot_limit
に達したとき、 zn_primroot
がメッセージを表示するかどうか制御します。
Categories: Number theory
[ << ] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
この文書は市川 雄二によって10月, 11 2015にtexi2html 1.76を用いて生成されました。