The context is the following: I am performing some calculations on long integers in Montgomery form, and I need to know their parity without converting them back to normal form (which is slow). An integer $x \in [0; m)$ in Montgomery form is $x^\prime = (x R)\ \mathrm{mod}\ m$, where $m$ is an odd modulus, and $R = 2^k$. I wonder if there's a computationally easy way to find out $x\ \mathrm{mod}\ 2$ given only $x^\prime$
(To be more specific, I need to calculate $(a x + b y)/ 2\ \mathrm{mod}\ m$, where $a$ and $b$ are small integers, and $x$ and $y$ are long integers for which I only have their Montgomery form $x^\prime$ and $y^\prime$ - so I need to know the parity of $x$ and $y$ to apply corrections by 1. Or perhaps there's an easier way to do it?)
You can calculate $\ \left(\frac{ax+by}{2}\right) \mod{m} $ from $\ a,b,x',y'\ $ and $\ m\ $ without needing to find the parities of $\ x\ $ and $\ y\ $. You already have $$ R(ax+by)\equiv ax'+by'\mod m $$ and $$ 2\left(\frac{m+1}{2}\right)\equiv1\mod m\ . $$ Therefore \begin{align} \left(\frac{ax+by}{2}\right)&\equiv\left(\frac{m+1}{2}\right)^{k+1}R(ax+by)\mod m\\ &\equiv\left(\frac{m+1}{2}\right)^{k+1}(ax'+by')\mod m\ . \end{align} If multiplication $\ \mod m\ $ is computationally easy, then the square and multiply algorithm makes the calculation of $\ \left(\frac{m+1}{2}\right)^{k+1}\ $ easy for any likely value of $\ k\ $.