Alice and Bobの神秘小屋

在前面的章节中，我们已经介绍了数论的一些基础知识，现在我们将进入密码学数学基础的另一个重要领域：抽象代数，特别是群环域的基础知识。😎 本章节将为你揭开群论的神秘面纱，带你领略这个数学领域的独特魅力。我们将从最基本的群的定义开始，逐步深入到群的性质、子群、同态、商群等重要概念。🤪

当我们要计算一个与已知数近似的数的确定值时，连分数算法就像一把精确的放大镜🔍，能帮我们在无尽的小数世界中找到那个最接近的整数解。 欢迎来到《密码学核心算法实战》的 Wiener 算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 Wiener算法 🌟Wiener算法是基于连分数的一个算法，主要用于求解近似整数问题。它的核心思想是利用连分数的性质来找到一个数的最佳近似值，从而求解一些特定的数学问题。 具体来说，有一个已知数 $x$ 满足： x = \frac{p}{q} (1 - \epsilon)其中 $\epsilon$ 是一个很小的正数，且 $p$ 和 $q$ 是两个整数。Wiener算法的目标是通过已知的 $x$ 来找到 $p$ 和 $q$ 的值。 Wiener算法的原理 😭由 $Ad - Bk = 1$，可以得到 $\vert \frac{A}{B} - \frac{k}{d} \vert = \frac{1}{Bd}$，所以 $\frac{k}{d}$ 是 $\frac{A}{B}$ 的一个近似值。 引入连分数收...

当你在计算某个数的近似值时🔍，或者在求解某个方程的根时🧮，连分数算法 就像一把神奇的放大镜🔎，能帮你逐步逼近那个隐藏在数字背后的真相。 欢迎来到《密码学核心算法实战》的连分数专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 连分数算法的操作 🌟这个算法可以直接将一个有理数或者无理数直接表示成一个连分数形式，当然因为这个算法的原理十分简单，所以就不单独拿出来讲了，直接进入正题！🤗 输入：一个实数 $x$。令 $i = 0$，$x_0 = x$ 令 $a_i$ 为 $x_i$ 的整数部分 $b_i = x_i - a_i$，如果 $b_i = 0$，则算法结束 如果 $bi \neq 0$，则令 $x{i+1} = \frac{1}{b_i}$，$i = i + 1$，回到步骤 1 输出：连分数的部分商 $a_0, a_1, a_2, \ldots$，即 $x = [a_0, a_1, a_2, \ldots]$。 反过来，$x = [a_0, a_1, a_2, \ldots]$ 也可以通过递推关系来计算出 $x$ 的...

