| Presentation | 2004-07-20 A trial of GNFS implementation (Part V) : Speeding up sieving using bucket sort Kazumaro AOKI, Hiroki UEDA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 dramatically 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | integer factoring / sieving algorithm / number field sieve / largish prime / bucket sort / radix sort |
| Paper # | ISEC2004-25 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2004/7/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A trial of GNFS implementation (Part V) : Speeding up sieving using bucket sort |
| Sub Title (in English) | |
| Keyword(1) | integer factoring |
| Keyword(2) | sieving algorithm |
| Keyword(3) | number field sieve |
| Keyword(4) | largish prime |
| Keyword(5) | bucket sort |
| Keyword(6) | radix sort |
| 1st Author's Name | Kazumaro AOKI |
| 1st Author's Affiliation | NTT() |
| 2nd Author's Name | Hiroki UEDA |
| 2nd Author's Affiliation | NTT |
| Date | 2004-07-20 |
| Paper # | ISEC2004-25 |
| Volume (vol) | vol.104 |
| Number (no) | 199 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |