type
status
date
summary
password
category
slug
icon
LCG基本都学了，问了 一道题，挨骂了，小师傅说很简单，我觉得很难（不敢说），最后还是自己解决咯(lcg_6),这里来复习一下(毕竟我的记性……🥀🥀🥀🥀
目录
线性同余生成器 / 线性同余方法（LCG）
📑概念
线性同余方法（LCG）是个产生伪随机数的方法
LCG的性能和随机性取决于选取的参数。如果选择恰当的参数，LCG可以生成长周期和均匀分布的伪随机数序列。然而，不恰当的参数选择可能导致序列的周期较短或者存在可预测的模式，从而影响其随机性和安全性
LCG的周期最大为 M，但大部分情况都会少于 M。要令LCG达到最大周期，应符合以下条件：
- B,M 互质；
- M 的所有质因数都能整除 A-1
- 若 M 是4的倍数，A-1 也是
- A,B, 都比 M 小
- A,B 是正整数
💻代码
🔢公式及推论
公式
推论
① (已知)
很简单，公式： b左移，两边同乘a（mod m）下的逆
② 求a (已知）
③ 求b (已知）
④ 求m (已知多组x)
🫣例题
🐾lcg_1
📑题目
🪄题解
seed 给了，a,b,n,已知所有随机数都已知，ciphertext = seed^plaintext—→plaintext = seed^ciphertext
👀wp
🐾lcg_2
📑题目
🪄题解
flag就是seed,已知a,b,n,c求seed，即① (已知)
👀wp
🐾lcg_3
📑题目
🪄题解
知道两个连续的随机数，已知a,n， ③ 求b (已知）
b→flag
👀wp
🐾lcg_4
📑题目
🪄题解
flag→seed
知道产生的所有随机数，求seed, a,b未知，先求a ( ② 求a (已知）),再求b (③ 求b (已知） ) 然后求恢复seed (① (已知))
👀wp
🐾lcg_5
📑题目
🪄题解
和上一题一样，但是n不知道，多了一步求n (④ 求m (已知多组x))
👀wp
✨✨✨lcg_6
📑题目
🪄题解
hnp问题，构造格，恢复低位，高位已知，即可求出所有随机数
👀wp
二元LCG
题目
🪄题解
👀wp
三元LCG
LCG Revenge
🪄题解
xs = xs[1:] + [new_state]这一步相当于一个队列，将flag的第一部分丢掉，在队尾插入新的new_state。
求seed需要在前面插入
xs = [xs0] + xs[:2]👀wp
📎 参考文章
学会啦