格子を用いた素因数分解法について

以下である程度詳しく書いていますので，気になる方はこちらを見てみてください．

当該DLL及びSOファイルについて

GitHubにて配布しています．

何が入っているか

同梱されているC++ソースで言うところのlattice_factorization関数，入力された合成数を格子を利用した素因数分解法で素因数分解する関数が利用可能になっています．

使い方

第一引数にビットサイズで入力するか否か，第二引数に素因数分解したい合成数もしくはそのビットサイズで，第三引数にアルゴリズムの進捗情報を出力するかを入力します．
言葉だけでは分からないと思うので，Pythonをもちいた例を見てみましょう．

例えば，ランダムに生成した$50$ビットのRSA型合成数を素因数分解したいときは以下の様にします．

Linuxの場合

import ctypes

LatFact = ctypes.cdll.LoadLibrary("./libfact.so")
LatFact.lattice_factorization.restype = ctypes.POINTER(ctypes.c_longlong)
LatFact.lattice_factorization.argtypes = ctypes.c_int, ctypes.c_char_p, ctypes.c_int
a = LatFact.lattice_factorization(1, "50".encode('utf-8'), 1)

Windowsの場合

import ctypes, os

os.add_dll_directory(os.getcwd())
LatFact = ctypes.cdll.LoadLibrary("lat_fact.dll")
LatFact.lattice_factorization.restype = ctypes.POINTER(ctypes.c_longlong)
LatFact.lattice_factorization.argtypes = ctypes.c_int, ctypes.c_char_p, ctypes.c_int
a = LatFact.lattice_factorization(1, "50".encode('utf-8'), 1)

ビットサイズで入力するので第一引数には1，$50$ビットなので第二引数に50，とりあえず情報を出力することにして第二引数に1をそれぞれ入れています．これを実行すると以下の様になります．

1 pairs were found. (800 pairs are needed.)
2 pairs were found. (800 pairs are needed.)
3 pairs were found. (800 pairs are needed.)
4 pairs were found. (800 pairs are needed.)
5 pairs were found. (800 pairs are needed.)
6 pairs were found. (800 pairs are needed.)
7 pairs were found. (800 pairs are needed.)
...
526 pairs were found. (800 pairs are needed.)
527 pairs were found. (800 pairs are needed.)
528 pairs were found. (800 pairs are needed.)
X = 326468535471921, Y = 326468535471921
X = 304425036830297, Y = 304425036830297
X = 323034962977825, Y = 581779306839208
X = 74983483268960, Y = 829830786548073
529 pairs were found. (800 pairs are needed.)
530 pairs were found. (800 pairs are needed.)
X = 703919048958093, Y = 546415898737774
==============================
N = 904814269817033, bit size = 50
c = 5.0, beta = 2.0
N = 20347843 * 44467331
loop times = 15266
number of sr-pairs = 530
==============================
#Vector = 34492

情報が邪魔だと思ったら第三引数に0を入れてみてください．尚，以降はWindowsの場合は省略し，Linuxの場合の例だけ記載します．

import ctypes
import numpy as np

LatFact = ctypes.cdll.LoadLibrary("./libfact.so")
LatFact.lattice_factorization.restype = ctypes.POINTER(ctypes.c_longlong)
LatFact.lattice_factorization.argtypes = ctypes.c_int, ctypes.c_char_p, ctypes.c_int
a = LatFact.lattice_factorization(1, "50".encode('utf-8'), 0)
a = np.array([a[0], a[1]], int)

print(a)

以下は出力例です．

[22907887 44937131]

ただ，$50$ビットのランダムな整数を素因数分解してもあまり面白くありません．だいたい，$50$ビットのRSA型合成数を生成することなんてPythonでできます．自分で合成数を指定したいという場合は，第一引数に0を入れます．

import ctypes
import numpy as np

LatFact = ctypes.cdll.LoadLibrary("./libfact.so")
LatFact.lattice_factorization.restype = ctypes.POINTER(ctypes.c_longlong)
LatFact.lattice_factorization.argtypes = ctypes.c_int, ctypes.c_char_p, ctypes.c_int
a = LatFact.lattice_factorization(0, "157975686601668709".encode('utf-8'), 0)
a = np.array([a[0], a[1]], int)

print(a)

以下はその出力です．

[178987561 882607069]