victor@WATSON.IBM.COM (Burt Kaliski) (03/28/91)
ANNOUNCEMENT OF "RSA FACTORING CHALLENGE" ----------------------------------------- (3/18/91) RSA Data Security hereby announces that it is sponsoring an ongoing "factoring challenge" (with cash prizes) to encourage research in computational number theory and the pragmatics of factoring large integers. RSA Data Security specializes in cryptographic products, particularly those based on the RSA public-key cryptosystem. The results of this challenge will help users of the RSA public-key cryptosystem achieve the level of security they desire. The contest is based on two "challenge lists" of numbers. The first list, the "RSA List," contains numbers representative of those used in the RSA cryptosystem. The second list, the "Partition List," contains what mathematicians define as "partition numbers." The idea of using partition numbers was suggested to Dr. Hendrik W. Lenstra, Jr. (well-known for his contributions to the art of factoring) by Warren Smith in a discussion on the topic of finding a set of "standard" challenge numbers for factoring research. The shortest number in each list is 100 decimal digits long (well within the current state of the art). The RSA List contains numbers up to 500 digits in length, while the Partition List contains arbitrarily large numbers. The challenge is to factor the numbers on these lists; that is, to represent them as products of prime numbers (their "prime factors"). Prime numbers, such as 2, 3, 5, 7, 11, and 13, are those numbers that are not evenly divisible by any smaller number (except 1). A non-prime (composite) number greater than 1 can always be written as a product of smaller prime numbers, known as its prime factors. For example, the number 665 can be represented as the product of its prime factors 5, 7, and 19. Finding all the prime factors of a given number is known as "factoring" the number. As the length of the number increases, the problem of factoring it rapidly becomes more and more difficult. Although factoring 100-digit numbers is within the current state of the art, factoring arbitrary 200-digit numbers is not. Over time, advances in computer hardware and computational number theory are expected to advance the state of the art. One purpose of this contest is to "track" the state of the art. The RSA List contain numbers of the kind we believe to be the hardest to factor; the numbers on this list should be particularly challenging. These are the kind of numbers used in devising secure RSA cryptosystems. The Partition List contains numbers that are more-or-less "random"; some of these numbers (even very large ones) may be quite easy to factor, although others may be quite difficult. Although RSA Data Security views the RSA List as the primary and most interesting challenge list, the Partition List challenge is also provided in order to encourage work on factoring in general as well as on factoring numbers of cryptographic interest. If you factor a number on a challenge list, please report it to RSA Data Security, which maintains an "Honor Roll" naming the first person to factor each number on each list. Being placed on an Honor Roll also makes you eligible to win a prize. Cash prizes are awarded quarterly, beginning with the second quarter of 1991 (ending June 1991). For each challenge list, a cash prize of $1000 is awarded if any previously unfactored numbers from that list are factored during the quarter. If more than one such number is factored, then the cash first prize of $1000 is awarded to the person factoring the smallest such number, $500 is awarded to the person factoring the second smallest such number, and $250 if awarded to the person factoring the third smallest such number (if any). (The award system favors factoring the smallest as-yet-unfactored number in order to focus attention on the boundary between what is easily factorable and what is not.) Any unawarded prizes carry over to following quarters to increase the values of the prizes above the amounts just indicated. Queries can be addressed to RSA Challenge Administrator, RSA Data Security. (Address: 10 Twin Dolphin Drive, Redwood City, California 94065; Phone: 1-415-595-8782. Internet Email address: challenge-info@rsa.com). CONTEST RULES AND INFORMATION ----------------------------- 1. The challenge lists. The challenge numbers are in two lists, the "RSA List" and the "Partition List." These lists are available from RSA Data Security. They contain numbers of length at least 100 decimal digits. Each number is labelled with an "identifying tag," such as "RSA-150" (for the 150-digit number from the RSA List), or "p(9721)" (for a number from the Partition List). A copy of the RSA List will be sent to you automatically if you send an email request to: challenge-rsa-list@rsa.com A copy of the Partition List will be sent to you automatically if you send an email request to: challenge-partition-list@rsa.com. You can also request copies of these lists by writing to the RSA Challenge Administrator (address below). 2. The Honor Rolls RSA Data Security maintains two Honor Rolls: the RSA Honor Roll and the Partition Honor Roll. These honor rolls specify which numbers have been factored (and by whom) and which numbers remain unfactored. Copies of the Honor Rolls may be obtained by writing to RSA Data Security or sending Internet email to: challenge-honor-rolls@rsa.com. The Honor Rolls contain the factorization reports (see below) for the first factorization of each challenge number, plus an indication as to whether a prize was awarded for that factorization. 3. Reporting a factorization If you factor a number that is listed as unfactored on the Honor Roll, you can report it to RSA Data Security. It is preferred that you submit your report by electronic mail to challenge-report@rsa.com or on an IBM PC-compatible 3.5" diskette. These reports will be automatically checked and logged on to the honor rolls, so please use the following format in the body of your message. (line from list describing challenge number and its length) Factors: (first prime factor) * (second prime factor) * ... * (last prime factor) Date: (date factorization completed) Method: (a phrase or sentence describing the method used) Time: (an estimate of the CPU time used in MIP-years) Name: (your name) Address: (your mailing address) Email: (your email address) Phone: (your telephone number) Here is an sample report claiming the factorization of p(197): p(197) = 3068829878530 (13 digits) Factors: 2 * 5 * 13 * 43 * 257 * 2136131 Date: January 3, 1807 Method: Trial division Time: 0.00001 Name: C. F. Gauss Address: University of Gottingen Partition numbers that have at most one prime factor greater than 1,000,000 are considered "easy targets"; please do not send in factorization reports for easy targets that are more than 50 digits longer than the smallest unfactored challenge partition number. Note that easy targets are not excluded from the contest; you can win a prize for factoring an easy target, and factorizations of easy targets will be listed in the honor roll. However, for ease of administration we request that you not send in factorizations of easy targets that are unlikely to win a prize because they are so much larger the smallest unfactored number. If more than one person is involved in the factorization effort, please list the "contact person" first in the Name field. The Date, Method, and Time fields are optional, although you are encouraged to provide this information so that others can more accurately assess how the state of the art is progressing. If two reports are received for the same challenge number, RSA Data Security will generally give priority to the first report received by RSA Data Security (not necessarily the one with the earlier Date field). However, RSA Data Security reserves the right to judge the merits of each claim on a case-by-case basis and to make what it judges to be reasonable resolutions of competing claims, including making multiple awards, splitting awards, or taking other actions. For the Method field, you may specify the method used with standard acronyms and names, such as TD (trial division), ECM (elliptic curve method), QS (quadratic sieve), etc., a combination of these, references to the literature, etc. To clarify the Time field, note that a MIP-year is the computational power supplied by a one-MIP (million-instruction per second) machine running for one year. For example, if you use a 10-MIP machine half-time for 6 months, you have used 2.5 MIP-years of computational power. The Address, Email, and Phone entries may be omitted if you already have a report in the Honor Roll and these values haven't changed. Please give the prime factors in increasing order. The prime factors you specify do not need to be "proved" to be primes; it suffices if they are "probable" primes. RSA Data Security will carefully check the primality of each proposed factor with the Miller-Rabin probabilistic primality-testing routine. (For a description of this test see, for example, Chapter 33 of Introduction to Algorithms by Cormen, Leiserson, and Rivest (MIT Press, 1990).) You may give the factor list on one or more lines; white space and carriage-return/line-feeds are ignored in the factor list. You may also give multiline responses for the other fields. (But please start each field on a new line, and don't leave blank lines between fields.) 4. Prizes RSA Data Security will award prizes quarterly, beginning with the second quarter of 1991 (ending June 30, 1991). Prizes are awarded separately for each challenge list (as if they were two entirely independent contests). In each contest, up to three cash prizes may be awarded each quarter: a First Prize, a Second Prize, and a Third Prize. Each contest maintains a separate "fund" from which to award prizes. RSA adds $1750 to each fund at the end of each quarter before awarding prizes for that quarter, so that a First Prize recipient will receive at least $1000, a Second Prize recipient will receive at least $500, and a Third Prize recipient will receive at least $250. At the end of quarter, a First Prize recipient will receive 1000/1750 (i.e. 4/7, or 57.14%) of the fund, a Second Prize recipient will receive 500/1750 (i.e. 2/7, or 28.57%) of the fund, and a Third Prize recipient will receive 250/1750 (i.e. 1/7, or 14.29%) of the fund. Any unawarded funds are carried over to the next quarter, so that the actual amount of the prizes may increase over time. The prize structure is arranged to encourage work on the smallest of the previously unfactored numbers, focusing attention on the dividing line between "factored" and "unfactored." Therefore, if one or more factorization reports for previously unfactored challenge numbers are received during a quarter, then First Prize is awarded for the report on the smallest of such reported numbers, Second Prize for the second smallest, and Third Prize for the third smallest. (This implies that First Prize is awarded whenever the factorization of previously unfactored numbers is reported, even if the smallest previously unfactored number remains unfactored. You win a First Prize if you factor a previously unfactored challenge number during the quarter and nobody else factors a smaller previously unfactored challenge number.) 5. Administrivia Employees of RSA Data Security and their relatives are not eligible. RSA Data Security reserves the right to change the contest rules at any time at its sole discretion, without notice, including the right to change or extend the challenge lists, to change the prize amounts, and/or to terminate the contest. RSA Data Security is the sole arbiter and administrator for this contest; the judgement of RSA Data Security in all matters is final. For a status report on the contest and a summary of recent developments, you can send an email request to: challenge-news@rsa.com. Queries can be addressed to: RSA Challenge Administrator RSA Data Security 10 Twin Dolphin Drive Redwood City, California 94065 1-415-595-8782 Internet email address: challenge-administrator@rsa.com