Tháng 03/2008 - Suy nghĩ về số nguyên tố

Đặc trưng của số nguyên tố

Số nguyên tố là một con số kỳ diệuĐã có rất nhiều người bị cuốn hút bởi sự quyến rũ của số nguyên tố và họ đã để lại nhiều thành quả nghiên cứu trong giới giới toán học.

Chi tiết các hoạt động của từng người thì chẳng hạn sẽ được giới thiệu ở 2 cuốn sách [1, 2] .

Số nguyên tố (p) , là số chỉ có thể chia hết cho ước số hiển nhiên là「1 và chính nó（p）」.

Là số không có "Ước số thực" - là ước số khác với ước số hiển nhiên , và không có dạng của hệ số mà khác với p = 1 × p .

Hay nói cách khác, là số không thể biểu thị được bằng tích của số nhỏ hơn chính nó (P), trong khi đó nó là số cơ sở để kết hợp với số nguyên tố khác để tạo ra bất kỳ số nào khác.

Với điểm này, nó là con số đại diện cho ý nghĩa của khẩu hiệu "No.1 & the Only One" của Học viện Máy tính Kyoto và Trường Sau Đại học Công nghệ Thông tin Kyoto.

Chỉ có thể chia hết cho chính nó tượng trưng cho ý nghĩa là “the Only One”".

Ngoài ra với đặc điểm là số đứng đầu tiên trong nhóm các số là tích của {Số nguyên tố P và số nguyên tố lớn hơn P}, cho nên nó là số “No.1”.

Ví dụ, số nguyên tố p=41, thì chỉ có thể chia hết cho 41, và nó là số đứng đầu trong nhóm số {41, 41×41, 41×43, 41×47, 41×53, …}.

Điều này xuất phát từ ý nghĩa tự bản thân sẽ tự hiểu những gì thuộc về mình và nhóm của mình.Và sẽ đóng một vai trò khi phán đoán rằng số mà lớn hơn bản thân 「Có phải là số nguyên tố hay không?」

Tìm số nguyên tố

Một cách để tìm tất cả số nguyên tố mà nhỏ hơn số N thì có phương pháp 「Sieve of Eratosthenes」.Quy trình đó có thể được diễn đạt theo như sau:

1.  Cho tất cả giá trị ban đầu đều là (1).

2. Bắt đầu từ số p=2, cho giá trị pr của tất cả bội số của p là (0), và loại bỏ ra khỏi các đối tượng của số nguyên tố.

3. Sẽ lặp lại bước 2 cho đến khi số p trở thành là (p×p) > N.

 

Ví dụ, sẽ có 25 số nguyên tố cho đến N=100.

 

Trong các số nguyên tố, cặp số nguyên tố mà chênh lệch nhau chỉ 2 giá trị thì được gọi là số nguyên tố sinh đôi.

Đến N=100 thì sẽ có 6 cặp số nguyên tố sinh đôi.

 

Đặc biệt, tôi nhớ là cặp [41 và 43] như 「Tốt・Đọc」.

Số nguyên tố sinh đôi lớn hơn một chút như có cặp số [1,000,037, 1,000,039].

  

Có tồn tại công thức liên quan đến số nguyên tố hay không?

Vậy thì, vì sao phương pháp「Sieve of Eratosthenes」 và những phương pháp dựa trên cơ sở đó lại được người ta sử dụng?

Điều này là do vẫn chưa tìm được công thức hay cách tính toán để giải quyết 2 vấn đề sau đây.

Vấn đề 1: Có bao nhiêu số nguyên tố cho đến số N?π(N)

Vấn đề 2: Từ số 2 thì số nguyên tố thứ K là số bao nhiêu?prime[K]

Trong quá trình nỗ lực giải vấn đề này, đã có rất nhiều người thử nghiên cứu, và đã đóng góp nhiều khái niệm trong lĩnh vực toán học [1, 2]。Có cấp số, chuỗi vô hạn, mối quan hệ của e với π, logarit, và hàm Riemann zeta[1, p107].

 
 

