-
常见的距离测度
在对向量进行相似度计算的时候经常需要纠结的是用什么测度来衡量相似度。经常听到的距离测度无非是欧氏距离、曼哈顿距离、切比雪夫距离、闵科夫斯基距离、海明距离、编辑距离、余弦距离、杰卡德距离这么几个，稍微生僻点的再加上什么标准化欧氏距离、卡方距离、马哈拉诺比斯距离、巴塔恰里雅距离、皮尔逊距离。前面说的那些距离大都是一回事，掌握了初中左右的知识基本都能理解，而后面说的这些距离就相对复杂很多了，得有离散统计线性代数这类的扎实功底才能吃透。。。这里就稍微介绍下概念上距离测度的定义，以及简单的距离测度。…
-
伽罗华域性质简析
伽罗华（伽罗瓦）域名字听起来挺酷的，其实就是有限域。域这个东西由于他能够进行满足加减乘除四则运算，在加密解密、编码解码当中应用非常广泛。但是我们常见的实数域却无法直接在计算机中精确的保存，因此有限域这类能够支持四则运算而且能够用有限的编码精确保存的东西就非常有用了。 （顺带提一句，伽罗瓦这个人的生平很有意思，如果他活久点，说不能成为跟高斯、欧拉一样档次的人。。。） 域 域的定义在各种与离散数学相关的地方都能看到，看上去定义的十分啰嗦，说白了其实就是从有理数抽象出来的一种集合，能加能减能乘…
-
Reed-Solomon纠删码简析
Reed-Solomon编码（又叫RS编码、里德-所罗门编码）作为一种前向纠错编码，是一种很常见的数据冗余技术，也就是通过对数据增加冗余部分来保证当数据丢失时能够在一定程度上进行恢复。最典型的应用就是在现在最流行的QR二维码的编码设计中。 实现功能 他所解决的问题是：给定$n$个数据块$(d_1,d_2,d_3,...,d_n)$，对于一个确定的正整数$m$， RS编码能够根据这$n$个数据块生成$m$个校验块， $(c_1, c_2,..., c_m)$。 我们能够做到，从这$m+n$…
-
幂定律和齐夫定律
幂定律 幂定律又叫幂律，大量的事实表明，很多现象都服从类似于幂函数$y=cx^a$的形式，其中$a$是幂，而且通常是负数。 幂定律可以非常直观的用马太效应(Matthew effect)解释，说白了其实就是所谓的“富者越富，穷者越穷”。例如图书的销售，本来销售好的图书可能会发布更多的广告，做更多的营销从而导致销量更多。这样如果将图书销售量按照名次排列下来就会发现图书销量会随着名次的提高而指数性的提高。 齐夫定律 齐夫定律(Zipf's Law)其实可以说是幂定律的一种形式，只是由于在曾…
-
二次剩余理论的数学基础
二次剩余理论在密码学中占有重要的地位，很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”，可见其重要性。这里列举关于二次剩余的常见定理，方便日后查阅。 定义 对于奇素数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|=…
-
数论基础专题小结
这个专题很杂，牵涉到很多数学公式和一些优化方法，还是要根据不同的题目来积累经验。 LightOJ 1282 Leading and Trailing: 这道题牵涉到求一个大数的前几位和后几位的方法，前者主要是通过对数进行处理，后者通过快速取模。 #include
#include …#include #include #include using namespace std; int powMod(int a,int n,int mod){ int ans=1; while(n>0){
-
大组合数取模的Lucas定理
一般情况下，我们计算大组合数取模问题是用递推公式进行计算的： $$ 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…
-
Shamir密钥分享算法简析
简述 秘密共享技术是密码学和信息安全的一个重要研究内容，$Shamir$密钥分享算法最早是由$Shamir$和$Blackly$在1970年基于$Lagrange$插值和矢量方法提出的，其基本思想是分发者通过秘密多项式，将秘密$s$分解为$n$个秘密分发个持有者，其中任意不少于$k$个秘密均能恢复密文，而任意少于$k$个秘密均无法得到密文的任何信息。 实际应用 比如在门限体系中，为了保证信息安全性，一个秘密通常不能由单个持有者保存。比如一些重要场所的通行，比如遗嘱的生效等，必须将秘密分由…