GMP_ECMによる素因数分解

概要

(岩波書店『科学』編集部 2024) にあった”RSAと素因数分解”に GMP-ECM が紹介されていたので、実際に動かしてみた。

GMP-ECMの準備

ZIMMERMANN Paul / ecm · GitLab を利用した。 

git clone https://gitlab.inria.fr/zimmerma/ecm.git

INSTALL.dev にある記載のように実行して、コンパイルした。 

cd ecm
autoreconf -i
./configure
make -j4
make check

コンパイル後に実行ファイル ecm がフォルダに生成されている。

素数の生成

2つの素数を生成して、素因数分解のための合成数を用意する。 

import sympy

N = 100
p1 = sympy.randprime(2**(N+1), 2**(N+2))
p2 = sympy.randprime(2**(N+1), 2**(N+2))

print(f'{p1=}')
print(f'{p2=}')
print(f'{p1*p2=}')

p1=2869069113607969685726929882709
p2=3871722605512470843352197003061 
p1*p2=11108239743933603608670116823884965417896735085597594043972249

2つの素数p1, p2から合成数: 11108239743933603608670116823884965417896735085597594043972249 を得た。

実行

GMP-ECM の使い方 の USAGE を参考にコマンドのオプションの引数を決定した。未知の素因数の桁数が30桁なので表から以下の値を採用した。

  • -c(反復): 500
  • B1: 250000

結果の最後部をみると、合成数が元の2つの素数に分解されていることが分る。 

echo 11108239743933603608670116823884965417896735085597594043972249 | ./ecm -c 500 250000


GMP-ECM 7.0.6-dev [configured with GMP 6.3.0, --enable-asm-redc, --enable-assert] [ECM]
Input number is 11108239743933603608670116823884965417896735085597594043972249 (62 digits)
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:4010257250
Step 1 took 77ms
Step 2 took 70ms
Run 2 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2451171661
Step 1 took 70ms
Step 2 took 69ms
Run 3 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2557109986
Step 1 took 70ms
Step 2 took 69ms

...

Run 18 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:504643144
Step 1 took 70ms
Step 2 took 70ms
Run 19 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2975852467
Step 1 took 70ms
Step 2 took 71ms
********** Factor found in step 2: 2869069113607969685726929882709
Found prime factor of 31 digits: 2869069113607969685726929882709
Prime cofactor 3871722605512470843352197003061 has 31 digits

参考文献

岩波書店『科学』編集部, ed. 2024. 科学2024年3月号［雑誌］. Kindle版. 岩波書店. https://lead.to/amazon/jp/?op=bt&la=ja&key=B0CW1DZS1W.

ラゲール法による多項式の求解

概要

(長田 2024) の第4章代数方程式:1ラゲール法をもとに実装する。以下のサイトも参考にした。

  1. ラゲール法による求根アルゴリズム～Pythonコード付き～ – LASCODE

方針

根 1, 2, 3, 4, 5 を持つ5次の多項式を解くことにする. 

import numpy as np

p5deg = np.polynomial.polynomial.Polynomial.fromroots([1, 2, 3, 4, 5])
print(p5deg)

-120.0 + 274.0·x - 225.0·x² + 85.0·x³ - 15.0·x⁴ + 1.0·x⁵

実装

def laguerre(f, x0, delta=0.01, max_iter=100):
    ans = []

    f = f.copy()
    while 1 < f.degree():
        n = f.degree()
        df = f.deriv()
        ddf = df.deriv()

        x = x0
        iter = 0
        while not (np.abs(f(x)) < delta):
            numerator = n * f(x)
            denom_plus = df(x) + np.sqrt((n-1)**2 * df(x)**2 - n*(n-1)*f(x)*ddf(x))
            denom_minus = df(x) - np.sqrt((n-1)**2 * df(x)**2 - n*(n-1)*f(x)*ddf(x))

            denominator = denom_plus if np.abs(denom_minus) < np.abs(denom_plus) else denom_minus
            x -= numerator / denominator

            if np.abs(f(x)) < delta:
                break
            if max_iter < iter:
                break
            iter += 1

        ans.append(x)
        f = f // np.polynomial.polynomial.Polynomial.fromroots([x])

    if f.degree() == 1:
        ans.append(-f.coef[0])
    return ans

検証

5つの根の近似値が得られた。 

roots = laguerre(p5deg, x0=0, delta=0.00001)
print(roots)

[1.0000000000000002, 1.9999999999999907, 3.0000000000000107, 4.000000000000017, 4.999999999999981]

参考文献

長田 直樹. 2024. 数値解析 非線形方程式と数値積分. 単行本. 現代数学社. https://lead.to/amazon/jp/?op=bt&la=ja&key=4768706266.

ラグランジュ基底多項式とSympy

