Blogs

泊松定理设 是正整数， 是常数，则对于任意的正整数 有 对于公式的理解:这里的 可以理解为期望，即整个事件发生的平均值泊松定理表明了，在重复次数足够多的情况下，二项分布的分布率趋向泊松分布 离散型随机变量0-1 分布若随机变量 的可能取值只有 ，且那么就称其为 0-1 分布 二项分布若随机变量 的分布律满足且其中的 那么称 满足服从参数 的二项分布，记为 容易发现，在 的时候退化为 0-1 分布二项分布的概率意义是在n次独立实验（放回）中，事件出现k次的概率 泊松分布若随机变量 满足其中的 为常数，则称变量 服从泊松分布，记为 注意，这里的 k 的可能取值是从0开始的泊松分布的 可以认为是事件的期望，即平均值泊松分布刻画的是在平均值为 的情况下，变量出现小概率事件 的概率 几何分布如果随机变量 的分布律满足其中 那么称变量 服从参数为 的几何分布，记作 几何分布描述的是单次实验概率为 的事件在前 次不发生，在第 次发生的概率 几何分布的无记忆性无记忆性的概率表达式是 超几何分布假定在 N 件产品中有M件不合格品 ...

函数调用完成控制转移之后的栈形态从图中可以看到，在完成了控制转移等一系列操作之后，函数的第一个实参的地址在 的位置上，这是由于前面依次是 EBP旧值 和 返回地址 两个指针，各占据了4个字节 注意，在函数压栈的时候，入口参数是返序压栈的，即先压入栈中的是最后一个参数，而在C语言中写在最前面的参数最靠近 ebp 注意事项： 做题的时候注意题目给出的立即数是小端还是大端方式存放的 看汇编写C语言的时候，除了要注意数据的大小，还要通过指令的类型来区分是有符号数还是无符号数 函数调用的几条指令分别的作用： leave 的作用只是先把当前的 esp 设置为当前 ebp 的值，然后把 ebp 恢复成 ebp 旧值 ret 指令的作用是通过上一步恢复的 esp 取出返回地址，把 eip 的值指向返回地址，移交控制权限 call 的作用是保存返回地址，然后移动 eip 到指定位置，移交控制权限

What is it 流密码是一种确定性的算法，通过输入一个随机的种子，输出一串看起来像是随机的比特串 用处是替代PRG，更快地加密 缺点是并没有严格的安全性证明 Definition一个 stream cipher 包括两个部分: Init: GetBits: 此处的 表示状态信息 Init 算法通过输入种子 和一个随机的向量 来输出一个初始状态 GetBits 操作通过获取当前状态输出一个看起来随机的bit 并更新状态为

