[comp.theory] RSA Factoring Challenge

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