
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Bucket Sieving
Kazumaro AOKI Hiroki UEDA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.8
pp.18451850 Publication Date: 2009/08/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.1845
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Theory Keyword: integer factoring, sieving algorithm, number field sieve, largish prime, bucket sort, radix sort,
Full Text: PDF(207.6KB) >>Buy this Article
Summary:
This paper proposes a new sieving algorithm that employs a bucket sort as a part of a factoring algorithm such as the number field sieve. The sieving step requires an enormous number of memory updates; however, these updates usually cause cache hit misses. The proposed algorithm significantly reduces the number of cache hit misses when the size of the sieving region is roughly less than the square of the cache size, and the memory updates are several times faster than the straightforward implementation according to the PC experiments.

