22-11-15-Math

Posted on Edited on In Symbols count in article: 2.4k Reading time ≈ 2 mins.

Some import theorems which are suitable for applying to Cryptography.

At the same time, the post which is made as the record to note me that how to improve or deduction.

Fermat’s little theorem

Let $p$ be a prime number, and $a$ be any integer. Then $a^{p} - a$ is always divisible by $p$.

And we can write as:
$$
a^{p} \equiv a \mod p
$$
Make a deduction, we can get that:
$$
a^{p-1} \equiv 1 \mod p
$$

Euler’s criterion

If the modulo $p$ is a odd prime and is prime to $a$, we can get $a^{p-1}\equiv 1 \mod p$ by using the fermat’s little theorem.

We define that $p = 2q + 1$， and we will get $a^{2q} \equiv 1 \mod p$:
$$
\Longrightarrow (a^{2q} - 1) \times (2^{2q} + 1) \equiv 0 \mod p
$$
So the $a^q \equiv \pm 1 \mod p$，means that $a^{\frac{p-1}{2}} \equiv \pm 1 \mod p$.

In fact, we have the equation which is called euler’s criterion.
$$
(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \mod p
$$

Groups and Abelian group

Usually needs to satisfy the qualities below.

首先说下群论的基础。代数中的群简单来说就是一组元素集合和定义在元素上的运算。比如说全体整数构成了一个群，运算包括加法等。这里的集合用 G（group）表示，集合要变成群，一般要满足以下性质：

  1. 封闭性：如果 $a$ 和 $b$ 都属于 $G$ 集合，那么 $a+b$ 也属于$G$;
  2. 结合律：$(a+b)+c=a+(b+c)$
  3. 存在单位元（在二元运算中，单位元指与任意元素运算不改变其值的元素，以实数为例，乘法单位元为1，加法单位元为0）$O$ 使得$a+O=O+a=a$ ;

4.每个元素都存在逆元素，就是说对于任意元素 $a$ 必存在 $b$ 使得 $a+b=O$ ($O$是单位元) 。

集合满足以上四个性质就是称为群，还有一些特殊的群，如阿贝尔群（Abelian Group）除了满足群的基本性质，还满足交换律即：
$$
a+b=b+a
$$
故阿贝尔群又称交换群。根据这些性质，我们可以知道整数集Z是一个阿贝尔群，自然数集N却并不是一个群，因为它不满足第四条性质。

Elliptic Curve Group

椭圆曲线上的群元素是椭圆曲线上的点 单位元是无穷远点记为 $O$

任意点 $P$ 的逆是该点关于 $x$ 轴对称点。

椭圆曲线群的加法也不同于整数的加法，它的加法定义可以描述为：

给定三个共线非零的点 $P$ ，$Q$，$R$ ，它们的和为 $P+Q+R=O$。

几何意义

过 $𝑃$ 、$𝑄$ 两点做直线 $𝐿$，与椭圆曲线相交于第三点，该点关于 $x$ 轴的对称点即是所求的 $𝑅$ 点。椭圆曲线的这种加法运算有比较明确的几何含义。

异常情况

  1. $𝑂+𝑂=𝑂$，对任意的 $𝑃$，有 $𝑃+𝑂=𝑃$ ；$𝑂$看做零点
  2. $𝑃=(𝑥,𝑦)$ 的负元是关于 $x$ 中对称的点 $−𝑃=(𝑥,−𝑦)$（而不是关于原点对称），$𝑃+(−𝑃)=𝑂$，可以看做 $P$ 与 $-P$ 连线与椭圆曲线相交于无穷远点
  3. 计算 $𝑃$ 点（$𝑃≠𝑂$）的两倍时，是做该点的切线，再取切线与椭圆曲线交点 $𝑆$ 关于 $x$ 轴的对称点$−𝑆$，也即是 $2𝑃=𝑃+𝑃=−𝑆$ ，得出2倍值可以递推到若干倍。

可以看出，椭圆曲线的点集（包含无穷远点$O$）和上述定义的加法运算构成了一个阿贝尔群：
单位元是 $𝑂$ 点，$𝑃(𝑥,𝑦)$ 的逆元是 $𝑃(𝑥,−𝑦)$ ，封闭性，结合性以及交换性也是显然满足的。

椭圆曲线代数计算

几何解释主要方便理解椭圆曲线的加法意义，代数便于计算。过曲线 $P(x_p, y_p)$以及 $Q(x_q, y_q)$两点（*$P$ 与 $Q$ 不互为负元*）做直线，求第三个交点很容易用代数求解出来。
$$
y^2 = x_3 + ax + b \tag{1}
$$

$$
y - y_p = k(x - x_p) \tag{2}
$$

于是斜率为$k = \frac{y_q - y_p}{x_q - x_p}$（ $P$ 与 $Q$ 不同点）/ $k = \frac{3x_{q}^2 + a}{3y_p}$（ $P$ 与 $Q$ 相同点） 。

将$(2)$代入$(1)$再利用次数对齐的方法从而求得第三个交点的对称点，也就是$P,Q$之和$R(x_r, y_r)$为：
$$
x_r = k^2 - x_p - x_q
$$

$$
y_r = -y_p + k(x_p - x_r)
$$

如果 $P = Q$，则两者相加为倍乘运算。例如 $P+P = 2P = R$。
$$
x_r = ((3x_p^{2} + a)/2y_p)^2 - 2x_p
$$

$$
y_r = ((3x_p^{2} + a)/2y_p)(x_p - x_r) - y_p
$$

-------------THE END-------------