788 views

Skip to first unread message

Mar 18, 1991, 9:21:26 AM3/18/91

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu