01/10/2018, 16:47

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

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!

‏ viết 18:56 ngày 01/10/2018

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

Hoang viết 18:55 ngày 01/10/2018

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 viết 18:59 ngày 01/10/2018

Lucas-Lehmer là thuật toán kiểm tra chính xác cho dạng số này còn RM là để chặn bớt không để test vô ích.

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 đó) và chạy “curve” p - 1. Xem bên mersenne.org.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Hoang

0 chủ đề

0 bài viết

Tác giả nổi bật