课程复习

第一章 整除、公因数公倍数 若$a\mid b$，则$\exist c$，使得$b=ac$ 若$p\mid ab$，则$p\mid a$或$p \mid b$ 若$a \mid mb$且$(a,b)=1$，则$a \mid m$ （单边消去） $am \mid bm ,\space m \ne 0\Leftrightarrow a \mid b$ （双边消去） $[a,b](a,b)=ab$ $d =(a,b)$，则$(\frac ad,\frac bd)=1$ a，b的最大公因数可以用辗转相除法求，例如$(78,108)=(78,30)=(18,30)=(18,12)=(6,12)=6$ 第二章 同余关系 $a\equiv b\mod m \Leftrightarrow m \mid a-b$ （证明mx+mx通过mm的完系时常用） 对于同余式组： $$ \begin{cases} a\equiv b\mod m\\ \alpha \equiv \beta \mod m \end{cases} $$有$a+\alpha \equiv b+\beta \mod m$；$a\cdot\alpha \equiv b \cdot\beta \mod m$；$f(a) \equiv f(b)\mod m$ 威尔逊定理：$(p-1)!+1 \equiv 0\mod p$ ...

中国剩余定理 设$m_1,m_2,\dots,m_k$两两互素，则方程组： $$ \begin{equation} \begin{cases} x\equiv a_1(\bmod\space m_1) \\ x\equiv a_2(\bmod\space m_2) \\ \dots \\ x\equiv a_k(\bmod\space m_k) \end{cases} \end{equation} $$有唯一解：$x\equiv M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\dots+M_kM_k^{-1}a_k(\bmod\space m)$ 其中，$m=m_1m_2\dots m_k$，$M_i=\frac m{m_i}$，$M_iM_i^{-1}\equiv 1(\bmod\space m_i)$ RSA密码算法 密钥生成 选择两个保密的大素数$p$、$q$ 取$n=p*q$，并计算$n$的欧拉函数值：$\varphi(n)=(p-1)*(q-1)$ 选择一个介于1与$\varphi(n)$之间的整数$e$，且满足$\gcd(\varphi(n),e)=1$，即与$\varphi(n)$互素 计算$e^{-1}(\bmod\space\varphi(n))$得到$d$ 将公钥设为$(e,n)$，私钥为$(d,n)$ 加密 $$ c\equiv m^e(\bmod\space n) $$解密 $$ m\equiv c^d(\bmod\space n) $$Rabin密码算法 密钥生成 固定了$e=2$，且p、q的阶需要相同 公钥为$n$，私钥为$(p,q)$ 加密 $$ c\equiv m^2(\bmod\space n) $$解密 相当于求解二次同余方程$x^2\equiv c\bmod n$，等价于求解$x^2\equiv c\bmod p$与$x^2\equiv c\bmod q$，即： $$ \begin{equation} \begin{cases} x\equiv \sqrt c\bmod p \\ x\equiv \sqrt c\bmod q \\ x\equiv -\sqrt c\bmod p \\ x\equiv -\sqrt c\bmod q \end{cases} \end{equation} $$求解后一共会产生四组解，逐个验证并选择有意义的一项作为明文即可 ...

随机网络和相关统计量 上课所指的是G(N, p)模型的生成 假设有N个节点，每次选中其中两个节点，然后生成一个0到1之间的随机数，如果这个随机数小于p，则在这两节点直接增加一个链接，否则不放置链接 统计量： 度：邻居数量 平均度：所有节点度的平均数 度分布：随机选取一个节点，其度值恰好为k的概率 路径 距离与网络直径：网络中的最大距离称为网络直径 介数：通过该节点的最短路径条数（或一个节点在网络中所有最短路径中出现的频率），条数越多，说明这个节点越重要 集聚系数：刻画某个节点相邻的两个节点彼此也相邻的概率 一个度为$k_i$的节点i的聚类系数$C_i$定义为$C_i=\frac{2E_i}{(k_i(k_i-1))}$，其中$E_i$是节点i的$k_i$个邻居节点之间实际存在的邻居对的数目 整个网络的集聚系数就是所有节点聚类系数的平均值，是一个0到1之间的值，越偏向0说明网络越松散，否则越集聚（每个节点都相连） 同配性：考察度值相近的节点是否倾向于互相连接 如果总体上度大的节点倾向于连接度大的节点（趋于和它近似的节点相连），那么就称网络的度正相关的，或称网络是同配的；如果总体上度大的节点倾向于连接度小的节点，那么就称网络的度负相关的，或者称网络是异配的 用同配系数来度量，-1为负相关（异配性），+1为正相关（同配性），0为不存在相关 邻接矩阵：描述一个网络拓扑结构 网络模型 无标度网络：是一种度分布（即对复杂网络中节点度数的总体描述）服从或者接近幂律分布（一个量是另一个量的幂次方）的复杂网络 BA无标度网络：首先，过去的网络没有考虑现实网络的增长特性（网络的规模是不断扩大的）；其次，没有考虑现实网络的优先连接特征（新的节点更倾向于与那些具有较高度的“大”节点相连接），基于此提出BA无标度网络，其中包含了网络的增长和优先连接特点 增长：在网络中每次增加一个节点，这个节点与网络中的一部分原有节点连接（可以是全部原有，也可以仅仅是一部分） 优先连接：一个新节点与一个已经存在的节点相连接的概率与节点的度成正比 拷贝模型：主要是考虑到例如互联网中互相引用的静态网页，当新增一个网页，大概率是会与其他类型相似的静态网页引用相同的内容，此时就需要对网络结构进行拷贝复制 无标度性、高聚类系数、层次结构和模块化 每次增加一个新节点，对于这个新节点，选择一个母节点并复制其所有连接，最后再以一定概率删除一部分连接 复制模型更加自然地模拟了基于“模仿”的连接机制，而 BA 模型强调“富者愈富”的优先连接原则 配置模型：在复杂网络研究中用于生成具有特定度分布（但边的具体连接方式随机）的随机网络模型 度分布、随机连接、无偏结构（在给定度分布的条件下具有最大随机性） 给定一个网络度序列$\{k_1,k_2,\ldots,k_N\}$，然后为每一个独立的节点配置数量为$k_i$的半边，最后将所有的半边与另一节点的半边随机两两连接起来 可以生成任意指定的度分布，不要求是幂律的；是一种静态模型，只需要输入度序列，无需生长机制 仅能保证度的分布，但无法生成复杂结构；此外还可能会有自环和多重边的出现 隐藏参数模型：通过引入一些未直接观察到的“隐藏参数”来解释节点之间的连接概率，这些隐藏参数通常代表节点的某些潜在特性或属性，这些特性影响节点之间形成连接的可能性 灵活性、解释性、适用性 为每个节点分配一个或多个隐藏参数$\theta_i$，再定义一个连接概率函数（通常就是隐藏参数的函数）$P(i,j)=f(\theta_i,\theta_j)$，然后再根据这个连接概率函数在两个节点之间生成边 更关注节点的隐藏属性 选择合适的隐藏参数和连接函数可能较为复杂；计算和优化隐藏参数可能需要大量的计算资源 评价网络是否同配 同配是指网络中度数大的节点更倾向于与同样度数大的节点连接 全统计描述（Full Statistical Description） 使用 $e_{jk}$ 矩阵表示随机选择的边两端的节点分别具有度数 $j$ 和 $k$ 的概率 如果网络没有度相关性，$e_{jk}$ 应满足特定的公式：$e_{jk} = q_j q_k$，其中 $q_k$ 是具有度数 $k$ 的节点出现在边上的概率 也就是说，如果网络没有同配关系，那么理应有【左右两端节点概率】等于【左端节点概率】乘【右端节点概率】 偏离该预测的情况可以作为度相关性的标志，即同配 / 异配 ...