It is easy to see that if $(z,u,w)$ is a primitive pythagorean triple, then $w$ is odd and either $z$ is odd and $u$ is even or $z$ is even and $u$ is odd. WLOG suppose that $u=2x$ is even, so $z$ is odd. Then
$$u^2=4x^2=w^2-z^2=(w+z)(w-z).$$
It is plain that $\gcd(w+z,w-z)=2$, so $y_1:=(w+z)/2$ and $y_2:=(w-z)/2$ are relatively prime positive integers. Thus
$$x^2=y_1y_2,$$
and therefore $y_1$ and $y_2$ are relatively prime divisors of $x^2$. This implies that $y_1$ and $y_2$ are perfect squares, so write $y_1=a^2$ and $y_2=b^2$. Hence,
$$u=2x=2ab,\quad z=y_1-y_2=a^2-b^2,\qquad\text{and}\qquad w=y_1+y_2=a^2+b^2.$$
This proves that every primitive triple has the form $(a^2-b^2,2ab,a^2+b^2)$, as wanted.
Of course, the condition $\gcd(a,b)=1$ is needed, otherwise $(a^2-b^2,2ab,a^2+b^2)$ won't be primitive.
One way to find the decomposition of $173$ fairly quickly is to observe that the two component squares must add up to a number er ending with $3$. But $0+3$ fails because no square ends in $3$, and various other attempts die for a similar reason except for $4+9$. So you know the even square in the decomposition must have a square root ending with $2$ or $8$, thus limiting trials.
If you can set up screenings based in quadratic residues in modular arithmetic (basically I used mod $5$ in my argument above), you can design a reasonably efficient method to get the required sum of squares for a given prime hypotenuse.
Best Answer
If $a^2+b^2=c^2$ with integers $a,b,c$, recall that the square of an even number is $\equiv 0\pmod4$ and the square of an odd number is $\equiv1\pmod8$. Therefore, either $a,b,c$ are even (and then $\frac12ab$ is even) or $c$ and one of $a,b$ are odd and the other is a multiple of 4 (because its square is a multiple of 8), so again $\frac12ab$ is even.