$5$ is a prime number, but it can be expressed as $2*3*3$ mod $13$.
So I am wondering if we are given a number $l$ and a prime $p$ that is smaller than $l$ but doesn't divide it, can we write write $p$ as a product of a small number of small factors (mod $l$)?
And here by small I mean some function of l like $\log(l)$ or $log(l)^2$ or even $l^\epsilon$ where $\epsilon < 1$.
Thanks.
The best known bound for a quadratic the least quadratic non-residue modulo a prime $l$ is as far as I know (see Burgess - The distribution of quadratic residues and non-residues) $$ \ll l^{\frac{1}{4\sqrt{e}}} $$ thought it is conjectured to be much smaller.
Now the least quadratic non-residue is a prime, and given any factorization it will have necessarily at least a prime quadratic non-residue on it. This means that the least order of magnitude you may hope for with current knowledge is $l^{\frac{1}{4\sqrt{e}}} $.
On the positive side, according to this paper for any $p \pmod{l}$ you can find $a,b \ll l^{3/4}$ such that $ab \equiv p \pmod{l}$, so this gives $\epsilon \le \frac{3}{4}$ in your factorization.
Note: the symbol $\ll A$ means a constant times $A$, it is similar to $O(A)$.