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.

This paper describes the design principles, the specification, and evaluations of a new 128-bit block cipher E2, which was proposed to the AES (Advanced Encryption Standard) candidates. This algorithm supports 128-bit, 192-bit, and 256-bit secret keys. The design philosophy of E2 is highly conservative; the structure uses 12-round Feistel as its main function whose round function is constructed with 2-round SPN structure, and initial/final transformational functions. E2 has practical security against differential attack, linear attack, cryptanalysis with impossible differential, truncated differential attack, and so on. Furthermore, E2 can be implemented efficiently and flexibly on various platforms because the primitive operations involve byte length processing.

This letter describes several techniques for optimizing software implementations of E2 on various platforms. We propose optimization techniques for each part of E2; a new inversion algorithm, efficient byte splitting and merging for BP-Function, and an efficient SPN (Substitution-Permutation Network) implementation for 32- or 64-bit processors. As a result, E2 achieves the encryption speeds of 100.5 kb/s, 68.3 Mb/s, 162.3 Mb/s, and 130.8 Mb/s for H8/300 (5 MHz), Pentium Pro (200 MHz), Pentium II (450 MHz), and 21164A (600 MHz).