数论入门

单向函数和单向陷阱门函数

单向函数

函数f 若满足下列条件, 则称f 为单向函数:

  • 对于所有属于f 域的任一x, 容易计算y= f(x)
  • 对于几乎所有属于f 域的任一y, 求得x, 使y= f(x), 在计算上不可行。

离散对数问题

因数分解问题

背包问题

单向陷阱门函数

“可逆”函数F若满足下列二条件, 则称F为单向陷井门函数:

  • 对于所有属于F域的任一x, 容易计算F(x)=y;
  • 对于几乎所有属于F域的任一y, 除非获得暗门信息(trapdoor), 否则求出x, 使得 x = F-1(y)在计算上不可行, F-1为F之逆函数; 如有额外信息(暗门), 则容易求出x = F-1(y)。

费马定理

若p是素数,a是正整数且不能被p整除,则$a^{p-1}mod \ p = 1$。

等价形式

$a^p \equiv a \ mod \ p$,p是素数。

证明

因为{a mod p, 2a mod p, …, (p-1)a mod p}是{1, 2, …, (p-1)}的置换形, 所以, (ax2ax … x (p-1)a)≡(1x2x … x(p-1)) (mod p)≡ (p-1)! mod p.
但是, ax2ax…x(p-1)a=(p-1)!ap-1, 因此(p-1)!ap-1≡(p-1)! mod p, 两边去掉(p-1)!, 即得ap-1mod p = 1.

证明置换形

用a乘以集合中所有元素并对p取模,则得到集合
X={a mod p,2a mod p,…, (p-1)a mod p}。因为p不能整除a,
所以X的元素都不等于0,而且各元素互不相等。
假设ja ≡ ka(mod p),其中1≤j<k≤p-1,因为a和p互素,所以两边可
以把a消去,则推出j ≡ k(mod p),而这是不可能的。
因此X的p-1个元素都是正整数且互不相等。所以说X和
{1,2,…,p-1}构成相同,只是元素顺序不同。

欧拉定理

欧拉函数

$\phi(n)$是比n小且与n互素的正整数个数。

p和q是素数,$n = p*q$,$\phi(n) = \phi(p)\phi(q) = (p-1)(q-1)$。

显然对于素数p,$\phi(n) = p-1$。

欧拉定理

对于任意互素的a和n有:

$$\begin{gather}
a^{\phi(n)} \equiv 1 (mod \ n) \
a^{\phi(n)+1} \equiv a (mod \ n)
\end{gather}
$$

证明

(1)若 n 是素数,根据$\phi(n) = p-1$和费马小定理,則上式成立;
若p是素数, a是正整数且不能被p整除, 则$a^{p-1} \pmod p=1$

(2)所有小于 n ,且与 n 互质的正整数的集合 有个公式

即每一个元素都有gcd(xi,n)=1。用a与R中的每个元素模n相乘:有个公式

S是R的一个排列,因为
(1) a与n互素,且xi与n互素,所以axi必与n互素,这样S中所有元素均小于n且与n互素。
(2) S中没有重复元素,所以集合S是集合R的一个置换。

有个公式

中国剩余定理

中国余数定理CRT说明某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构

Z10(0,1,…,9)中的10个整数可通过它们对2和5(10的素因子)取模所得的两个余数来重构. 假设数x的余数r2=0 且r5=3, 即x mod 2=0, x mod 5=3, 则x是Z10中的偶数且被5除余3, 唯一解x=8.

一种CRT的表示形式

令M= mi, 其中mi两两互素, 1<=i, j<=k, i≠j, gcd(mi, mj)=1
将Zm中的任一整数对应一个k元组, 该k元组的元素均在Zmi中, 对应关系为A↔(a1,a2,…,ak), 其中A∈Zm, 对1<=i<=k, ai∈Zmi, 且ai = A mod mi

有个公式
断言一
对任何A,0≤A≤M,有唯一的k元组(a1,a2,…,ak)与之对应,
其中0≤ai<mi,并且对任何这样的k元组(a1,a2,…,ak),ZM中
有唯一的A与之对应。

由A到(a1,a2,…,ak)的转换显然是唯一确定的。即只需取
ai = A mod mi 。对给定的(a1,a2,…,ak),可如下计算A。
有个公式

第二个断言与算术运算有关,可从模算术规则推出
有个公式

令d1,…,dt两两互素, n=d1d2…dt, 则
x mod di=xi, i=1,…,t 在[0, n-1]中有一个公共解x.
证明:对每一个I, i=1,…,t, gcd(di, )=1, 存在yi, 使得
( )yi mod di=1;
进一步地, ( )yi mod dj=0, j≠i, (因为dj是( )的一个因数)
令x=[ ( )yi xi] mod n.
∵ x mod di = ( )yixi mod di = xi, (( )yi mod di =1)
∴ x是x mod di=xi (1≤i≤t)的公共解。

孙子算经

今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何。
x mod 3=2 n=357=105
x mod 5=3 d1=3, d2=5, d3=7
x mod 7=2 x1=2, x2=3, x3=2