4
$\begingroup$

A cyclic sequence can be produced with

$$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ primes.
and $a$ a primitive root of $p$ and $q$.
The starting point $s_0$ is a square ($\mod N$)
It will produce a cycle of length $\mathrm{lcm}(p-1.q-1)$
(except $s_0$ is a $p$-th or $q$-th power $\mod N$)

Given now a starting point $s_0 = x_1$ it will generate such a cyclic sequence.
Given another starting point $s_0 = x_2$ it will generate a cyclic sequence of same length but it an have completely different members.

Is there any way to transform $x_2$ so it will produce the same cyclic sequence as $x_1$ does?
(Edit: the posted answer is if any and not how, same as the question, will mark it as answer here)


(related to the answer of this)


Update:
It looks like the number of different cycles $N_c$ is: $$ N_c = (S_N - S_{pq}) /L_c$$ $$ S_N = |\{ v^2 \mod N\}| \text{ with } v\in[1,N-1]$$ $$L_c = \mathrm{lcm}(p-1.q-1)$$ and $S_{pq}$ the number of squares which are also a $p$-th, $q$-th power $\mod N$ .
$S_N$ probably always larger than $\frac{1}{4}N$

In some test for $N=3901$ with $P=47$ , $Q=83$, $a = 7$ (or $11, 17, 19,..$) two cycles are possible with $L_c =440$, $S_N = 1006$, $S_{pq}=127$.
One $x1$ can be transformed to a value from the other cycle (which starts with $x_2$) with an exponent $b$ like $x_1^b \mapsto s_i\in \mathrm{cycle}_{x_2}$
This exponent need to be $b \in [3 , 5 , 6 , 10 , 12 , 13, 20 , 21 , 24 , 26 , 27 , 29 , 33 , 35 , 37, 40, 42 , 43 , 45, 47, ...]$
No idea why exactly those values do work out.

For $N=40633, P= 179, Q= 227$ with $S_N= 10259$ squares, including $S_{pq}= 403$ it has $8$ cycles with length $L_c= 1232$. The exponent $a$ for sequence generation can be $a\in[3, 19, 23, 29, 43,..]$
For this exponent $b$ need to be $b \in [7 , 13, 17 , 21, 28 , 39 , 51 , 52 , 62 , 63 , 68 , 71 , 79 , 84 , 110 , 112 , 117,125,..]$
Applying any of those exponents $b$ to a starting value $x_0$ will result in a cycle of the next sequence. This cyclic sequence order is equal for every exponent $b$.

$\endgroup$
2
  • $\begingroup$ I think there's "prime root" where there should be primitive root. Independently, a justification of "except (if) it contains a $p$-th or $q$-th power$\bmod N$" would help me. $\endgroup$
    – fgrieu
    Mar 2 at 10:04
  • $\begingroup$ @fgrieu thanks for the hint. changed ti to primitive root. Unfortunately can't tell yet why this happen for $p$-th, $q$-th power. First time dealing with $\mathrm{mod}$ a non-prime. But I did some test case ($P=47, Q=83, a=7$) about it and as expected it did not work out with those numbers (cycle length of $40$ instead of $440$ in test case). The cycle size was much shorter (but constant) for those numbers tested. An exception again but e.g. $1^p=1$ will result in a cycle length of $1$. $\endgroup$
    – J. Doe
    Mar 2 at 10:57

1 Answer 1

3
$\begingroup$

In analyzing cases like this, it is useful to look at the behaviors modulo $P$ and modulo $Q$ separately, and then see how they combine. I will add in the assumption that $P \ne Q$; you didn't explicitly say so; I believe it is reasonable that you assumed it.

When we look at the cycle structure modulo $P$, we first see that $s_0 \bmod P$ is a quadratic residue modulo $P$ (which is a mathy way of saying "it's a square"); since $a$ is a primitive root of $p$, then we see that there are three cycles:

  • A cycle of length 1 (the value 0)

  • Another cycle of length 1 (the value 1)

  • A cycle of length $p-1$; this is because $a^i \bmod p-1$ are distinct values in the range $[0, p-2]$, and $s_0$ has order $p-1$ (in this group, quadratic residues other than 1 are always that order), and so $s_0^{a^i}$ are $p-1$ distinct values.

