From: Shimoyama Takeshi Subject: Factoring c128 in 7^352+1 by using special sieving hardware Date: Mon, 04 Sep 2006 13:40:21 +0900 Dear factoring people, We are pleased to announce the factorization of the 128-digit cofactor in 7,352+ (7^352+1) from the Cunningham numbers. We used GNFS to factor it. The factorization is: C128 in 7,352+ = 1100292287249685340593831918 27308803313137425143391686904758535609065326627643 13982410627848016549371557142696986441756488958657 = p62 . p66 p62 = 45493637292816464852067014736571339792315419859784218076875841 p66 = 241856301831338437537787898096062692359819543303619864074410382977 In the sieving part, we used a "SPECIAL SIEVING HARDWARE" using FPGA and DAPDNA-2. This hardware was developed by Fujitsu LTD. As far as we know, this is the first successful experiment in factorization of an unfactored composite integer by using a special hardware for GNFS algorithm. This factoring hardware project is sponsored by the National Institute of Information and Communications Technology (NICT). For the other parts in GNFS (the linear algebra part and the square root part) we used softwares developed by Fujitsu Laboratories LTD. Fujitsu LTD. Fujitsu Laboratories LTD. ===== Detail ===== [Polynomial selection] The following polynomial pair was used: f(x) = 2339280*x^5-224252480052*x^4-36214284961370646*x^3 +408360934897040026852*x^2+101636022741097137772677441*x -263678243765181773090543855595 g(x) = 5175123296671*x - 1362966569805857108976278 The polynomial pair was generated by Franke/Kleinjung polynomial selection code. [Sieving] We only used line sieving. The sieving procedure finished after 42 days from the beginning, however, the sieving hardware actually ran about 32 days. The sieving hardware consists of three procedures, (1) line sieving procedure, (2) trial division for the relation check, (3) mini-factoring for the two large primes variation, For the procedures (1) and (2) are implemented on two FPGA boards separately, and for the procedure (3), we implemented on the dynamic reconfigurable processor DAPDNA-2. In total, we found 2828755 relations. There were 30025 broken and 100613 duplicated relations which may be due to some interruptions and resuming of the systems. Then, 2698117 relations were used for the following procedure. [Linear algebra] After the filtering procedure, the matrix 600718 x 599480 was generated, and 256 solutions were found by using block Lanczos algorithm. [Square root] Computing square root used Montgomery-Nguyen algorithm. We found the factor by the first solution. After the sieving procedure, we took 2.8 hours on one PC (P4 3.8GHz) until we derived the factors. / Takeshi Shimoyama Fujitsu Laboratories LTD. \ _/ Tel:+81(Japan)-44-754-2681 Fax:+81(Japan)-44-754-2666 \_ __/ 4-1-1, Kamikodanaka Nakahara-ku Kawasaki 211-8588, Japan \__ From: Shimoyama Takeshi Subject: Re: Factoring c128 in 7^352+1 by using special sieving hardware Date: Tue, 05 Sep 2006 16:48:16 +0900 Dear Paul, Thank you for your replying mail. The factor base bounds for c128 are as follows. rp:3000000, ap:22000000, rlp:17000000, alp:30000000 Sincerely yours, Takeshi Shimoyama > Thank you Shimoyama Takeshi for this announce, and congratulations for that > very first hardware-aided factorization! > > The factor base bounds are missing from your report. > Which bounds did you use? > > Regards, > Paul Zimmermann