輾轉相除法
長分别可表示252和105，則其中每一小分段長代表最大公因數21。如动画所示，只要輾轉地从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公因数。]] 辗转相除法，又称欧几里得算法（），是在數學中求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法…
标签：#数论算法
共 5 篇文章
模幂
模幂（）是一种对模进行的冪运算，在计算机科学，尤其是公开密钥加密方面有一定用途。 模幂运算是指求整数b的e次方b^e被正整数m所除得到的余数c的过程，可用数学符号表示为c=b^e \bmod m。由c的定义可得0\leq c 。 例如，给定b=5，e=3和m=13，5^3=125被13除得的余数c=8。 指数e为负数时可使用扩展欧几里得算法找到b模除m的模逆元d来执行模幂运算，即： : c=b^e \bmod m=d^{-e} \bmo…
整方根函数
整方根函数（），是指函数值为不大于自变量a的算术平方根的最大整数，定义域为自然数，符号表示为\lfloor\sqrt{a}\rfloor。 定义 整方根函数\lfloor\sqrt{a}\rfloor用原始递归函数可定义为： 参考资料
扩展欧几里得算法
扩展欧几里得算法（）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式ax + by = \gcd(a, b)。如果a是负数，可以把问题转化成\left | a \right |(-x) + by = \gcd(|a|, b)（\left | a \right |为a的绝对值），然后令x'=(-x)。 在欧几里得算法中，我们…
离散对数的波拉德ρ算法
离散对数的波拉德ρ算法是1978年所发明解决离散对数问题的算法。 算法的目标是求 \gamma 使得 \alpha ^ \gamma = \beta，其中 \beta 属于一个由 \alpha 生成的 循环群 G。该算法寻找 a, b, A, B 使得 \alpha^a \beta^b = \alpha^A \beta^B。若他们基于的群是一个 n 阶的循环群，则 \gamma 是方程 (B-b)\gamma = (a-A) \pmod…