Ideal Area

介绍

是一种在数论中的等价关系，当两个整数除以同一个正整数，若得到相同的余数，则两个整数同余。

性质

加法原理

$(a+b)\ mod\ n=[(a\ mod\ n)+(b\ mod\ n)]\ mod\ n$

乘法原理

$ab\ mod \ n=[(a\ mod\ n)(b\ mod\ n)]\ mod\ n$

传递性

$a ≡ b\ (mod\ m),b ≡ c\ (mod\ m),可以推出 a≡c\ (mod\ m)$

费马小定理

发表于 2020-10-10 更新于 2020-10-11 分类于 Math | Cryptography

定理描述

假设 P 是一个素数，a 是一个整数，那么 $a^P-a\ 是 P 的倍数$ ，即 $a^{p} ≡ a（mod\ p）$

如果 a 不是 P 的倍数，这个定理也可以写成： $a^{p-1} ≡ 1（mod\ p）$

证明过程

根据同余的性质，只需要证明 $a^P ≡ a \ (mod\ P)\ ，对于 0\le a \le P-1 成立，就可以可出上述定理。$

反证法。假如结论不成立的话，就会有 i, j 两个数字，使得

$i * a \equiv j * a\pmod n$

不妨假设 i > j，将上式移动一下位置，就会有

$(i - j) * a \equiv 0\pmod n$

换句话说，就是 (i - j) * a 可以被 n 整除。而 n 是素数，那么 (i - j) 或者 a 其中之一就必须包含因子 n。但 (i - j) 和 a 都比 n 要小，显然不可能包含因子 n。于是结论得证。

上面的证明中，不一定需要 a < n。只要 n 为素数，而 a, n 两者互质，证明也可成立，费马小定理也可成立。

-—————————-

因为乘以 a 再 mod n，只是 1 到 n - 1 的重新排列，数字并不会重复。于是我们就可以知道

$(1 * 2 * 3 .... n - 1) = (a\bmod n)(2a\bmod n)(3a\bmod n) ... ((n-1)a\bmod n)$

应用同余的乘法原理，使用同余的记号，可以将上式记为

$(1 * 2 * 3 .... n - 1) \equiv a * 2a * 3a * ... (n-1)a\pmod n$

将上式同时除以 $(1 * 2 * 3 .... n - 1)$ ，费马小定理得证

$a^{n-1}\equiv 1\mod n$

欧几里得算法

发表于 2020-10-09 更新于 2020-10-10 分类于 Math | Cryptography

欧几里得算法

又称辗转相除法，指的是：对于任意的非负整数 𝑎 和正整数 𝑏 ，求这两个数的最大公因数 ，记为 $gcd(a,b)$ ，其中 gcd 是 greatest common division 的首字母组合。

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数，即 $gcd(a,b) = gcd(b,a\ mod\ b)$

证明过程

对于任何可以整除 a 和 b 的整数，那么它也一定能整除 a-b （和 b )，因此我们选择该整数（前面提到的任何整数）为 gcd(a,b) ，它一定比 a-b 和 b 的最大公约数小： $gcd(a,b) \le gcd(a-b,b)$

同理，任何可以整除 a-b 和 b 的整数，一定可以整除 a 和 b ，因此我们选择该整数为 gcd(a-b,b) ，它一定比 a 和 b 的最大公约数小： $gcd(a-b,b)\le gcd(a,b)$

由此可得： $gcd(a,b)=gcd(a-b,b)$

必然存在整数 n ，使得 $a - n*b = a \ mod\ b$ ，所以迭代可知：

$gcd(a-b,b)=gcd(a-2b,b)=...=gcd(a-n*b,b)=gcd(a \ mod\ b,b)$

实现及其工程优化

def gcd(num1,num2):
    while num1 % num2 != 0:
        num1, num2 = num2, num1
    if num1 % num2 == 0:
        return num2

但是当整数很大时，取模运算的性能较低，所以我们对其进行优化，使用 移位运算 + 更相减损术

