(The problem is my original, unless there's prior art I'm unaware of.)
Given a parallelogram whose vertices have all integer coordinates, you can give it a "massage". Each "move" of the massage is a shear transformation where one side remains fixed and the opposite side is shifted by a vector parallel to that side and also with integer coordinates. That vector will necessarily be a multiple of the vector equal to the side itself (understood as a vector) divided by GCD(x,y) where x and y are the coordinates of the side-as-vector.
Question:
Is it possible to massage any such parallelogram into an axis-aligned rectangle? If so, how hard is the problem of finding the right sequence of moves? I understand that it is at least as hard as integer factorization, because the solution explicitly gives a factorization of the (necessarily integer) area of the parallelogram, which is preserved by moves. But is it harder? Is the sequence of moves easily computed from either a bifactorization or full factorization of the area?
EDIT: Revisiting this with a fresh mind and after Jean Marie's comments:
- We can fix a vertex to the origin and always move a "free" side so the fixed vertex stays at origin; this simplifies the model.
- If we manage to bring either side to an axis, it's one more trivial move (a shear along that axis) and we're done.
- If we could massage the parallellogram so that one of the side-vectors have non-coprime coordinates, then the GCD of the coordinates would necessarily divide the area. This is because that side would contain lattice points along its length, allowing us to slice the parallelogram evenly into smaller ones with integer area, which is clearly only possible if the number of the smaller ones divides the area. We could then keep massaging the small one, and the big one would notionally follow. So a necessary condition for general possibility is to always be able to massage a prime area $p$ into a $1 \times p$ rectangle. Always nice to reduce (part of) a problem to primes!
A provisional answer whose merit is to give a simplified version of your problem.
Do we agree that any translation can be decomposed into (at most) four successive "massages"? See figure below: going from Red parallelogram to Blue parallelogram, is done by transiting through the Black parallelogram. One can move from R to B by two "massages", from B to R as well by two "massages".
Then we can assume WLOG that our parallelogram (P) has one of its vertices at the origin, the 3 other ones being
$$u=\binom{a}{b}, \ v=\binom{c}{d}, \ u+v=\binom{a+c}{b+d}$$
Let us assume that the area of (P) is equal to the determinant of $u,v$, i.e., $ad-bc$ assumed WLOG positive is factorizable as $L \times W$. Then, the problem boils down to being able to find a sequence of "massages" sending parallelogram (P) onto rectangle with vertices:
$$\binom{0}{0}, \ u'=\binom{L}{0}, \ v'=\binom{0}{W}, \ u'+v'=\binom{L}{W}$$
which is possible (working backwards) if matrix $M$ defined by:
$$M\begin{pmatrix}L&0\\0&W\end{pmatrix}=\begin{pmatrix}a&c\\b&d\end{pmatrix} \iff M=\begin{pmatrix}a/L&c/W\\b/L&d/W\end{pmatrix}$$
has integer entries.
Remark: one can check that $\det(M)=1$ which is necessary for area preservation.
I stop here because I want to see first if you agree with what I have said.