Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed boost in private-key operation, with little (conjectured) reduction in security for small-enough $k$; the effort saving relative to 2-primes RSA is next to $(k/2)^2$, assuming standard modular multiplication techniques and huge prime factors; and $k$ CPUs can be put to near full use. In early 2000, Compaq was publicizing its use of Multi-prime RSA. There has been earlier realization it was possible and had an interest, and even some uses at least at a prototype stage (I'll describe some).

The question is: Who first published that technique, mentioning its interest?

From a patent standpoint the question appears all settled: the inventors are Thomas Collins, Dale Hopkins, Susan Langford, and Michael Sabin, describing Multi-prime RSA in patent US 5,848,159 following provisional application 60/033,271 filed Dec. 9, 1996, and patent US 7,231,040. Patenting is a slow process: one European version of these patents, EP0950302, was still under examination in 2013 if my understanding is correct. I'm NOT wanting to be part of a patent war, and that's why I have waited until the end of the opposition period to ask this question here.

Ronald Rivest, Adi Shamir, and Leonard Adleman themselves, in their patent US 4,405,829 filed Dec. 14, 1977, on a Cryptographic communications system and method we now know as RSA, already mention:

the present invention may use a modulus $n$ which is a product of three or more primes (not necessarily distinct). Decoding may be performed modulo each of the prime factors of $n$ and the results combined using "Chinese remaindering" or any equivalent method to obtain the result modulo $n$

However it is not clear that the motivation or effect is a speedup at a given security level, which matters to the present question. Here are some of the arguments used to repel that prior art during the lengthy examination process of EP0950302.

Using CRT for a speedup in 2-factors RSA has been known since at least 1982, with the publication by Jean-Jacques Quisquater and Chantal Couvreur of Fast decipherement algorithm for RSA public-key cyptosystem. But the article has no mention of more than two factors.

By 1993-1994, several persons in the European crypto/Smart Card microcosm fully realized the interest of Multi-prime RSA. When asked in mid-December 1993 to inventory valuable knowledge about RSA that our company had, with attribution, I wrote that I had learned about RSA with 3 primes from Professor Jean-Jacques Quisquater on November 30, 1993. The context was trying to make a not-unbearably-slow software-only implementation of RSA in an 8-bit Smart Card intended as a signing tool for medical acts. The technique was described in the (confidential) answer to an official tender made in March 1994, with the technique described to experts of the jury, including Marc Girault, who went as far as confirming our arguments that given the state of the factoring art, our proposal to use 4-factors 768 bit keys, and 3-factors 528-bit keys, was reasonable. I was told some year(s) later (and can't be sure) that the winners of that early CPS tender used similar techniques. I was then working under at least a moral non-disclosure agreement about such speedup techniques; and my memo, or the work of Jean-Jacques Quisquater in that area, remained unpublished for years AFAIK.

Also, the aforementioned patents US 5,848,159 and US 7,231,040 mention a document RSA Moduli Should Have 3 Prime Factors, August 1996, cited by the examiner, with attribution to Captain Nemo (sic! Depending on source, either Captain or the date is missing). The title seems very relevant, but I have been unable to locate it (which could be essential to an answer).

Update: the earliest published implementation of the RSA private-key function, using the CRT, and clearly engineered for more than two factors, that I located so far, is Michael Scott's MIRACL library version 3.23, released on January 1994. File DECODE.C (modification date October 1993) contains:

np=2; /* two primes - could be used with more */

However I located no accompanying indication that using more than two factors allows a speedup at constant modulus size, or with similar security.

  • $\begingroup$ @DmitryKhovratovich: Thank for your link, it's important to notice that the RSA patent contains all the features attribuated to other inventors. Snipped for the RSA pattent 1977. "... In alternative embodiments, the present invention may use a modulus n which is a product of three or more primes (not necessarily distinct). Decoding may be performed modulo each of the prime factors of n and the results combined using "Chinese remaindering" or any equivalent method to obtain the result modulo n." $\endgroup$ Commented Feb 4, 2015 at 8:34
  • 2
    $\begingroup$ @fgrieu: Not Catherine but Chantal Couvreur, she was in same industrial group, and a good mathematician. The paper she published with JJQ as a co-author is great! But experiment with 3 or more RSA factors was know by everyone and is a "secret de polichinelle". In my compagny we trained with 3 modulus factors on embedded systems with very low ressources in the $90^{ies}$. $\endgroup$ Commented Feb 4, 2015 at 8:40
  • $\begingroup$ @Robert NACIRI: I now have put the correct first name (my mistake, JJQ had given me the correct one, and details about how an early version of the paper, not published, mentioned more than two factors). $\;$ I concur with you that the interest of RSA with 3 factors as a speedup technique was known by those who cared to listen or think in 1995, perhaps earlier; but the question asks: who first published on that subject, turning that secret de polichinelle into public knowledge? $\endgroup$
    – fgrieu
    Commented Feb 4, 2015 at 10:19
  • 2
    $\begingroup$ @fGrieu, Without wishing to mitigate the subsequent works, the RSA patent had already mentioned these two elements since 1977. However for 3 or more RSA factors, the Garner algorithm, with the recombination principle was already largely detailed in Knuth, vol 2, 1980. This was the essential reason, why I compared all the confidentials threads of this period, as "secret de Polichinelle". With the dramatic increase in VLSI technology, the interest of 3 or more RSA factors, became quickly caduca as well as employing alternative moduli of the form $p^2.q$ Thanks for your valuable feedback. $\endgroup$ Commented Feb 4, 2015 at 22:02
  • 2
    $\begingroup$ Dr. Scott graciously replied to my questions about this issue. He called it "a pretty obvious idea" that "To be honest, I am sure it wasn't me that was first to think of it. I would credit it to Quisquater, although it may have been known much earlier." And the identity of Nemo is still a mystery. I focused on the question of who first came up with the idea of using more than two factors. $\endgroup$
    – Patriot
    Commented Jul 30, 2021 at 2:48

1 Answer 1


I obtained the reference cited by the examiner of patent application #09/694,416, using the procedure that was given to me there, and put it online (as permitted in the paper).

Captain Nemo: RSA Moduli Should Have 3 Prime Factors.

The paper states it was written in February 1996. It's in the style of a paper to a crypto conference, including being typeset in LaTex with LNCS template, and giving proper references. It contains what then was the best description I know of what got known as multiprime RSA a few years later, complete with description of how to use the Chinese Remainder Theorem to obtain a speedup, analysis of the speed benefit by standard algorithms and when using Karastuba, experimental results, and a security analysis.

Unfortunately I don't know who wrote under the pseudonym Captain Nemo, if and where the paper was submitted, if it got published, and in the negative how it came in the hands of a patent examiner.

Update: Samuel Neves unmasked that Captain Nemo is Richard Schroeppel!

  • 2
    $\begingroup$ Richard Brent and Peter Montgomery are both cited as "personal communication" in the bibliography. While the latter is not among us anymore, the former might have an idea about who wrote this paper? $\endgroup$ Commented Mar 28, 2023 at 12:55
  • 3
    $\begingroup$ Looking at that peculiar copyright notice, one arrives at this 1994 post by Richard Schroeppel on a niche mailing list. From there we find this comment on the NSS codebase which confirms it. $\endgroup$ Commented Mar 28, 2023 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.