DH鍵共有の話は置いておくとして、Z_p の原始元というのは、Z_p^* の生成元か？という質問の答えはyesです。つまり、mod p の世界で、g, g², g³, …, g^p-1 が全部違っていて、集合として{1,2,3,…,p-1}と同じになるような g のこと。
別の言い方をすると、g, g² mod p, g³ mod p,…を順番に計算したときに、最初に１になるのが g^p-1 mod p であるような g 。

そうそう、その通り。じゃあ、例えば、p=11 のときは、2は原始元？

ちょっとズルを教えてあげようか？

実は、1乗と2乗と5乗だけチェックすればいい。位数は必ず p-1 の約数である、という法則があるから。 　

そういうことになるね。

ちょっと待って！
DH鍵共有では、g を原始元にするのは良くない。

それには、少し歴史的な背景があってね。DH鍵共有は、DiffieさんとHellmanさんが発明したのだけど、彼らの論文では確かに g は Z_p の原始元と書いてある。でも、残念ながら、それだと安全ではないことが分かっているんだ。 　

まず、どうして安全ではないかを説明するよ。

今、a をランダムに選んで g^a mod p を送る、と言ったね。g^a mod p は誰でも見れてしまうけど、a が何なのか全くわからない、というのが、DH鍵共有の安全性の根拠になってる。

そう。でも、g の位数が p-1 の時には、g^a mod p を見た人は、a が奇数なのか偶数なのか、すぐにわかってしまうんだよ。
もう少し具体的に言うと、Z_p^* の要素のうち、半分は平方根を持っていて、残りの半分には平方根がない。そして、この平方根の有り無しを見分ける簡単な計算式がある。「ルジャンドル記号」って呼ばれている。

g が原始元の場合、g は絶対に「平方根がないグループ」に属する。そして、a が奇数なら g^a mod p も「平方根がないグループ」に属するし、a が偶数なら g^a mod p は「平方根があるグループ」に属する。 　

そうなんだよ。離散対数問題が解けないからOK！とはいかない。

「平方根がないグループ」と「平方根があるグループ」に二分される元々の原因は、位数 p-1 が2で割り切れる、というところから来ているんだよ。ほら、p は大きな素数だから、必ず奇数でしょう？ ということは、p-1 は必ず偶数になる。
だから、実際のDH鍵共有方式では、g は原始元ではなく、「位数が大きな素数」であるものを使っているよ。

g の位数が奇数ならば、g は必ず「平方根があるグループ」に入っている。そうすると、どんな a を選んでも、g^a mod p は「平方根があるグループ」の中に入ってしまって、ルジャンドル記号を使っても意味のある情報は得られない、というわけ。 　

たとえば位数が3で割り切れる場合には、3グループに分けることができるし、数が5で割り切れる場合には、5グループに分けることができる。少数のグループに分けることができると、2グループでなくても安全性を損なう原因になってしまう。その点、位数が素数ならば、そういうグループ分けが全くできないから安全だよ。

そこは発想の転換だよ。p を決めてから「p-1 を割り切る大きな素数」を見つけるのは大変。素因数分解をしなければいけないし、そんな大きな素数は存在しないかもしれない。だから、g の位数である素数 q を先に選んでおいて、そこから素数 p を決めるのが普通。例えば、q を決めて、p＝2q+1 を計算して、p が上手いこと素数になってくれれば出来上がり！ 　

DH鍵共有では、必ずしも p＝2q+1 という素数を使う必要はないのだけど、この形の素数 p は safe prime と呼ばれて、いろいろなところで使われている。Safe、つまり安全ということだけど、私も詳しくは知らないから、勉強して何かわかったら教えてね。