Số 50 trong thuật toán xác định "số nguyên tố" (Mersenne numbers)

[HoangNew (Hoang)]

Mọi người có thể giải thích cho mình số 50 trong thuật toán có nghĩa là gì không??
Và tại sao lại là 50. Trong tài liệu mình đọc nó chỉ ghi là “50” là một số ma thuật… kiểm soát khả năng test của số nguyên tố.

Đây là nguyên văn.

This program is a straightforward encoding of the prose description above: it starts with the primes, computes the corresponding Mersenne numbers, filters out all but the primes (the magic number 50 controls the probabilistic primality test), limits the resulting stream to twenty elements, and prints them out.

Đây là mã:

    public class PrimaryNumber {
    static Stream<BigInteger> primes() {
        return Stream.iterate(BigInteger.TWO, BigInteger::nextProbablePrime);
    }

    public static void main(String[] args) {
        primes().map(
                p ->
                BigInteger.TWO.pow(p.intValueExact()).subtract(BigInteger.ONE))
                .filter(mersense -> mersense.isProbablePrime(50))
                .limit(20)
                .forEach(System.out::println);
    }
 }

Thank all!

[tntxtnt]

phương thức isProbablePrime có lẽ là xài Rabin-Miller test, nếu vậy thì số 50 nghĩa là số lần kiểm tra xem n có phải là số ng tố hay ko. Chọn 1 số ngẫu a nhiên trong đoạn [2, n - 2] rồi kiểm tra thử xem số ngẫu nhiên này có “tố cáo” n ko phải là số ng tố hay ko. Đương nhiên nếu n ko phải ng tố, a vẫn có thể ko tố cáo n, nên phải lập đi lập lại nhiều lần.

If n is composite then the Miller–Rabin primality test declares n probably prime with a probability at most 4^−k.

Ước tính nếu 1 số a ko tố cáo n ko phải ng tố thì n được thêm 75% khả năng là số nguyên tố. Nếu 10 số ngẫu nhiên ko tố cáo n thì xác suất n ko phải là ng tố là 0.25^-10 = 2^-20 ~ 1 phần triệu.Ở đây chọn 50 lần nghĩa là xác suất n ng tố là 100% - 100 x 2^-100 ~ 99.99999999999999999999999999992%

edit: Java doc ghi:

certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2^certainty). The execution time of this method is proportional to the value of this parameter.

chắc là ko xài Miller-Rabin

[HoangNew (Hoang)]

Có đó anh. Mà nó xài 2 thuật toán để tìm tính đúng sai của số nguyên tố - (Miller-Rabin và LucasLehmer)
(Y)

boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    }

[rogp10]

Lucas-Lehmer là thuật toán kiểm tra chính xác cho dạng số này còn RM có false positive

Thực ra RM không dùng để chặn trước (vì thời gian cũng tương đương với LL), mà dùng chia thử ( thừa số có dạng 2*k*p + 1 k = 1…) và chạy “curve” p - 1. Xem bên mersenne.org.