有限体上の多項式の既約性判定アルゴリズム

（この記事はQiitaからの転載です） 暗号や符号などで既約多項式がよく使われることは誰しも知っていると思う。 でも、じゃあその既約多項式ってどうやって見つけてくるの？ということはよくわからない。 そこで私が調べた結果わかったことを記事にしてみようと思った。 今回紹介するのは、Ben-Orの（多項式の）既約性判定テストの方法だ。 私が知っていたのは手元に以下の本を持っていたからだ。 計算機代数の辞書的な本に相当するが、数学系のプログラミングをしている人にはぜひともおすすめしたい。ネットで調べて出てくるのはアイゼンシュタインの判定法とかだが、計算機で使う判定法とはあまり関係ない。 （値段がすごいことになってますが、自分が買ったときは1万円行かなかったと思います。ノイキルヒの代数的整数論より高い？） この本には以下のような疑似コードが書かれている。 １．ランダムに有限体上の多項式を取り、それを