BETA

多項式の係数のみ剰余を取る方法(Sympy)

投稿日:2019-11-09
最終更新:2019-11-09

コード

import sympy as sym  

def mod_coeffs(f, p):  
    f_vars = list(f.free_symbols)  
    f_coeffs = [f.coeff(var) for var in f_vars]  
    f_coeffs_mod = sym.Mod(sym.Matrix(f_coeffs), p)  

    ret = f_coeffs_mod.transpose() * sym.Matrix(f_vars)  

    return ret[0, 0]  

f = 123*x + 456*y  

print(mod_coeffs(f, 13)) # 6*x + y  

条件

  • 次数は1次のみ(定数や2次以上の多項式は正しい結果がでません)

背景

多項式の剰余をPythonの代数演算でよく用いられているSympyを用いて計算すると以下のようになります。

例1

数式

\begin{align}
f(x, y) = 123x + 456y \mod 13
\end{align}

コード

import sympy as sym  

x, y = sym.var("x y")  
f = 123*x + 456*y  

f_mod = sym.Mod(f, 13)  
print(f_mod)    # 出力: Mod(123*x + 456*y, 13)  

上にもあるように、変数の入った剰余は出力がMod(123*x + 456*y, 13)というようになります。そしてこのf_modxyを代入すると剰余の結果が返ってきます。便利ではあるのですが、次のようなことがしたいときに困りました。

例2

数式

\begin{align}
f(x, y) &= 123x + 456y \mod13 \\
g(x, y) &= 789x + 1011y \mod13 \\
\end{align}
とした後に
\begin{align}
h(x, y) &= f(x, y) + g(x, y) \mod13 \\
&=912x + 1467y \mod13 \\
&\equiv2x + 11y \mod13
\end{align}

コード

import sympy as sym  

x, y = sym.var("x y")  
f = 123*x + 456*y  
g = 789*x + 1011*y  

f_mod = sym.Mod(f, 13)  
g_mod = sym.Mod(g, 13)  

print(f_mod, g_mod)  
 #出力: Mod(123*x + 456*y, 13) Mod(789*x + 1011*y, 13)  
print(f_mod + g_mod) #出力: Mod(123*x + 456*y, 13) + Mod(789*x + 1011*y, 13)  

最後の行を見てみると、Mod(123*x + 456*y, 13) + Mod(789*x + 1011*y, 13)となっているのがわかります。同様に代入してあげると剰余の結果はわかるのですが、その目的以外に使えなくなってしまいます。

この回避策として、$h(x, y)$を計算してから剰余を取る方法もありますが、演算回数が多くなると係数が多くなってしまいメモリの無駄です。
ということで係数だけ剰余を取ってくれないのかなと思ったのですが、ググっても見つからなかったので作ってみました。より良い方法がありましたら教えてください。<(_ _)>

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

@syakooのブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう