辗转相除+中国剩余定理(含代码).doc

仅供参考实验一：辗转相除法及其应用姓 名： 周伟康 学 号： 班 级： 信息安全11-1 实验地点： 三机房 实验时间： 2012/11/23 第1页，共8页1 实验目的和要求实验目的：掌握用欧几里德算法实现最大公约数、最小公倍数；掌握a模m的逆的求解方法；掌握用中国剩余定理求解线性同余方程组。 实验要求： (1).利用欧几里得算法求解两个数的最大公约数。 (2).利用欧几里得算法求解两个数的最小公倍数。 (3).利用中国剩余定理求解线性同余方程组 2 实验环境和工具Microsoft Visual C+3 实验结果3.1 求逆算法的流程图开始a, m互质？aa 1 (mod m)求a 流程图。 t2 = 1;t1 = 0;m | a ？q = a / m;t1 -= q * t2;a %= m;swap(t1, t2);swap(a, m);输入 a ， m输出t2（即a）结束NYN3.2 程序核心代码#include #define LL _int64#define len 100using namespace std;LL gcd(LL a, LL b) / Eucild if (a%b) return gcd(b, a%b);return b;LL exgcd(LL a, LL b, LL &x, LL &y) /扩展欧几里德，递归实现。 if (!b)x = 1;y = 0;return a;LL g = exgcd(b, a%b, x, y);LL t = x; x = y; y = t-(a/b)*y;return g;int exgcd2(LL a, LL b, LL &x, LL &y) /扩展欧几里德，递推实现。LL q, s1, s2, t1, t2;s1 = t2 = 1;s2 = t1 = 0;while (a % b) q = a / b;s1 -= q * s2;t1 -= q * t2;a %= b;swap(s1, s2);swap(t1, t2);swap(a, b); x = s2; y = t2;return b;int crt() / 孙子定理解线性同余方程LL Alen, Mlen, l;int i, j; printf(CRT (n): n); scanf(%I64d, &l); for (i=0;il;+i) scanf(%I64d %I64d, &Ai, &Mi); for (i=0;il-1;+i) for (j=i+1;jl;+j) if (gcd(Mi, Mj)!=1) printf(M array unsatisfied co-prime condition!nn); return -1; LL d, x, y, m, n=1, ans=0; for (i=0;il;+i) n *= Mi; for (i=0;il;+i) m = n / Mi; d = exgcd(Mi, m, x, y); ans = (ans + (y * m * Ai) % n) % n; d = (n + ans) %n; printf(Minimun X = %I64dnn, d);int main() LL a, b; LL g1, g2, x, y; int c; while (printf(Press 1 for Euclid， 2 for Chinese reminder theory.n),scanf(%d, &c), c=1 | c=2) if (c=2) crt(); else while (printf(Please enter 2 numbers a, b : (Quit when a=b=0)n),scanf(%I64d %I64d, &a, &b),a*b) / 多组数据，a=b=0时结束处理。 g1 = gcd(a, b); printf(%I64d, %I64d) = %I64dn, a, b, g1); printf(%I64d, %I64d = %I64dn, a, b, abs(a*b)/g1); g2 = exgcd(a, b, x, y); printf(X = %I64d Y = %I64dn, x, y); printf(%I64d * %I64d + %I64d * %I64d = %I64dn, x, a, y, b, g2); g2 = exgcd2(a, b, x, y); printf(%I64d * %I64d + %I64d * %I64d = %I64dnn, x, a, y, b, g2); system(pause); return 0;3.3 运行结果及分析（1）a = 18 ，b = 12 时，gcd（a，b）= 6，lcm（a，b）= 36。且有x = 1，y = -1 时，ax + by = gcd(a,b) 成立。结果正确 （2）a = -1859 ，b = 1573 时，gcd（a，b）= 143 ，lcm（a，b）= 20449。且有x = 5，y = 6 时，ax + by = gcd(a,b) 成立。结果正确 （3）a =169 ，b = 121 时，gcd（a，b）= 1 ，lcm（a，b）= 20449。且有x = 58，y = -81 时，ax + by = gcd(a,b) 成立。结果正确 （4）a =46480 ，b = 39423 时，gcd（a，b）= 1 ，lcm（a，b）= 1832381040。且有x = 16720，y = -19713 时，ax + by = gcd(a,b) 成立。结果正确 （5）a =737 ，b = 635 时，gcd（a，b）= 1 ，lcm（a，b）= 467995。且有x = 193，y = -224 时，ax + by = gcd(a,b) 成立。结果正确 （6） （7）（8） （9）（9）（10）（11）4 思考题（