在前面的章节中，我们已经介绍了连分数的基本概念和一些重要的性质。现在，我们将进一步深入探讨连分数的一些进阶内容，而且我们会在渐进分数的基础上，介绍一些更高级的定理和应用。😎 话不多说了，可能有些难，但是直接进入正题！🤗 渐进分数 🤩渐进分数是指连分数的前 $n$ 项所对应的有理数，例如 $[a_0]$, $[a_0, a_1]$, $[a_0, a_1, a_2]$ 等等。 我们记 $[a_0, a_1, \ldots, a_n] = \frac{p_n}{q_n}$，其中 $p_n$ 和 $q_n$ 分别是分子和分母，那么我们可以得到以下递推关系①： \begin{align*} p_n &= a_n p_{n-1} + p_{n-2} \\ q_n &= a_n q_{n-1} + q_{n-2} \end{align*}还有一个有趣的定理②：对于任意的 $n \geq 1$，都有 p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}而且这种渐进分数有一种特殊单调性③（很重要，快看！😡）：对于有限连分数 $[a_0, a_1, \ldots, ...

当你熟练掌握 Tonelli-Shanks 算法求解同余方程问题，但是在处理多项式方程的根📐，发现问题和以前有一点点不太一样，在这里需要将模 $p$ 的解提升到模 $p^k$ 的解时😱，别担心，这时候 Hensel-lifting 算法 就像一把神奇的梯子🪜，能帮你一步步攀登到更高的解空间。 欢迎来到《密码学核心算法实战》的 Hensel-lifting 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 Hensel-lifting算法 🌟Hensel-lifting 算法用于将模 $p$ 的多项式方程的解提升到模 $p^k$ 的解。具体来说，如果我们有一个多项式 $f(x)$ 和一个整数 $a$，满足 $f(a) \equiv 0 \pmod{p}$，并且 $f’(a) \not\equiv 0 \pmod{p}$，那么 Hensel-lifting 算法可以帮助我们找到一个整数 $b$，使得 $f(b) \equiv 0 \pmod{p^k}$。 Hensel-lifting算法的原理 😵设 $k \geq 1$ 是...

当你在椭圆曲线上进行加密操作时📐，需要计算某个点的平方根，但又发现这个点在有限域中没有平方根时😱，别担心，这时候 Tonelli-Shanks 算法 就像一把灵巧的钥匙🔑，能帮你在无解的荒漠中精准定位那唯一的坐标点。 欢迎来到《密码学核心算法实战》的 Tonelli-Shanks 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 Tonelli-Shanks算法 🌟Tonelli-Shanks 算法用于求解形如： x^2 \equiv a \pmod{p}的同余方程，其中 $ p $ 是奇素数，$ a $ 是模 $ p $ 下的平方数。 Tonelli-Shanks算法的操作 🙃输入：一个整数 $ a $ 和一个奇素数 $ p $，满足 $ a $ 是模 $ p $ 下的平方数。则 $ (\frac{a}{p}) = 1 $。输出：一个整数 $ x $，满足 $ x^2 \equiv a \pmod{p} $。 算法步骤： 将 $ p-1 $ 分解为 $ Q \cdot 2^s $，其中 $ Q $ 是奇数。（如果 ...

在上一章我们介绍了欧几里得算法和扩展欧几里得算法，这些算法在计算最大公约数和模逆元方面非常有用，但当我们需要处理多个模数时，效率可能会变得很低。中国剩余定理（Chinese Remainder Theorem，CRT）就是为了解决这个问题而诞生的。 这个定理也可以叫做孙子定理（Sunzi Theorem），是中国古代数学家孙子在《孙子算经》中提出的一个重要定理。原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这个定理就是在这里提取的。👻 欢迎来到《密码学核心算法实战》的中国剩余定理CRT专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 中国剩余定理 😋中国剩余定理的核心思想是：如果模数两两互质，那么一个同余方程组的解可以通过将各个模数对应的解进行组合来得到。具体来说，给定一组同余方程： \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \en...

本章节我们将深入探讨欧几里得算法（Euclidean Algorithm），这是一个古老而又强大的工具，用于计算两个整数的最大公约数（GCD）。这个算法不仅在数学领域有着重要的地位，更是密码学中不可或缺的基础算法之一。 在密码学中，我们常常使用这个算法完成对裴蜀定理的解决，计算模逆元，以及在一些加密算法中进行关键的数论运算。通过理解欧几里得算法的原理和实现，我们可以更好地掌握密码学中的许多核心概念。 欢迎来到《密码学核心算法实战》的欧几里得算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 欧几里得算法的原理 😋欧几里得算法基于一个重要的性质：对于两个整数 $ a $ 和 $ b $，如果 $ a > b $，那么 \text{gcd}(a, b) = \text{gcd}(b, a \mod b)这个性质告诉我们，两个数的最大公约数等于较小的数和较大的数对较小的数取模后的结果的最大公约数。通过不断地将较大的数替换为较小的数和它们的余数，我们可以快速找到最大公约数。 欧几里得算法的实现 🤨下面是欧几里得算法的一个简单实...

当你在验证数字证书的真伪📜、向钱包里导入私钥🔑、或是在区块链上完成一笔跨链交易⛓️时，那些在代码底层飞速运转的 “黑盒”，背后其实是一群不知疲倦的算法工匠在精准操刀⚙️。欢迎来到《密码学核心算法实战》的硬核工坊！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 在密码学的兵器谱里，数学是铸造神兵的矿石⛰️，而算法就是将矿石锻造成利剑的炉火与锤法🔨。本系列专题将带你亲手拆解密码学中最经典、最核心的算法实现，特别是数论算法、开方算法和离散对数算法这三大 “王牌工具”🧰。从古老却依旧强悍的欧几里得算法，到堪称 “中国智慧之光” 的孙子定理（CRT），再到能在有限域中 “求根问底” 的 Tonelli-Shanks 算法，我们会一层层剥开这些算法的外衣，看清它们最核心的运行逻辑。 别害怕，我会用庖丁解牛的方式（🔪➡️🐂），让你发现这些看似复杂的逻辑，其实是构建现代密码体系的精密发条。它们不仅是 RSA、ECC 这些非对称加密的 “心脏”❤️，更是零知识证明、多方安全计算等前沿领域的基石。 想象一下：当你计算私钥的模逆元时♻️，扩展欧...

这首歌改编自薛之谦的《我好像在哪里见过你》，当然，说唱的话用那首歌的DJ版的旋律和节奏来唱会更好哦！😎虽然只有一小段，相信我跟着DJ的旋律你一定会上头的，那就让我们一起嗨起来吧！😋 I \ thought \ that \ travelers \ burned \ my \ passion \ into \ pieces.Ur \ like \ a \ love \ letter, \ preliminary.Love \ secrets \ in \ the \ password \ is \ where \ all \ people \ keep.Full \ of \ execuses \ we \ both \ know \ its \ you \ tryna \ leave.I \ heard \ ur \ voice \ it \ felt \ so \ deep.And \ I \ saw \ ur \ heart \ that \ cant \ be \ seen.I \ hid \ in \ a \ crowd \ thats \ real \ picky....