Background在堆的合并中，仅仅只是拷贝都需要 的时间复杂度，所以希望提出一种更好的数据结构，让堆的合并的效率更高 Definition外节点只有一个儿子或没有儿子的节点，即左右儿子至少有一个为空节点的节点。 距离/零路长距离/零路径长 null path length ： 定义为 X 结点到它的后代中离它最近的外结点的最短路径长度，即两结点之间路径的权值和。特别的，外结点的距离为 0 ，空结点的距离为 。 左式堆左偏树/左式堆：一种满足左偏性质的堆有序的二叉树，其左偏性质体现在左儿子的距离大于等于右儿子的距离。即对于任意一个节点， 左式堆的距离左偏树/左式堆的距离：我们将一棵左偏树根结点的距离作为该树的距离。 合并操作 如果两个堆中有一个堆为空，就直接返回另一个堆。 否则为了合并两个堆，需要比较它们的根。 将具有大的根值的堆H2与具有小的根值的堆H1的右子堆H3合并得到一个新的左式堆，其中H2和H3的合并也采用同样的逻辑。 合并代码示例12345678910111213141516171819202122232425void LeftistHeap::merge(Le ...

Definition of MAC一个消息认证码(Message authentication code or MAC) 算法包括三个部分，即 Gen: 通过输入安全参数，输出一个 key，长度是 Mac: 生成认证码的算法，输入一个 key 和一个消息 然后输出一个tag: Vrfy: 通过输入k,m,t，判断消息是不是有效的(Valid) 如果是，输出1否则输出0 Secure MAC消息认证实验 通过 生成一个key 记为k，k对于攻击者是保密的 攻击者对于标签生成器 MAC 有神谕机的访问权限，可以获取多项式对 记所有的攻击者访问的明文的集合为 攻击者获胜当且仅当 如果攻击者获胜输出1，否则输出0整个实验记作 Plain secure如果一个标签算法是在选择明文攻击下不可伪造的(unforgeable) 当且仅当对于任意PPT的敌手，有 定义的缺陷攻击者可能可以给出以前已经认证过的消息一个新的标签，所以需要定义一个更强的安全性 Strong MACStrong unforgeable 实验 通过 生成一个key 记为k，k对于攻击者是保密的 攻击 ...

negl 可忽视函数定义一个定义在自然数集上的非负函数 是可忽视的当且仅当对任意的正多项式 都存在一个自然数 使得对于任意的大于 的整数，满足 一个等价的定义： 如果对任意一个 满足 那么就是可忽视的 计算安全The Adeversarial indistinguishable experiment (计算安全实验)对于模式 实验 首先输入参数 攻击者 给出两个等长的明文 然后输出给加密算法 加密算法随机依据安全参数调用生成器 Gen 随机生成密钥 key 然后随机采样 加密 并把密文给到 输出一个 如果 那么 赢得这个实验，即 否则为0 计算安全定义如果上面的实验满足对于任意的PPT时间内的敌手，都有那么这个加密方式是满足 eav 不可区分的。 CPA 安全CPA安全实验 首先运行密钥生成器 Gen 生成一个密钥 key 攻击者有向加密器 Enc 加密长度为 神谕机访问权限，并且可以根据访问得到的明文-密文对决定输出一对消息 ，长度也是 的 加密算法随机生成一个bit，即随机采样 然后输出密文 给到 攻击者 还有访问加密神 ...

Definition It’s conjugate（共轭） function is . 注意，这里其实 在输入之后是固定的，是平移 取到距离最远的点 Property 永远是凸函数 if is convex and closed 如果 是凸的并且是可微的，那么$$f^*(y) x^{T} \nabla f(x^) - f(x^*) = x^{*T} y -$$

PRGBackground提出的背景是生成真随机函数的速度太慢了，如果通过CPU温度来生成真随机，那么不能满足加密的速度要求，进而提出一种伪随机方法，来通过比较短的随机种子生成更长的随机串 Definition定义一个多项式 和一个确定的多项式时间的算法 ，对于输入 ， 输出一个长度为 的字符串，如果算法 满足以下性质，那么就称 是满足 PRG 的： 拓展性(Expansion): 对于任意PPT时间范围内的区分器 ,都有一个可忽略函数 使得其中的 均匀且随机，是真随机，而 是独立采样的，注意区分器是看不到 的，也不能看到 具体是什么 但是你构造反证的时候，是能够知道G的特征的，并且需要依据G的特殊性构造 这不是扯淡，因为你只需要证明存在一个D就可以了 ——By Danny 这里的实验分两种情况: 如果是走前半边，那么就是随机等可能从 里面采样出一个 出来，然后传给 输出一个数给判别器。 后半边是随机从 里面采样出一个 ，传给判别器 。 判别器 输出 当且仅当它正确判断了是真随机还是伪随机。 注意： PRG的算法本身不是随机的 ...

堆的概念堆是满足一下性质的树： 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树 堆的分类根据堆的节点大小关系，分为大根堆和小根堆。大根堆中每个节点都比它的子节点大，小根堆则是每个节点都比它的两个子节点小 大根堆示意图 小根堆示意图 在数组中储存的下标特征在储存堆的时候，一个节点如果下标是 那么它的父节点的下标是 。左子节点的下标是 ，右子节点的下标是 。 堆的操作以下操作均以大根堆为例 堆的插入 每次把一个节点放到数组的最后 依次比较它和其父节点的值，如果父节点更小，那么使用 shift up 操作，把当前节点和父节点交换，然后向上递归 如果父节点已经比此时调整的调整节点大了，调整结束时间复杂度是 级别的。 堆的删除堆只支持删除堆顶端的元素 找到最后一个插入的元素 将最后一个元素和顶部的元素互换 向下递归调整进行 shift down 相关文章[[Bachelor/DataStructure/Leftist heap]]

Nonnegative Weighted sumsFinite sums , is convex is convex Infinite sums略 Composition with an affine mapping Affine mappingsholds convexity Pointwise Maximum is convexis convex Proof is simple. Compositions h,g are convex is convex in some conditions <!–TODO: finish convex conditions>