模算數
模算數或稱同餘運算（）是一個整数的算术系統，其中數字超過一定值後（稱為模或餘數）後會「捲回」到較小的數值，模算數最早是出現在卡爾·弗里德里希·高斯在1801年出版的《算术研究》一書中。 模算數常見的應用是在十二小時制，將一天分為二個以十二小時計算的單位。假設現在七點，八小時後會是三點。用一般的算術加法，會得到，但在十二小時制中，超過十二小時會歸零，不存在「十五點」。類似的情形，若時鐘目前是十二時，二十一小時後會是九點，而不是三十三點。小…
标签：#同余
共 31 篇文章
中国剩余定理
中國剩餘定理，又稱孫子定理或中國餘數定理，是数论中的一個关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。该定理在中国古代也被称为「韓信點兵」、「求一术」（宋 沈括）、「鬼谷算」（宋 周密）、「隔-{zh-cn:墻;zh-tw:牆;}-算」（宋 周密）、「剪管術」（宋 杨辉）、「秦王暗點兵」、「物不知數」等。 物不知数 一元线性同余方程组问题最早可见于中國南北朝时期（公元5世纪）的数学著作《孫子算經》卷下第二…
同餘
同余（，符號：≡）在数学中是指數論中的一種等價關係。當两个整数除以同一个正整数，若得相同餘數;}-，则二整数同余。同餘是抽象代數中的同餘關係的原型。最先引用同余的概念与「≡」符号者为德國数学家高斯。 定義 對某兩個整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，也就是嚴格來說，存在整數k使得 : a-b = km 則稱a,\,b對於除數m是同餘的。一般記做 : a \equiv b \pmod{m} 比如 : 26…
同餘關係
在数学特别是抽象代数中，同餘关系或简称同餘是相容于某个代数运算的等价关系。 模算术 元型例子是模算术：对于一个正整数n，如果a − b整除于n（还有一个等价的条件是它们除以n得出同样的餘数），则两个整数a和b被称为*同餘模n*。 例如，5和11同餘模3： :11 ≡ 5 (mod 3) 因为11 − 5得出6，它整除于3。或者等价的说，这两个数除以3得到相同的餘数： :11 = 3×3 + 2 :5 = 1×3 + 2 如果a_1 \e…
费马小定理
费马小定理（）是数论中的一个定理。假如a是一个整数，p是一个質数，那么a^p - a 是p的倍数，可以表示为 :a^p \equiv a \pmod{p} 如果a不是p的倍数，這個定理也可以寫成更加常用的一種形式 :a^{p-1} \equiv 1 \pmod{p} 註：如果a是p的倍数，則 :a^{p-1} \equiv 0 \pmod{p} 費馬小定理的逆敘述不成立，即假如a^p - a 是p的倍数，p不一定是一个質数。例如2^{3…
整数模n乘法群
在同余理论中，模 n 的互质同余类组成一个乘法群，称为整数模 n 乘法群，也称为模 n 既约剩余类。在环理论中，一个抽象代数的分支，也称这个群为整数模 n 的环的单位群（单位是指乘法可逆元）。 这个群是数论的基石，在密码学、整数分解和 質數測試}-均有运用。例如，关于这个群的阶（即群的“大小”），我们可以确定如果 n 是质数当且仅当阶数为 n-1。 群公理 容易验证模 n 互质同余类在乘法运算下满足阿贝尔群的公理。 :互质同余类的乘法是…
吠陀方形
NOTOC 吠陀方形（Vedic square）屬於古印度數學，是9 × 9 乘法表的變形，每個數字都用乘積的數根來代替。換句話說，與乘積除以9以後的余数的概念接近，若是該乘積為9的倍數，其數根為9不為0。 吠陀方形中有許多幾何模式及對稱特性，其中有些模式會出現在傳統的伊斯蘭藝術。]] 代數性質 吠陀方形可以視為是幺半群((\mathbb{Z}/9\mathbb{Z})^{\times}, \{1, \circ\})的乘法表，其中\ma…
高斯引理
在数论中，高斯引理给出了一个整数是模另一个整数的二次剩余的条件。尽管高斯引理没有实际计算上的意义，但作为二次互反律的证明中的一环，高斯引理有着理论上的重要性。 高斯引理最早出现在高斯1808年发表的二次互反律的第三个证明中，并在第五个证明中再次用到。 叙述 设p为奇质数，a是一个与p互质的整数。考虑以下数组：a, 2a, 3a, \dots, \frac{p-1}{2}a, 取它们模p的最小非负剩余。这些剩余两两不等，因此我们共有\fr…
模除
(q) 和 餘數 (r) 作為被除數 (a) 的函數時的圖像。左侧是除数为正的情况，右侧除数为负。从上至下分别使用了：向零取整、向下取整和欧几里得除法。]] 模除（），又稱模算術、取模、取模運算等，它得出一个数除以另一个数的余数。给定两个正数：被除数 a 和除数 n (有时也称作模數，英文寫作modulus)，a \,\operatorname{modulo}\, n（通常缩写为a \bmod n），得到的是使用欧几里得除法时的余数。a…
雅可比符号
在数论中，雅可比符号是勒让德符号的一种推广，首先由普鲁士数学家卡尔·雅可比在1837年引进。雅可比符号在数论中的各个分支中都有应用，尤其是在计算数论的素性检验、大数分解以及密码学中有重要作用。 定义 勒让德符号(\tfrac{a}{p})是对于所有的正整数 a 和所有的素数 p 定义的。 : :. :； :. :. 当(\frac{a}{p})= 1 时，稱a 是模p的二次剩餘；当(\frac{a}{p})=- 1 时，稱a 是模p的二…
模幂
模幂（）是一种对模进行的冪运算，在计算机科学，尤其是公开密钥加密方面有一定用途。 模幂运算是指求整数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…
卡邁克爾函數
卡邁克爾函数\lambda(n)满足a^{\lambda(n)}\equiv 1\pmod{n}，其中a与n互质。 定义 当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当n为2,4以外的2的次幂时为它的一半。 \lambda(n) = \begin{cases} \varphi(n) & n=1,2,3,4,5,6,7,9,10,11,13,14,17,19,22,23,25,26,27,29\dots\\ \dfra…
線性同餘方法
線性同餘方法（LCG）是個產生偽隨機數的方法。 它是根據以下的遞迴關係式： : N_{j+1} \equiv (A \times N_j + B ) \pmod{M} 其中A,B,M是產生器設定的常數。 LCG的週期最大為M，但大部分情況都會少於M。要令LCG達到最大週期，應符合以下條件： B,M互質； M的所有質因數都能整除A-1； 若M是4的倍數，A-1也是； A,B,N_0都比M小； A,B是正整數。 随机性 因为通过线性同余方法…
二次互反律
在数论中，特别是在同余理论里，二次互反律（Law of Quadratic Reciprocity）是一个用于判别二次剩余，即二次同余方程x^2 \equiv p \pmod q 之整数解的存在性的定律。二次互反律揭示了方程x^2 \equiv p \pmod q 可解和 x^2 \equiv q \pmod p 可解的简单关系。运用二次互反律可以将模数较大的二次剩余判别问题转为模数较小的判别问题，并最后归结为较少的几个情况，从而在实际…
高次剩餘
數論中，模正整數m的n次剩餘（n為正整數），即某整數X的n次方數X^n除以m的餘數。以下討論m是奇質數p，且餘數d不為零的情況。 給定d，若對某個X，有X^n \equiv d \pmod{p}成立時，則稱d為模p的n次剩餘（）。 否則，對任意X，都有X^n \not\equiv d \pmod{p}，此時稱d為模p的n次非剩餘（）。 n次剩餘有類似於二次剩餘歐拉判別法的判別法如下： 若p是奇質數，p不能整除d，且n|p-1（即n能整除…
置换同余生成器
置换同余生成器，简称PCG（）是一个用于产生伪随机数的算法，开发于2014年。该算法在线性同余生成器（LCG）的基础上增加了输出置换函数（output permutation function），以此优化LCG算法的统计性能。因此，PCG算法在拥有出色的统计性能的同时，也拥有LCG算法代码小、速度快、状态小的特性。 置换同余生成器（PCG）和线性同余生成器（LCG）的差别有三点，在于： LCG的模数以及状态大小比较大，状态大小一般为输出…
蔡勒公式
蔡勒公式（），是一種計算任何一日屬一星期中哪一日的演算法，由十九世紀德國數學家推算出來。 公式 : w = \left(y+\left[\frac {y}{4}\right] + \left[\frac {c}{4}\right] - 2c + \left[\frac{26(m+1)} {10}\right] + d-1 \right) \bmod 7 or : w = \left(y+\left[\frac {y}{4}\right]…
欧拉函数
{{Otheruses|subject=小於等於n的正整數中與n互質的數的數目|other=形式為\phi(q)=\prod_{k=1}^\infty (1-q^k)的函數|歐拉函數 (複變函數)}} 在數論中，對正整數n，歐拉函數\varphi(n)是小於等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數（由高斯所命名）或是歐拉總計函數（totient function，由西爾維斯特所命名）。 例如，因為…
离散对数
在整數中，離散對數（）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 \log_b a 是指對於給定的 a 和 b，有一個數 x，使得b^x=a。相同地在任何群 G中可為所有整數 k 定義一個冪數為 b^k，而離散對數 \log_b a 是指使得 b^k=a 的整數 k 。 離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細選擇…
费马素性检验
费马素性检验是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。 概念 根据费马小定理：如果 p 是素数，1 \le a \le p-1，那么 :a^{p-1} \equiv 1 \pmod{p}。 如果我们想知道 n 是否是素数，我们在中间选取 a，看看上面等式是否成立。如果对于数值 a 等式不成立，那么 n 是合数。如果有很多的a能够使等式成立，那么我们可以说 n 可能是素数，或者伪素数。 在我们检验过程中，有可能我们…