以下の多項式をラグランジェ基底多項式と呼ぶ。

\begin{equation}
L_k(x) := \frac{\Pi_{j \neq k} (x-x_j)}{\Pi_{j \neq k} (x_k-x_j)}
\end{equation}

手計算では大変そうなので、sympyを使ってみた。 Polynomials Manipulation Module Reference – SymPy 1.12 documentation を参考にすると、 3次のラグランジェ基底多項式 \(L_3(x)\) は下記のようになる。 

import sympy
from sympy.core import Add, Mul, symbols
from sympy.abc import x, y

n = 3
X = symbols("%s1:%s" % ('x', n+1))
# Y = symbols("%s1:%s" % ('Y', n+1))

numert = Mul(*[x - X[i] for i in range(n)])

i = 2
numer = numert/(x - X[i])
denom = Mul(*[(X[i] - X[j]) for j in range(n) if i != j])
sympy.latex(numer / denom)

\frac{\left(x - x_{1}\right) \left(x - x_{2}\right)}{\left(- x_{1} + x_{3}\right) \left(- x_{2} + x_{3}\right)}

\[ \frac{\left(x – x_{1}\right) \left(x – x_{2}\right)}{\left(- x_{1} + x_{3}\right) \left(- x_{2} + x_{3}\right)} \]

matplotlibによるアニメーション

下記を参考にmatplotlibのアニメーションを試してみた。

  1. matplotlib.animationでグラフをアニメーションさせる – Qiita
  2. [Python/matplotlib] FuncAnimationを理解して使う – Qiita

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation

fig = plt.figure()

MAX_FRAME = 100

def plot(frame):
    """."""
    plt.cla()
    xs1 = np.arange(0, 10, .01)
    ys1 = np.sin(xs1)
    xs2 = np.arange(0, 10.0 / MAX_FRAME * frame, .01)
    ys2 = np.sin(xs2)
    _ = plt.scatter(xs1, ys1)
    _ = plt.scatter(xs2, ys2)

ani = animation.FuncAnimation(fig, plot, frames=range(MAX_FRAME), interval=100)
ani.save(f, writer="imagemagick")
plt.close()
f
matplotlib_anim.gif

udev

サスペンドからの復帰可能デバイスの設定

下記の2つのページを参考に設定する。

  1. 20.04 – Mouse movement wakes system up from sleep if the USB adapter is not reconnected – Ask Ubuntu
  2. 復帰トリガー – ArchWiki

具体的にはマウスによるサスペンドからの復帰を阻止したい。まず、マウスのデバイス情報を lsusb で取得する。 

lsusb


Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 001 Device 007: ID 25a7:fa10 Areson Technology Corp 2.4G Wireless Receiver
Bus 001 Device 004: ID 2be8:0002 ARCHISS PTR87 ARCHISS PTR87
Bus 001 Device 002: ID 05e3:0608 Genesys Logic, Inc. Hub
Bus 001 Device 006: ID 0b05:19af ASUSTek Computer, Inc. AURA LED Controller
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub

25a7:fa10 がマウスに対応する情報である。ワイヤレス・マウスであるため、レシーバがUSB機器として認識されている。 25a7 がベンダーIDで fa10 が製品IDとなる。

/etc/udev/rules.d に wireless_mouse.rules を作成する。 

ls /etc/udev/rules.d


keyboard.rules
wireless_mouse.rules

wireless_mouse.rules に下記を記載する。 idVendor にベンダーID、 idProduct に製品IDを割り当てる。 ATTR{power/wakeup} がサスペンド時に考慮される機器の設定でこのマウスでは復帰させたくないため diabled を設定する。 

ACTION=="add", SUBSYSTEM=="usb", DRIVERS=="usb", ATTRS{idVendor}=="25a7", ATTRS{idProduct}=="fa10", ATTR{power/wakeup}="disabled"

PCを終了し、起動すれば設定が反映されサスペンド時にマウスでの復帰は行なわれなくなる。

elispでの検索とその後の処理

org2blogでのorg-roamのノードの投稿 を実装した際に得た知見を書き出す。

検索

正規表現での検索は re-search-forward で行なう。この関数を実行するとカーソルが移動するため、 必要に応じて save-excursion などで元のカーソル位置などを保存する。

下記をテスト用の文字列とする。(■はカーソル位置) 

■abc-123-ABC

カーソル位置で下記のLispを実行する。 

(defun test-search ()
  (re-search-forward "\\(abc\\)-\\(123\\)-\\(ABC\\)"))

カーソルはマッチした正規表現の後部に移動する。 

abc-123-ABC■

置換

テスト用の文字列の 123 を 456 に変換してみる。 

