US patent 8218760, Joye, compressed RSA keys

Text of the patent

No reported enforcement attempts. Priority date 2007.02.27. "The general inventive idea consists in fixing a large part of an RSA modulus N (e.g., up to its top half in the preferred embodiment) so that the primes forming N can be drawn arbitrarily from an interval (and not tried incrementally as was suggested in previous proposals)."

Prior art:

1998 Lenstra "Generating RSA moduli with a predetermined portion": "If L-|p| is chosen larger, then q can be chosen at random from among the primes in a much wider range".
2000 Bernstein "A secure public-key signature system with extremely fast verification": "Generate a uniform random number p between 4 2^765 and 5 2^765 satisfying p mod 40 = 3; repeat until p is prime. Generate a uniform random number q between ceil(2^800 pibar/p) and ceil(2^800(pibar+1)/p) satisfying q mod 40 = 7; repeat until q is prime."
2003 Bernstein "Compressing RSA keys and signatures": "Reduce keys to 800 bits with fast key generation; or 768 bits with fairly fast key generation".