The Fiat-Shamir heuristic is a general method to construct a non-interactive proof (or signature) scheme from an interactive proof of knowledge scheme. An example of interactive scheme amenable to the Fiat-Shamir heuristic is the schnorr-identification protocol in a Schnorr group. That's how I'll interpret the question (that other answer discuss the more general perspective of the Fiat-Shamir heuristic).
A Schnorr group is a subgroup of prime order $q$, and generator $g$, of the multiplicative group modulo some prime $p$. That main group $\mathbb Z_p^*$ has order $\varphi(p)=p-1$. Since the order of a subgroup divides the group order, $q$ must be a prime dividing $p-1$. Since $g$ is a generator, it must be such that $g^q\equiv1\pmod p$ and $g\not\equiv1\pmod p$. The Schnorr group is typically stated as the three integers $(p,q,g)$.
How big should the prime number $p$ be? How to select $p$ so that, for example, Pohlig–Hellman algorithm or other known algorithms could not break it?
For the Schnorr group to be of cryptographic interest, the Discrete Logarithm Problem must be difficult in the Schnorr group. This implies resisting known DLP algorithms. The algorithm that practically determines the required size of $p$ in a Schnorr group is the DLP variant of GNFS, which is index calculus specialized to $\mathbb Z_p^*$. The current record is a 795-bit bit $p$, and a minimum recommended size for current applications is 2048-bit, or 3072-bit for "2030 and beyond".
It's also necessary that $q$ is large enough that Pollard's rho for DLP is infeasible. It's cost is about $\Theta(\sqrt q)$ group multiplications. Thus it's recommended a minimum of 224-bit or 256-bit $q$.
These requirements are enough to insure the Pohlig-Hellman algorithm is not to fear. That's because Pohlig-Hellman requires solving a DLP in each subgroup of order $q^k$ with $k\ge 1$, $q$ prime, and $q^k$ dividing the order of the base group; and $k=1$ is the easiest case.
How to select the primitive root $g$?
This probabilistic polynomial time algorithm will do:
- choose random prime $q$ of desired size
- choose random even $r$ for prime $p=qr+1$ of desired size
- chose random $s$ in $[2,p-2]$, and compute $g=s^{(p-1)/q}\bmod p$, until $g\ne1$ (which is almost certain)
- as a consistency check, verify $g^q\bmod p=1$ (that holds unless there was an error).
Is it safe to use the same values of $p$ and $g$ for a couple of challenges?
Yes. Knowing the solution to a particular DLP in a Schnorr group demonstrably does not help solve other unrelated random DLPs on the same Schnorr group (there remains the possibility that some precomputation can be amortized between several DLPs, but that's marginal).
Why is it better to use a Schnorr group instead of safe prime $p$?
A safe prime $p$ corresponds to $p-1=2q$, or $r=2$ in the above. While technically that still matches the definition of a Schnorr group, it's not fulfilling a key motivation of Schnorr groups: having an order $q$ of much smaller size than $p$. This is interesting because exponents are in $\mathbb Z_q$, thus shorter $q$ leads to faster exponentiation, shorter secrets, and (in a common variant of the Fiat-Shamir heuristic) shorter signatures. Also, the search of $p$ is slightly more involved. As far as we know, using a Schnorr group with large-enough $q$ and $p$ is as secure as using a safe prime $p$ of comparable size.
