Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Describes a distributed implementation of two factoring algorithms, the elliptic curve method (ECM) and the multiple polynomial quadratic sieve algorithm (MPQS). The authors' ECM-implementation on a network of DEC MicroVAX processors has factored several numbers from the Cunningham project. The authors have also implemented the multiple polynomial quadratic sieve algorithm on the same network. On this network alone, they are now able to factor any 100 digit integer, or to find 35 digit factors of numbers up to 150 digits long within one month. To allow an even wider distribution of their programs they made use of electronic mail networks for the distribution of the programs and for inter-processor communication. Even during the initial stage of this experiment, machines all over the United States and at various places in Europe and Australia contributed 15 percent of the total factorization effort. At all the sites where the program is running, the authors only use cycles that would otherwise have been idle. This shows that the enormous computational task of factoring 100 digit integers with the current algorithms can be completed almost for free. Since they use a negligible fraction of the idle cycles of all the machines on the worldwide electronic mail networks, the authors could factor 100 digit integers within a few days with a little more help
Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota