@KConrad provided a lot of useful details in his answer that also helped me better understand what's going on here and what I want from the problem exactly. I'd like to use a separate answer to summarize what I find most relevant to this specific question, and also provide a bit more details on the algorithmic part.

In essence, what I was looking for boils down to finding a non-trivial homomorphism
$$
f: \mathbb Z[\sqrt{a_1}, \dots, \sqrt{a_n}] \to \mathbb F_{p^2}.
$$
The original question only bothers about preservation of additive expressions (so, like a module homomorphism), so to simplify the answer I won't consider preservation of multiplicative properties here.

It simplifies the situation somewhat, because the degree of $\mathbb Z[\sqrt{a_1}, \dots, \sqrt{a_n}]$ is equal to the number of distinct square-free cores of $a_1, \dots, a_n$. In terms of $\mathbb Q^\times / (\mathbb Q^\times)^2$, as I understand, it would mean the size of $\{a_1,\dots, a_n\}$ rather than $\langle a_1, \dots, a_n \rangle$.

In any case, one way to construct such a homomorphism is, for each distinct square-free core $x$ of $a_i$, to pick one of at most $2$ its possible square roots in $\mathbb F_{p^2}$ (any choice should do), and then for each $a_i = y^2 x$ to define $f(\sqrt{a_i}) = y f(\sqrt x)$, then it's possible to define $f$ on other arguments naturally.

Finally, for the algorithmic part of the process, it's worthwhile to note that we do not need to actually find the square-free cores, and thus we do not need to factorize input numbers. This is because $a_i$ and $a_j$ have the same square-free core if and only if $a_i a_j$ is the full square. Then, in each group of $a_i$ that has the same square-free core, we can choose any square root for one element, and then define
$$
f(\sqrt{a_j}) = \sqrt{\frac{a_j}{a_i}} f(\sqrt{a_i}),
$$
which will be well-defined because $\sqrt{\frac{a_i}{a_j}}$ is rational if $a_i$ and $a_j$ have the same core.