Score:1

Is there a general formula for the number of different sequences produced with $x\mapsto x^\alpha \mod N$?

at flag

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.

Score:2
sa flag

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.

J. Doe avatar
at flag
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.
J. Doe avatar
at flag
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.
kodlu avatar
sa flag
no worries, happy to help when I can. what exactly do you mean by 3D?
J. Doe avatar
at flag
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. ..
J. Doe avatar
at flag
..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..
J. Doe avatar
at flag
..Besides that a number can also have (other) neighbors on up to 2 additional sheets (2-torus each). If multiple numbers are on two different sheets (2-tori) they all lay on one line (1-torus) - like at the intersection of two 2-tori. With this the node distances/neighbor-edges are equal in between those nodes. At least $2^{32}$ nodes are at 3 sheets. Given two random members it should be as hard as possible (related to the total amount of members) to find the existing connection from one node to the other (target about $2^{100}$ computation steps)...
J. Doe avatar
at flag
..The adversary can also run the program and generate random values/nodes. Not so nice but multiple instances of about the same structure can exist (not much more than 10) - so for random nodes there is only a (about constant) chance to be connected. Best would be if random nodes of a single target instance can be generated without leaking security related information. The total member size (including the instances) should be as small as possible (best case $\approx 2^{100}$ members (may only work with nodes), $\approx 2^{150}$ members if the problem is not reducible to 1D each )...
J. Doe avatar
at flag
..This I think is the most general problem description. If we go back to aligned $6$-neighborhood it would be $x^{\alpha_i} \bmod N$ with 6 suitable $\alpha_i$ again. For a higher member size like $2^{218}$ members EC can be a sub-optimal solution (not a 3-torus). With $2^{300}$ members $x^\alpha$ does the job - but that's way to many members...
J. Doe avatar
at flag
..They will serve as an euclidean and random but consistent arrangement of seeds for a RNG which can be iteratively constructed starting at a random point and proceeding with euclidean near neighbors and finally resulting (after endless of time for generation) into the same consistent (secret) structure. ....and way too long again. Thanks for reading if you reached that point.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.