前言在密码学、RSA 加密、数论类 CTF 题目里最大公约数 GCD是最基础、最高频的前置知识点几乎所有公钥密码题型都会依赖 GCD 与互质的概念。 这道入门题完整讲解了 GCD 定义、互质概念、欧几里得辗转相除法同时提供可直接运行的 Python 代码非常适合新手入门数论类密码题。本文整理成完整可发布的技术博客包含原理、代码、拓展知识点。一、题目完整信息基础信息题目名称Greatest Common Divisor最大公约数题型密码学 - 基础数论分值15 分难度入门级题目原文描述最大公约数GCD也叫最高公因数指能够同时整除两个正整数(a,b)的最大正整数。示例 1a12b812 的因数{1,2,3,4,6,12}8 的因数{1,2,4,8}公共因数最大值为 4即gcd(12,8)4示例 2a11b17二者均为质数 质数的因数只有 1 和自身因此公共因数只有 1gcd(11,17)1核心概念互质Coprime若两个整数a,b的最大公约数gcd(a,b)1则称a和b互质。 推论两个不同质数一定互质若a是质数且b a则a、b一定互质思考题如果质数ab a二者不一定互质例a3b6gcd3不互质。解题要求推荐使用欧几里得算法辗转相除法编写代码先用a12,b8测试代码正确性最后计算gcd(a66528, b52920) 计算结果即为 flag。二、前置核心知识点1. GCD 基础定义给定两个正整数能同时整除两者的最大自然数记作 gcd(a,b)。若 gcd(a,b)1两数互质质数p与小于它的所有自然数互质若另一个数包含该质数作为因子则不互质。2. 欧几里得辗转相除法核心原理核心公式gcd(a,b)gcd(b, amodb) 循环取模直到余数为 0此时的b就是最大公约数。 逻辑演示测试样例 a12,b8gcd(12,8)gcd(8, 12mod84)gcd(8,4)gcd(4, 8mod40)余数为 0终止结果 4和题目示例一致。3. Python 两种实现方式手动实现欧几里得算法理解底层原理CTF 数论题必考手写标准库math.gcd快速调用适合快速出结果注意库函数限制。三、完整解题代码 分步讲解方案 1手动实现欧几里得辗转相除法推荐学习python运行# 自定义欧几里得算法求GCD def gcd(a, b): while b ! 0: # 取模更新a、b a, b b, a % b return a # 题目测试用例 test_a 12 test_b 8 print(f测试用例 gcd({test_a},{test_b}) {gcd(test_a, test_b)}) # 题目要求计算的数值 num_a 66528 num_b 52920 result gcd(num_a, num_b) print(f目标 gcd({num_a},{num_b}) {result})代码拆解循环条件while b ! 0只要余数不为 0持续迭代a, b b, a % b同步更新变量把除数变成新被除数余数变成新除数当b0时循环结束此时a就是最大公约数先用题目给的12,8测试验证代码逻辑无错误再代入题目大数计算。方案 2Python 标准库快速求解python运行import math # math.gcd仅接收非负数且返回绝对值GCD a 66528 b 52920 res math.gcd(a, b) print(res)注意math.gcd存在限制只能处理正数、大数模运算手写算法兼容性更强CTF 复杂数论场景推荐手写。四、运行结果与验证控制台输出plaintext测试用例 gcd(12,8) 4 目标 gcd(66528,52920) 1512最终计算结果1512与题目给出的 flag 完全匹配。手动推演简略过程辅助理解gcd(66528, 52920) gcd(52920, 13608)gcd(52920, 13608) gcd(13608, 12096)gcd(13608, 12096) gcd(12096, 1512)gcd (12096, 1512) gcd (1512, 0) 余数为 0终止GCD1512。五、核心概念拓展密码学高频考点1. 互质在密码学中的作用RSA 加密算法的核心前提选取两个大质数p,q计算 φ(n)(p−1)(q−1)加密公钥e必须满足 gcd(e,φ(n))1互质否则无法求出解密私钥d。2. 欧几里得算法拓展扩展欧几里得普通 GCD 只能求最大公约数扩展欧几里得算法可以同时求出满足 axbygcd(a,b) 的整数解x,y是求解模逆元的核心工具几乎所有 RSA 解密题都会用到。3. 常见题型变形给出两个大数求 GCD本题原型多数字 GCDgcd(a,b,c) gcd(gcd(a,b),c)结合模逆元、RSA 分解模数、同余方程。六、新手学习避坑总结不要暴力枚举因数大数分解因数效率极低欧几里得算法迭代次数极少百万级数字也能瞬间算出区分「质数」和「互质」两个数互质不代表都是质数例gcd (8,9)1二者都不是质数库函数math.gcd坑点只返回正数、无法处理 0、负数会自动取绝对值复杂数论场景建议手写辗转相除思考题答案质数a3b6bab是a的倍数此时 gcd3≠1不互质。