Resive world

斜率优化dp专题小结

Posted on 2015-10-11 | In Algorithm

斜率优化dp是一种通过构造斜率表达式，用维护凸包的方法来去除多余的点以减少算法复杂度的方法。通常可以将问题规模减小一个维度，从而提高运行效率。
这个算法的关键是将dp的状态转移方程进行转换，比如对于如下状态转移方程：
$$dp[i]=Min(dp[j]+M+(sum[i]-sum[j])^2),j\in [1,i),i\in [1,n]$$
如果直接dp那么复杂度将会是(O(n_2)),某些情况下就会显得效率不够。这时候就可以用斜率dp进行优化，将其优化到$O(n)$。
首先我们需要将状态转移方程进行变形，在计算$dp[i]$的时候，对于任何x和y，如果x比y更优，那么也就是说:
$$\begin{aligned} & dp[x]+M+(sum[i]-sum[x])^2\ \lt dp[y]+M+(sum[i]-sum[y])^2\end{aligned}$$
成立。
将上式进行变形，可以得到一种类似斜率的表达形式:
$$(dp[x]+num[x]^2-(dp[y]+num[y]^2))/(2*(num[x]-num[y]))<sum[i]$$

令:

$$Cmp(x,y)=(dp[x]+num[x]^2-(dp[y]+num[y]^2))/(2*(num[x]-num[y]))$$

现在从左到右，设$x\lt y\lt z$，如果$Cmp(z,y)\lt Cmp(y,x)$，那么y点便永远不可能成为最优解，可以直接将它踢出我们的最优解集。同时，由于$sum[i]$单调增，所以如果$Cmp(y,x)\lt sum[i]$那么x点也不可能成为最优解。
据此，我们可以便可以通过维护这样的一个队列，每加入一个元素就判断排除所有不可能是最优解的点从而进行优化。
斜率优化dp的套路基本是固定的，基本上就是用数组模拟队列，然后两个while循环判断是否可以去除无用的点。

Hdoj3507–Print Article:

#include<stdio.h>
#include<string.h>
int a[500004];
int dp[500004];
int sum[500004];
int q[500004];
int getUp(int i, int j){
	return dp[i] + sum[i] * sum[i] - dp[j] - sum[j] * sum[j];
}
int getDown(int i, int j){
	return 2 * (sum[i] - sum[j]);
}
void init(){
	memset(a, 0, sizeof a);
	memset(dp, 0, sizeof dp);
	memset(sum, 0, sizeof sum);
	memset(q, 0, sizeof q);
}
int main(){
	int n, m;
	while (scanf("%d%d", &n, &m) == 2){
		init();
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			sum[i] = sum[i - 1] + a[i];
		}
		int head = 0, tail = 0;
		q[tail++] = 0;
		for (int i = 1; i <= n; i++){
			while (head + 1 < tail){
				int a1 = q[head], a2 = q[head + 1];
				if (getUp(a2, a1) <= getDown(a2, a1)*sum[i]){
					head++;
				}
				else{
					break;
				}
			}
                        int k=q[head];
			dp[i] = dp[k] + m + (sum[i] - sum[k])*(sum[i] - sum[k]);
			q[tail++] = i;
			while (head + 2 < tail){
				int a1 = q[tail - 3];
				int a2 = q[tail - 2];
				int a3 = q[tail - 1];

				if (getUp(a2, a1)*getDown(a3, a2) >= getDown(a2, a1)*getUp(a3, a2)){
					tail-=2;
					q[tail++]=a3;
				}
				else{
					break;
				}
			}
		}
		printf("%dn", dp[n]);
	}
}

Hdoj3480–Division:

