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.
 A: 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.
A: Expanding on my comment, the central symmetry of the product suggests looking at symmetric pairs:
$$
\begin{align}
(z^2-j^2)(z^2-(k-j+1)^2) &=\color{red}{(z-j)}\color{blue}{(z+j)}\color{red}{\big(z-(k+1-j)\big)}\color{blue}{\big(z+(k+1-j)\big)}
\\ &= \color{red}{\big(z^2 - (k+1)z +j(k+1-j)\big)}\color{blue}{\big(z^2 + (k+1)z +j(k+1-j)\big)}
\\ &= \big(z^2+j(k+1-j)\big)^2 - (k+1)^2z^2
\\ &= \big(z^2+n_j\big)^2 - (k+1)^2z^2
\end{align}
$$
Here $\,n_j=j(k+1-j)\,$, which can be calculated recursively with $\,n_1=k\,$ and $\,n_{j+1}=n_{j}+k-2j\,$.
For $\,j=1\,$ to $\,k/2\,$, an approximate count ignoring some half $\,1/2\,$ ops:

*

*the sequence $\,k-2j\,$ can be calculated iteratively by subtracting $\,2\,$ at each step, total $\,k/2\,$ ops;


*the sequence $\,n_{j+1}=n_j+(k-2j)\,$ then takes one addition at each step, total $\,k/2\,$ ops;


*the term $\,\big(z^2+n_j\big)^2\,$ takes $\, 2 \cdot k/2 = k\,$ ops;


*the difference of terms takes $\,k/2\,$ op.


*the multiplication of pairs take $\,k/2\,$ ops.
In the end, it adds up to about $\,3k\,$ ops, which is slightly better than the baseline, but still short of the target $\,2k\,$.
A: This method is similar to marty cohen's.  It uses recursive addition to evaluate polynomials.
It takes $2$ adds and $1/2$ a multiply for each of your quadratic factors $(z^2-i^2)$.
I don't know if your language requires an extra step for a counter that you don't use, but that would be an extra half an add.
Take the $(z^2-i^2)$ in pairs.
$$G(z,m)=(z^2-(2m-1)^2)(z^2-(2m)^2)$$
$G(z,m)$ is a degree-4 polynomial in $m$.  Define
$$H(z,m)=G(z,m+1)-G(z,m)\\
I(z,m)=H(z,m+1)-H(z,m)\\
J(z,m)=I(z,m+1)-I(z,m)\\
K(z)=J(z,m+1)-J(z,m)$$
$H(z,m)$ is cubic in $m$, $I(z,m)$ is quadratic in $m$, $J(z,m)$ is linear in $m$ and $K(z)$ is independent of $m$.
Each of $J,I,H,G$ can be calculated with one addition.
$$J(z,m+1)=J(z,m)+K(z)\\
I(z,m+1)=I(z,m)+J(z,m)\\
H(z,m+1)=H(z,m)+I(z,m)\\
G(z,m+1)=G(z,m)+H(z,m)$$
So each $G(z,m)$ can be calculated in a total of four additions.
Multiply them all together as you go along, with one multiply per pair.
You don't need subscripts as you overwrite $G,H,I,J$ as you go.
A similar trick, with $7k/3$ or $8k/3$ steps per $(z^2-i^2)$, works if you group the $(z^2-i^2)$ in threes, and so on.
