普通に $ brew install mysql とするとmysql8がインストールされてしまいます。 mysql5のデータベースを8にマイグレートする余裕などありません。 mysql5.7をインストールするには以下のようにします。 $ brew install mysql@5.7 コマンドパスを通すため、.b…

アルゴリズムの実際の計算をもう少し詳しくみていきます。 が成り立つかどうかの計算をみていきます。 まず、この式はがreductionの最終結果がxのみの多項式で分母と分子があるということを意味します。 lは奇数なのでにはyは入らないです。 そして、で割り…

macOS で git gcしたときに、warning: unable to unlink '.git/objects/ff/xxx': Operation not permitted というメッセージが表示される現象の対応方法です。 .git ディレクトリに移動して、以下のコマンドを打ちます。 chflags -R nouchg * error: failed …

楕円曲線の点(x, y)をn倍した点(n torsion point)はx,yの具体的な多項式で表せます。 としたとき、n倍点の座標(X, Y)は以下となります。 はdivision polynomialと呼ばれており、以下の漸化式で定義されます。 はmが奇数のとき、xの任意次数の関数。 mが偶数…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその１ - Pebble Coding の続きです。 を素数 l=2, 3, 5, ...について計算するアルゴリズムは以下の通りです。 素体, 楕円曲線とします。 まず、l=2の場合は、の値が1かどうか調べます。 ここでgcdはxの素…

中国剰余定理とは、2式の場合を互いに素とするとき、 を満たす整数xがの範囲内にただ一つ存在するというものです。 xの求め方はこうです。 まずを満たす(p, q)のセットを一つ求めます。 以下のアルゴリズムを用います。 37x+10y = 1 を拡張されたユークリッ…

37と10は違いに素なので、は整数解(x, y)を持ちます。 この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。 具体的には、の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。 とおきます。 とおきます。 とおきま…

こちら 多項式の割り算、商と余り - Pebble Coding の1変数多項式の商と余りを拡張し、素体上での計算をみてみます。 (nがxの最大次数)を、 (mがxの最大次数)() で割ることが考えるとき、以下のようにしてxの最大次数を下げていけばよさそうです。 例えば、 …

xcode address sanitizerでヒープ破壊箇所を検出してみます。 - (void)viewDidLoad { [super viewDidLoad]; uint8_t* a = malloc(16); memset(a, 0, 17); } 普通に実行してみると、 どこで破壊されているのか分かりませんね。 これをソースの行レベルで検出…

素体 (pは素数)をpythonで実装してみました。 なお、計算効率については考慮していません。 #!/usr/bin/env python3 class F: def __init__(self, p, v): self.p = p self.v = v self.normalize() def normalize(self): self.v = self.v % self.p def __add_…

を解きます。 これを満たすaは0以上、未満に一つしかありません。 とおけます。 とおけます。 が解となります。 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語

1変数多項式の四則演算をpythonで実装してみました。 係数は整数の範囲としています。 加算、減算、乗算、剰余を実装します。 剰余では割られる側の最大次数の係数は1のみに限定します。 以下、実装です。 #!/usr/bin/env python3 from fractions import gcd…

多項式の割り算、商と余りの求め方をみていきます。 1変数xの２つの多項式A(x), B(x)を考えます。多項式の係数は全て整数とします。 次数の大きい方をA(x), 次数の少ない方をB(x)とし、 ここでは次数の少ない方の多項式の最大次数の係数は1としておきます。 …

２つの整数の最大公約数を求めるアルゴリズムとしてユークリッドの互除法があります。 ２つの整数を割り算して余りを求める操作を繰り返し、余りが0になったら終了するアルゴリズムです。 pythonで2つの整数の最大公約数を求める関数gcd()を実装したのがこち…

有限体の楕円曲線の有理点の数からZ関数を導いていきます。 定理1 qを素数とし、有限体上の楕円曲線Eの有理点について、 とおきます。 また、の解を複素数とおきます。 すると、有限体 上の楕円曲線Eの有理点の数は、 となります。 証明は省略します。 ここ…

ラグランジュの定理 Gが有限群、 ならgの位数は群Gの位数の約数である。 この定理より、以下の定理が導かれます。 gが群Gの位数n>0の元でなら、の位数は である。 例: (65537は素数です)の場合、 の位数は

中国の剰余定理 で m, n は互いに素とする。 つまり、 を満たすはの範囲にただ一つ存在する。 中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語 これは、２つの値の場合ですが、もっと拡張します。 を異なる素数とし、 ... を満たすxはの範囲…