On square root modulo $2^t-1$

Question

Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?

Answer 1

It is not known if there is a more efficient way to solve this than via factoring $2^t-1$. At a high level, it is well-known that your problem (search Quadratic Residuoisity) reduces to factoring $2^t-1$, e.g. you can solve your problem by factoring $2^t-1$, and similarly in the reverse direction.

Note that $2^t-1$ is a Mersenne number. There is a surprisingly large interest in factoring mersenne numbers as part of the GIMPS project. In particular, the aformentioned Wikipedia article contains the excerpt

As of September 2022, the largest completely factored number (with probable prime factors allowed) is $$2^{12,720,787} − 1 = 1,119,429,257 \times 175,573,124,547,437,977 \times 8,480,999,878,421,106,991 \times q,$$ where $q$ is a 3,829,294-digit probable prime. It was discovered by a GIMPS participant with nickname "Funky Waddle".

The data for factoring this is here. It looks like a combination of trial division and Pollard's $p-1$ algorithm (which may be sped up for Mersenne numbers), though on this page I also see reference to ECM (a general-purpose factoring algorithm that finds small factors fast). The justification for the usage of these (though not ECM) in GIMPS is here*.

Therefore, it is unlikely you can solve your problem more efficiently than factoring $2^t-1$ (though this can be done mildly more efficiently than normal with the modified version of Pollard's $p-1$ algorithm described in the above starred link). If this could be done, then by the aformentioned equivalence one could also factor $2^t-1$ more efficiently. If one could factor $2^t-1$ more efficiently, it would be surprising if GIMPS wasn't using this more efficient factoring method.