#include<cstdio>
#include<cstring>
using namespace std;
int a[10004];
int dp[5004][10004];
int q[10004];
int getUp(int i,int x,int y){
	return dp[i - 1][x] - dp[i - 1][y] +a[x+1]*a[x+1]-a[y+1]*a[y+1];
}
int getDown(int x, int y){
	return  a[x + 1] - a[y + 1];
}
int getRight(int i){
	return 2 * a[i];
}
int main(){
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++){
		int n, m;
		memset(a, 0, sizeof a);
		memset(dp, 0, sizeof dp);
		memset(q, 0, sizeof q);
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
		}
		sort(a + 1, a + 1 + n);
		for (int i = 1; i <= n; i++){
			dp[1][i] = (a[i] - a[1])*(a[i] - a[1]);
		}
		for (int i = 2; i <= m; i++){
			int head =0,tail = 0;
			q[tail++] = i - 1;
			for (int j = i; j <= n; j++){
				while (head + 1 < tail){
					int a1 = q[head];
					int a2 = q[head+1];
					if (getUp(i, a2, a1) <= getDown(a2, a1)*getRight(j)){
						head++;
					}
					else{
						break;
					}
				}
				int k = q[head];
				dp[i][j] = dp[i-1][k]+(a[j]-a[k+1])*(a[j]-a[k+1]);
				q[tail++] = j;
				while (head + 2 < tail){
					int a1 = q[tail - 3];
					int a2 = q[tail - 2];
					int a3 = q[tail - 1];
					if (getUp(i,a2,a1)*getDown(a3,a2)>=getUp(i,a3,a2)*getDown(a2,a1)){
						tail -= 2;
						q[tail++] = a3;
					}
					else{
						break;
					}
				}
			}		
		}	
		printf("Case %d: %dn",t, dp[m][n]);
	}
}

Hdoj2829–Lawrence:

#include<cstdio>
#include<cstring>
using namespace std;
int sum[1004];
int a[1004];
int dp[1004][1004];
int q[100004];
int getUp(int i, int x, int y){
	return dp[i - 1][x] - dp[i - 1][y]-dp[0][x]+dp[0][y]+sum[x]*sum[x]-sum[y]*sum[y];
}
int getDown(int x, int y){
	return sum[x] - sum[y];
}
int main(){
	int n, m;
	while (scanf("%d%d", &n, &m), n || m){
		memset(sum, 0, sizeof sum);
		memset(dp, 0, sizeof dp);
		memset(q, 0, sizeof q);
		memset(a, 0, sizeof a);
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			sum[i] = sum[i - 1] + a[i];
			dp[0][i] = dp[0][i - 1] + a[i] * sum[i - 1];
		}
		for (int i = 1; i <= m; i++){
			int head = 0, tail = 0;
			q[tail++] = 0;
			for (int j = 1; j <= n; j++){	
				while (head + 1 < tail){
					int a1 = q[head];
					int a2 = q[head + 1];
					if (getUp(i, a2, a1) <= getDown(a2, a1)*sum[j]){
						head++;
					}
					else{
						break;
					}
				}
				int k = q[head];
				dp[i][j] = dp[i - 1][k] +dp[0][j]-dp[0][k]- (sum[j] - sum[k])*sum[k];
				q[tail++] = j;
				while (head + 2 < tail){
					int a1 = q[tail - 3];
					int a2 = q[tail - 2];
					int a3 = q[tail - 1];
					if (getUp(i, a2, a1)*getDown(a3, a2) >= getUp(i, a3, a2)*getDown(a2, a1)){
						tail -= 2;
						q[tail++] = a3;
					}
					else{
						break;
					}
				}
			}
		}
		printf("%dn", dp[m][n]);
	}
}

Hdoj3045–Picnic Cows:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[400004];
long long sum[400004];
long long dp[400004];
long long q[400004];
long long getUp(long long x, long long y){
	return dp[x] - dp[y] - sum[x] + sum[y] + a[x+1] * x - a[y+1] * y;
}
long long getDown(long long x, long long y){
	return a[x + 1] - a[y + 1];
}
int main(){
	long long n, m;
	while (scanf("%I64d%I64d", &n, &m) == 2){
		memset(dp, 0, sizeof dp);
		memset(q, 0, sizeof q);
		memset(sum, 0, sizeof sum);
		memset(a, 0, sizeof a);
		for (long long i = 1; i <= n; i++){
			scanf("%I64d", &a[i]);
		}
		sort(a + 1, a + 1 + n);
		for (long long i = 1; i <= n; i++){
			sum[i] = sum[i - 1] + a[i];
		}
		long long head = 0, tail = 0;
		q[tail++] = 0;
		for (long long i = 1; i <= n; i++){
			while (head + 1 < tail){
				long long a1 = q[head], a2 = q[head + 1];
				if (getUp(a2, a1) <= getDown(a2, a1)*i){
					head++;
				}
				else{
					break;
				}
			}
			long long k = q[head];
			dp[i] = dp[k] + sum[i] - sum[k] - a[k + 1] * (i - k);
			if (i - m + 1 < m){
				continue;
			}
			q[tail++] = i - m + 1;
			while (head + 2 < tail){
				long long a1 = q[tail - 3];
				long long a2 = q[tail - 2];
				long long a3 = q[tail - 1];
				if (getUp(a2, a1)*getDown(a3, a2) >= getDown(a2, a1)*getUp(a3, a2)){
					tail -= 2;
					q[tail++] = a3;
				}
				else{
					break;
				}
			}
		}
		printf("%I64dn", dp[n]);
	}
}

