「どんな素数でも一瞬で素因数分解する方法」の話

どんな素数でも一瞬で素因数分解する方法 - 西尾泰和のはてなダイアリーという記事で知ったネタなのですが、冒頭の「素数」という文字がごちゃごちゃして読みにくいからと読み飛ばした上で「『素因数分解』と書いてあるからきっと整数の話なんだろうな」と脳内補完してしまうと見事にだまされる羽目になります*1。私も25秒ぐらいだまされたまま過ごしてしまいました。
しかしながら冷静に反省してみると、素因数分解の定義からして0は素因数分解できないので、「一瞬で素因数分解する方法」の入力範囲が整数（の全体）であるはずがなく、従って「素数」という文字をちゃんと読まなかったとしても文字数が2文字である時点で怪しいと看破出来なくてはならなかったのです。うむ、私もまだまだ功夫が足りていませんな。

元記事に

「分解」という言葉の定義は書かれていませんが「正の整数aは素数の積に分解することができる」ということは、素数であっても1であっても素数の積に分解できるということ。つまり「素数は1個、1は0個の素数の積に分解される」という意味に取るしかないんじゃないかなと思います。

どんな素数でも一瞬で素因数分解する方法 - 西尾泰和のはてなダイアリー

とありますが、その解釈で問題ありません。大雑把な言い方をすると、通常数学では「1個の数の積はその数自身」「0個の数の積は1」と定められていますので。（例えば、1の階乗も0の階乗も1と定義されています。）

元記事にツッコミを入れている別の記事（http://shaga.sakura.ne.jp/daily/20090203.html#p03）にて、Wikipediaで「積」という言葉の意味を調べた結果を基に「素数を素因数分解はできない」と主張しているのを発見。
きちんと数学者が監修して作られた岩波数学辞典の記述について、どこの誰が書いているとも知れないWikipediaの記述を根拠として否定するというのは、Wikipediaが過度に信頼され過ぎているのか、それとも岩波数学辞典やその背後にいる「数学者」という存在がそれだけ信頼されていないということなのでしょうか。
あと、数学辞典ではない普通の辞典で「分解」という言葉を引いた結果についても言及しておられますが、ある単語の日常的な用法と数学における用法が厳密に一致しないというのはよくあることです。「分解」という言葉の日常的な意味とは関係なく「素因数分解」という用語は数学的に定義されていて、その定義に基づくと素数だろうと1だろうと確かに素因数分解できますので、数学以外の場面における「分解」という言葉の意味を根拠に1や素数が素因数分解できないと言われても困ってしまいます。「分解」という言葉を使うと紛らわしい、という主張であればある程度は同意しますが。

なお、もっとマニアックな話としては、「入力した数をそのまま出力する」というアルゴリズムは果たして本当にいつでも「一瞬で」実行できるのだろうか、という観点もあります。
例えば、数の書かれた紙を渡されてその数を読み上げるという実装を採用した場合、素数が天文学的桁数になった際などに、紙に書かれた数を認識する時間やその数を読み上げる時間が到底「一瞬」とは言えないほどになってしまいます。つまり、件の方法が「一瞬で」実行できるかどうかは数の入出力の形態の定義、もっと大げさに言うとそのアルゴリズムを記述するための計算モデルの定義に依存すると考えられるわけです。

最後に余談。某友人には素数（もとかず）君という息子さんがいますが、彼のことを分解しちゃ駄目ですからね。

*1:初めから全くだまされなかった賢明な方のために補足しますと、元記事のアンケート結果にある40.5%以外の方々は「どんな整数でも一瞬で・・・」という設問だと勘違いしたと思われるわけです