卢恩算法
卢恩算法（），也称为“模10”（Mod 10）算法，是一种简单的校验和算法，一般用于验证身份识别码，例如发卡行识别码、国际移动设备识别码，美国号码，或是。该算法由IBM科学家创造，专利于1954年1月6日申请，1960年8月23日颁证，美国专利号2950048。 该算法现已属于公有领域并得到了广泛的应用，例如ISO/IEC 7812-1。它不是一种安全的加密哈希函数，设计它的目的只是防止意外出错而不是恶意攻击。 描述 卢恩算法会通过校验…
标签：#同余
共 31 篇文章
原根
原根（）是一个在数论中的重要概念，特别是整除理论。 對於两个正整数\gcd(a,m)=1，由欧拉定理可知，存在正整数d \le m-1， 比如说欧拉函数d= \varphi (m)，即小于等于m的正整数中与m互質的正整数的个数，使得a^d \equiv 1 \pmod{m} 。 由此，在\gcd(a,m)=1時，定義a对模m的指数\delta_m(a)為使a^d \equiv 1 \pmod{m}成立的最小的正整数d。由前知 \delt…
亨泽尔引理
亨泽尔引理（）是数学中模算术的一個结论。亨泽尔引理说明，如果一个模（是给定的质数）的多项式方程有一个单根，则可以通过这个根求出该方程在模的更高次方时的根。在完备交换环（包括p进数）中，亨泽尔引理被看作是类似于牛顿法的渐进求根方法。由于p进数分析在某些方面比实分析更加简单，亨泽尔引理可以加强为多项式方程有根的判定方法。 定理内容 設f(x)為整係數多項式，k為不少於2的整數，p為質數。若整數r是下面同餘式的根： : f(r) \equiv…
卡邁克爾數
在數論上，卡邁克爾數（）是正合成數n，且使得對於所有跟n互質的整數b，b^{n-1} \equiv 1 \pmod{n}。 概觀 費馬小定理說明所有質數都有這個性質。在這方面，卡邁克爾數和質數十分相似，所以它們稱為偽質數。 因為這些數的存在，使得费马素性检验變得不可靠。不過，它仍可用於證明一個數是合數。另一方面，隨着數越來越大，卡邁克爾數變得越來越少，1至10^{17}有585 355個卡邁克爾數。 卡邁克爾數的一個等價的定義在Kors…
欧拉定理 (数论)
在数论中，欧拉定理（也称费马-欧拉定理或欧拉{\varphi}函数定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a 互質}-（即\gcd(a,n)=1），则 a^{\varphi(n)} \equiv 1 \pmod n 即a^{\varphi(n)}与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。 欧拉定理实际上是费马小定理的推广。 例子 首先看一个基本的例子。令a = 3，n = 5…
模反元素
模逆元（Modular multiplicative inverse）也称为模倒数、数论倒数。 一整数a對同餘n之模反元素是指滿足以下公式的整數b :a^{-1} \equiv b \pmod{n}. 也可以寫成 :ab \equiv 1 \pmod{n}. 或者 :ab \mod{n} = 1 整数a對模数n之模反元素存在的充分必要條件是a和n互質，若此模反元素存在，在模数n下的除法可以用和對應模反元素的乘法來達成，此概念和實數除法的…
欧拉准则
在数论中，二次剩余的歐拉判別法（又稱歐拉準則）是用来判定给定的整数是否是一个质数的二次剩余。 叙述 若p是奇質數且p不能整除d，則： : d是模p的二次剩余当且仅当： :: d^{ \frac{p-1}{2}} \equiv 1 \pmod{p} : d是模p的非二次剩余当且仅当： :: d^{ \frac{p-1}{2}} \equiv -1 \pmod{p} 以勒让德符号表示，即為： d^{ \frac{p-1}{2}} \equi…
平方同餘
在數論中，平方同餘是個經常被用於整數分解演算法的同餘關係。 由來 給定一正整數 n，費馬因式分解法想找到兩數 x, y 滿足下列方程式： : x^2-y^2=n 從上式我們便可以分解得 n = x2 - y2 = (x + y)(x - y)。 此演算法在實際用途上較慢因為我們需要試圖找出許多類似的數字，而只有一部分會滿足這個嚴格的式子。 然而， n 也可能可以被分解，如果我們能滿足以下較弱的平方同餘的情況： : x^2 \equiv …
三次互反律
在数学中，三次互反律是关于模代数中两个对应的三次方程的可解性之间的关系的结论和定理。 相关术语 三次互反律最常使用艾森斯坦整数进行表述。艾森斯坦整数是指由形如 a + b\,\omega 的复数组成的环，记作 \mathbb{E}。其中 a 和 b 是整数，\omega 为三次单位根： :\omega = \frac{1}{2}(-1 + i\sqrt 3) = e^{2\pi i/3} 定理 如果 \pi 是\mathbb{E}中范数…
线性同余方程
在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如： :ax \equiv b \ \pmod{n} \ \ \ \ (1) 的方程。此方程有解当且仅当b能够被a与n的最大公约数整除（记作\gcd(a,n)|b）。这时，如果x_0是方程的一个解，那么所有的解可以表示为： :\{x_0+k\frac{n}{d}\mid k\in\mathbb{Z}\}. 其中d是a与n的最大公约数。在模n的完全剩余系\{…
威尔逊定理
威尔逊定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的，尽管这对师生都未能给出证明。华林于1770年提出该定理，1771年由拉格朗日首次证明。 在初等数论中，威尔逊定理给出了判定一个自然数是否为質數的充分必要条件。即：当且仅当p为質數时： :(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p) 证明 充分性 如果 p 不是質數，那么它的正因数必然包含在整数 2,3,4,\cdots,p-1 中，因此 \gcd(…