位运算

这个更是密码学基础中的基础了

与运算

规则：两位都为1，结果才为1
0 & 0 = 0
0 & 1 = 0  
1 & 0 = 0
1 & 1 = 1

或运算

规则：有一位为1，结果就为1
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

异或运算

规则：两位不同为1，相同为0
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1  
1 ^ 1 = 0

取反运算

规则：位取反
~0 = 1
~1 = 0

左移运算

普通左移

规则：二进制位向左移动，低位补0，高位丢弃
示例(8位)：10101010 << 2 => 10101000
          ↑↑丢弃      ↑↑补0

循环左移

规则：二进制位向左移动，高位移出的位依次补充到低位
示例(8位)：10001001 <<< 2 => 00100110
           ↑↑移出放到右边→→→→→↑↑

右移运算

逻辑右移

规则：二进制位向右移动，高位补0，低位丢弃
示例：10101010 >> 2 => 00101010
        ↑↑补0      ↑↑丢弃

算术右移

规则：二进制位向右移动，高位补符号位，低位丢弃
示例(有符号)：10101010 >> 2 => 11101010
              ↑↑补符号位

循环右移

规则：二进制位向右移动，低位移出的位依次补充到高位
示例：10001001 >>> 2 => 01100010
       ←←←←←↑↑移出放到左边↑↑

模运算 (Modular Arithmetic)

欧几里得算法

gcd(a,b)
if a > b:
    a / b % x
    b / x % y
    if y == 0:
        return x
    else
        x / y % z
        ....

gcd(a, b):
    while b ≠ 0:
        r = a mod b
        a = b
        b = r
    return a

拓展欧几里得

函数 gcd_extended(a, b):
    输入：两个整数 a, b
    输出：三元组 (gcd, x, y)，满足 a*x + b*y = gcd
    
    步骤：
    1. 如果 b == 0:
        - 此时 gcd(a, 0) = a
        - 因为 a*1 + 0*0 = a，所以返回 (a, 1, 0)
        
    2. 否则（b ≠ 0）:
        a. 递归调用：gcd, x1, y1 = gcd_extended(b, a % b)
           - 这里我们计算更小规模的 gcd(b, a % b)
           - 并得到对应的系数 x1, y1，满足：b*x1 + (a % b)*y1 = gcd
           
        b. 计算当前层的系数 x 和 y:
           - x = y1
           - y = x1 - (a // b) * y1
           
        c. 返回 (gcd, x, y)

群

群是一个代数结构，包含一个集合G和一个二元运算，如果满足一下定理那么这个就是一个群

在G中任意取出元素a,b指定某个运算，得到结果依旧属于G 运算符号代指 => ⋅

封闭性
对于任意a,b∈G,有a⋅b∈G
结合律
当a,b,c∈G，并且(a⋅b)⋅c = a⋅(b⋅c)
单位元存在
存在e∈G，使得对所有a∈G，有e⋅a = a ⋅ e = e
逆元存在
对任意a∈G,存在b∈G,使得a⋅b=b⋅a=e,称a为b的逆元，记作a^-1

阿贝尔群

在群的基础上加了

交换律
对任意a,b∈G，有a⋅b = b⋅a

X25519密钥交换