# Kiểm tra Rabin-Miller
---
**Tác giả : [Dương Nguyên Khánh](https://github.com/kduongnguyen07)**
###### tags:`Algorithm`,`Prime`
# **Mở đầu**
### Khái niệm
Một cách để kiểm tra số nguyên tố([Xem thêm về số nguyên tố](https://hackmd.io/wOyf7-orRlWHUfksG3h0RA))
#### Ý tưởng
Đây là một thuật toán khá là phức tạp ([Bấm vào đây để tìm hiểu thêm](https://vi.wikipedia.org/wiki/Ki%E1%BB%83m_tra_Miller-Rabin))
Một cách tổng quát thì thuật toán này chưa được chứng minh là đúng. Tính đúng đắn của nó phụ thuộc vào giả thuyết Reimann.
Tuy nhiên, với n nhỏ (n<3,317,044,064,679,887,385,961,981) thì thuật toán đã được kiểm tra và chứng minh là đúng. Ngoài ra, ta cũng không cần kiểm tra hết tất các các số nguyên a như ở trên, mà chỉ cần dùng một vài số là đủ.
[Minh hoạ](https://www.cs.usfca.edu/~galles/visualization/Search.html)
##### Cài đặt

#include <bits/stdc++.h>
using namespace std;
int power(int x, unsigned int y, int p)
{
	int res = 1;
	x = x % p; 
	while (y > 0)
	{
		if (y & 1)
			res = (res*x) % p;

		// y must be even now
		y = y>>1; // y = y/2
		x = (x*x) % p;
	}
	return res;
}
bool miillerTest(int d, int n)
{
	int a = 2 + rand() % (n - 4);
	int x = power(a, d, n);
	if (x == 1 || x == n-1)
	return true;
	while (d != n-1)
	{
		x = (x * x) % n;
		d *= 2;

		if (x == 1)	 return false;
		if (x == n-1) return true;
	}
	return false;
}
bool isPrime(int n, int k)
{
	if (n <= 1 || n == 4) return false;
	if (n <= 3) return true;
	int d = n - 1;
	while (d % 2 == 0)
		d /= 2;
	// kiểm tra lần 
	for (int i = 0; i < k; i++)
		if (!miillerTest(d, n))
			return false;

	return true;
}
int main()
{
	int k = 4; // Số k càng lớn độ chính xác càng cao đi kèm với thời gian
	for (int n = 1; n < 100; n++)
	if (isPrime(n, k))
		cout << n << " ";
	return 0;
}

Nhận xét : Độ chính xác còn chưa tuyệt đối và khá khó cài đặt và chỉ nên áp dụng 1 số bài