Leet Arxiv

RSS: https://leetarxiv.substack.com/feed

用你喜欢的语言动手实现 Arxiv 论文的练习场。

适用于机器字整数的快速素性测试

介绍 Forisek 和 Jancina 的一个 32 位整数快速素性测试方法：不跑多项 Miller-Rabin 轮次，而是用 256 个预设底数表，配合一个把 32 位输入映射到 0-255 的哈希函数选出一个底数，做一次 strong probable prime 测试即可完成判定。代码展示了该哈希（两轮 0x45d9f3b 乘法混洗）、strong probable prime 判定逻辑，以及完整 C 实现。对需要快速判断机器字内整数是否为素数的场景（如密码学筛法、竞赛代码、轻量随机数生成器验证）有实用价值；主要争议点在于 256 底数表是否能保证在 32 位范围内无假阳性，以及该方案的理论依据和适用边界。

收藏2 天前

构造异常椭圆曲线

这是 Leet Arxiv「实用椭圆曲线理论」系列的第 10 篇。前一篇介绍了"异常曲线"（Frobenius 迹 t=1，ECDLP 易解）及其 Smart 攻击，本篇讲如何主动构造异常曲线。核心：Olson(1976) 证明若 p=12s²+6s+1 为素数，则必存在形式 y²=x³+b (mod p) 的异常曲线；Leprévost 等人则用复亏格/CM 搜索方法，把搜索范围关联到 Heegner 数和判别式 D（非 7 且非 ≡3 mod 8 的情形）。反方向限制：y²=x³+ax 这类曲线不可能异常，Heegner 数小（1,2,3,7）的 CM 曲线也不可能异常，所以搜索要限定在 y²=x³+b、y²=x³+ax+b 及其 twists。后续用 Python 实际构造。内容偏数学理论+工程实现，信息密度高，但深度专业，普通读者门槛较高。

收藏5 天前

Bernstein 因式分解方法助力 2020 年分解 RSA-240

本文讲解 Bernstein 2002 年提出的批量平滑性检测算法（batch smoothness detection），该算法利用积树（product trees）加速对一组整数同时查找小于阈值 B 的所有小因子。 2020 年 Boudot 等人用 CADO-NFS 分解 795 位的 RSA-240 时，该算法贡献了约 25% 的加速。文章面向编程实践，属于 Practical NFS 系列第 8 篇，重点讲"延迟目标离散对数（delayed-target DLP）"：在数域筛法中需要同时求多个单个元素的离散对数，Bernstein 批量算法把这一批目标合并处理，减少总体计算量。文章给出 Python 骨架代码和 Colab 链接，逐节展开辅助算法（格规约、特殊下降、多项式下降等）。对了解现代 RSA 分解工程细节的读者有参考价值；信息密度中等偏上，一手实践性不错，但属于系列长文的某一节点，单篇讨论入口有限。

收藏9 天前

GCC 如何用魔法数字消除不必要的整数除法

作者把 Ammon 2011 年《Fast Unsigned Division by Constants》论文应用到素数筛选（number field sieve）场景，演示 GCC 如何用乘法+比较替换常量整除：以 x%17==0 为例，x86 汇编里变成 imul + cmp，而变量除法仍走 div 指令；并对比了 1 亿次循环下常量模 0.45s vs 变量模 0.56s 的性能差异。文中给出 32/64 位常见除数的魔法数字对照表（如 x%3→x*0xAAAAAAAB<=0x55555555），解释 round-up 与 round-down 两种算法（后者解决 33 位魔法数溢出 32 位寄存器的问题），并基于 libdivide 参考实现了一段 C 代码，可现场计算任意除数的魔法数并做整除判定，示例除 7 得到 multiplier=1227133513、post-shift=1、increment=1。整体偏教学向，有可运行代码和汇编对照，适合想了解编译器优化细节的读者动手复现。

收藏16 天前

连分数与格基筛法加速

Franke和Kleinjung在2025年发表论文，用连分数展开改进GLM格基筛法中找下一个有效格点的过程。文章是Number Field Sieve编程系列第7篇，给出Python代码和Colab实现，核心思路是利用连分数系数的最佳有理逼近性质，在格点上快速跳跃而非逐个枚举。

收藏24 天前

Python 中的 Sherry、龙舌兰与量化精灵

BitNet b1.58 将大语言模型权重压缩到 -1/0/1 三个值，矩阵乘法退化为加减法。Sherry 在此基础上引入 3:4 稀疏约束——每4个权重中恰好3个非零、1个固定为零，用5位存储一个块，适配 SIMD 并行。训练时用 absmean 量化函数约束权重范围，配合 STE 反向传播。Arenas 模块在 QAT 阶段注入梯度以缓解权重陷入局部区域的梯度同质化问题。

收藏51 天前

匈牙利分配算法：从任务分配到矩阵平衡

匈牙利分配算法解决任务与资源的最优一对一匹配问题，将总成本或总时间最小化。原始Kuhn算法时间复杂度O(n⁴)，现代Scipy等实现采用Jonker-Volgenant算法降至O(n³)，可处理大规模分配问题。该算法与Sinkhorn-Knopp矩阵平衡算法密切相关，也可将Gumbel-Sinkhorn网络输出的双随机矩阵转换为排列矩阵。

