Standard bodies and organizations are pushing for increas-ingly larger RSA keys. Today, RSA keys range from 512 bits to 2048 bits and some bodies envision 4096-bit RSA keys in the near future. This paper devises a new methodology for generating RSA keys. Con-trary to what is usually done, the key generation is divided into two phases. The first phase is performed off-line, before the input parame-ters are even known. The second phase is performed on-line by the smart card once the input parameters are known, and is meant to be very fast. Compared to the fastest reported method ([4]), our solution —or more precisely the on-line phase thereof, is conceptually more advanced and achieves extreme execution speeds as generating 1024-bit or 2048-bit RSA keys amounts to practical running times lowered by several orders of magnitude. Moreover, our technique achieves on-line generation of RSA keys of arbitrary length from a small set of seeds computed during the off-line phase. Subsequently, in addition to be fast and flexible, our solution also features attractively low memory requirements.