Analysis of some elementary algorithms for prime factorization

Authors
Bahmann, H Schatte, P
Citation
H. Bahmann et P. Schatte, Analysis of some elementary algorithms for prime factorization, COMPUTING, 66(1), 2001, pp. 91-95
Citations number
8
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTING
ISSN journal
0010485X → ACNP
Volume
66
Issue
1
Year of publication
2001
Pages
91 - 95
Database
ISI
SICI code
0010-485X(2001)66:1<91:AOSEAF>2.0.ZU;2-T
Abstract
For factoring a positive integer n into primes. Four variants of the elemen tary algorithm are analysed. The worst-case time complexities vary from The ta(rootn) up to Theta(rootn/log n). The average time complexities vary from Theta(rootn) up to Theta(rootn/log(2) n).