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
📎 参考文章
学会啦