0
$\begingroup$

I'm trying to figure out what is period of PCG generator XSL-RR-RR:

https://www.pcg-random.org

https://en.wikipedia.org/wiki/Permuted_congruential_generator

If we use just random multiplier and increment in LCG in that PCG. M. O'Neill wrote:

"For the PCG family, arbitrary k-dimensional equidistribution (and the huge periods it implies) requires PCG's extended generation scheme."

It looks like their generators has big periods, XSL-RR-RR too. But I can't find accurate information about that. She proved somehow that they are k-dimensional equidistributed. But what is k exactly, what periods it implies and could it be the same with every parameter of LCG in XSL-RR-RR? She tested some specific multiplier and increments so maybe other ones have worse parameters and periods?

I don't understand exactly why she use just some specific miltipliers (two ones if I understand it well) and increments in XSL-RR-RR. What will happen if we will use other, random ones?

$\endgroup$
3
  • $\begingroup$ LCGs are fun to be sure. But is there something deeper that you're thinking about? Is there an ultimate objective, especially related to security (this is the crypto forum after all)? Some here can help. $\endgroup$
    – Paul Uszak
    Jan 27 at 21:42
  • $\begingroup$ In this case it is rather math problem, but people here know well such topics, so I thought someone can give me answear. If they all have a big periods it implies that we can built quite fine cipher with just some number of keyed LCGs in PCG, one by one. PCG with specific keyed LCG could be just one round of the cipher and if it has big period and other parameters, as with multipliers proposed by M. O'Neill - it will be strong (keyed) PRF. So that's my motivation. $\endgroup$
    – Tom
    Jan 27 at 21:51
  • $\begingroup$ I wrote about PCG, not LCG. Anyway cipher is different story. Now I have to decide what is period of PCG with random LCG mod 2^128 and what are properties of such generators (do they also pass randomness tests). $\endgroup$
    – Tom
    Jan 28 at 0:44
1
$\begingroup$

PCG is just LCG where the output is run through a transformation. The amount of internal state of the PCG - which is what controls the period - is all contained in the underlying LCG. So the period is $2^n$ where $n$ is the number of bits of state. The only thing to worry about is if the output transformation makes the period smaller, but since it's a permutation it does not.

When pcg-random.com talks about "arbitrary" period, they just mean that they have a way to make the internal state arbitrarily large. For a given state size, the period is the same as other algorithms of the same size.

$\endgroup$
13
  • $\begingroup$ Thus to achieve period 2^128 we can use Hull–Dobell Theorem, which guarantee full period in LCG mod 2^n. So PCG mixer itself does not change the period length, right? By the way note that XSL-RR-RR transform 128-bit input into 128-bit output. I find it not obvious to prove, that period of PCG will be the same as in LCG, which we used in that PCG (XSL-RR-RR). How do you know that? I suspect that it's true for every permutation on which we act with some mixer. But, for example, permutation composition is also kind of mixer and it won't preserves cycles. $\endgroup$
    – Tom
    Jan 28 at 21:26
  • $\begingroup$ What is expected cycle length in random 128-bit LCG? Is is the same as in uniform random permutation, where expected cycle length is about 2^127? $\endgroup$
    – Tom
    Jan 29 at 0:03
  • $\begingroup$ The periods of LCG are well-studied, see the Wikipedia article for details. $\endgroup$
    – bmm6o
    Jan 29 at 0:18
  • $\begingroup$ Something is wrong here. If we consider LCG + simple mixer it is not always true that expected period of such generator will be the same. Let's reverse block after every step in our mixer. It looks like LCG + reverse gives different expected period (I can't proof it, but it looks like this). So how do we know that something changing the permutation in such a complicated way like XSL-RR-RR will give us the same period as underlying LCG. And by the period I understand expected cycle length (maybe I undesrtand it wrong?). $\endgroup$
    – Tom
    Jan 29 at 12:54
  • $\begingroup$ Your WP link claims XSL-RR-RR is invertible, therefore a permutation, therefore the period is the same as the LCG. I'm not sure what you mean by "reverse", but if it's invertible it won't affect the period. $\endgroup$
    – bmm6o
    Jan 29 at 16:12

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.