數論
===
###### tags: `Algorithm` `Todo`
* a|x a 是因數
## 費馬小定理(唬爛法)
* a^p-1=1

#define _for(i,a,b) for(int i=(a);i<(b);i++)
#include <iostream>
#include <random>
using namespace std;

long long power(long long a, long long n,long long m)//  power(a, n) 表示詢問 a^n
{
	long long tmp = a,ans = 1;
	while (n) {
		if (n&1) {
			ans = tmp*ans%m;
		}
		n /= 2;
		tmp = tmp*tmp%m;
	}
	return ans;
}

mt19937 mt(123);


int main() {

	long long p; while (cin>>p)
	{
		bool isPrime = true;
		_for (i, 0, 5) {
			if (power(mt()%(p-1)+1, p - 1,p) != 1) isPrime = false;
		}
		if (isPrime) cout << "質數\n";
		else cout << "非質數"<<"\n";

	}
	return 0;
}

## 米勒拉賓測試
滿足x^ 2 ≡ 1(mod p) 的 x(x<p) 值 只能等於 1 或 p-1
把所有結果為 1 的 x 拿出來 ,看他們 是不是等於 p - 1 或 1

能通過費馬測試的p, a^p-1≡ 1,p-1 為偶數(2特判)
何一個偶數 都可以寫成 $2^{r}*d$的形式 比如 6 可以寫成 2^1 * 3

所以 p-1 也可以寫成 $2^{r}*d$

那麼 $a^{p-1}$ 就等於 $a^{2^{r}*d}$ 也就可以寫成 $(a^{d})^{2^{r}}$

那麼式子就變成了 $(a^{d})^{2^{r}}\equiv 1$（mod p）（mod p）

我們把 $a^{d}$ 看作 k 那麼式子就是 $(k)^{2^{r}} \equiv 1$（mod p）

>[ref1](https://www.itread01.com/content/1545750663.html

## 因數問題
* random(唬爛法)
* 生日攻擊
* Plllard's p Algorithm
* Floyd 判環法
* Brent 判環法
* 

## 歐拉函數

1. 如果n=1，則φ(1) = 1 。因為1與任何數（包括自身）都構成互質關係。

2. 如果n是質數，則φ(n)=n-1

3. 如果 n = p^k (p為質數,k>=1,k∈Z)，則


這是因為只有當一個數不包含質數p，才可能與n互質。
而包含質數p的數一共有 `p^(k-1)`個，即`1×p、2×p、3×p、...、p^(k-1)×p`，把它們去除，
剩下的就是與n互質的數。

上面的式子還可以寫成下面的形式：


可以看出，上面的第二種情況是k=1 時的特例。

4. 如果n可以分解成兩個互質的整數之積

$n = p1 × p2$

則

$φ(n) = φ(p1p2) = φ(p1)φ(p2)$

5. **歐拉函數通用計算公式**

因為任意一個大於1的正整數，都可以寫成一系列質數的積。

根據第4條的結論，得到

再根據第3條的結論，得到


也就等於


這就是歐拉函數的通用計算公式。比如，1323的歐拉函數，計算過程如下：


欧拉函数公式：euler(x) = x*(1-1/p1)(1-1/p2)……(1-1/pn),p为x的质因数。用公式法求解代码

 int euler(int n){    
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++){  
         if(a%i==0){  
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出   
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
}  

打表求法，用的比较多

void Euler()
{
     euler[1]=1;  
     for(int i=2;i<MAX;i++)  
       euler[i]=i;  
     for(int i=2;i<MAX;i++)  
        if(euler[i]==i)  
           for(int j=i;j<MAX;j+=i)  
              euler[j]=euler[j]/i*(i-1);
}

> 作者：oliver233
来源：CSDN
原文：https://blog.csdn.net/oliver233/article/details/70990869
版权声明：本文为博主原创文章，转载请附上博文链接！
>[ref](https://www.kancloud.cn/kancloud/rsa_algorithm/48486)

## 歐拉定理

## 歐拉降冪法
a^b%p=a^(b%phi(p)+phi(p))%p

# 計算幾何
向量

>
>
判斷點有沒有在直線上下:叉積=0