Bác nào chỉ cho em về cái thuật toán kiểm tra số nguyên tố với

theo t> t'i ưu lĂ s' l>n mĂ ngĂn ngữ lập trĂnh khĂng h- trợ ....KhĂng biết cĂ thuật toĂn như vậy khĂng ? xử lĂ s' trĂn chu-i

H"i xưa em dĂng pascal hay dĂng mảng 'Tng 'f lưu s' l>n (cỡ 70!). Từ h"i chuyfn sang C khĂng phải lĂm vi?c v>i s' l>n nữa, may quĂ

Vừa đọc lại dòng này, bác htcuong chú ý nhé:
Kiểm tra Miller-Rabin lặp
Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân), nếu thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên 90%. Để giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác nhau, nếu n vượt qua 50 lần thử thì P(B|A)le frac 1 {4^k}, khi thay vào công thức với 50 lần thử nếu cả 50 lần, phép thử đều "dương tính" thì xác suất sai giảm xưống chỉ còn là một số rất nhỏ không vượt quá 9 cdot 10^{-29}.

không biết nếu chạy số lớn cữ trên 100 chữ số với chip mới nhất của Intel ở VN liệu có hết 1 đêm mới chạy xong không nhỉ

Trong bài code mà mình post ở trang 1, tớ chỉ làm với các số nhỏ theo kiểu Miller-Rabin này và lấy random những 1000 lần tại sao thử n=25 vẫn ra sai nhỉ , hay là do cách cài đặt ko đúng với thuật toán chăng, mọi người check hộ với

Nếu là nông dân thì duyệt từ 1 đến n xem số n có chia hết bao nhiêu số nếu =2 -> là số nguyên tố.
Tối ưu hoá thì chỉ cần duyệt đến [n/2] thôi
hình như còn 1 vài cách nữa tối ưu hơn, nhưng quên toi mất rồi

Oa?i, cái na?y la?m sao ma? chạy được với nhưfng số có tâ?m va?i trăm chưf số được.

Đang định code thi? ti?m được "sách văn mâfu"

Below is the C++ code, this is only one simple implementation which only handle 32-bits value, remember to put more randomWitness if the "prime" value to be tested is bigger when using big number integer like in OpenSLL or other or mine (yes, I have the big integer class for C/C++ on my web site as well):
BOOL MillerRabinPrimeTestDWORD(DWORD prime)
{
// randomWitness = witness that the "prime" is NOT composite
// 1 < randomWitness < prime-1
DWORD totalWitness = 15;
DWORD randomWitness[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
DWORD primeMinusOne = prime - 1;
DWORD oddMultiplier;
DWORD bitLength;
DWORD i, j;
DWORD result;
// find oddMultiplier, defined as "prime - 1 = (2^B) * M"
// get bitLength (B) and find the oddMultiplier (M)
// init value multiplier
oddMultiplier = primeMinusOne;
bitLength = 0; // reset
while(!(oddMultiplier & 1))
{ // it is even
oddMultiplier >>= 1; // right shift
bitLength++;
}
for(i = 0; i < totalWitness; i++)
{
// init value of result = (randomWitness ^ oddMultiplier) mod prime
result = ExpModDWORD(randomWitness, oddMultiplier, prime);
// is y = 1 ?
if(result == 1)
continue; // maybe prime
// is y = prime-1 ?
if(result == primeMinusOne)
continue; // maybe prime
// loop to get AT LEAST one "result = primeMinusOne"
for(j = 1; j <= bitLength; j++)
{
// square of result
result = ExpModDWORD(result, 2, prime);
// is result = primeMinusOne ?
if(result == primeMinusOne)
break; // maybe prime
}
if(result != primeMinusOne)
return(TRUE); // COMPOSITE
}
// it may be pseudoprime/prime
return(FALSE);
}
DWORD ExpModDWORD(DWORD value, DWORD exp, DWORD mod)
{
// use ULONGLONG 64bits to prevent overflow when calculate 32bit x 32bit
ULONGLONG ullResult = 1;
ULONGLONG ullValue = value;
while(exp)
{
if(exp & 1)
{ // odd
// result = (result * value) % mod
ullResult *= ullValue;
ullResult %= mod;
}
// value = (value * value) % mod
ullValue *= ullValue;
ullValue %= mod;
// exp = exp / 2
exp >>= 1;
}
return((DWORD) ullResult);
}
The odds of a composite passing decreases faster with this test than with previous ones. Three-quarters of the possible values of a are guaranteed to be witnesses. This means that a composite number will slip through t tests no more than (1/4 * T) of the time, where T is the number of iterations. Actually, these numbers are very pessimistic. For most random numbers, something like 99.9 percent of the possible a values are witnesses.

Oa?i, đây nưfa:
http://en.literateprograms.org/Specialownloadcode/Miller-Rabin_primality_test_%28C%29