# Is there a cyclic RNG without an explicit form for $i$'th element which is guaranteed to have a sum of zero (subset of elements, $\mod P$ possible)

Let $$X$$ be a sequence element list of (pseudo) random values generated by a RNG and $$x_i \in X$$ a member of it. The period length is $$k = |X|$$ and it is a cyclic generator. For $$i>k$$ the value $$x_i = x_{((i-1) \mod k)+1}$$ (the list of random value outputs repeats again after $$k$$ values)

Now is there any such RNG with a sum of zero (of selected elements) :

$$0 =\sum_{j=1}^k \delta(x_j)\cdot g(x_j)$$

with $$e_m =\sum_{j=1}^m \delta(x_j)\cdot g(x_j)$$ $$s =\sum_{j=1}^k \delta(x_j)\cdot x_j$$ $$c =\sum_{j=1}^k \delta(x_j)$$

using $$\delta()$$ as a selection function (selects by value). $$\delta(x_j) =\begin{cases} 1 &\quad\text{if x_j should be part of the sum} \\ 0 &\quad\text{else} \\ \end{cases}$$ $\delta\ could be e.g. only values which are less than a number or end with a 7 or have integer root or...what ever you like (but not index related) an $$g()$$ as a modifier function to accomplish a sum of 0. That could be e.g.: $$g_1(x) = x \mod P$$ $$g_2(x) = x -s/c$$ Target values and restrictions: +Amount of unneeded computations should be small: $$k/c < 10$$ +Number of unique values of partial sum should be as many as possible $$|\{e_m, 0 < m <= k\}|=u$$ $$u/c > 0.6$$ +Computation time of $$\delta, g$$ should not increase during run time +able to scale +there should exists no efficient way to compute $$x_i$$ or $$g_i$$ for given $$i$$ (except $$i=k$$ or $$i=v+k$$ for known $$x_v$$) or index $$i$$ for given value $$w=x_i$$ (source code and runtime variables are known by the attacker, some linear speedup of $$<10$$ times is allowed) +The RNG need to be started at different seeds but still generating all elements in $$X$$ in the same order. Some seeds may generate a different $$X'$$ with different values and/or order. Not more than 4 of those $$X$$ is allowed. +There need to be a way to randomly pick a seed for the RNG +Number of possible seeds $$>=c/2$$ +random value type can be integer, real, complex, vector, .... anything your like but it need to be representable in binary format Outro & Example With formulas above I tried to generalize the question. A valid solution would also be a RNG which produces a permutation of all values between $$1$$ and $$N$$. For Example $$N=2^8-1=255$$. The sum of those would be $$N \cdot (N+1)/2$$. To accomplish a zero sum $$\delta(x)$$ could just be $$1$$ all the time and $$g(x) = x \mod (P=2^7)$$ If now for some reason the RNG produces all values from $$1$$ to $$300$$ $$\delta(x)$$ could only be $$1$$ for $$x$$ with a highest leading bit of $$0$$. With this it only sum up values from $$0$$ to $$255$$ again. • I don't understand the selection function what does "if$x_i$is a part of the sum" mean? Which sum? Do you want to find a subset$J$of the index set$\{1,\ldots,k\}$where$\delta(x_i)=1$if and only if$i \in J$? And what is the set$X$? Subset of reals? Integers? – kodlu Nov 27 '19 at 3:10 • @kodlu Given a pseudo random number generator with a seed then$X$is a list of all random numbers the RNG generates until it generates the same sequence of length$k$again. The first number of such a RNG generates would be$x_1$, the 2nd$x_2$and so on ($X = [x_1,x_2,x_3, ... ,x_k]$). The random values can be integer,real,complex numbers, vectors,..whatever you like but it need to be computed at a common PC so values need to be stored in binary system of limited length. – J. Doe Nov 27 '19 at 13:36 • @kodlu The sum of all selected values should be zero:$0 =\sum_{j=1}^k \delta(x_j)\cdot g(x_j)$. The selection function$\delta$is not by index. It is by value. E.g. only sum up values which are less than a number or end with a 7 or have integer root or... whatever you like. The selected values are a subset of$S=\{X\}$with size$|S| <= k$, with$\{X\}$all unique values of list$X$. If the modifier function$g()$is applied to all selected values ($\forall x_j \in X \land \in S_{selected}$, with$S_{selected} = \{\forall s_i \in S, \text{with} \delta(s_i)=1\}$) the sum of those should be zero. – J. Doe Nov 27 '19 at 13:48 • @fgrieu explicit form can be generalize to 'there should be no faster way known to compute the$i$'th element than iterate to it '. Linear speedups$<10$times are ok. As far as I know it need to be bound to$x_{i+1} = f(x_i) $. Other internal states or values are possible but they won't be hidden. Users have interest to find index$i\$ themself and share all internal variables. Use case: Two users which start at different seed should not know the index of a value generated by the other users RNG. (the index for their own RNG to generate the other users value (at know index of their RNG)) – J. Doe Nov 27 '19 at 14:13
• You should edit the question and include these details. – kodlu Nov 27 '19 at 20:53