一般数体篩法実装実験(2)--ミニ素因数分解·ミニ素数判定

摘要

素因数分解問題などにおける篩型のアルゴリズムでlarge primeを用いた高速化が用いられている．Large prime部分の処理の高速化のためには篩に用いる因子基底の上限を若干越える数からその自乗ぐらいまでの数という，分解対象の数に比べてかなり小さいが，しかし試し割では困難な素因数分解処理や素数判定処理を必要とする．本稿では，その"ミニ"素因数分解や素数判定処理を実装レベルで高速化した結果を報告する．