一方向関数

大きな素数を2つ掛ければ、積は一瞬で求まる。その積を素因数分解しようとすると、桁数によっては何年も待つことになる。一方向関数はハッシュ、パスワード保管、電子署名の土台である。パスワードそのものではなくハッシュを保存しておけば、データベースを盗んだ者の手に入るのは、逆向きには動かせない関数だけになる。

一方向関数が存在することは、まだ誰にも証明されていない。あくまで仮定であり、証明できればPとNPが等しくないことも同時に示される。暗号は、信じてはいるが示せないものの上に成り立っているわけで、証明を好む分野としては居心地の悪い立場である。