收藏52 天前

L2 Reduction: LLL Algorithm With Quadratic Complexity

This is part of our series on LLL where we’ve coded Original 1982 LLL Reduction paper. Lattice reduction in 2-Dimensions. Gaussian lattice sieving. LLL Applied to Hermite Normal Forms and GCD. (we are...

收藏58 天前

每个程序员都应该了解的椭圆曲线扭运算

给定13个故障和一台好的电脑，一个人可以在1分钟内破坏secp256k1（和比特币）。保罗·S.L.M.巴雷托。这篇免费文章是我们关于程序员实用椭圆曲线理论:：在C语言中破解休眠的比特币钱包。：对异常曲线的智能攻击。：寻找异常曲线。：Python 中椭圆曲线的除多项式。：将除法多项式应用于点计数。：具有高效自同构的曲线上的快速点乘法。第七部分（我们到了：Sage/Python 中椭圆曲线的扭曲。：利用等价类加速在短时间内解决离散对数问题。巴雷托是BLS椭圆曲线家族中的B型曲线<h2>1.0 简介</h2>椭圆曲线理论有些晦涩，椭圆曲线的扭曲也相当晦涩。本指南向节目观众演示椭圆曲线扭转的工作原理。按照典型的LeetArxiv风格，我们展示的是实际代码，而不是密集的数学方程。我们教程序员如何将高级数学论文转化为代码。订阅我们的主要资料是椭圆曲线的扭曲（《它》，1997年）.摘要椭圆曲线的扭曲（《它》，1997年）<h2>1.1 “椭圆曲线扭曲”的定义</h2>椭圆曲线的“扭曲”一词有些模糊。当人们说反转如果没有修饰语，它们往往意味着二次扭转椭圆曲线（Cook，2019）.不过，立方体、六型以及其他扭曲也存在。非正式地说，*椭圆曲线的扭曲是另一条与原始椭圆曲线共享某些x或y坐标和群律的代数曲线。<h2>*吹毛求疵的人会把我钉在十字架上。</h2>例如，比特币secp256k…

收藏61 天前

Pollard's p-1 因数分解算法的纯 C 语言实现

Leet Arxiv 用 C 语言实现 Pollard's p-1 整数分解算法，基于 Wagstaff 2013 和 Charest 2005 论文，提供从数学定理到代码的完整推导。算法利用费马小定理，当素因子 p-1 含小素因子时高效分解大整数，Stage 1 指数 S 通过 LCM 树状捷径计算，B=1000 时 S 达 1438 位。 GitHub 可获取完整代码，适合密码学、数论或工程实践读者深入阅读。

收藏64 天前

使用泰勒级数和帕德逼近为 FPGA 实现 Softmax 近似

Leet Arxiv 团队在 FPGA 上实现 Softmax，对比了泰勒级数与帕德逼近两种近似方法。实验显示：低误差场景下建议使用带 LUT 的二次插值；追求性能时泰勒展开更快，帕德逼近更准。代码已开源，含 Python 实现与评估基准。

收藏64 天前

Writing a Wikipedia XML Parser in Plain C

LeetArxiv 系列教程第三部分，介绍使用纯 C 语言编写 MediaWiki 和 Wikipedia XML 解析器。内容从递归下降 PEG 解析器的尝试转向状态机实现，以适配数据压缩需求（Hutter Prize）。教程基于 Enwik9 数据集，展示了内存映射加载数据、字符索引等底层 C 语言实现细节，并探讨了处理维基百科复杂混合格式（Markdown、XML、HTML）的工程挑战。

收藏68 天前

用 Python 实现 Schoof 的 1985 年椭圆曲线点计数算法

Schoof 算法将椭圆曲线点计数复杂度从指数级降至多项式级。文章通过 Python 代码实现该算法，利用 Frobenius 迹和 Chinese Remainder Theorem 计算有限域上椭圆曲线的点数。内容涉及 Division Polynomials 和 Endomorphism 算术，适合对密码学和算法实现感兴趣的开发者。

收藏69 天前

HNP-Sum: Hidden Number Problem with Small Unknown Multipliers in Python

Abstract for The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications (Heninger & Ryan, 2023) This is part of our series on Practical Hidden ...

收藏87 天前

Python中的椭圆曲线除法多项式

基于2008年论文，用Python实现椭圆曲线除法多项式及椭圆可除序列。代码验证了序列与标量乘法的关联，并给出了简化形式的实现。对密码学、数论研究者及想动手复现算法的开发者有参考价值。

收藏88 天前

The Annotated Triple Product Property Matrix Multiplication Algorithm

Subscribe now Code is available on Github or Google Colab. Here are some free GPU credits if you’d like to try this on Runpod (first come, first serve). 1.0 Introduction Dua Lipa alongside the abstrac...

收藏91 天前

神经排序算法：Gumbel-Sinkhorn 网络

基于 Mena 等人 2018 年的论文，介绍如何用 Gumbel-Sinkhorn 网络架构在 Python 中训练神经网络进行排序。该网络利用 Sinkhorn-Knopp 算法对置换矩阵进行可微近似，从而实现无需显式标签的隐式排列学习。文章提供了从理论推导到代码实现的完整路径，适合对可微排序、组合优化及神经架构设计感兴趣的开发者参考。

收藏94 天前