We get similar results for looking at the behavior modulo $Q$.

Given those basics, how do they combine?

Well, the cycle modulo $PQ$ repeats only when both the cycle modulo $P$ repeats and the cycle modulo $Q$ repeats; if the $P$-cycle is length $\alpha$ and the $Q$-cycle is length $\beta$, this combined cycle has length $\text{lcm}(\alpha, \beta)$.

This implies that any combination of the two large cycles will have length $\text{lcm}(p-1,q-1)$ (which is a result you have already found). And, there are $\gcd(p-1,q-1)$ ways these two large cycles can combine.

We now consider a combination that includes a small cycle; we have two combinations with cycle length $p-1$, two combinations with cycle length $q-1$, and four combinations with cycle length 1 (which includes $s_0 = 0$ and $s_0 = 1$).

Hence, the total number of cycles is $\gcd(p-1, q-1) + 8$.

And, to answer your question:

Is there any way to transform $x_2$ so it will produce the same cyclic sequence as $x_1$ does?

Well, for any integer $\beta$, we have $s_{i+1}^\beta = (s_i^\beta)^a$. That is, if we take every element of a cycle, and raise it to the power $\beta$, we still have a cycle.

So, if we have the value $\beta$ for which $x_2^\beta = x_1$, then that gives us a way to transform one cycle to another.

It turns out that there is always such a $\beta$ if the two cycles are both large (that is, of length $\text{lcm}(p-1, q-1)$). For the degenerate cycles (all the others), there won't be - however, I don't consider that case that interesting...

Of course, finding such a $\beta$ given $x_1, x_2$ is a nontrivial problem if $P, Q$ are large...

$\endgroup$
6
  • $\begingroup$ thanks for explaining. It's more clear now, During testing around I also found out it is possible (with $x_2^\beta$) (at examples update). I planned to do some new question about it but now there seem so to be no need anymore. So the actually question is how such a $\beta$ can be found. To be clear is it known to be nontrivial problem for large $P,Q$ or was it 'just' an educated guess? Also $x_2^\beta $ don't need to be equal to $x_1$. A $\beta$ with $x_2^\beta=x_1^{a^i}$ would be sufficient. Allowing this many $\beta$ were possible at the example cases ($b$). But can't tell for large $P,Q$. $\endgroup$
    – J. Doe
    Mar 3 at 21:00
  • 1
    $\begingroup$ @J.Doe: finding the specific $\beta$ so $x_2^\beta = x_1$ is known as the 'discrete log problem' (over a composite); it is known to be as hard are factoring the modulus (and solving the discrete log in both the prime groups). The more general problem of finding any $\beta$ as you mentioned may be easier - actually, a random guess has a good probability of working, but it's not clear how one would verify your guess. On the other hand, I can't think of a hard problem that it would reduce to... $\endgroup$
    – poncho
    Mar 3 at 21:06
  • $\begingroup$ ... But even such a general $\beta$ would probably depend at the chosen $x_2$ value or more precisely the sequence it will generate. So probably another operation is needed which return the same value for each sequence element. If such an operation exits random values could be tested against this. So the whole problem could also be rephrases as picking random values out of a single sequence (while many other exist) without leaking security related parameter or a relation to other sequence elements (like random $s_i$ for given $s_0$) $\endgroup$
    – J. Doe
    Mar 3 at 21:19
  • $\begingroup$ Ok, DLP would be hard. Also though about this but deleted it again because for sequences with $x_i = x_o \cdot g^i \mod P$ it can be done without the DLP. But this is also from one given value to a random value out of the sequence ( more general version). $\endgroup$
    – J. Doe
    Mar 3 at 21:47
  • $\begingroup$ shouldn't it be $a^i \mod p$ with values from $1$ to $p-1$ instead of $a^i \mod p-1$ with values from $0$ to $p-2$? $\endgroup$
    – J. Doe
    Mar 4 at 17:04

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.