Identifying the type of algorithm for a PRNG that uses modular multiplication and addition
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
GNU libc uses the following pseudo-random number generator: $$(mathitstate times 1,103,515,245) + 12,345 pmod 2^31$$ where state is the result of the previous call to the generator.
My questions are:
What are PRNGs using this algorithm - possibly using different numerical
constants - called?Assume that this generator has the maximum possible period. What is its
period?Given the result of a call to this PRNG, show how to obtain the result of
the previous call symbolically?
For the last question it is not required to perform any numerical
calculation.
This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.
random-number-generator pseudo-random-generator
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
add a comment |Â
up vote
4
down vote
favorite
GNU libc uses the following pseudo-random number generator: $$(mathitstate times 1,103,515,245) + 12,345 pmod 2^31$$ where state is the result of the previous call to the generator.
My questions are:
What are PRNGs using this algorithm - possibly using different numerical
constants - called?Assume that this generator has the maximum possible period. What is its
period?Given the result of a call to this PRNG, show how to obtain the result of
the previous call symbolically?
For the last question it is not required to perform any numerical
calculation.
This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.
random-number-generator pseudo-random-generator
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
GNU libc uses the following pseudo-random number generator: $$(mathitstate times 1,103,515,245) + 12,345 pmod 2^31$$ where state is the result of the previous call to the generator.
My questions are:
What are PRNGs using this algorithm - possibly using different numerical
constants - called?Assume that this generator has the maximum possible period. What is its
period?Given the result of a call to this PRNG, show how to obtain the result of
the previous call symbolically?
For the last question it is not required to perform any numerical
calculation.
This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.
random-number-generator pseudo-random-generator
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
GNU libc uses the following pseudo-random number generator: $$(mathitstate times 1,103,515,245) + 12,345 pmod 2^31$$ where state is the result of the previous call to the generator.
My questions are:
What are PRNGs using this algorithm - possibly using different numerical
constants - called?Assume that this generator has the maximum possible period. What is its
period?Given the result of a call to this PRNG, show how to obtain the result of
the previous call symbolically?
For the last question it is not required to perform any numerical
calculation.
This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.
random-number-generator pseudo-random-generator
random-number-generator pseudo-random-generator
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
edited Aug 11 at 1:41
PaÃ…Âlo Ebermann
18.3k456104
18.3k456104
asked Aug 10 at 20:54
Ashley Watson
505
asked Aug 10 at 20:54
Ashley Watson
505
asked Aug 10 at 20:54
Ashley Watson
505
505
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^31$ in that case).
Finding the previous value is a matter of inverting the iteration: $(textstate - 12345) cdot 1103515245^-1 bmod 2^31$.
answered Aug 10 at 21:24
Samuel Neves
7,0972540
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^31$ in that case).
Finding the previous value is a matter of inverting the iteration: $(textstate - 12345) cdot 1103515245^-1 bmod 2^31$.
answered Aug 10 at 21:24
Samuel Neves
7,0972540
add a comment |Â
up vote
6
down vote
accepted
These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^31$ in that case).
Finding the previous value is a matter of inverting the iteration: $(textstate - 12345) cdot 1103515245^-1 bmod 2^31$.
answered Aug 10 at 21:24
Samuel Neves
7,0972540
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^31$ in that case).
Finding the previous value is a matter of inverting the iteration: $(textstate - 12345) cdot 1103515245^-1 bmod 2^31$.
answered Aug 10 at 21:24
Samuel Neves
7,0972540
These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^31$ in that case).
Finding the previous value is a matter of inverting the iteration: $(textstate - 12345) cdot 1103515245^-1 bmod 2^31$.
answered Aug 10 at 21:24
Samuel Neves
7,0972540
answered Aug 10 at 21:24
Samuel Neves
7,0972540
answered Aug 10 at 21:24
Samuel Neves
7,0972540
answered Aug 10 at 21:24
Samuel Neves
7,0972540
7,0972540
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f61436%2fidentifying-the-type-of-algorithm-for-a-prng-that-uses-modular-multiplication-an%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password