Esta es, posiblemente, demasiado largo para un comentario, pero creo que es útil en la búsqueda de este problema. Deje $G$ ser un grupo. Para $H,K\subseteq G$ definir
$$HK=\{hk\;|\; h\in H,\; k\in K\}$$
A continuación, una buena generalización de su pregunta es
¿Cuál es la menor $S\subseteq G$ tal que $S^2=G$?
Observe que, en su caso $G=(\mathbb{Z}/p\mathbb{Z})^{\times}$, y en realidad lo que quería era $S^2=\mathbb{Z}/p\mathbb{Z}$, no $S^2=G$. Sin embargo, como se nota por los comentarios si $S^2=G$,$(S\cup \{0\})^2=\mathbb{Z}/p\mathbb{Z}$, y si $S^2=\mathbb{Z}/p\mathbb{Z}$$0\in S$$(S\setminus \{0\})^2=G$. Por lo tanto la respuesta a tu pregunta es, simplemente, $+1$ a la más natural, la pregunta general que se propone con $G=(\mathbb{Z}/p\mathbb{Z})^{\times}$, debido a que sólo tenemos que añadir $0$ a la mínima establecida.
Definir
$$\phi(G)=\min\{|S|\; |\; S\subseteq G, \; S^2=G\}$$
La primera observación es bastante obvio
Si $G_1\cong G_2$,$\phi(G_1)=\phi(G_2)$.
Así, como se nota por los comentarios desde $(\mathbb{Z}/p\mathbb{Z})^{\times}\cong Z_{p-1}$ (donde $Z_n$ es el grupo cíclico de orden $n$), podemos considerar este problema en los poco más fácil de entender aditivo grupo $\mathbb{Z}/p\mathbb{Z}$. Y para comprender el problema en la mano realmente sólo necesitamos entender $\phi$ en grupos cíclicos. Entonces tenemos dos propiedades útiles.
Propiedad 1.$\phi(H\times K)\le \phi(H)\phi(K)$
La prueba de ser, por supuesto, si $S_1^2=H$$S_2^2=K$,$(S_1\times S_2)^2=H\times K$. Existe una posibilidad de que esta es una igualdad, que no he sido capaz de evaluar todavía. Y finalmente nos damos cuenta de que
Propiedad 2. Si $G$ es abelian y $N\le G$,$\phi(G)\le \phi(G/N)\phi(N)$.
Deje $R$ ser un conjunto fijo de representantes de los cosets en $N$ con el grupo de operación definida por $r_1,r_2\in R$, $r_1r_2=r_3$ donde $r_3$ es tal que $r_1r_2N=r_3N$. Por supuesto, $R\cong G/N$. Ahora vamos a $R_0$ ser tal que $R_0^2=R$$|R_0|=\phi(R)=\phi(G/N)$, y deje $S_0$ ser tal que $S_0^2=N$$|S_0|=\phi(N)$. Desde $G$ es abelian tenemos $R_0S_0=S_0R_0$, y desde el cosets de $N$ partición $G$, se deduce que
$$(R_0S_0)^2=R_0^2S_0^2=RN=\bigcup_{r\in R}rN=G$$
Por lo tanto $\phi(G)\le |R_0S_0|\le |R_0|\cdot |S_0|\le \phi(G/N)\phi(N)$.
Esto nos da la siguiente propiedad de grupos cíclicos.
Propiedad 3. Supongamos $G$ es finito abelian, a continuación, $$\phi(G)\le \prod_{p^{\alpha}\, \mid\mid \, |G|}\phi(Z_p)^{\alpha}$$
Esto se desprende de la clasificación de finito abelian grupos y los dos anteriores propiedades, sin embargo, voy a dar una prueba de que sólo el uso de solvencia y de la propiedad 2. Desde $G$ es abelian es solucionable. Desde $G$ es también finito, existe una cadena de
$$1=G_0\triangleleft G_1\triangleleft\dots \triangleleft G_n=G$$
tal que $G_{n+1}/G_n$ es cíclico con el primer pedido. Por la propiedad 2 entonces tenemos que
$$\phi(G)\le \prod_{i=1}^{n-1}\phi(G_{i+1}/G_i)=\prod_{p^{\alpha}\, \mid\mid \, |G|}\phi(Z_p)^{\alpha}$$
donde la última igualdad proviene de la construcción que $G_{i+1}/G_i\cong Z_p$ algunos $p\mid |G|$ todos los $i$, así como la observación de que cada una de las $Z_p$ se producirá $v_p(|G|)$ veces.
Esta prueba es útil porque si la Propiedad 2 puede ser extendido al conjunto de los grupos de $\mathcal{C}$ $\mathcal{S}$ es el conjunto de solucionable grupos, luego de la Propiedad 3 se extiende automáticamente a todos los de $\mathcal{C}\cap\mathcal{S}$.
Otras Observaciones
Claramente si $S\subseteq H$$H<G$, es decir, $H$ es un buen subgrupo de $G$,$S^2\subseteq H^2=H\neq G$. Donde sabemos que $H^2=H$ desde $H\subseteq H^2$ (desde $1\in H$), y $H^2\subseteq H$ desde $H$ es cerrado bajo la operación. Desde $\langle S\rangle$ es el menor subgrupo que contiene $S$, debemos tener por esto $\langle S\rangle =G$. Por lo tanto cuando se mira en los grupos cíclicos, vemos que $S$ necesariamente contiene un generador.
Por supuesto, esto no afectará mucho al considerar $Z_p$ sin embargo.
