Can we somehow compute $(z^2 - 1)(z^2 - 4)(z^2 - 9)(z^2 - 16) \cdots (z^2 - k^2)$ in half the number of operations? Let $f(z, k) = (z^2 - 1)(z^2 - 2^2)(z^2 - 3^2)(z^2 - 4^2) \cdots (z^2 - k^2)$ in less than $1 + k + k + k + (k-1) = 4k$ arithmetic operations, specifically I need it to be roughly $2k$ operations or less.
In the cost formula, the first $1$ comes from needing to square $z$, the first $k$ from incrementing a counter $k$ times to make up $1, 2, 3, \dots k$, i.e. you don't get to have arbitrary constants or tables of constants which really wouldn't add much efficiency anyway.  The second $k$ comes from squaring each $k$, the third $k$ comes from the subtraction in each parenthesis.  The $(k-1)$ comes from the $(k-1)$ multiplications.  So that the totals is $4k$ arithmetic operations if computed directly using the given formula for $f$.
Where does this come from?  These are the factors (combined) in $\dfrac{x!}{(x - 2k - 1)!}$ where $z$ is taken to the median factor in the sequence $x(x-1)(x-2)\cdots (z+1)z(z-1) \cdots (z-k)$.  I don't know if that is 100% accurate, but that part doesn't matter.  Just to tell you where it comes from.  Computing this directly requires twice as many operations as $f(z,k)$.  So already in computing a factorial I've reduced the operations by half.  So I'm just wondering if we can or can't find a way of reducing it by another half.

Question. How can we compute $f(z,k)$ in $2k$ arithmetic operations or less (roughly)?

If you can do it with $\dfrac{8k}{5}$ operations or something that would also be interesting if you get my drift.

This might help because of group theory: All the arithmetic is done modulo some $n\in \Bbb{N}\setminus 1$ and $\sqrt{n} \geq z,k$.  But note $n$ will be huge or 1000's of digits (think RSA numbers that are hard to factor).  But also note that we can take each $1,2,3,\dots, k$ as well as $z$ to be coprime to $n$ because in any factorization algorithm you can check the result of every arithmetic operation and only add a polynomial factor slow-down (the cost of computing $\gcd(x\pmod n, n)$).  Thus on the right we have that the results of all arithmetic operations are units in $\Bbb{Z}/n$.  If it turns out that they're not, then we can halt the algorithm because a factor has been found or $\gcd(x\pmod n, n) = n$ in which case we can stop computing the long factorial and change the binary search parameters to another range $[y,x]$ because a $\gcd$ result of $n$ would indicate "you've gone too far" and included all factors of $n$, so back up and try again.
Because of coprimality, the set $\{ y^2 \pmod n\} \leqslant (\Bbb{Z}/n)^{\times}$ forms a subgroup of the units.  We're also able to "pretend that we're working in a field" because of this, that is until a factor is found.  I know that other integer factorization algorithms do just that.

Using $(n+1)^2=n^2+(2n+1)$,
set $m=1, j=3, y=z^2-1, p=y$.
Then
$m=m+j, j=j+2, y=y-m, p=p*y$
until $j=(k+1)^2$.
So $j=3, 5, 7, ...,
m=1, 4, 9, ...,
y=z^2-1, z^2-4, ...
$.
Each step takes 2 adds, 1 subtract,
and 1 multiply.
Don't immediately how to do it faster.
