From challenge-administrator@RSA.COM Sun Oct 12 09:36:53 1997
Received: from RSA.COM ( [])
	by (8.8.5/8.8.5) with SMTP id JAA17514
	for ; Sun, 12 Oct 1997 09:36:52 -0500
Received: by RSA.COM 
	id AA20116; Sun, 12 Oct 97 06:29:47 PDT
Date: Sun, 12 Oct 97 06:29:47 PDT
Message-Id: <9710121329.AA20116@RSA.COM>
From: challenge-administrator@RSA.COM (RSA Factoring Challenge Administrator)
Status: RO

		 Partition Challenge List Information

Here is information about obtaining the Partition List for the RSA
Factoring Challenge, with some description of how this list was
generated.  For more information about the RSA Factoring Challenge,
including information on how to report factorizations of numbers on
this list, contact:

	RSA Challenge Administrator
	100 Marine Parkway, Redwood City, California 94065
	(415) 595-8782

or send email to:

The file you are reading now is returned automatically for an email
message sent to:

The idea of using of partition numbers as factoring challenge numbers
was proposed by Warren Smith during a discussion between Dr. Hendrik
W. Lenstra, Jr. and other mathematicians involved in research on
factoring.  The partition number p(n) is the number of ways of
expressing n as a sum of positive parts.  For example, p(5) = 7, since
there are 7 such ways of expressing 5:
	4 + 1
	3 + 2
	3 + 1 + 1
	2 + 2 + 1
	2 + 1 + 1 + 1
	1 + 1 + 1 + 1 + 1
A good reference on partition numbers is the book, "The Theory of
Partitions," by George E. Andrews, Volume 2 of The Encyclopedia of
Mathematics and its Applications (Addison-Wesley, 1976).

The partition numbers seem relatively "random."  As such, some of them
might be "easy targets" in that they have at most one prime factor
greater than (say) 1,000,000, and are thus quite easy to factor.  On
the other hand, it is expected that others will be quite challenging.

In order to reduce the list of challenge partition numbers to a
reasonable size, only the partition numbers p(n) where n is prime are
on the challenge list.  Even so, there are roughly 20 partition
challenge numbers of each length (in decimal digits).

The challenge numbers on the Partition List were generated by the
Common Lisp program given below.  (Common Lisp was used because it has
a built-in capability for working with arbitrarily large integers.)
This program prints p(n) for each prime n in the range 8681 to 20000.
Here 8681 is the smallest prime n such that p(n) is 100 digits long.
The computation is based on a beautiful theorem by Euler (see
Corollary 1.8 in Andrews' book).  Computing this list takes about 1/2
hour on a SUN Sparcstation.

It is expected that the RSA challenge numbers will be at least as
hard, if not harder, to factor than the partition numbers of the same

;;; Program to output Partition List of challenge numbers to factor.   ;;;
;;; by Ronald L. Rivest 2/9/91                                         ;;;
;;; for RSA Data Security, Inc.                                        ;;;

(defvar *pt*) ;; will hold array of partition number values

(defun make-partition-list(nn)
  ;;; Computes p(0), p(1), ..., p(nn) and stores them in array *pt*
  ;;; Based on Euler's theorem:
  ;;; p(n) = sum_{m>0} (-1)^{m+1} [ p(n-m(3m-1)/2) + p(n-m(3m+1)/2) ]
  (setq *pt* (make-array (list (1+ nn)) :initial-element 0))
  (setf (aref *pt* 0) 1)
  (do ((n 1 (1+ n)))
      ((> n nn))
      (do* ((m 1 (1+ m))
	    (d 1 (+ d (- (* 3 m) 2)))
	    (sum 0)
	    (sign 1 (- sign)))
	   ((> d n) (setf (aref *pt* n) sum))
	   (cond ((<= d n) (incf sum (* sign (aref *pt* (- n d))))))
	   (cond ((<= (+ d m) n) (incf sum (* sign (aref *pt* (- n d m))))))

(defvar *n1* 8681)  ;; smallest value of n for which to print p(n)
(defvar *n2* 20000) ;; largest value of n for which to print p(n)

(defun print-challenge-list()
  ;;; Print out partition number p(n) for n >= *n1* (so p(n) has at
  ;;; least 100 decimal digits), and for n prime (to keep the size of
  ;;; the list reasonable).  Although the list goes on forever in
  ;;; principle, this program doesn't print any values for n > *n2*
  ;;; The output file is called "PList".
  (make-partition-list (1+ *n2*))
  (let ((f (open "PList" :direction :output :if-exists :supersede)))
    (format f "Challenge Numbers: The ``Partition List''")
    (dolist (n (primes-upto *n2*))
	    (if (>= n *n1*)
		(let* ((p (aref *pt* n))
		       (ps (format nil "~D" p)))
		  (format f "~%~%p(~D) = ~A (~D digits)" n ps (length ps)))))
    (close f)))

(defun primes-upto(bound)
  ;; returns list of all primes not larger than given bound.
  (let ((sa (make-array (1+ bound) :element-type 'bit :initial-element 1))
	(answer nil))
    (do ((i 2 (1+ i)))
	((> i bound) (nreverse answer))
	(cond ((= (sbit sa i) 1) 
	       (push i answer)
	       (do ((i1 (+ i i) (+ i1 i)))
		   ((> i1 bound))
		   (setf (sbit sa i1) 0)))))))

;;; End of program to print challenge list of partition numbers        ;;;

Since the partition list is larger than many mailers can handle, we
have broken it up by 5-digit groups into 11 separate files:

partition-list-100 (containing 100-104 digit partition numbers)
partition-list-105 (containing 105-109 digit partition numbers)
partition-list-110 (containing 110-114 digit partition numbers)
partition-list-115 (containing 115-119 digit partition numbers)
partition-list-120 (containing 120-124 digit partition numbers)
partition-list-125 (containing 125-129 digit partition numbers)
partition-list-130 (containing 130-134 digit partition numbers)
partition-list-135 (containing 135-139 digit partition numbers)
partition-list-140 (containing 140-144 digit partition numbers)
partition-list-145 (containing 145-149 digit partition numbers)
partition-list-150 (containing 150-153 digit partition numbers)

These files should accompany this note.

To receive the partition list information for just a particular
5-digit group, send mail to the following address:

where XXX is one of the following numbers: 100, 105, 110, 115, 120,
125, 130, 135, 140, 145, 150.