BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Tiếp tục chứng minh một số rất lớn là số nguyên tố
- 10 giờ trước
- 57 lượt xem
| Việc chứng minh một số rất lớn là số nguyên tố không nhằm mục đích dạy học sinh thông thường, chỉ nên trao đổi trong đội tuyển HSG MTCT. Riêng GV phụ trách đội tuyển nên tự mình thực hiện điều này để biên soạn những bài tập phù hợp cho học sinh đội tuyển. Trong bài này ta chứng minh số $500000003$ là số nguyên tố. Bài toán này ta không sử dụng được định lý Pocklington. |
Tiêu chuẩn Miller-Rabin kiểm tra $n$ là số nguyên tố.
| BƯỚC 1: Phân rã cấu trúc của $(n – 1)$.
Phân tích $n-1=2^s\times d$ với $d$ là số tự nhiên lẻ. BƯỚC 2: Tiêu chuẩn Miller-Rabin. Với mỗi cơ số $a$ được chọn (thỏa mãn $1 < a < n-1$), số $n$ sẽ vượt qua phép thử Miller-Rabin nếu nó thỏa mãn một trong hai điều kiện đồng dư sau đây: Nếu $s=1$ thì $r=0$, điều kiện 2 trở thành $a^d \equiv -1 \quad (\text{mod}\ n)$. |
BƯỚC 1: Phân rã $500000003-1=2\times 250000001$, $s=1$ và $d=250000001$ là số lẻ.
BƯỚC 2: Với $a=2$. Ta kiểm tra $2^{250000001} \equiv \pm 1 \quad (\text{mod}\ 500000003) $ ?
.
Vậy $250000001=\underbrace{2^0+2^7+2^9+2^{12}+2^{13}+2^{15}}_{\text{hết hàng dưới}}+2^{17}+2^{18}+2^{21}+2^{22}+2^{23}+2^{25}+2^{26}+2^{27}.$
Suy ra $2^{250000001}=2^{2^0}\times 2^{2^7}\times 2^{2^9}\times 2^{2^{12}}\times 2^{2^{13}}\times 2^{2^{15}}\times 2^{2^{17}}\times 2^{2^{18}}\times 2^{2^{21}}\times 2^{2^{22}}\times 2^{2^{23}}\times 2^{2^{25}}\times 2^{2^{26}}\times 2^{2^{27}}.$
(Vì $2^{2^0}=2$ được tính riêng để tận dụng $2^{2^m}$ cho dòng thứ $m$).
Từ $A_2$ đến $A_{27}$ điền công thức $A_1^2- \text{Int}\dfrac{A_1^2}{A}$ 
.
Copy các giá trị phủ hợp của tích sang cột B, bắt đầu là $B_1$ nhập số $2^{2^0}$ và $B_{14}$ nhập $=A_{27}$. 
Sau đó tính tích luỹ tiến: 
.
Tại $C_{14}$ kết quả $500.000.002$, nghĩa là $2^{250000001} \equiv -1 \quad (\text{mod}\ 500.000.003)$, đáp ứng Điều kiện (2).
vậy số $500.000.003$ vượt qua được phép thử Miller-Rabin với cơ số $a=2$. Bây giờ ta xét cơ số $a=3$, rất may chỉ cần thay số $4=2^{2^1}$ ở $A_1$ bằng số $9=3^{2^1}$ và số $2=2^{2^0}$ ở $B_1$ thành $3=3^{2^0}$ và chọn Recalculate, kết quả 
.
Vậy $3^{250000001}\equiv 1 \quad (\text{mod}\ 500.000.003)$. Số $500.000.003$ vượt qua được phép thử Miller-Rabin với cơ số $a=3$.
Theo phép thử Rabin-Miller với các số có 9 chữ số ta kết luận $500.000.003$ là số nguyên tố.
About TS. Nguyễn Thái Sơn
