I have a tricky problem I'm working on solving, and it involves the following subproblem:
Let $C$ be a large odd 64-bit constant. Given an integer $0 \leq N < 2^{37}$, find integers $x, y$ such that
\begin{align*} x \cdot C = 2^{27} N + y \pmod{2^{64}} \end{align*} and \begin{align*} 0 \leq x, y < 2^{27} \end{align*}
if they exist, or return "no solution" if no such $x, y$ exist.
Obviously given $N$ there is only one degree of freedom as any choice of $x$ fixes $y$.
Currently I am solving this for my relevant constants $C$ with a space-time tradeoff by iterating over all values of $x$ and seeing which $N$ they are a solution for, and storing that in a table for lookup given any $N$. This is fast but the tables are slow to build and take up a lot of memory (many gigabytes). It is a bottleneck for me currently and I don't know how to improve it.
I did some investigative work and found that the values of $N$ for which this equation admit a solution have an interesting structure. For instance, if you set $C = 6364136223846793005$, I noticed that if some $N$ admits a solution, then either (at least?) one of $N + 417, N + 418, N + 471, N + 472, N + 899, N + 890$ also admits a solution, and this seems to cover all inputs which admit solutions as well.
But I wasn't able to find a pattern to which one of the six "offsets" above will be the correct one for any given $N$; the pattern looks pretty regular but seems to change subtly and unpredictably over the range of $N$.
The relatively regular distribution of the $N$ for which the equation admits a solution suggests to me that there is some approach involving the extended Euclidean algorithm which could be used to solve for $x$ given $N$, but I'm not seeing it. Can somebody help me out?
It's kind of like trying to find an $x$ such that $xC$ has particular most significant bits...