RSA factoring challenge
Burt Kaliski
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: challen...@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.com
A copy of the Partition List will be sent to you automatically
if you send an email request to:
challenge-pa...@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-...@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
challeng...@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:
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-a...@rsa.com