Help: questions on Diffie-Hellman prime selection on small generator cases

From: Feng Ye (f_ye_at_yahoo.com)
Date: 05/29/03 

Date: 29 May 2003 09:36:25 -0700

Hello,

I have done weeks of search and study myself, but still I have couple
questions about picking the small generators (2, 3, or 5) in
Diffie-Hellman. Hope somebody out here can help me. I looked at
implementation by OpenSSL/ssleay (but I think theory-wise other
implementation will be the same).

In OpenSSL there're such comments (copied from the code):
  for 2, p mod 24 == 11
  for 3, p mod 12 == 5 <<<<< does not work for safe primes.
  for 5, p mod 10 == 3 or 7

My questions are about those comments.

(1) g = 2 case:
I understand that when p = 3 mod 8, 2 will be the quadratic nonresidue
(QNR) modulo p(can get from Legendre symbol (2|p) ), so 2 will be the
primitive root of the whole group , and p is a safe prime which means
p = 2 mod 3, this can lead to p = 11 mod 24, as stated in the above
comments.
My question here is that Legendre symbol (2|p) actually shows 2 will
be the QNR when p = +3 or -3 mod 8. Now where is the -3 mod 8 (e.g. 5
mod 8) case? This case can lead to p = 5 mod 24 (satisfy both 5 mod 8,
and 2 mod 3) as another valid choice of p when g = 2. Is this p = 5
mod 24 correct?

(2) g = 3 case:
Legendre symbol (3|p) shows when p = +1 or -1 mod 12, 3 is the QNR,
combine this with safe prime requirements (p = 2 mod 3), we get p = 11
mod 12 is the only case. Is this p = 11 mod 12 a valid case?

(3)g = 5 case:
I don't know how to compute (5|p), can somebody show me? And, after
compute the (5|p) value, how to relate the QNR case with the primitive
root? (I found some such explanation in internet for g=2 and g=3
cases, but not g=5 case).

I have did a lot of number theory study myself, still I have the above
questions, hope somebody can give me some clue.
Thanks a lot!

Regards,
Feng