info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
PRNG based on two LCGs - will it pass spectral tests?
91 views
Skip to first unread message
osobli...@gmail.com
Dec 30, 2021, 6:01:22 PM12/30/21
to
Let's consider two LCGs mod 2^32. Now let's consider we are iterating next numbers by switching this two LCG's randomly. So we start with seed and calculate next numbers using one time one generator, then another (randomly).
Now let's consider that we only do 32 such iterations. Then we randomly select a new seed and run 32 iterations again. Over and over again. So we have sequences consist of 32 numbers, each sequence is started with a random seed and these sequences are generated using randomly switched LCG.
I am researching such generators for some reasons. I use powerful output mixers on them (otherwise they would be very weak generators), but that's not what I want to ask.
Suppose I randomly select multipliers and increments in such LCGs. Will spectral tests detect problems in such generators? Suppose I intentionally choose multipliers with wrong parameters - will the classic spectral test detect anything in this case?
I can't do spectral tests, so I can't check it. As far as I understand spectral tests, such a generator design will cause the spectral test will not detect the distribution of points on hyperplanes, because for that to be the case, the successive numbers generated by LCG must appear in a certain order.
At the same time such generators (without output mixers) fail the tests very badly (NIST, PractRand). This is probably due to the problems with low bits, which the design I propose does not completely eliminate. There are still some bad patterns, even if we would reseed the generators every 32 iterations and even if we switch two LCGs randomly (such operations are not enough to eliminate pathologies on low bits). Nevertheless - the question is whether such a design avoids problems with the spectral tests?
Now let's consider that we only do 32 such iterations. Then we randomly select a new seed and run 32 iterations again. Over and over again. So we have sequences consist of 32 numbers, each sequence is started with a random seed and these sequences are generated using randomly switched LCG.
I am researching such generators for some reasons. I use powerful output mixers on them (otherwise they would be very weak generators), but that's not what I want to ask.
Suppose I randomly select multipliers and increments in such LCGs. Will spectral tests detect problems in such generators? Suppose I intentionally choose multipliers with wrong parameters - will the classic spectral test detect anything in this case?
I can't do spectral tests, so I can't check it. As far as I understand spectral tests, such a generator design will cause the spectral test will not detect the distribution of points on hyperplanes, because for that to be the case, the successive numbers generated by LCG must appear in a certain order.
At the same time such generators (without output mixers) fail the tests very badly (NIST, PractRand). This is probably due to the problems with low bits, which the design I propose does not completely eliminate. There are still some bad patterns, even if we would reseed the generators every 32 iterations and even if we switch two LCGs randomly (such operations are not enough to eliminate pathologies on low bits). Nevertheless - the question is whether such a design avoids problems with the spectral tests?
osobli...@gmail.com
Dec 30, 2021, 6:23:26 PM12/30/21
to
I would like to add that my doubts concern whether with such a project we have to worry about the correct selection of multipliers at all, since spectral tests will not detect anything anyway (as it seems to me, maybe they will)?
David Eather
Dec 30, 2021, 11:51:30 PM12/30/21
to
On 31/12/2021 8:55 am, osobli...@gmail.com wrote:
> Let's consider two LCGs mod 2^32. Now let's consider we are iterating next numbers, switching this two LCG's randomly. So we start with seed and calculate next numbers using one time to one generator, then another (randomly).
>
> At the same time, such generators (without output mixers) fail the tests very badly (NIST, PractRand). This is probably due to the problems with low bits, which the design I propose does not completely eliminate. There are still some bad patterns, even if we would reseed the generators every 32 iterations and even if we switch two LCGs randomly (such operations are not enough to eliminate pathologies on low bits). Nevertheless - the question is whether such a design avoids problems with the spectral tests?
>
No. All output of a LCG are linearly related to the previous output
> Let's consider two LCGs mod 2^32. Now let's consider we are iterating next numbers, switching this two LCG's randomly. So we start with seed and calculate next numbers using one time to one generator, then another (randomly).
>
> Now let's consider that we only do 32 such iterations. Then we randomly select a new seed and run 32 iterations again. Over and over again.
>
> So we have 32 numerical sequences of numbers started with random seeds, and these strings are generated using randomly switched LCG.
> Now let's consider that we only do 32 such iterations. Then we randomly select a new seed and run 32 iterations again. Over and over again.
>
>
> I am researching such generators for some reasons. I use powerful output mixers on them (otherwise they would be very weak generators), but that's not what I want to ask.
>
> Suppose I randomly select multipliers and increments in such LCGs. Will spectral tests detect problems in such generators? Suppose I intentionally choose multipliers with wrong parameters - will the classic spectral test detect anything in this case?
>
> I can't do spectral tests, so I can't check it. As far as I understand spectral tests, such a generator design will make the spectral test will not detect the distribution of points on hyperplanes, because for that to be the case, the successive numbers generated by LCG must appear in a certain order.
> I am researching such generators for some reasons. I use powerful output mixers on them (otherwise they would be very weak generators), but that's not what I want to ask.
>
> Suppose I randomly select multipliers and increments in such LCGs. Will spectral tests detect problems in such generators? Suppose I intentionally choose multipliers with wrong parameters - will the classic spectral test detect anything in this case?
>
>
> At the same time, such generators (without output mixers) fail the tests very badly (NIST, PractRand). This is probably due to the problems with low bits, which the design I propose does not completely eliminate. There are still some bad patterns, even if we would reseed the generators every 32 iterations and even if we switch two LCGs randomly (such operations are not enough to eliminate pathologies on low bits). Nevertheless - the question is whether such a design avoids problems with the spectral tests?
>
No. All output of a LCG are linearly related to the previous output
Max
Dec 31, 2021, 9:45:14 AM12/31/21
to
On 31.12.21 05:51, David Eather wrote:
> On 31/12/2021 8:55 am, osobli...@gmail.com wrote:
>> Let's consider two LCGs mod 2^32. Now let's consider we are iterating
>> next numbers, switching this two LCG's randomly. So we start with seed
>> and calculate next numbers using one time to one generator, then
>> another (randomly).
>>
>> Now let's consider that we only do 32 such iterations. Then we
>> randomly select a new seed and run 32 iterations again. Over and over
>> again.
>>
*snip*
> On 31/12/2021 8:55 am, osobli...@gmail.com wrote:
>> Let's consider two LCGs mod 2^32. Now let's consider we are iterating
>> next numbers, switching this two LCG's randomly. So we start with seed
>> and calculate next numbers using one time to one generator, then
>> another (randomly).
>>
>> Now let's consider that we only do 32 such iterations. Then we
>> randomly select a new seed and run 32 iterations again. Over and over
>> again.
>>
>>
>
> No. All output of a LCG are linearly related to the previous output
output, he would simply have a TRNG, if he never re-seeds it, he gets
the full linear series. I was wondering what the "threshold" is at which
the linearity starts to show and can be utilized. I just don't have an
approach to assess how much information those series of 32 iterations
really leak. So, how much easier it is to guess the next value in the
series after 1, 2, 3, ... runs.
Message has been deleted
Message has been deleted
Chris M. Thomasson
Jan 1, 2022, 6:18:23 PM1/1/22
to
On 1/1/2022 6:16 AM, osobli...@gmail.com wrote:
> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
>
> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
>
> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
>
>
> def XSLRR(x):
> count = x >> 28
> x16 = (x ^ (x >> 16)) & 65535
> x = (x16 >> count) | (x16 << (16 - count)) & 65535
> return x
>
> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
>
> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
Try it with the Salsa20 core as a mixer and see how it does:
https://en.wikipedia.org/wiki/Salsa20
> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
>
> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
>
> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
>
>
> def XSLRR(x):
> count = x >> 28
> x16 = (x ^ (x >> 16)) & 65535
> x = (x16 >> count) | (x16 << (16 - count)) & 65535
> return x
>
> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
>
> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
Try it with the Salsa20 core as a mixer and see how it does:
https://en.wikipedia.org/wiki/Salsa20
osobli...@gmail.com
Jan 1, 2022, 9:25:38 PM1/1/22
to
By the way here the authors studied spectral scores and summarized as follows:
https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3030
"We remark that good spectral scores are known to be correlated with success in certain statistical tests, and in particular with the collision test (see Knuth,3 §3.3.2.I) and the birthday-spacing test (see Knuth,3 §3.3.2.J). We have verified empirically that in several cases our multipliers provide LCGs that in isolation perform better than previous proposals (e.g., better than Knuth's MMIX LCG3 with multiplier 6364136223846793005). However, there is currently no mathematical theory that can prove whether these improvements percolate to the output once other PRNGs are mixed in, or when using output functions with good mixing properties, as in the LXM case."
I think the spectral properties of the multipliers do matter, because both my generators and the regular LCG with the output mixer fail in PractRand faster with the bad multipliers. But figuring out why this is happening can be difficult (no theory). We will almost certainly not see bad properties in spectral tests, because mixers remove them. But some artifacts remain, since bad multipliers perform worse.
One could simplify this question and ask why PCG generators perform worse with bad multipliers (suppose we choose them so that at least the period is maximum)? The creator of PCG wrote a little about it:
https://www.pcg-random.org/posts/critiquing-pcg-streams.html
PCG certainly do not show the spectral problems that characterize LCG. But nevertheless, multipliers with good spectral scores perform better in PractRand tests. For the sake of simplicity, I am testing the 32-bit LCG and 32 bit to 16 bit version of XSLRR.
From these few of Melissa O'Neil's tests and from my tests it appears that we can use really bad multipliers and we won't lose much in quality. If XSLRR generator with good multiplier would fail after 2^n bytes, then with bad multiplier would fail after about 2^(n*0.85) bytes.
Chris M. Thomasson
Jan 3, 2022, 5:26:46 PM1/3/22
to
On 1/1/2022 6:25 PM, osobli...@gmail.com wrote:
> niedziela, 2 stycznia 2022 o 00:18:23 UTC+1 Chris M. Thomasson napisał(a):
>> On 1/1/2022 6:16 AM, osobli...@gmail.com wrote:
>>> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
>>>
>>> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
>>>
>>> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
>>>
>>>
>>> def XSLRR(x):
>>> count = x >> 28
>>> x16 = (x ^ (x >> 16)) & 65535
>>> x = (x16 >> count) | (x16 << (16 - count)) & 65535
>>> return x
>>>
>>> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
>>>
>>> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
>>
>> Try it with the Salsa20 core as a mixer and see how it does:
>>
>> https://en.wikipedia.org/wiki/Salsa20
>
> But Salsa20 needs 16 32-bit numbers of which 256 bits are the key. So how should I use this core? It seems to me that this will only obscure the matter. How will it relate to the answer on question, do spectral scores matter in my generator? Salsa20 has nothing to do with it.
>
>
> By the way here the authors studied spectral scores and summarized as follows:
>
> https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3030
[...]
> niedziela, 2 stycznia 2022 o 00:18:23 UTC+1 Chris M. Thomasson napisał(a):
>> On 1/1/2022 6:16 AM, osobli...@gmail.com wrote:
>>> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
>>>
>>> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
>>>
>>> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
>>>
>>>
>>> def XSLRR(x):
>>> count = x >> 28
>>> x16 = (x ^ (x >> 16)) & 65535
>>> x = (x16 >> count) | (x16 << (16 - count)) & 65535
>>> return x
>>>
>>> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
>>>
>>> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
>>
>> Try it with the Salsa20 core as a mixer and see how it does:
>>
>> https://en.wikipedia.org/wiki/Salsa20
>
> But Salsa20 needs 16 32-bit numbers of which 256 bits are the key. So how should I use this core? It seems to me that this will only obscure the matter. How will it relate to the answer on question, do spectral scores matter in my generator? Salsa20 has nothing to do with it.
>
>
> By the way here the authors studied spectral scores and summarized as follows:
>
> https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3030
I was just thinking about using a LCG to create blocks that the Salsa20
core can work on... Then output the result of the mix. Something like:
create a block using LCG.
mix it using Salsa20.
output the result.
create another block using LCG, xor it with the Salsa20 output, then run
it through Salsa20 again, output, repeat.
I wonder how the outputs score in various tests Btw, I am quite fond of ent:
https://www.fourmilab.ch/random/
and DieHarder...
osobli...@gmail.com
Jan 5, 2022, 6:05:14 PM1/5/22
to
poniedziałek, 3 stycznia 2022 o 23:26:46 UTC+1 Chris M. Thomasson napisał(a):
> On 1/1/2022 6:25 PM, osobli...@gmail.com wrote:
> > niedziela, 2 stycznia 2022 o 00:18:23 UTC+1 Chris M. Thomasson napisał(a):
> >> On 1/1/2022 6:16 AM, osobli...@gmail.com wrote:
> >>> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
> >>>
> >>> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
> >>>
> >>> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
> >>>
> >>>
> >>> def XSLRR(x):
> >>> count = x >> 28
> >>> x16 = (x ^ (x >> 16)) & 65535
> >>> x = (x16 >> count) | (x16 << (16 - count)) & 65535
> >>> return x
> >>>
> >>> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
> >>>
> >>> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
> >>
> >> Try it with the Salsa20 core as a mixer and see how it does:
> >>
> >> https://en.wikipedia.org/wiki/Salsa20
> >
> > But Salsa20 needs 16 32-bit numbers of which 256 bits are the key. So how should I use this core? It seems to me that this will only obscure the matter. How will it relate to the answer on question, do spectral scores matter in my generator? Salsa20 has nothing to do with it.
> >
> >
> > By the way here the authors studied spectral scores and summarized as follows:
> >
> > https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3030
> [...]
>
> I was just thinking about using a LCG to create blocks that the Salsa20
> core can work on... Then output the result of the mix. Something like:
>
> create a block using LCG.
I have to create 16 blocks, not one, becase Salsa needs 16 32-bit blocks.
> On 1/1/2022 6:25 PM, osobli...@gmail.com wrote:
> > niedziela, 2 stycznia 2022 o 00:18:23 UTC+1 Chris M. Thomasson napisał(a):
> >> On 1/1/2022 6:16 AM, osobli...@gmail.com wrote:
> >>> I would like to add that such generators perform worse when we use multipliers with a bad score in spectral tests.
> >>>
> >>> In PractRand they can withstand up to 2^23 bytes with bad multipliers (e.g. 65539 and 3722304989 - they are really bad) and with good multipliers (e.g. 2891336453 and 29943829) they do not wrap up to 2^27 bytes.
> >>>
> >>> On the output I use a bit mixer dedicated to LCG (taken from PCG generators), 32-bit to 16-bit version XSLRR by Melissa O'Neil (Python code):
> >>>
> >>>
> >>> def XSLRR(x):
> >>> count = x >> 28
> >>> x16 = (x ^ (x >> 16)) & 65535
> >>> x = (x16 >> count) | (x16 << (16 - count)) & 65535
> >>> return x
> >>>
> >>> Otherwise the generators would fail immediately. Either way, it's a very small range of scores in PractRand (2^23 vs 2^27) compared to the huge range between spectral scores in between mutipliers 65539, 3722304989 and 289133645, 29943829.
> >>>
> >>> I wonder what PractRand detects in this case? Why it prefers multipliers with good spectral scores? Theoretically, a spectral test even without an output mixer should not show anything (or maybe he will show something?). There must therefore be something else wrong with multipliers with bad spectral scores.
> >>
> >> Try it with the Salsa20 core as a mixer and see how it does:
> >>
> >> https://en.wikipedia.org/wiki/Salsa20
> >
> > But Salsa20 needs 16 32-bit numbers of which 256 bits are the key. So how should I use this core? It seems to me that this will only obscure the matter. How will it relate to the answer on question, do spectral scores matter in my generator? Salsa20 has nothing to do with it.
> >
> >
> > By the way here the authors studied spectral scores and summarized as follows:
> >
> > https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3030
> [...]
>
> I was just thinking about using a LCG to create blocks that the Salsa20
> core can work on... Then output the result of the mix. Something like:
>
> create a block using LCG.
> mix it using Salsa20.
>
> output the result.
>
> create another block using LCG, xor it with the Salsa20 output, then run
> it through Salsa20 again, output, repeat.
>
> I wonder how the outputs score in various tests Btw, I am quite fond of ent:
>
> https://www.fourmilab.ch/random/
>
> and DieHarder...
https://www.pcg-random.org/paper.html
https://vigna.di.unimi.it/ftp/papers/LXM.pdf
Maybe worse, maybe better. For sure it will be slow compared to PCG mixers, so there is no point in using such "big mixers" like salsa for LCG. What is more, they are not dedicated to LCG and you can certainly get better results by performing a much smaller number of mixing operations, but designed to overcome the drawbacks of LCG concretely.
Chris M. Thomasson
Jan 5, 2022, 11:01:53 PM1/5/22
to
purposes", it might be fun to mix two different LCG algorithms together
to produce a single output stream using the salsa20 core. Humm... Or the
same LCG algorithm using different seeds?
Nomen Nescio
Apr 9, 2022, 11:08:41 PM4/9/22
to
Look at this :
https://github.com/hcastillomartinez/LCG-and-Cipher
"osobli...@gmail.com" <osobli...@gmail.com> a écrit dans le message de
news: 2ec8dc7a-50a2-451a...@googlegroups.com...
https://github.com/hcastillomartinez/LCG-and-Cipher
"osobli...@gmail.com" <osobli...@gmail.com> a écrit dans le message de
news: 2ec8dc7a-50a2-451a...@googlegroups.com...
Let's consider two LCGs mod 2^32. Now let's consider we are iterating next
numbers, switching this two LCG's randomly. So we start with seed and
calculate next numbers using one time to one generator, then another
(randomly).
Now let's consider that we only do 32 such iterations. Then we randomly
select a new seed and run 32 iterations again. Over and over again.
numbers, switching this two LCG's randomly. So we start with seed and
calculate next numbers using one time to one generator, then another
(randomly).
Now let's consider that we only do 32 such iterations. Then we randomly
select a new seed and run 32 iterations again. Over and over again.
0 new messages