Given a large random (prime or composite) N, how do I find $a$ (non-trivial: $a\neq1$ and $a\neq{N-1}$) and $b<N/2$ such that $a^b=1 \bmod N$ as quickly as possible?
I'm guessing I need to factor N to get the totient, but hoping there is some faster trick.
For example, what $a$ and $b$ work for the following $N$?
535681323635377947803477563729034842741283197685482147845846116229490072327829772255980786581056231891824965196685872407087235634574765922267452145891219949840333521605137458047897130486331989436075480864422748548516493270268959879090425463
While you are struggling with giving an example, let me mention that it is in general not easy to find the order of an element $a$ modulo $N$.
Think about the case when $N = pq$ is a product of two different prime numbers. If you pick a random number $a$ modulo $N$, then there is a significant probability that $a$ is in fact a primitive root modulo both $p$ and $q$. Thus knowing the order of $a$ modulo $N$ will likely let you know $\phi(N)$, and that again implies that you know the factorization of $N$.
Therefore a factorization of $N$ seems unavoidable to me.
Of course, once $N$ is factorized, you know everything and the task becomes trivial.