Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Factoring Small to Medium Size Integers: An Experimental Comparison

Jérôme Milan 1 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : We report on our experiments in factoring integers from 50 to 200 bit with the NFS postsieving stage or class group structure computations as potential applications. We implemented, with careful parameter selections, several general-purpose factoring algorithms suited for these smaller numbers, from Shanks's square form factorization method to the self-initializing quadratic sieve, and revisited the continued fraction algorithm in light of recent advances in smoothness detection batch methods. We provide detailed timings for our implementations to better assess their relative range of practical use on current commodity hardware.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00188645
Contributor : Jérôme Milan Connect in order to contact the contributor
Submitted on : Friday, January 29, 2010 - 2:30:00 PM
Last modification on : Friday, February 4, 2022 - 3:12:28 AM
Long-term archiving on: : Wednesday, November 30, 2016 - 11:47:32 AM

File

smallint_expcomp_draft_02_1.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00188645, version 3

Collections

Citation

Jérôme Milan. Factoring Small to Medium Size Integers: An Experimental Comparison. 2010. ⟨inria-00188645v3⟩

Share

Metrics

Record views

528

Files downloads

3638