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