I have found some contradicting answers regarding finding a safe prime.
When p is a "safe prime", this means that $(p−1)/2$ is also prime. We then define $q=(p−1)2$. In that situation, the order of any non-zero $g\mod p$ (except 1 and p−1) is either $q$ or $2q$
If it can produce a group of size $2q$ then the groups length is by definition not a prime.
Okay, so following this theory, 83 should be regarded as a safe prime.
$(83-1)/2=41$ and $41$ is a prime.
The length of the subgroup produced by $2 \mod 83$ is $82$. (can you phrase it like that? Even though it refers to a set/group of congruences by $2^{1..p-1} \mod p$?
I can prove it with a little program
const groupSize = (p, g) => {
const group = new Set()
for(let i = BigInt(0); i < p-BigInt(1); i++){
group.add((g**i)%p)
}
console.log(group.size)
}
groupSize(BigInt(83), BigInt(2))
output: 82
This contradicts an answer to one of my previous questions regarding choosing a safe prime.
If h is a factor of the size of the group generated by g, then given $g^x\mod p$, we can compute $h\mod n$ in $O(\sqrt h)$ time. If g generates the entire group, well, its size will be $p−1$, which always has a factor of 2 (assuming $p>2$), and so we'd be giving away $x\mod 2$ for free.
Diffie-Hellman what is the subgroup
This makes me believe that the group cannot be an even number, since it is then a factor of 2?