Từ suy đoán của Riemann [2, tr.15] rằng「Liệu có nguyên tắc phổ biến hay là công thức nào mà biểu thị số lượng số nguyên tố nhỏ hơn số N không?」đã cho ra đời một dự báo Riemann「Tất cả phần số thực của số Zero mà không phải là hiển nhiên của hàm số Zeta thì đều là 1/2」[2, p.17].

Và điều đó cho đến nay vẫn chưa được giải quyết.

Đã gần như là một lời giải, định lý về số nguyên tố sau đây và hệ quả của nó dường như được người ta phản ứng rất tốt [2, p70-71].

Định lý về số nguyên tố: π(N) ~ N / log N (Ký hiệu “~” biểu thị tính gần bằng)

Hệ quả từ định lý số nguyên tố:
　　　　　Xác suất N là số nguyên tố là ~ 1 / log N.
　　　　　Số nguyên tố thứ K ~ K log K

Sự chuyển mình của máy tính

Máy tính đang có nhiều đóng góp quan trọng vào việc tính toán các số nguyên tố và xác minh tính chất của các số nguyên tố.

Ví dụ, có xu hướng và kết quả sau đây.

  
 
10,000,019 079(Phía sau thì có 2 số)

 
[1, p.77 & p.137][2, p.60 & 64]
 

Ngược lại, yêu cầu phải tìm được số nguyên tố prime[K] thứ KVới điều này, trong phạm vi 1 chữ 32 bit là được yêu cầu cách đây một thời gian, còn hiện tại thì có lẽ sẽ yêu cầu trong thời gian ngắn hơn.

Trong phạm vi 1 chữ 64 bit thì sẽ trở nên như thế nào nhỉ?Nhất định, bạn hãy thử nó nhé.

  [1, p.315]

 

   

  

Kết quả này phát triển thành hệ thống mã hóa RSA dựa trên tích của hai số nguyên tố (P,Q) (Ron Rivest, Adi Shamir, Leonard Adleman, Năm 1997).

Với điều này, việc tìm được tích của P và Q thì đơn giản, tuy nhiên ngược lại thì khó có thể phân tích nhân tử của số lớn M thành 2 số nguyên tố. Tại đây thì phép toán (modulo) được sử dụng đến.

    

Triển khai tính toán lượng tử

Phân tích nhân tử của số lớn N thì cần nhiều thời gian để tính toán, đó là điều cốt lõi của RSA.

Tuy nhiên, trong tính toán lượng tử mà sử dụng máy tính lượng tử, thì 「Thuật toán phân tích nhân tử của Shor」- có thể sẽ tính toán được ngay trong một thời gian ngắn thì đang được đề xuất đưa vào sử dụng. Nó là phương pháp tận dụng tính chu kỳ của phép toán và tính chất về sự chồng chập trong phép tính lượng tử.

Ngay cả khi sử dụng thuật toán của Shor và máy tính hiện tại để tính toán mô phỏng, thì cũng có thể phát huy được những đặc trưng đó một cách đầy đủ.
Thế giới của số nguyên tố mở rộng không giới hạn.

[1] Marcus du Sautoy, The Music of the Primes, 2003,

Tác giả Marcus du Sautoy (Được dịch ra bởi Tominaga Hoshi),
Âm nhạc của các số nguyên tố, Nhà xuất bản Shinchosha, 30/08/2005, 2,400 yên.

[2] John Derbyshire, Prime Obsession, 2003,

Tác giả John Derbyshire (Được dịch ra bởi Matsuura Shunsuke),
Những người bị ám ảnh bởi các số nguyên tố, Nhà xuất bản Nikkei Business Publications, 30/08/2004, 2,600 yên.

[3] Keith Devlin, The Millennium Problems, 2002,

Tác giả Keith Devlin (Được dịch ra bởi Yamaguchi Junichi),
Toán học lý thú, Nhà xuất bản Iwanami Shoten, 25/08/2004, 2,940 yên).

Katsumasa Watanabe