Số nguyên tố, mặc dù theo định nghĩa là dạng số đơn giản nhất (chỉ có ước là 1 và chính nó), thế nhưng luôn là đối tượng nghiên cứu liên quan đến rất nhiều lĩnh vực không chỉ trong Toán học mà còn mang lại những ứng dụng không nhỏ trong cuộc sống.
http://diendantoanhoc.net/modules.php?name=News&file=article&sid=153
Phương pháp đầu tiên mà mọi người nghĩ đến là thử chia số cần xét cho các số từ 2 đến n-1 xem nó có chia hết cho số nào hay không. Tuy nhiên, nếu n chia hết cho 2 thì n/2 là số nguyên lớn nhất (<n) chia hết n. Do đó, ta chỉ cần thử chia n cho các số từ 2 đến n/2 mà thôi. Nếu chỉ dừng lại ở đây thì nhiều người sẽ thấy chưa đủ. Xét tổng quát thì nếu n chia hết cho x thì ta không cần xét số n/x vì chắc chắn số này cũng chia hết n. Khi hai số x và n/x bằng nhau thì x = căn bậc 2 của n. Do đó, ta chỉ cần xét các số từ 2 đến căn bậc 2 của n xem chúng có chia hết n hay không. Bạn thử nghĩ xem, nếu n = 1.000.000 thì cách đầu phải chạy xấp xỉ 1.000.000 lần, cách thứ hai chạy xấp xỉ 500.000 lần còn cách cuối chỉ chạy khoảng 1.000 lần thôi.
Trong suốt nhiều thế kỷ, kỹ thuật mã hóa dựa theo phương pháp cổ truyền: sử dụng một mật mã (có thể là một từ, một văn bản đối chiếu, một dãy số...) để bảo mật thông tin. Người nhận, được người gửi cho biết mật mã, chỉ cần áp dụng quá trình ngược lại là có thể hiểu được thông tin bị mã hóa.
Theo các chuyên gia, đây là phương pháp hai chiều, tức là sử dụng một mật mã để làm hai việc là mã hóa và giải mã. Kỹ thuật này có một nhược điểm là độ bí mật tuyệt đối của mật mã không được đảm bảo. Vì trên thực tế, người gửi phải thông báo cho người nhận mật mã thông qua một hình thức nào đó. Ví dụ, nếu ta muốn chuyển một thông tin mã hóa nào đó cho một người ở rất xa thì ta phải chuyển văn bản chứa đựng thông tin được mã hóa và mật mã cho người đó bằng thư, điện thoại, hoặc Internet và chính vì thế mật mã của bạn (không được mã hóa) sẽ dễ bị người khác biết.
Để đảm bảo độ bí mật, người ta đã áp dụng nguyên lý số nguyên tố. Như chúng ta biết, số nguyên tố rất đặc biệt vì chúng là một số nguyên chỉ chia hết cho 1 và chính nó. Ta dễ dàng thực hiện phép nhân giữa các số nguyên tố với nhau. Ví dụ, ai cũng có thể nhân được 319489 x 242483 = 774707470337. Nhưng quá trình ngược lại lại rất phức tạp. Ví dụ để kiểm tra xem số 267281174273 có phải là số nguyên tố hay không, ta phải mất rất nhiều thời gian với hàng loạt phép tính mới có thể phát hiện được số này là kết quả của phép nhân giữa 274177 với 974849. Mà đây mới chỉlà những số có ít chữ số. Các bạn hình dung nếu kết quả ban đầu là một số có 20, 30 hay 50 chữ số thì khối lượng các phép toán sẽ khổng lồ đến mức nào!
Ngược lại với các phương pháp hai chiều hay còn gọi là đối xứng, mô hình số nguyên tố cho phép dễ dàng mã hóa thông tin nhưng dường như là không thực hiện được quá trình ngược lại. Ví dụ, chúng ta có thể chọn hai số nguyên tó p và q bất kỳ sau đó nhân chúng với nhau để thu được kết quả N. N chính là mật mã và ai cũng có thể biết được mật mã này và sử dụng nó để khóa một thông tin ai đó gửi cho bạn nhưng không ai biết được kết quả N là phép nhân hai số p và q (hai yếu ốt không thể thiếu để giải mã và chỉ có bạn biết) nên không thể đọc được thông tin mã hóa của bạn. Phương pháp này vừa dễ thực hiện mà độ bảo mật lại rất cao.
Dựa trên nguyên tắc này, các nhà lập trình và quản lý mạng máy tính đã nghĩ ra một hệ thống mã hóa đáp ứng được hai yêu cầu cơ bản là dễ sử dụng và độ bảo mật cao của các thông tin trên mạng Internet mang tên RSA (*) (RSA là tên viết tắt của các thành viên sáng lập: Rivest, Shamir và Adleman). Năm 1991, Phil Zimmermann cũng đã nghĩ ra một phiên bản khác hiệu quả hơn đặt tên là PGP (Pretty Good Privacy). Tất cả mọi người đều có thể truy cập vào PGP thông qua Internet để khóa thông tin của mình.
The Code:
Private Function GeneratePrimeList2(ByVal numOfPrimes As Int32) As Int32()
Dim primes(numOfPrimes - 1) As Int32
Dim cntr As Int32 = 5
Dim pcntr As Int32 = 2
Dim i As Int32
Dim maxPrimeSqrRoot As Double
primes(0) = 2
primes(1) = 3
Do Until pcntr = numOfPrimes
'get the highest factor to check against if under the
'predetermined maximum
maxPrimeSqrRoot = Math.Sqrt(cntr)
'for each prime other than two
For i = 1 To pcntr - 1
'check for clean division
If cntr Mod primes(i) = 0 Then
'not prime
Exit For
Else
'if all primes up to maxfactor used or all primes used then it is prime
If primes(i + 1) > maxPrimeSqrRoot OrElse i = pcntr - 1 Then
primes(pcntr) = cntr
pcntr += 1
Exit For
End If
End If
Next
cntr += 2
Loop
Return primes
End Function
Giải thích:
Primes=mảng chứa các số ngto tìm được
Cntr=số đang được test
Pcntr=số lượng số ngto đã tìm thấy
Cntr+=2 ta chỉ test với các số lẻ, số chẵn khác 2 đương nhiên không phải số ngto