def gcd(num1,num2):
    if num1 < num2:
        return gcd(num2,num1)
    if num1 == num2:
        return num2
    if (num1 % num2 == 0) and (num2 % 2 == 0):
        return gcd(num1 >> 1, num2 >> 1) << 1
    elif (num1 % 2 == 0):
        return gcd(num1 >> 1, num2)
    elif (num2 % 2 == 0):
        return gcd(num1, num2 >> 1)
    else:
        return gcd(num2, num1-num2)

扩展欧几里得算法

是欧几里得算法的扩展。已知整数 a，b，扩展欧几里得算法可以在求得 a、b 的最大公约数的同时，能找到一组整数解 x、y（其中一个很可能是负数），使他们满足 $ax+by=gcd(a,b)$ 。

我们知道，在欧几里得算法中我们仅仅利用了每步带余除法所得的余数，而扩展欧几里得算法中还利用了带余除法所得的商。扩展欧几里得算法可以用来计算模反元素（也叫模逆元），计算模反元素是 RSA 加密算法中获得所需公钥、私钥的必要步骤。

过程

在欧几里得算法中，我们记欲求最大公约数的两个数为 a、b，第 i 次的带余除法所得的商为 $q_i$ ，余数为 $r_{i+1}$ ，则欧几里得算法可以写成如下形式：

$r_0=a \\ r_1=b \\ .\\ .\\ .\\ r_{i+1}=r_{i-1}-q_ir_i$

当计算到 $r_{i+1}=0$ 时，计算结束。上一步得到的 $r_i$ 即为 a、b 的最大公约数。

而在扩展欧几里得算法中，再增加两组序列 $s_i,t_i$ ：

$r_0=a ,\ s_0=1,\ t_0=0\\ r_1=b ,\ s_1=0,\ t_1=1\\ .\\ .\\ .\\ r_{i+1}=r_{i-1}-q_ir_i,\ s_{i+1}=s_{i-1}-q_is_i,\ t_{i+1}=t_{i-1}-q_it_i$

结束的条件和欧几里得算法一致，即 $r_{i+1}=0$ ，此时所得的 $s_i和t_i即满足\ gcd(a,b)=r_i=as_i+bt_i$

实现

def ext_euclid(a,b):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = a, b
    if b == 0:
        return 1,0,a
    else:
        while(r != 0):
            q=old_r // r
            old_r, r = r, old_r-q*r
            old_s, s = s, old_s-q*s
            old_t, t = t, old_t-q*t
    return old_s,old_t,old_r

Knowledge-of-Exponent Assumption 简介

发表于 2020-09-23 更新于 2020-09-27 分类于 cryptography | ZKP

假设有这样一个场景，我们在解决一个值得获得图灵奖的一个问题，在最后的关头，需要大量的计算来支持我们的理论，但是由于经费问题，我们本身是无法去完成这样庞大的计算的，所以我们准备和别的实验室合作，借用对方的机器来完成这些计算，但是我们肯定是不希望把这些计算暴露出来，但是我又希望对方没有篡改我输入的数据，怎么办？这就引出了这篇文章所要讲的 KEA ，即 Knowledge-of-Exponent Assumption 。

阅读全文 »

np vs p

发表于 2020-09-22 更新于 2020-09-23 分类于 math

关于 P 与 NP 问题的简单说明：

假设你正在为 400 名大学生组织住宿，但是空间有限只有 100 名学生能在宿舍里找到位置。更复杂的是还给了你一份不相容学生的名单，并要求在你的最终选择中不要出现这份名单中的任何一对。
这是计算机科学家称之为 NP 问题的一个例子，因为很容易检查一个同事提出的一百个学生的给定选择是否令人满意，然而从头开始生成这样一个列表的任务似乎太难了以至于完全不切实际。
事实上从 400 名申请者中选择 100 名学生的方法总数比已知宇宙中的原子数量还要多！这类其答案可以被快速检查，但是通过任何直接的程序需要不可接受长度的时间来解决，比如 300 年或者更多…
斯蒂芬·库克和列昂尼德·莱文在 1971 年独立地提出了 P (即容易找到)和 NP (即容易检查)问题。

阅读全文 »