1
$\begingroup$

Depending on $\alpha,N,x$ the sequence $x\mapsto x^\alpha \mod N$ can have a different length. If the first element $x_0$ is initialized with $x_0 = x_r^\alpha$ for a random $x_r$ the sequence will almost always have the same constant size.
We will focus here only at the most common sequences with max size $N_L$ (for given $\alpha,N$).

Depending on chosen $x_0$ it can lead to different, disjoint sequences with still the same max sequence size.


Question: Is there some general formula to compute the number of those sequences (for given $\alpha,N$)?

Edit: The posted & accepted answer did not answered this question but was very helpful.
An answer to this question is still welcome. (edit end)


While tinkering around I already found some formula for some $N, \alpha$ of special structure. The cycle length $\alpha$ modulo some prime factors of $\phi(N)$ and also the factors of $\phi(\phi(N))$ seem to have some impact on that count.
It's also related to the number of different values $N_{\alpha}=|\{x^\alpha \bmod N\}|$ and the max length of those sequence $N_L$.

For $N_\alpha$ it got some answer in another thread. If $N$ is a product of unique prime factors: $$N = \prod_{i=1}^n p_i$$ The number of different values $N_\alpha$ would be $$N_{\alpha} =\prod_{i=1}^n\left(1+\frac{p_i-1}{\mathrm{gcd}(\alpha,p_i-1)}\right)$$ For $N_L$ I only made up some equations which do work out for some $N, \alpha$. A general formula would also be welcome.
Both together could lead to an approximation of the sequence count.

Side-question: Do those sequence have a special name? Is this and other properties described somewhere (in a compact form)?


The target $N$ will also have $2$,$3$ or $4$ odd unique prime factors.

$\endgroup$

1 Answer 1

2
$\begingroup$

This is a very difficult and unsolved in general mathematical problem. Maybe you should focus your question to specific cases and possibly ask at mathoverflow but there is always the risk that they may be ignored, unless you demonstrate prior research and ask well-considered questions.

The specific case of $N$ prime has been considered by Igor Shparlinski. A good place to start is to chase up citations to his work. As explained in the abstract of the paper I mention below, this problem is intimately related to other problems and applications in number theory.

Chua and Shparlinski, On the cycle structure of repeated exponentiation modulo a prime, Journal of Number Theory, vol. 107 (2004) pp. 345–356.

I could access a copy via

Elsevier here

Note that some results were obtained by assuming the generalized Riemann hypothesis which Shparlinski and his coauthor removed, this alone should tell you how hard this problem is in the generality you seem to want. In that paper, some moments of cycle length and number of cycles are estimated.

I suggest it may be more helpful to you if you do more research and see what other related results have been obtained in the literature before asking again a related very general and heavily mathematical question here on crypto stackexchange.

$\endgroup$
9
  • $\begingroup$ Thanks for the info & link. The problem is the potential target special case relies at the sequence length & count. Building up $\alpha,N$ for some properties did work out. Unifying them did not - I'm almost sure it won't work out at the very end. I looked for some clarity about this. Too long threads including all what have been done also get ignored in most cases. And on mathoverflow you will need some extra portion of luck. You will never know if its either unsolvable/hard or just no answer. $\endgroup$
    – J. Doe
    Apr 1 at 15:54
  • $\begingroup$ This $x^\alpha$ is one attempt of solving the more general problem projecting random values into a as small as possible 3D domain with encrypted relation in between these points. All questions done here are about trials solving this problem. They are part of many different topics. Fully understanding each of those topics and finding out they won't work out would take a long time as non-cryptographer/mathematician. So I'm thankfully for any guidance on topics which might work out. $\endgroup$
    – J. Doe
    Apr 1 at 15:55
  • $\begingroup$ no worries, happy to help when I can. what exactly do you mean by 3D? $\endgroup$
    – kodlu
    Apr 1 at 17:14
  • $\begingroup$ Something which is arranged similar like a 3-dimensional torus, so a set of values which is cyclic in 3 directions (+ their inverse direction & about same size in each direction). It doesn't need to have each of those 6 direction for each member (like for $x^{\alpha_i} \bmod N$ with 6 suitable $\alpha_i$). Some network with nodes having $1$ to $n$ neighbors wold also work. However the neighborhood of one member need to be representable at three 2D planes (it's three 2-torus to be exact) with an intersection point of that member. The node density need to be around equal everywhere. .. $\endgroup$
    – J. Doe
    Apr 1 at 21:28
  • $\begingroup$ ..Some deterministic way of mapping neighbors to a plane need to exist. Something like a neighbor-radii need to exist - a node can not have neighbors all over the surface. Graphically speaking if random dots on a sheet of paper represent the different members the members closest would be most likely his neighbors (or neighbors of neighbors)(we wrap around the sheet border - so the net is cyclic in two dimensions like in a 2-torus). To describe what I'm looking for we give all dots/nodes on that sheet also a number. So each number on that sheet has a set of numbers as bidirectional neighbors.. $\endgroup$
    – J. Doe
    Apr 1 at 21:29

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.