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?

  • 1
    $\begingroup$ How do you define 'the period of unconcealed messages'? $\endgroup$
    – poncho
    Sep 20 '17 at 18:38
  • $\begingroup$ Interesting question! @poncho I think he is using the definition of a period as the repeating part of the decimal. 19/23 has a repeating cycle of 132 digits. Paul, please correct me if I'm incorrect. $\endgroup$
    – Q-Club
    Sep 20 '17 at 20:14
  • $\begingroup$ By period (or is order a better word?) I mean the repeating sequence. For example, with p=19,q=23, the period is 132 such that the minimal number of unconcealed messages occur at e = 35,47,59,71,83,95, 107,119,131 and then repeat at 167,179,191,203,215,227,239,251,263. Or stated differently, There is a minimal unconcealed messages at e=35+(n*132) and 47+(n*132) [...] $\endgroup$
    – Paul Bunn
    Sep 20 '17 at 20:41
  • $\begingroup$ Are you sure? My calculations show that e=5, 17, 29, 41, 53, 65, 101, 113, 137, ... (in addition to the ones you have listed) also achieve the minimum. And, the period would appear to be 66... $\endgroup$
    – poncho
    Sep 20 '17 at 21:12
  • $\begingroup$ I also calculated 152964 as the repeating number of decimal digits for the expanded fraction 1009/3643. $\endgroup$
    – Q-Club
    Sep 20 '17 at 21:28

The diagram below may help. The upper left is my inputs, P, Q, and e, with the corresponding calculations. Below this is a table showing the 9 quines and how they relate to P and Q. Upper center shows quine calculation. Upper right shows multiples of P and Q are quines.

Then we get into the bigger table. Down the first column are messages. Across the top is 0 to lambda, with increasing multiples (k) as these rows go up. I've included a short note above some of the e values. Near the middle are the number of quines (in red) for each e, when it meets certain conditions. The red cells are 1 (multiplicative identity). The blue cells are when the values equal the original message (quine). The other colors are when number match P, Q, and e, or match a quine.

Notice that $0 < e < \lambda$, as well as d' (based on $\lambda$), where d (based on $\phi$) is d' + a multiple of $\lambda$ (47 = 17 + 30). As $\lambda$ divides $\phi$. Also, the second column of 1's is the start of the period. And column 3 is $ed \equiv 1 \pmod{n}$, the multiplicative identity. Therefore, any number raised to the power of 1 is itself, which is my RSA works.

Looking at RSA in two dimensions allows us to see some symmetry in both axis. The second table shows the 9 quines (blue) along the vertical axis and the formula to calculate each. Along the right side of this table shows a few of thes symmetries. Along the horizontal axis, where e=15 is $\lambda/2$. We can see the e values which meet those conditions mirror each other. I'm not certain of the exact pattern yet, but these are $6n \pm 1$ (where n is a multiple and not the product of PQ).

So to answer the original question, each message has a different period (spot the red 1's horizontally for each message), which divides $\lambda$, except for multiples of P and Q. However, $\lambda$ would probably be the smallest period you are looking for when calculating which $e$ produces the minimum number of quines.

Quines vs Lambda


Convention states that $P > 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&=0\\ U_1&=1\\ U_2&=kP, &&\text{where $k=1$ to $Q/2$. Test if unconcealed. Stop once you find one.} \\ U_3&=kQ, &&\text{where $k=1$ to $P/2$ (try $U_2\pm1$ before trying multiples of $Q$).} \\ U_4&=U_2+U_3 \bmod N \\ U_5&=N-U_4 &&\text{(also, $U_6+U_7 \bmod N$)} \\ U_6&=N-U_3 \\ U_7&=N-U_2 \\ U_8&=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&=0 \\ U_1&=1, &U_8&=1080, &U_1+U_8&=N \\ U_2&=46, &U_7&=1035, &U_2+U_7&=N \\ U_3&=47, &U_6&=1034, &U_3+U_6&=N \\ U_4&=93, &U_5&=988, &U_4+U_5&=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.

  • $\begingroup$ When I state U3=U2+/-1, clearly I don't mean U3 is both U2+1 and U2-1. It will be one or the other. The same for U6=U7+/-1 will be either U7+1 or U7-1, and not both. However, they will be opposite signs. If U3=U2+1 then U6=U7-1. Essentially U2 and U3 will have a difference of 1, and U6 and U7 will also have a difference of 1. $\endgroup$
    – Carl Knox
    Nov 5 '17 at 17:07
  • $\begingroup$ Thanks for taking the time to write such a detailed answer Carl, it is appreciated. I will try to incorporate this into my algorithm in the next week or so, and will mark it as accepted answer if it checks out. $\endgroup$
    – Paul Bunn
    Nov 9 '17 at 23:20
  • $\begingroup$ I've had time to look at this again. Let's take the simple case where p=47,q=23. This gives a value of phi=(p-1)(q-1)=1012 enumerating through all e from 3 to phi, where gcd(e,t)==1 and gcd(e,p-1)==2 && gcd(e,q-1)==2 results in the following sequence: 3 7 15 19 27 31 35 39 43 51 59 63 71 75 79 83 87 91 95 103 107 119 123 127 131 135 147 151 159 163 167 171 175 179 183 191 195 203 211 [...] 1081 I don't see how that ties into this answer.. $\endgroup$
    – Paul Bunn
    Nov 19 '17 at 1:28
  • $\begingroup$ Try gcd(e-1,p-1)==2 && gcd(e-1,q-1)==2. See my answer in Project Euler Problem 182 Clarification. $\endgroup$
    – Carl Knox
    Nov 19 '17 at 4:27
  • $\begingroup$ The 9 unconcealed messages are 0, 1, 1080, 46,1035,47, 1034, 93, 988. This worked exactly as described above. The period is 506, or a divisor such as 253, 46, 23, and 11. This depends on the message. $\endgroup$
    – Carl Knox
    Nov 19 '17 at 5:12

It turns out that finding the period is equivalent to factoring $N$.

The period divides $\operatorname{lcm}(p-1, q-1)$. So by the time you factor $N$ to get $p$ and $q$, you already have done the factoring. The other way to do this is brute force guessing of R which is not better than brute force guessing $p$, $q$, $\phi$, $d$, or any other RSA variable.

\begin{align*} N &= p \cdot q \\ R &= \operatorname{lcm}(\phi(p-1), \phi(q-1)) \end{align*}

An option might be to try $R$ as powers of 2, from $2…N-1$, as the lcm will be an even number.

  • $\begingroup$ Since I know the values for p,q already (and therefore, p-1,q-1 and N) does this change the complexity of calculation? I thought that knowing the prime factors of p-1 and q-1 might be useful, which are relatively inexpensive to calculate. $\endgroup$
    – Paul Bunn
    Oct 23 '17 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.