「(1) アリスはボブに対して、2つの素数PとGを送信する」は，『暗号技術入門-秘密の国のアリス』ではp.280に，『新版暗号技術入門 秘密の国のアリス』でもp.280に，そして2015年9月1日初版発行の『暗号技術入門 第3版』ではp.294に書かれています．7つのステップからなるDiffie-Hellman鍵交換の最初のステップで，太字になっています．
ただし，そのあとの文章では，Gが素数であるとは書かれていませんし，素数である必要もありません．また各版でページをめくると，生成元の意味が書かれていますが，13の生成元の1つに，合成数の6が含まれています．
ということで「2つの素数PとG」は単純ミスであり，「2つの整数PとG」または「素数Pとその生成元G」と書くべきではないかと思っていますが，ひょっとしてPが大きくなると，その生成元が，1に近い割合で素数になってしまったりしないかと，不安になり，Rubyスクリプトを書いて検証しました．
コードはいつものようにGistにて公開しました．このプログラム(gen.rb)を引数なしで実行すると，13の生成元を出力します．引数を指定すると，まずその値が素数であるか，判定を行い，素数であれば，その生成元を小さなものから順に求めていきます．
RubyのBignumクラスと，OpenSSL::BN（OpenSSL内で利用される多倍長整数クラス）を用いているので，任意サイズの正整数に対して処理できるようになっています．
なぜOpenSSLが出てくるのかというと，生成元の判定に，以下の画像（講義スライドの一部です．「%」は，「mod」に読み替えてください）の最後の条件を使いたかったからです．
1番目（…どれも異なる）と2番目（…いずれも1ではない）は，1からスタートして，gを掛けて，pで割った余りを求めればよいので，Bignumクラスだけで行えます．しかし3番目の条件では，べき剰余の演算が不可欠です．
これについて，Rubyによる書き方がないかと調べたところ，Efficient way to power and mod in ruby - Stack Overflowを見つけまして，サンプルコードが以下の2行で，大いに感激したのでした*1．
require 'openssl'
1_299_709.to_bn.mod_exp(1_300_751, 104_729) # => 90827
これで道具が揃いましたので，あとはコーディングするだけです．用いたOpenSSL::BNのインスタンスメソッドには，べき剰余を計算するmod_expのほか，素数判定を行うprime?があります．
出力の最終行では，生成元の数と，そのうちいくつが素数であるかを打ち出しました．引数なしの全出力は以下のとおりです．
$ ruby gen.rb
2 is a generator and a prime number.
6 is a generator.
7 is a generator and a prime number.
11 is a generator and a prime number.
Found 4 generators, among which are 3 prime numbers.
素数表 (1～10000)の中で一番大きな素数の9973を与えると，出力の終わりのところはこうなります．
$ ruby gen.rb 9973 | tail -n 11
9929 is a generator and a prime number.
9934 is a generator.
9936 is a generator.
9940 is a generator.
9942 is a generator.
9944 is a generator.
9950 is a generator.
9956 is a generator.
9960 is a generator.
9962 is a generator.
Found 3312 generators, among which are 407 prime numbers.
素数表 (1万～10万)の中で一番大きな素数の99991だと，どうなるでしょうか．
$ ruby gen.rb 99991 | tail -n 5
99977 is a generator.
99981 is a generator.
99984 is a generator.
99986 is a generator.
Found 24000 generators, among which are 2350 prime numbers.
なんと，生成元の数は，キリ番（24000）でした．ではなくて…生成元に占める素数の割合が下がっています．素数Pを大きくすると，その生成元は，むしろ合成数になる可能性が高いと言ってよさそうです．
なお，gistに置いたコードのうち，「# check_generator(p, g)」のコメントを取り除いて実行すると，得られた生成元について，画像にした必要十分条件の1番目と2番目の条件をチェックします（「たしかめ」です）．処理時間もかかりますが，手元の実行環境では，99991を引数に与えて実行した場合でも，数分で終了しました．
*1:下線記号が多いコードですが，数の中の下線記号は無視されますので，1_299_709は，1299709のことです．
