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.
