素因数分解アルゴリズム(因数分解が既知の隣数から導く)

Chirp Z 変換で素因数分解

メモ

2以外の底を使った離散フーリエ変換の素案

ずっと素因数分解でフェルマーの定理を軸に累乗数の指数をいかに回してa^2=1を作るか考えていましたが、よく考えてみたら一度になるべくたくさんの数で割って余りを求めるのが手っ取り早いだろうと思うに至りました。普通の数だと大き過ぎて無理ですが、そういえばmod pなら行けるやんと。

【素因数分解】指数総当たり計算のショートカット法

一般数体ふるい法で使うふるいの実装トライアル