From challenge-administrator@RSA.COM Sun Oct 12 09:36:53 1997 Received: from RSA.COM (chirality.rsa.com [192.80.211.33]) by shire.ontko.com (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) To: rayo@ontko.com Status: RO Partition Challenge List Information ------------------------------------ 11/24/93 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: challenge-info@rsa.com The file you are reading now is returned automatically for an email message sent to: challenge-partition-list@rsa.com 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: 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 length. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; 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: challenge-partition-list-XXX@rsa.com where XXX is one of the following numbers: 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150.