A safe prime p is a prime such that (p-1)/2 is also a prime. A primality test or a safe primality test is normally a combination of trial division and a probabilistic primality test. Since the number of small odd primes used in the trial division affects the performance of the combination, researchers have studied how to obtain the optimal number of small odd primes to be used in the trial division and the expected running time of the combination for primality tests. However, in the case of safe primality tests, the analysis of the combination is more difficult, and thus no such results have been given. In this paper, we present the first probabilistic analysis on the expected running time and the optimal number of small odd primes to be used in the trial division for optimizing the tests. Experimental results show that our probabilistic analysis estimates the behavior of the safe primality tests very well.

Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, rank and select, are commonly used. In this paper we propose two implementations supporting rank and select in constant time for non-compressed bit strings. One uses O(n log log n / ) bits of extra space and the other uses n+O(n log log n / log n) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.