---

下位関数群
[数論的関数]

関数
int	ymp_odd_root (mp_ref_t root, mp_cref_t source, size_t pow)
	正の奇数に対し、完全奇数乗数かどうかを判定. より詳しく...
int	ymp_nsqrt_mod2exp (mp_ref_t root, mp_cref_t source, size_t e_mod)
	奇数に対し平方根の逆数を2の冪を法として求める. より詳しく...
int	ymp_odd_sqrt (mp_ref_t root, mp_cref_t source)
	奇数に対し平方根を求める. より詳しく...

---

関数の解説

int ymp_odd_root (  mp_ref_t    root, mp_cref_t    source, size_t    pow )  [inline, static]

正の奇数に対し、完全奇数乗数かどうかを判定. <soruce>が完全pow乗数かどうかを判定し、存在すれば冪根を求める。 引数: root  もし存在すれば冪根を格納するstruct multiprecへのポインタ 根が不要ならNULLを指定する。 source  判定対象の奇数を表すstruct multiprecへのポインタ pow  冪指数 事前条件: sourceの表す数は正であること。そうでない場合結果は不定 sourceの表す数は奇数であること。そうでない場合、結果は不定 powは奇数であること。そうでない場合、結果は不定 覚え書き: rootとsourceは一致しても良い 戻り値: pow乗根となる自然数が存在したなら、その値が<root>に格納され、 非0が返る。存在しなければ0. 事後条件: 冪根が存在しなかった場合、<root>は変化しない perfect_power.c の 34 行で定義されています。 参照 multiprec::len, mp_cref_t, multiprec::sign, ymp_abs_clog2, ymp_add, ymp_alloca_initialize, ymp_assign, ymp_assign_2exp, ymp_assign_digit, ymp_compare, ymp_mod_2exp, ymp_modmul_2exp, ymp_modpow_2exp_z, ymp_mul_digit, ymp_pow, と ymp_sub. 呼出 ymp_is_perfect_power, と ymp_proot. { /* * 2-adic Newton iteration. `Modern computer algebra' p.264-268参照 */ size_t clog2, k, two_exp; struct multiprec g, s, tmp; /* clog2 := */ clog2 = ymp_abs_clog2(source->digits, source->used); if (clog2 == 0) { if (root) ymp_assign_digit(root, 1); return 1; } /* k := 2**{n*k} > <digits> なる最小のk */ k = clog2 / pow + (clog2 % pow != 0); ymp_alloca_initialize(&g, k * pow + 1); ymp_alloca_initialize(&s, source->len + 1); ymp_alloca_initialize(&tmp, k * pow + 1); ymp_assign_digit(&g, 1); ymp_assign_digit(&s, 1); for (two_exp=2; two_exp<k; two_exp<<=1) { /* tmp := f(g_i)s_i = (g_i**pow - source)) * s_i (mod 2**two_exp) */ ymp_modpow_2exp_z(&tmp, &g, two_exp, pow); ymp_sub(&tmp, &tmp, source); ymp_mod_2exp(&tmp, &tmp, two_exp); ymp_modmul_2exp(&tmp, &tmp, &s, two_exp); /* g_{i+1} := g_i - tmp */ ymp_sub(&g, &g, &tmp); ymp_mod_2exp(&g, &g, two_exp); /* tmp := f'(g_{i+1})* s_i**2 * = pow * g_{i+1}**(pow-1) * s_i**2 (mod 2**two_exp) */ ymp_modpow_2exp_z(&tmp, &g, two_exp, pow-1); ymp_mul_digit(&tmp, &tmp, pow); ymp_mod_2exp(&tmp, &tmp, two_exp); ymp_modmul_2exp(&tmp, &tmp, &s, two_exp); ymp_modmul_2exp(&tmp, &tmp, &s, two_exp); /* s_{i+1} := 2*s_i - tmp */ ymp_add(&s, &s, &s); ymp_mod_2exp(&s, &s, two_exp); ymp_sub(&s, &s, &tmp); ymp_mod_2exp(&s, &s, two_exp); } /* g = g_i - f(g_i)s_i ( mod 2**k )*/ ymp_modpow_2exp_z(&tmp, &g, k, pow); ymp_sub(&tmp, &tmp, source); ymp_mod_2exp(&tmp, &tmp, k); ymp_modmul_2exp(&tmp, &tmp, &s, k); ymp_sub(&g, &g, &tmp); ymp_mod_2exp(&g, &g, k); /* if (g < 0) g += 2**k */ if (g.sign) { ymp_assign_2exp(&tmp, k); ymp_add(&g, &g, &tmp); } ymp_pow(&tmp, &g, pow); if (ymp_compare(&tmp, source) == 0) { if (root) ymp_assign(root, &g); return 1; } else { return 0; } }

int ymp_nsqrt_mod2exp (  mp_ref_t    root, mp_cref_t    source, size_t    e_mod )  [inline, static]

