Luyu Huang's Tech Blog

RSA算法背后的数学原理

1. 引言 RSA算法(RSA algorithm)是一种非对称加密算法, 广泛应用在互联网和电子商务中. 它使用一对密钥进行加密和解密, 分别称为公钥(public key)和私钥(private key). 使用公钥加密的内容只能用私钥解密, 使用私钥加密的内容只能用公钥解密, 并且不能通过公钥在可行的时间内计算出私钥. 这使得加密通信不需要交换私钥, 保证了通信的安全. 那么它是怎么做到这一点的呢? 背后有哪些数学原理? 这篇文章我们来讨论这个问题. 本文会先介绍RSA算法中用到的数论概念和定理: 模算术, 最大公约数与贝祖定理, 线性同余方程, 中国余数定理, 费马小定理; 然后再介绍RSA算法的原理, 并证明其是有效的. 本文会假设你了解数论的基本概念, 如素数, 最大公约...

Read more

通过 UNIX domain socket 在进程间传递文件描述符

Linux 提供了一系列系统调用使我们能在进程间传递文件描述符. 这里的 "传递文件描述符" 不是简单地传递文件描述符这个32位整数, 而是真正地把这个文件句柄传递给目标进程, 使目标进程可以对文件执行读写操作. 现在假设 进程B 要给 进程A 发送文件描述符, 我们来看具体做法. 1. UNIX domain socket 要想传递文件描述符, 首先需要建立进程间通信. 这里我们需要用到 UNIX domain socket. UNIX domain socket 是一种进程间通信的方式, 它和普通的 socket 类似, 不同的是不需要用到 ip 地址, 而是使用一个 socket 文件. 我们要利用它发送控制信息, 从而传递文件描述符. 首先我们让进程A先创建一个 socket...

Read more

解数独算法

1. 引言 数独是一种经典的数字游戏, 玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复. 通常盘面上会给出一些提示数让玩家推导. 通常数独的解是唯一的, 但随着提示数的减少, 数独也可以有多个解; 极端情况下, 没有提示数, 数独也是可以解的, 只不过解的数量会非常多. 本文讨论解数独的算法, 并且尝试求出一个数独的所有可行解. 2. 合法的数 我们来看数独的规则: 玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复. 首先我们需要根据任意一个给定的棋盘, 快速地得出任意一个空白格子上可填的数. 怎样做到这一点呢? 遍历这个格子所在的行, 列和...

Read more

详解寻路算法(2)-生成图

1. 引言 上篇文章 中主要讲解了 A* 算法. 然而 A* 算法只是一个图搜索算法, 我们在游戏中的地图通常是用一些不规则图形定义的一片行走区域, A* 算法并不能识别这样的地图. 因此我们要做的工作就是把一张这样的地图抽象成可用邻接矩阵或邻接链表表示的数学上的图 $G=(V,E)$. 本文介绍两种方法, 可视图(visibility graph) 法和 导航网络(Navigation Meshes)法. 2. 可视图(visibility graph) 对于大多数地图来说, 我们可以看成由一个无限大的行走区域和若干个障碍物组成; 为了简化问题, 障碍物通常都可以看做多边形. 如下图所示: 想象我们处于起始点, 要绕过障碍物到达目标点. 当我们绕过障碍物时, 最短的方式...

Read more

编辑距离

题目源自Leetcode: 编辑距离-leetcode 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 示例: 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解法: 动态规划 这是一道很漂亮的动态规划问题. 我们这样想: 越长的单词求解就越困难, 越短的单词求解就越简单: 长度为1的单词只需比较字母是否相...

Read more

详解寻路算法(1)-图搜索

1. 引言 寻路算法广泛应用在各种游戏中. 寻路算法要解决的问题是, 给定一个 "地图"(定义可行走区域), 一个起点, 和一个目标点, 求起点到目标点的最短路径. 解决寻路问题是一个复杂的过程, 涉及到若干个算法. 大体可以分为两个步骤: 把 地图 抽象成 图. 这里的图指的是数学上的图 $G=(V,E)$; 对图进行搜索. 相比图搜索, 把地图抽象成图通常会比较复杂. 这篇文章先介绍介绍图搜索算法. 在下篇文章中, 我会介绍几种把地图抽象成图的方法. 图搜索算法有很多. 在寻路算法中, 主要用到 A* 算法. 这里我会先介绍 Dijkstra 算法, 然后引出 A* 算法. 稍后会看到, 这两种算法很相似: Dijkstra 算法总是搜索最近的, 适用于求解单源对所...

Read more

牛顿迭代法求平方根

1.先说结论 $\sqrt{a}$ 可这样求得: 令 $x_0$ 为任意实数, 执行以下迭代式: \[x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1}\] 迭代若干次, 当 $|x_i-x_{i-1}|$ 小于想要的精度时便可停止迭代. 最终的 $x_i$ 便可视为 $\sqrt{a}$. 根据 (1) 式我们可以很快写出求平方根的代码: def sqrt(a): x = 1.0 while True: pre = x x = (x + a / x) / 2 if abs(x - pre) < 1e-6: break retur...

Read more

在Lua中使用装饰器

引言 使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行"声明": def decorator(f): def wrapper(x): print 'call %s' % f.__name__ return "The 2nd power of {0} is {1}".format(x, f(x)) return wrapper @decorator def foo(x): return x ** 2 装饰器本质上只是一种语法糖: 把目标函数作为参数传入装饰器. 巧妙地使用装饰器, 可以让程序变得简洁优雅. 比如说, 声明一个函数是事件, 声明一个函数是远程调用接口, 等等. 在...

Read more