ng this list as a database. Assume next that we select (p, q) from a huge list of known primes, for instance up to 109, yielding numbers of the order of 1018 Even at a rate of 109 division tests per second (a computing power that only a few states are able to afford), this would take about 109 seconds or 31.7 years to check! With large PKC and RSA key sizes (e.g., n 2 264 2 1019, ~ 2128 2 1038), the prob- lem of factorization is no longer within easy reach, and rather requires both extended computing facilities and time effort. To promote the advancement and security of cryp- tography, the company RSA Security offers challenges to the public, which take the form of huge modulus numbers to factorize (namely, given n, find the two primes p and q such that n = pq). 7 The current challenges concern different numbers with lengths from 704 to 2048 bits. Here is the RSA-2048 number, which has 617 decimal digits:8 2519590847565789349402718324004839857142928212620403202777713783604366202070 1595556264018525880784406918290641249515082189298559149176184502808489120072 84499268739280728777673597141834727026189637501497182469116507761337985909570 (00973304597488084284017974291006424586918171951187461215151726546322822168699 8754918242243363725908514186546204357679842338718477444792073993423658482382 42811981638150106748104516603773060562016196762561338441436038339044149526344 32190114657544454178424020924616515723350778707749817125772467962926386356373 28991215483143816789988504044536402352738195137863656439121201039712282 2120720357 Two of the earlier challenges, named RSA-140 (140 decimal digits, 465 bits) and RSA-155 (155 decimal digits, 512 bits), were successfully met by international teams of researchers from both academy and industry in February and August 1999, respectively. Note that RSA-155 was renamed RSA-512 SO that the number defines bit size rather than decimal-digit size. Factorizing RSA-140 required 125 workstations (175 MHz) and 60 personal comput- ers (3001 MHz) to run for about one month, a combined 8.9 yea