RSA: Detecting period of unconcealed messages Referencing:
Project Euler Problem 182 Clarification

I'm trying to determine the (minimum) period for a given value of $(p, q)$. 

For a simple case where $p=19,q=23$ the period of repeating order is 132 (which I assume is from 2x2x3x11, the prime factors of 18 and 22).
It's trivial to explore the number-space of 132 to see where $\gcd(e,\phi)=1$ and $\gcd(e,p-1)=2$ and $\gcd(e,q-1)=2$. Same goes for when $p=1009$ and $q=3643$ and I calculate the period to be 152964.

But what about for larger values for $p$ and $q$, like $p=232919$, $q=233117$?

Given that $\phi = 54296912488$, and the prime factors of $p-1$ are 2, 7, 127, 131 and the prime factors of $q-1$ are 2, 13, 4483 then I calculate the period is 27148456244 (is there any possibility of reducing this number-space?)
Is there any other order/period that can be used to my advantage in order to drastically reduce the number of gcd calcs that I have to perform?
Convention states that $P &gt; Q$.
At best, there are 9 unconcealed messages. I'll refer to these as $U_0$ through $U_8$.
Here are some relationships between these.

\begin{align*}
U_0&amp;=0\\
U_1&amp;=1\\
U_2&amp;=kP, &amp;&amp;\text{where $k=1$ to $Q/2$. Test if unconcealed. Stop once you find one.} \\
U_3&amp;=kQ, &amp;&amp;\text{where $k=1$ to $P/2$ (try $U_2\pm1$ before trying multiples of $Q$).} \\
U_4&amp;=U_2+U_3 \bmod N \\
U_5&amp;=N-U_4 &amp;&amp;\text{(also, $U_6+U_7 \bmod N$)} \\
U_6&amp;=N-U_3 \\
U_7&amp;=N-U_2 \\
U_8&amp;=N-U_1 \\
\end{align*}

Looking at this example, there is no period for unconcealed messages. Also note $e$, $\phi$, and Carmichael values are not needed.

$P=47, Q=23, N=1081$, where $e$ results in 9 unconcealed messages.

\begin{align*}
U_0&amp;=0 \\
U_1&amp;=1, &amp;U_8&amp;=1080, &amp;U_1+U_8&amp;=N \\
U_2&amp;=46, &amp;U_7&amp;=1035, &amp;U_2+U_7&amp;=N \\
U_3&amp;=47, &amp;U_6&amp;=1034, &amp;U_3+U_6&amp;=N \\
U_4&amp;=93,  &amp;U_5&amp;=988, &amp;U_4+U_5&amp;=N \\
\end{align*}

The most you'll need to test is $(P+Q)/2$ and will often be far less. This reduces the number-space you need to search.

For clarity:

$$U_0=N \bmod N, \quad \text{or $0$}$$

The first pair is $U_1=N+1 \bmod N$ and $U_8=N-1 \bmod N$. Their sum equals $N$.

The second pair, $U_2$ and $U_7$ are a multiple of either $P$ or $Q$ and sum $N$. If the is a multiple of $P$, then you only need to search to $Q/2$ as these mirror each other. Once you go beyond $Q/2$ you are testing the same values against the other half of the pair.

Similarly, the third pair, $U_3$ and $U_6$, will be a multiple of the other factor with the same consideration (sum $N$ and test to $P/2$ assuming this is a multiple of $Q$). This would be $Q$ if the second pair were a multiple of $P$, and $P$ if the second pair were a multiple of $Q$. The small numbers which I've tested, $U_3$ is $U_2\pm1$. Which means $U_6$ is also $U_7\pm1$. I don't know why this is, or if this holds for larger numbers. I have yet to code this and test.

The fourth pair, $U_4$ and $U_5$, also sum $N$. This pair is calculated from pair two and three. $U_4=U_2+U_3$, you can append '$\bmod N$' for consistency, but since both are $\mathit{factor}/2$, these will always sum less than $N$. Conversely, $U_5$ is the sum of $U_6$ and $U_7$, both on the high side of $\mathit{factor}/2$ due to their relation of $U_2$ and $U_3$, therefore will sum greater than $N$ and will require '$\bmod N$'.

So, three unconcealed messages are known, $U_0$, $U_1$, and $U_8$. By discovering $U_2$ and $U_3$, the remaining four can be calculated. In the process of discovering $U_2$ and $U_3$, the multiple, $k$, ranges from $1$ to $\mathit{factor}/2$. You can stop once a factor is found because the compliment is calculated. Then test $U_3$ as $U_2\pm1$ before testing multiples of the opposite factor.

When the selection of $e$ results in more than 9 unconcealed messages, these same 9 are always the same, as they are based on $P$ and $Q$.

There are three simple formulas, $U=k*\mathit{factor}+1, U=k*\mathit{factor}, U=k*\mathit{factor}-1$, which demonstrate concisely how and why these 9 relate to each other the way they do. It was an awesome discovery and I'll share in another post.