Efficient ways of prime number generation for ring signatures
José Luis Salazar, Jose Luis Tornos, Joan Josep Piles · IET Information Security · 2015
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 = 2 e 1 e 2 + 1 will be a prime integer. With a naïve 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.