Quote from: pythonpro1337 on February 07, 2015, 11:02:01 PM

Though you possibly qualified it by saying "at least in the context of...", I just thought I'd note that 2 is not necessarily a generator of ℤp× where p is prime. Consider, for example, p = 7.

My bad, pythonpro1337 is correct. However, 2 is a generator of the multiplicative group of integers modulo 7237005577332262213973186563042994240857116359379907606001950938285454250989 (the order of the Curve25519 elliptic curve group), so the rest of my argument holds.

Proof

For convenience:

N = 7237005577332262213973186563042994240857116359379907606001950938285454250989

Note that saying 2 is a generator of ℤ_N^× is the same as saying 2 is primitive root modulo N.

Since N is prime, ϕ(N) = N-1

If 2 isn't a primitive root then then it's order must divide N-1.

Given the prime factorization of N-1 = 276602624281642239937218680557139826668747 * 198211423230930754013084525763697 * 33 * 2 * 2

and the fact that:

2^{(N-1)/276602624281642239937218680557139826668747} ≢ 1 (mod N)
2^{(N-1)/198211423230930754013084525763697} ≢ 1 (mod N)
2^(N-1)/33 ≢ 1 (mod N)
2^(N-1)/2 ≢ 1 (mod N)

We can conclude that 2 is indeed a primitive root (and thus a generator of ℤ_N^×).