128 bit key exchange

? nn=2^128-159
%89 = 340282366920938463463374607431768211297
? factor(nn)
%90 =
[340282366920938463463374607431768211297 1]

? znprimroot(nn)
%91 = Mod(5, 340282366920938463463374607431768211297)

So 5 can be the base for diffie-hellman key exchange. Missing 159 or so keys, but that's such a small fraction of the keyspace, so who cares.

? nn=2^256-189
%92 =
115792089237316195423570985008687907853269984665640564039457584007913129639747
? factor(nn)
%93 =
[115792089237316195423570985008687907853269984665640564039457584007913129639747
1]

? znprimroot(nn)
%94 = Mod(2,
115792089237316195423570985008687907853269984665640564039457584007913129639747)

Similarly 2 can be the base for 256 bit keys. ---- Too bad such small primes can be broken with current methods of finding discrete logs. ---- Elliptic Curve Diffie Hellman would work, though.