」(...(**))である。gが原始元でないならば、[定理]「∀a;ordp|p-1」より、「ordp(g)|p-1」を満たす。よって、あるm≧2に対して、p-1=ordp(g)×mが成り立つ。仮定と組み合わせると、次が成り立つ。よって、qi|mが成り立つ。)これは(**)を満たす。p-1=10の素因数は2と5である。11)どちらの結果も1に一致しないので、2は生成元である。11)1に一致するものがあったので、3は生成元ではない。◇この定理を使うと、(*)をt+1回チェックするだけで、原始元かどうかを判定できることになる。ところが、この定理は原始元の判定アルゴリズムに利用できそうだが、実際には使うことはできない。ElGamal暗号のときはp=1,024ビットなので、pを素因数分解することは無理である。この定理を使うためには、p-1の素因数分解を知らなければならないため、直接使うことは不可能である。そこで、実装においては次のように行う。1:qをランダムに選び、素数判定アルゴリズムで判定する。普通にMiller-Rabinアルゴリズムを使えばよい。2:次にp=2q+1を計算し、このpが素数かどうかを素数判定アルゴリズムで判定する。3:もしp,qどちらも素数ならば、p-1の素因数は2とqとすでに知っているので、上記の原始元かどうかを判定するアルゴリズムを利用できる。図の原始元生成アルゴリズムはgの選択と原始元判定アルゴリズムの組合わせを意味としている。2回のチェックのみで原始元の判定ができる。pの原始元となるわけである。素数生成アルゴリズム(3935d)。