Roots of x-squared minus one modulo a composite

Definitions and mathematical statement

Let $N\geq4$ be composite and let \[ R(N)=\{\overline x\in\mathbb Z/N\mathbb Z:x^2\equiv1\pmod N\}. \] Develop an efficient algorithm for, or a characterization of, the subset of relevant roots intended in the slides. The extract does not define relevant, give a small-root bound or interval, or state any auxiliary information about $N$.

The classes $\pm1$ always satisfy the congruence, so finding an arbitrary root would not express a nontrivial task. A nontrivial root means one not congruent to either $1$ or $-1$. In the classical special case $N=pq$ with distinct odd primes, such a root yields factors through $\gcd(x-1,N)$ and $\gcd(x+1,N)$, as reported in the supplied summary. This fact does not supply an efficient way to find the root from $N$ alone or identify the missing small-root variant.

The general composite input is not silently restricted to two primes. A complete algorithmic target must specify root representatives and size bounds, what factorization information is supplied, and whether output is one selected root, an explicit enumeration, or a compressed characterization. If a runtime bound is in input bit length, write it in terms of $\log N$ and account for output size when listing all roots. The source gives no exact efficiency or success-probability requirement.

Short English statement

Find or characterize the roots of $x^2\equiv1\pmod N$ selected by the missing slide conditions. Trivial roots and the classical factoring implication do not resolve the unspecified small-root task.

Sources

• Alexander May, IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6222, PDF page 17, printed slide 12, schedule source https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; accessed 2026-07-29. The supplied provenance records a PDF/legacy-PPT visual audit.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800023$, source code catalogue entry, Roots of x-squared minus one modulo a composite. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.
• The supplied summary mentions the classical nontrivial-square-root factoring step and Miller--Rabin/splitter context without a separate publication citation.