n次元実ベクトルxに対し，xとの標準内積をとると0になるn次元非零整数ベクトルmをxのinteger relationという．このinteger relationを見つけるアルゴリズムは，与えられた実数が代数的数であるかの判定や，円周率などの数学定数の任意精度近似値の導出などへの応用がなされている．また近年では数値解析の分野においても，準モンテカルロ法による数値積分への応用が期待されている．
本発表ではJ. Hastadらによって提案されたHJLS法[1]を紹介する．HJLS法はグラムシュミットの直交化を利用してxと直交する方向の整数ベクトルmを構成する方法で，探索範囲にinteger relationがあればそれを返し，無ければその範囲には無いことを示す多項式時間アルゴリズムである．発表ではアルゴリズムの動作と正当性，および多項式時間で判定が終了することについて説明する．

[1] J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput., Vol. 18, pp. 859-881, 1988.