Erm, this seems too simple? If $p-1 \ge 6$ we can recover $a_i^2$ using $a_ia_j \cdot a_ia_k \cdot (a_ja_k)^{-1}$, and if we know $a_i^2$ $\pmod {p}$, we know $a_i$. So $p \ge 7$ is good enough. If $p=5$, we cannot find whether $a_1=1, a_2=2$ or $a_1=2, a_2=1$. So $p \ge 7$ is the answer.

rkm0959 wrote: Erm, this seems too simple? If $p-1 \ge 6$ we can recover $a_i^2$ using $a_ia_j \cdot a_ia_k \cdot (a_ja_k)^{-1}$, and if we know $a_i^2$ $\pmod {p}$, we know $a_i$. So $p \ge 7$ is good enough. If $p=5$, we cannot find whether $a_1=1, a_2=2$ or $a_1=2, a_2=1$. So $p \ge 7$ is the answer. But if you don't know which one is a_1*a_2？

MF163 wrote: Let $p>3$ be a prime and let $a_1,a_2,...,a_{\frac{p-1}{2}}$ be a permutation of $1,2,...,\frac{p-1}{2}$. For which $p$ is it always possible to determine the sequence $a_1,a_2,...,a_{\frac{p-1}{2}}$ if it for all $i,j\in\{1,2,...,\frac{p-1}{2}\}$ with $i\not=j$ the residue of $a_ia_j$ modulo $p$ is known? Note that there is index $x$ such that $a_xa_r$ takes all the residues from $2$ to $\frac{p-1}{2}$. Thus, we must have $$a_x\cdot \left(\frac{(p-1)(p+1)}{8}-a_x\right)=\sum_r a_xa_r\equiv 2+3+\ldots+\frac{p-1}{2}=\frac{(p-1)(p+1)}{8}-1\pmod{p},$$which is equivalent to $(a_x-1)(a_x+\frac{9}{8})\equiv 0 \pmod{p}$. If $a_x\equiv 1\pmod{p}$, then $a_{r_1}a_{x}\equiv 2\pmod{p}$. If $a_x\equiv \frac{-9}{8}\pmod{p}$, then $a_{r_1}a_{x}\equiv 2\cdot \frac{-9}{8}=\frac{-9}{4}\pmod{p}$. Note that $2\equiv \frac{-9}{4}\pmod{p}\Longleftrightarrow p=17\implies a_x\equiv 1$. If $2\equiv \frac{-9}{8}\pmod{p}\Longleftrightarrow p=5$. This case implies either $a_x\equiv 1,2$. We conclude that for every $p>5$ is always possible to determine the sequence.