奇数に対し平方根の逆数を2の冪を法として求める. もし存在すれば<source> * i**2 = 1 (mod 2**(e_mod+1)) なる自然数iを求める 引数: root  もし存在すればiを格納する、struct multiprecへのポインタ source  判定対象の奇数を表すstruct multiprecへのポインタ e_mod  法の冪指数 事前条件: <source>の表す数は正であること。そうでない場合結果は不定 <source>の表す数は奇数であること。そうでない場合、結果は不定 覚え書き: rootとsourceは一致しても良い 戻り値: 解となる自然数が存在したならその値が<root>に格納され、非0が返る。 存在しなければ0が返る. 事後条件: 冪根が存在しなかった場合、<root>は変化しない perfect_power.c の 125 行で定義されています。 参照 DIGIT_BIT, mp_cref_t, ymp_alloca_initialize, ymp_assign_digit, ymp_div_2exp, ymp_modmul_2exp, ymp_neg, と ymp_sub_digit. 呼出 ymp_odd_sqrt. { /* * MATHEMATICS OF COMPUTATION Volume 67, Number 223, * July 1998, Pages 1253-1283 * * Daniel J. Bernstein * "DETECTING PERFECT POWERS IN ESSENTIALLY LINEAR TIME": Section 21 * * Algorithm S2 and Lemma 21.4 */ size_t n_digits; size_t e; struct multiprec tmp, r; if ((source->digits[0] & 0x03) != 1) return 0; if (e_mod == 1) { ymp_assign_digit(root, 1); return 1;} if ((source->digits[0] & 0x07) != 1) return 0; if (e_mod == 2) { ymp_assign_digit(root, 1); return 1;} n_digits = e_mod / DIGIT_BIT + (e_mod % DIGIT_BIT != 0); ymp_alloca_initialize(&r, n_digits+2); ymp_alloca_initialize(&tmp, n_digits+2); ymp_assign_digit(&r, 1); for (e = 3; e < e_mod; e = 2*e-1) { /* tmp := (3r - source*r**3) mod 2**(e+1) */ ymp_modmul_2exp(&tmp, source, &r, e+1); ymp_modmul_2exp(&tmp, &tmp, &r, e+1); ymp_sub_digit(&tmp, &tmp, 3); ymp_neg(&tmp, &tmp); ymp_modmul_2exp(&tmp, &tmp, &r, e+1); /* r := tmp/2 mod 2**e */ ymp_div_2exp(&r, &tmp, 1); } /* tmp := (3r - source*r**3) mod 2**(e_mod+1) */ ymp_modmul_2exp(&tmp, source, &r, e_mod+1); ymp_modmul_2exp(&tmp, &tmp, &r, e_mod+1); ymp_sub_digit(&tmp, &tmp, 3); ymp_neg(&tmp, &tmp); ymp_modmul_2exp(&tmp, &tmp, &r, e_mod+1); /* r := tmp/2 mod 2**e */ ymp_div_2exp(root, &tmp, 1); return 1; }

int ymp_odd_sqrt (  mp_ref_t    root, mp_cref_t    source )  [inline, static]

奇数に対し平方根を求める. もし存在すれば<source> = i**2 なる自然数iを求める 引数: root  もし存在すればiを格納する、struct multiprecへのポインタ 根が不要ならNULLを指定する source  判定対象の奇数を表すstruct multiprecへのポインタ 事前条件: <source>の表す数は正であること。そうでない場合結果は不定 <source>の表す数は奇数であること。そうでない場合、結果は不定 覚え書き: rootとsourceは一致しても良い 戻り値: 平方根となる自然数が存在したなら、 その値が<root>に格納され、非0が返る。存在しなければ0が返る. 事後条件: 冪根が存在しなかった場合、<root>は変化しない perfect_power.c の 194 行で定義されています。 参照 DIGIT_BIT, MAX, mp_cref_t, multiprec::sign, multiprec::used, ymp_abs_clog2, ymp_add, ymp_alloca_initialize, ymp_assign, ymp_assign_2exp, ymp_compare, ymp_modmul_2exp, ymp_mul, ymp_nsqrt_mod2exp, と ymp_sub. 呼出 ymp_is_perfect_power, と ymp_proot. { size_t n_digits, n_bits; size_t clog2, b; struct multiprec r, tmp; clog2 = ymp_abs_clog2(source->digits, source->used); b = clog2/2 + clog2%2; n_digits = b / DIGIT_BIT; n_bits = b % DIGIT_BIT; ymp_alloca_initialize(&r, n_digits + 1); if (!ymp_nsqrt_mod2exp(&r, source, b)) return 0; ymp_modmul_2exp(&r, &r, source, b); ymp_alloca_initialize(&tmp, MAX(2*(n_digits+1), 2*(r.used+1))); if (r.sign) { ymp_assign_2exp(&tmp, b); ymp_add(&r, &tmp, &r); } ymp_mul(&tmp, &r, &r); if (ymp_compare(source, &tmp) == 0) { if (root) ymp_assign(root, &r); return 1; } ymp_assign_2exp(&tmp, b); ymp_sub(&tmp, &tmp, &r); ymp_mul(&tmp, &tmp, &tmp); if (ymp_compare(source, &tmp) == 0) { if (root) ymp_assign(root, &r); return 1; } return 0; }

---