We found that the work of Kim et al. [1] on trace representation of the Legendre sequence with the periods p ≡ ±3 (mod 8) can be improved by restricting the selection of the periods p while maintaining the form p ≡ ±3 (mod 8) unchanged. Our method relies on forcing the multiplicative group of residue classes modulo p, Zp*, to take 2 as the least primitive root. On the other hand, by relaxing the very strong condition in the theorem of these authors and by using the product among powers of the primitive root and powers of any quadratic residue element to represent an element in Zp*, we could extend Kim's formula so that it becomes a special case of our formula more general.

The certified discrete logarithm problem modulo p prime is a discrete logarithm problem under the conditions that the complete factorization of p-1 is given and by which the base g is certified to be a primitive root mod p. For the cryptosystems based on the intractability of certified discrete logarithm problem, Sakurai-Shizuya showed that breaking the Diffie-Hellman key exchange scheme reduces to breaking the Shamir 3-pass key transmission scheme with respect to the expected polynomial-time Turing reducibility. In this paper, we show that we can remove randomness from the reduction above, and replace the reducibility with the polynomial-time many-one. Since the converse reduction is known to hold with respect to the polynomial-time many-one reducibility, our result gives a stronger evidence for that the two schemes are completely equivalent as certified discrete log cryptosystems.