RSA key gen: Illegal instruction (core dumped)

[Andreas Schuldei <andreas_(_at_)_schuldei_(_dot_)_org>]

I see core dumps like this 

Generating RSA private key, 1024 bit long modulus
............++++++Illegal instruction (core dumped) 

regularly when I try to generate RSA keys of any kind.

It does not matter if it is OpenSSH initializing itself (or regenerating its
key hourly) or if I try to generat keys using openssl.

I somehow doubt that it is software, because it would render openssh useless
for many people. Am I seeing problems with my FPU? Has anyone else seen
problems like this?