LaTeX中一些特殊数学公式的编写

Posted on 2015-10-10 | In LaTeX

前言

一般情况下，在编写数学公式的时候，符号表就能满足我们的需求。但是很多情况下，当我们书写一些比较复杂的行间公式时，这点符号就显得捉襟见肘了，一下就整理一些常用的特殊数学公式

上标和下标

$\text{\overset{}{}}$ 这个东西后面接两个参数，第一个参数表示想加上标，第二个参数表示施加的对象,如果不加大括号，那么默认是把最近的一个元素作为下一个参数，比如
$$\text{\overset{up}{base}}:\overset{up}{base}$$
$\text{\underset{}{}}$ 这个表示加下标，用法跟上标一样比如
$$\text{\underset{under}{base}}:\underset{under}{base}$$

大括号结构

很多情况下，我们需要大一点的括号来表示包含关系，平时的小括号就显得不够用了，这时候就需要left和right对来表示括号：
一般用法是$\text\left$后面接左括号的类型，最后再加上$\text\right$后面接右括号的类型。这里的$\text\left$和$\text\right$一定要成对出现，如果想不出现某一个括号，只需要加”.”，比如$\text{\right.}$就表示不显示右括号。
例：
$$\text{\left(\frac{a}{b}\right)}:\left(\frac{a}{b}\right)$$
$$\text{\left(\frac{a}{b} \right.}:\left(\frac{a}{b} \right.$$

当然，上面的方法适用与单行显示，如果想让大括号包括多行(比如显示方程组)，我们可以用类似下面的方法来显示：

$$
\text{\left\{\begin{aligned}function1\\function2\end{aligned}\right.}:
\left\{\begin{aligned}function1\\function2\end{aligned}\right.
$$

不同大小的嵌套括号

可以使用\big, \Big, \bigg, \Bigg控制括号的大小，比如代码
$$
\text{\Bigg ( \bigg ( \Big ( \big (} :
\Bigg ( \bigg ( \Big ( \big (
$$

多行公式

要处理多行的公式比如分段函数或者连等推导的时候，通常需要使用$\text{\begin{aligned}…\end{aligned}}$对，在这当中用双反斜杠表示换行，在每行中，用&符号来定位对齐，比如:

$$
\begin{aligned}(a + b)^3 &= (a + b) (a + b)^2\\
&= (a + b)(a^2 + 2ab + b^2) \\
&= a^3 + 3a^2b + 3ab^2 + b^3\end{aligned}
$$

矩阵

$\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}$

$\begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$

$\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$

$\begin{Bmatrix} 1 & 0 \\ 0 & -1 \end{Bmatrix}$

$\begin{vmatrix} a & b \\ c & d \end{vmatrix}$

$\begin{Vmatrix} i & 0 \\ 0 & -i \end{Vmatrix}$

大组合数取模的Lucas定理

Posted on 2015-10-09 | In Maths

一般情况下，我们计算大组合数取模问题是用递推公式进行计算的：
$$
C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p
$$
其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加$O(mn)$，在实践中不适用。当这时候就需要Lucas定理进行快速运算:
$$
C_n^m=\prod_{i=0}^{k}C_{n_i}^{m_i}\ mod\ p
$$
其中：
$$
m=m_kp^k+m_{k-1}p^{k-1}+…+m_1p+m_0
$$
$$
n=n_kp^k+n_{k-1}p^{k-1}+…+n_1p+n_0
$$
证明方法也很简单，主要用到如下等式：
$$
C_p^j\equiv 0\ mod\ p\ ( 1 \leq j \leq p-1 )
$$
$$
(1+x)^{p}\equiv 1+x^p \ mod\ p
$$
应用这个公式，可以的到如下递归式

这里的$Lucas(n,m,p)$就是$C_n^m\ mod\ p$，递归终点就是当n=0的时候。时间复杂度是$O(log_p(n)*p)$.

一些常见OJ网站的整理

Posted on 2015-10-09 | In Others

听说你们老喜欢刷题了，我就帮你们稍微整理下比较热门的刷题网站吧，这类网站其实有很多的，网上也能一抓一大把，在玩游戏玩累了，吹老牛吹烦了的时候多刷刷题还是非常有益身心健康的。
一般我们把这类的网站叫做在线评测系统，简称OJ(Online Judge)，主要用途是给广大程序员学习算法，或者广大学生备战程设比赛用的。过几天我们学校的ACM队应该也会招新了，到时也会提供一些学习资料和模拟比赛的机会，希望大家多多参与。
以下是一些比较有名气的OJ系统:

http://acm.hdu.edu.cn/
这是杭州电子科技大学的评测系统，杭电虽然综合排名不怎么样，但是它的OJ做的绝对是全国一流，ACM队实力也非常的强，也是大多数初学编程的同学比较常去的地方。具体使用说明不解释，你们自己去悟，我想提醒的就是不要想着把题目从第一页开始板刷下去，很多题是很有难度的，并且涉及到很多算法。对于刚学C语言的同学，我建议有空的话先把第11页的100道题目刷下(都是令人感动的中文题)，这里题目都比较基础，适合供大家熟悉语言用。如果有题目不会的话，可以直接百度题号，一般可以直接找到题解。
http://poj.org/
这是北大开发的系统，一直是全国最著名的OJ，题目更新速度很快。
http://acm.zju.edu.cn
这是浙大的OJ，国内的老牌OJ。
https://uva.onlinejudge.org/
这是西班牙的UVA，那个刘汝佳的《算法入门经典》就是基于这个评测系统的题目的，不过由于是国外的，有(fei)点(chang)卡。
http://codeforces.com/
俄罗斯的OJ，每个礼拜都有比赛，题目一般毕竟考思路，很多世界级的大牛都在里面刷（nue）题（chang）。
http://acm.hust.edu.cn
华中科技大的OJ。。。。其实他们什么都没有做，就是写了一大堆爬虫把别的OJ上的题目爬到自己的网站上。

基本常见的OJ就这些，当然还有些比如hihocoder啊萌码之类半娱乐半专业的OJ，有兴趣的话也可以玩玩。。。。

（以上纯属个人观点，如有雷同不胜荣幸，高中学过NOIP的同学请自觉绕道，谢谢合作）

二次剩余理论的数学基础

Posted on 2015-10-08 | In Maths

二次剩余理论在密码学中占有重要的地位，很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”，可见其重要性。这里列举关于二次剩余的常见定理，方便日后查阅。

定义

对于奇素数p，p和d互素，如果$x^2 \equiv d\ mod\ p$，那么称d是模p的二次剩余，否则称称d是模p的二次非剩余。记模p的二次剩余的全体为$QR_p$，模p的二次非剩余的全体为$QNR_p$。

定理(1)

模p的既约剩余系中，二次剩余与二次非剩余各占一半：$|QR_p|=|QNR_p|=\frac{p-1}{2}$

Euler判别法

设素数p为奇素数，p和d互素，那么d为模p的二次剩余的充要条件是：$d^{\frac{p-1}{2}}\equiv 1\ mod\ p$
d为模p的二次剩余的充要条件是：$d^{\frac{p-1}{2}}\equiv -1\ mod\ p$

注意到由欧拉定理，有$(d^{\frac{p-1}{2}}- 1)*(d^{\frac{p-1}{2}}+ 1)\equiv 0 \ mod\ p$

推论(1)

若$p \equiv 1\ mod\ 4$,则-1是模p的二次剩余；
若$p \equiv 3\ mod\ 4$,则-1是模p的二次非剩余。
(由Euler判别法易证得)

推论(2)

对于奇素数p，$(p,d_1)=1$，$(p,d_2)=1$，那么$d_1 d_2$是模p的二次剩余的充要条件是$d_1$和$d_2$均为模p的二次剩余或二次非剩余；$d_1 d_2$是模p的二次非剩余的充要条件是$d_1$和$d_2$一个为模p的二次剩余另一个为模p的二次非剩余。
接下来介绍两个重要的符号：$Legendre$符号和$Jacobi$符号。

Legendre符号

定义
对于奇素数p，令：
$$(\frac{d}{p})=\left\{\begin{aligned}& 0, & p|d\\& 1, & d \in QR_p\\&-1, & d \in QNR_p\end{aligned}\right.$$
称$\frac{d}{p}$为模p的$Legendre$符号。

性质

$(\frac{d}{p})=d^{(p-1)/2}\ mod\ p$
$(\frac{d}{p})=(\frac{d+p}{p})$
$(\frac{dc}{p})=(\frac{d}{p})(\frac{c}{p})$
$(\frac{-1}{p})=\left\{\begin{aligned}1,&& p \equiv 1\ mod\ 4\\ -1&& p \equiv 3\ mod\ 4\end{aligned}\right.$
$\frac{2}{p}\equiv(-1)^{(p^2-1)/8}$

Gauss二次互反定律
设p,q均为奇素数，$p \neq q$，那么$(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}2\frac{q-1}2}$

Jacobi符号

定义
设奇数p>1，$ P=p_1,p_2,p_3,…,p_n $.
其中$p_i$是素数，我们把
$(\frac{d}{P})=(\frac{d}{p_1})(\frac{d}{p_2})…(\frac{d}{p_n})$
称为$Jacobi$符号，此处$(\frac{d}{p_i})$是$Legendre$符号。

性质

$(\frac{1}{P})=1$
$(d,P)\neq 1,(\frac{d}{P})=0$
$(d,P)= 1,(\frac{d}{P})=\pm 1$
$(\frac{d}{P})=(\frac{d+P}{P})$
$(\frac{dc}{P})=(\frac{d}{P})(\frac{c}{P})$
$\frac{-1}{P}=(-1)^{(P-1)/2}$
$\frac{2}{P}=(-1)^{(P^2-1)/8}$

说明
$Jacobi$符号也满足二次互反定律，特别的，$Legendre$符号也可以当作$Jacobi$符号来计算，但是与$Legendre$符号不同，$Jacobi$符号$(\frac{d}{P})=1$并不代表二次同余方程$x^2\equiv d\ mod\ p$一定有解。

Garbled Bloom Filters算法简述

Posted on 2015-10-08 | In Cryptography

简述

Garbled Bloom Filters（GBF）算法是Bloom Filters （BF）算法的变形，并且结合了Shamir的信息分享算法，更好的解决了hash冲突的问题其形式上是将Bloom Filters算法中的BitSet数组转换成了字符串数组，数组中的每一个字符串长度为安全参数$\lambda$，可以通过调节这个参数来获得想要的安全性。该算法同Bloom Filters 一样，是一种有一定容错率的hash算法，对于存在于集合中的元素查询返回的值总是true，而对于不在集合中的元素查询的返回值大多为假，这里判断失误的概率是关于安全参数$\lambda$的可忽略函数。

初始化

1.创建一个长度为$m$的字符串数组，下标为$[0,m-1]$，数组中的每一个字符串长度均为$\lambda$，并将其置为空。
2.选择$k$个独立的均匀分布的的哈希函数$H=\{h_0 h_1 …h_{k-1}\}$，每一个$h_i$函数映射的值域在$[0,m−1]$中均匀分布，即hash函数映射到的值总是对应字符串数组中的一个位置。
3.我们将一个$Garbled\ Bloom\ Filter$ 用$(m,n,k,H,\lambda)$表示，将需要查询的集合用$S$表示，将对于集合$S$的$GBF$用$GBF_s$表示，将其中的第i个字符串用$GBF_s[i]$表示。

插入元素

1.依次用$k$个hash函数将元素$x$映射到数组中的$k$个位置上。记录第一个hash后对应字符串值为空的位置idx，对于在这之后的hash，如果对应的字符串为空，则随机将其置为一个长度为$\lambda$的字符串，否则保持不变。
2.将上述字符串中除下标为idx的字符串之外的字符串的进行异或处理，并将结果与$x$进行异或，将得到的值赋给$GBF_S[idx]$。(Shamir 算法的体现)
3.在插入完所有元素后，将所有未被赋值的$GBF_s[i]$赋一个随机值。

##查询元素
1.对于每一个待查询的元素$y$,我们用$k$个hash函数将元素$y$映射到数组中的$k$个位置上。
2.依次将这$k$个位置上的字符串进行异或，如果得到的值恰好为$y$，那么认为$y$存在于集合S中，否则不在。

删除元素

与BF算法一样不支持删除。

正确性

算法的正确性是显然的，如果$y$在集合S中，那么由于hash的过程是确定的，所以根据$Shamir$算法，将最后得到的k个字符串进行异或必然会恢复$y$。如果$y$不在集合S中，那么将那k个字符串进行异或后会恢复$y$的概率$p_1$必定是关于$\lambda$的可忽略函数，可以忽略不计。同时，该算法发生hash冲突的概率$p_2$也是关于$k$的可忽略函数，此时的表现为找不到对应的idx值。理论分析得知，$$p_1\leqslant 2^{-\lambda}$$$$p_2\leqslant1-2^{-k}$$

Qt概述和Linux下安装

Posted on 2015-10-07 | In Qt

概述

Qt 是一个1991年由奇趣科技开发的跨平台C++图形用户界面应用程序开发框架。它既可以开发GUI程序，也可用于开发非GUI程序，比如控制台工具和服务器。Qt是面向对象的框架，使用特殊的代码生成扩展（称为元对象编译器(Meta Object Compiler, moc)）以及一些宏，易于扩展，允许组件编程。2008年，奇趣科技被诺基亚公司收购，QT也因此成为诺基亚旗下的编程语言工具。2012年，Qt被Digia收购。2014年4月，跨平台集成开发环境Qt Creator 3.1.0正式发布，实现了对于iOS的完全支持，新增WinRT、Beautifier等插件，废弃了无Python接口的GDB调试支持，集成了基于Clang的C/C++代码模块，并对Android支持做出了调整，至此实现了全面支持iOS、Android、WP。

安装

下载

Qt的安装包需要从他的[下载链接](http://www.qt.io/download-open-source/)上下载（从官网直接来的话要回答写奇怪的问题，大概就是扯什么开源啊版权的问题，不会答的还下不了0.0）

运行安装程序

下载下的程序没有执行权限，我们得帮他加一下，然后跑起来进入安装界面。开始有个登陆界面咱们直接跳过，直接下一步下一步。最后选择路径，选择安装文件，等他自己跑好就行了。安装下来的就是一个Qt的集成开发环境。

1 2	myths@myths-X450LD:~/Download$ sudo chmod +x qt-unified-linux-x64-2.0.2-2-online.run myths@myths-X450LD:~/Download$ ./qt-unified-linux-x64-2.0.2-2-online.run

路径

一般都帮我们弄好了Desktop 文件，这里不去管他，想看的话用locate 命令。一般我们从dash里直接启动程序就行。这个程序的真正路径是：Qt/Tools/QtCreator/bin/qtcreator。如果我们需要卸载或者重装的话可以调用他的安装程序:Qt/MaintenanceTool。

说明

如果没有安装opengl的话据说还要安装下这个库

1	myths@myths-X450LD:~$ sudo apt-get install freeglut3-dev

Elgamal加密与签名算法简述

Posted on 2015-10-07 | In Cryptography

简述

ElGamal算法，是由T.Elgamal于1984年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题即CDH假设。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，其实现依据是求解离散对数是困难的，而其逆运算指数运算可以应用快速幂的方法有效地计算。也就是说，在适当的群G中，指数函数是单向函数。

用于签名

生成密钥:确定一个大素数$p$和它的一个原根$g$，在$Z_p$域上选择一个随机数$x$作为密钥，并计算$$y=g^x\ mod\ p$$

$(p,g,y)$作为公钥。

签名算法:用$m$表示待签名信息，在$Z_p$域上选择一个与$p-1$互质的数$k$，并计算$$C_1=g^k\ mod\ p$$

再运用Ext_Euclidean算法求出$C_2$，使其满足：$$m\equiv ax+C_2k\ \ mod\ p-1$$
3. 输出签名:$(C_1,C_2)$.
4. 验证签名:验证下式$$y^{C_1}\cdot \ C_1^{C_2}\equiv\ g^m\ mod\ p$$ $$C_1\in Z_p$$
5. 原理:这里应用了欧拉定理。

用于加密

生成密钥：确定一个大素数$p$和它的一个原根$g$，在$Z_p$域上选择一个随机数$x$作为密钥，并计算$$y=g^x\ mod\ p$$
$(p,g,y)$作为公钥。
加密算法：用$m$表示待加密信息，在$Z_p$域上选择一个与$p-1$互质的数$k$，并计算$$C_1=g^k\ mod\ p$$
$$C_2=y^k\cdot m\ \ mod\ p$$
输出密文$(C_1,C_2)$
解密算法:计算下式$$m=C_2\cdot(C_1^x)^{-1}\ \ mod\ p$$
这里需运用Ext_Euclidean算法求乘法逆元。

Shamir密钥分享算法简析

Posted on 2015-10-07 | In Cryptography

简述

秘密共享技术是密码学和信息安全的一个重要研究内容，$Shamir$密钥分享算法最早是由$Shamir$和$Blackly$在1970年基于$Lagrange$插值和矢量方法提出的，其基本思想是分发者通过秘密多项式，将秘密$s$分解为$n$个秘密分发个持有者，其中任意不少于$k$个秘密均能恢复密文，而任意少于$k$个秘密均无法得到密文的任何信息。

实际应用

比如在门限体系中，为了保证信息安全性，一个秘密通常不能由单个持有者保存。比如一些重要场所的通行，比如遗嘱的生效等，必须将秘密分由多人保管并且只有当多人同时在场时秘密才能得以恢复。在这些场合，就需要这样一套的密钥分享技术。

算法思路

表示

$Shamir$密钥共享算法由一个二元数$(k,n)$表示，其中$n$表示将明文$s$加密为$n$个$Shadow$，$k$表示必须至少同时拥有$k$个$Shadow$才能解密获得成明文。

加密

对于待加密的明文$s\in\ Z_p$($p$为大素数)，在有限群$GF(p)$任取$k-1$个随机数$a_1,a_2,…,a_{k-1}$，并令$a_0=s$，从而构造如下的多项式：$$f(x)=a_0+a_1x+a_2x^2+a_3x^3+…+a_{k-1}x^{k-1}mod(p)$$对于这个多项式，任取$n$个数$x_1,x_2,x_3,…,x_n$分别带入多项式得到$n$个密钥对:$$(x_1,f(x_1)),(x_2,f(x_2)),(x_3,f(x_3)),…,(x_n,f(x_n))$$分发给$n$个持有者。

解密

假设得到了$k$个密钥对$\{x_1,y_1\}\{x_2,y_2\}…\{x_k,y_k\}$，我们可以得到如下方程(运算均在$GF(p)$)：
$$\begin{matrix}a_0+a_1 x_1+a_2 x_1^2+…+a_{k-1}x_1^{k-1}=y_1\\a_0+a_1x_2+a_2x_2^2+…+a_{k-1}x_2^{k-1}=y_2\\……………….\\a_0+a_1x_k+a_2x_k^2+…+a_{k-1}x_{k-1}^k=y_k\end{matrix}$$
由矩阵乘法或者$Lagrange$插值法均可求的$a_0$即为明文$s$。

安全性

由伽罗华域以及矩阵运算的性质可知该算法的安全性是显然的。

补充

当$k=n$的时候，Shamir算法还有一种用异或运算的实现:任取$n-1$个随机数$(r_1,r_2,r_3,…,r_{n-1})$,对于明文$s$计算$$r_n=r_1 \oplus r_2 \oplus r_3 …\oplus r_{n-1}$$
这样就可以通过将这$n$个数全部进行异或来得到明文，同时，任意一个$Shadow$都不会泄露有关秘密的任何信息。

Bloom Filters简介

Posted on 2015-10-06 | In Data Mining

简介

Bloom Filter(又叫布隆过滤器)是由B.H.Bloom在1970年提出的一种多哈希函数映射的快速查找算法。该算法的原名叫：“Space/time trade-offs in hash coding with allowable errors”，即一种允许一定容错率的哈希算法，因为在实际应用中经常有这样的情况：普通hash算法相对高额的空间消耗承受不住过大的数据，而实际上对询问的正确性要求又不大。在这种情况下Bloom Filter的时空优越性就体现出来了。
为了说明Bloom Filter存在的重要意义，举一个实例：
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。比较靠谱的方法是建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。这个方法显然很合理，但是当数据量变得非常庞大的时候单一哈希函数发生冲突的概率太高。若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍！显然不符合实际。而事实上在这种应用中，少抓了几个网页的代价是很小的，所以其实并没有特别的必要来保证询问的完美正确性。
Bloom Filter算法相对朴素算法的区别就是使用了多个哈希函数，而不是一个。

初始化

创建一个$m$位$BitSet$，下标为$[0,m-1]$，将所有位初始化为0。
选择$k$个独立的均匀分布的的哈希函数$H =\{h_0\ h_1\ … h_{k-1}\}$，每一个$h_i$函数映射的值域在$[0,m-1]$中均匀分布。
我们将一个Bloom Filter 用一个$(m,n,k,H)$四元数表示，将需要查询的集合用$S$表示，将对于集合$S$的Bloom Filter 用$BF_s$表示，将那个$BitSet$中的第$i$位用$BF_s[i]$表示。

加值

为了将$x\in S$加入到$BF_s$中，我们需要计算$x$对于$k$个hash函数的值，并将其对应的$BF_s[i]$位置为１，即：
$$BF_s[i]=1,(0\leq i\leq k-1)$$

查询

对于待查询的元素$y$，我们同样需要将他用这$k$个hash函数进行映射，对于所得到的$k$个值，如果存在某一个值对应的$BF_s[i]$为０，则认为$y$存在集合$S$中，返回$true$，否则认为不存在，返回$false$。

删除

该数据结构不支持删除。

正确性

由于对于每一个加进集合中的元素$y$，其$k$个哈希值对应的那些比特位一定为１，所以如果$y$对$BF_s$的询问结果如果是$false$，那么可以断定$y$不在集合$S$中；但是如果$y$对$BF_s$的询问结果如果是$true$，那么我们并不能确实的断定$y$在集合$S$中。那么，由于每一个$BF_s[i]$被置为１的概率$p=1-(1-\frac1m)^{kn}$，我们可以从理论上证明判断失误的概率ｃ满足：$$c=p^k\times(1+O(\frac{k}{p}\sqrt{\frac{ln\ m-kln\ p}{m}}))$$即c是关于ｋ的可忽略函数，即我们总是可以通过调节参数来是我们的$BF_s$达到我们所要求的准确性。

参数选择

假设我们能容忍的出错几率为$\epsilon$，那么整个系统的效率应当取决与$m$和$k$值的选择。

数组大小m值的确定

由理论可以推得m值应当满足$$m\geq n log_2e\cdot log_2\frac1\epsilon.$$其中ｅ为自然对数。

哈希函数数目k值的确定

由于每一个$BF_s[i]$被置为１的概率为$$1-(1-\frac1m)^{kn}$$那么对于每一个返回值为$true$的询问，其判断失误的概率为$$(1-(1-\frac1m)^{kn})^k\approx(1-e^{\frac{kn}{m}})^k$$.当右边取最小值时，应满足关系式$$k=ln\ 2\times \frac{m}{n}$$如果m取上面的最优值，那么ｋ应当满足:$$k=log_2{\frac1\epsilon}.$$

其他操作

对于两个由唯一$(m,n,k,H)$构成的，用来处理两个不同集合$S_1$和$S_2$的Bloom Filter 来说，我们可以通过将$BF_{s_1}$和$BF_{s_2}$这两个$BitSet$进行位与运算得到一个新的Bloom Filter $BF_{s_1\cap_2}$