Efficient ways of prime number generation for ring signatures

The authors describe two different algorithms to perform efficiently the ring signature keys generation. Given an integer size, l, their algorithms find efficiently (memory and time, respectively) two distinct l/2-bit primes (e(1), e(2)) such that e = 2e(1)e(2) + 1 will be a prime integer. With a naive algorithm one only needs to store O(l) bits (more specifically, only one l/2-integer), and need, in average, O(l(4)) basic l-bit operations. With the second algorithm, one not only improves this computational complexity O(l(7/2)), but also needs to use, in average, O(l(3/2)) bits. The authors consider these algorithms useful for implementing ring signatures in mobile devices where there exist strong time and space constraints.