I started with:
  512-bit:     16338
 1024-bit:     51020
 2048-bit:    142718

My x86-32
  512-bit:      2864
 1024-bit:     10615
 2048-bit:     41807

My SSE2
  512-bit:      2168
 1024-bit:      7727
 2048-bit:     33163