(defun test-replace ()
  (re-search-forward "\\(abc\\)-\\(123\\)-\\(ABC\\)")
  (replace-match "\\1-456-\\3")) 


abc-456-ABC■

削除

削除はマッチした文字列を空文字に置換することで実現できる。 

(defun test-delete-1 ()
  (re-search-forward "\\(abc\\)-\\(123\\)-\\(ABC\\)")
  (replace-match ""))

また、マッチ部分の位置情報を利用しても可能である。 

(defun test-delete-2 ()
  (re-search-forward "\\(abc\\)-\\(123\\)-\\(ABC\\)")
  (delete-region (match-beginning 0) (match-end 0)))

match-beginning と match-end の引数は正規表現のグループ番号なので、それを指定することでグループ単位での位置情報も利用できる。 abc-123-ABC の 123 を削除するには下記のように指定する。 

(defun test-delete-3 ()
  (re-search-forward "\\(abc\\)-\\(123\\)-\\(ABC\\)")
  (delete-region (match-beginning 2) (match-end 2))) 


abc--ABC■

org2blogでのorg-roamのノードの投稿

テスト (Shalev-Shwartz and Ben-David 2009)

関数

org-roam のノードを wordpress に投稿するための関数を作成した。

単純に org2blog-buffer-post-publish で作成されたプロパティを移動するだけ。 

(defun ks-post-to-wordpress ()
  (interactive)
  (let ((snow (format-time-string (org-time-stamp-format t t) (org-current-time)))
        (rtitle (org-make-options-regexp (list "title" "TITLE")))
        (rdate (org-make-options-regexp (list "date" "DATE")))
        (rblog   (org-make-options-regexp (list "blog" "BLOG")))
        (rpostid (org-make-options-regexp (list "postid" "POSTID")))
        (rorb2blog (org-make-options-regexp (list "org2blog" "ORG2BLOG")))
        line1 line2)
    (save-excursion
      (goto-char (point-min))
      (if (re-search-forward rorb2blog nil t 1)
          (progn
            (re-search-forward rdate nil t 1)
            (replace-match (concat "#+\\1: " snow))
            (org2blog-buffer-post-publish))
        (if (re-search-forward rtitle nil t 1)
            (progn
              (insert "\n\n")
              ;; TITLEプロパティの下にORG2BLOGプロパティを
              (insert "#+ORG2BLOG:\n")
              ;; TITLEプロパティの下にDATEプロパティを
              (insert (concat "#+DATE: " snow))
              ;; 投稿
              (org2blog-buffer-post-publish)

              ;; ここからファイル上部に記載される BLOG, POSTID を移動する.
              (goto-char (point-min))

              ;; BLOG を退避、削除する.
              (re-search-forward rblog nil t 1)
              (setq line1 (match-string-no-properties 0))
              (delete-region (match-beginning 0) (match-end 0))
              (delete-char 1)
              ;; POSTID を退避、削除する.
              (re-search-forward rpostid nil t 1)
              (setq line2 (match-string-no-properties 0))
              (delete-region (match-beginning 0) (match-end 0))
              (delete-char 1)

              ;; BLOG, POSTID を追加する.
              (re-search-forward rdate nil t 1)
              (insert "\n")
              (insert line1)
              (insert "\n")
              (insert line2)))))))

参考文献

Shalev-Shwartz, Shai, and Shai Ben-David. 2009. Understanding Machine Learning. Cambridge University Press. https://doi.org/10.1017/cbo9781107298019.

tmux

#+ORG2BLOG

基本操作

prefix キーを C-t とする。

通常時

キーバインド 動作
C-t C-[ コピーモードに以降する
C-t C-] クリップボードの文字列を貼り付ける

コピーモード

キーバインド 動作
C-t 2 マーク
y 選択範囲をクリップボードにコピー

設定

設定ファイル .tmux.conf の再読込は tmux source-file ~/.tmux.conf で実行する。

Tmux Pluging Manager: tqm

まずはこれをインストール. 

git clone https://github.com/tmux-plugins/tpm ~/.tmux/plugins/tpm

下記のように .tmux.conf に記載。 

#===================================
# tpm - Tmux Plugin Manager
#===================================

# Plugins
set -g @plugin 'tmux-plugins/tpm'

# Initialize TMUX plugin manager 
# (keep this line at the very bottom of tmux.conf)
run '~/.tmux/plugins/tpm/tpm'

Plugins

prefix-I でインストール.

Tmux-yank

x1, wayland で自動的にcopyコマンドを切り替えてくれる。wl-clipboard, xsel, xclip をインストールすること。

  1. prefix+[ で選択モードになる
  2. Ctrl-2 で領域選択開始
  3. y で領域をコピー

下記のように .tmux.conf に設定。 

set -g @plugin 'tmux-plugins/tmux-yank'