BigInteger.isProbablePrime în Java

boolean isProbablePrime(int certitudine)
BigInteger nextProbablePrime()
static BigInteger probablePrime(int biti, Random rnd)

Ce face BigInteger.isProbablePrime

Verificarea exactă a primalității pentru numere cu sute de cifre ar dura prea mult. isProbablePrime(c) folosește teste probabilistice (Miller-Rabin): dacă returnează false, numărul este sigur compus; dacă returnează true, este prim cu probabilitatea de cel puțin 1 − 1/2^c.

Cu c = 50, șansa de greșeală este mai mică de 1 la un milion de miliarde. Un c mai mare înseamnă mai multă siguranță și mai mult timp.

nextProbablePrime() returnează primul număr (probabil) prim mai mare decât numărul dat. probablePrime(biti, rnd) generează un prim aleatoriu cu numărul de biți cerut.

Parametri

Parametru	Descriere
certitudine	Cât de sigur să fie răspunsul true: probabilitatea de eroare este cel mult 1/2certitudine.

Ce returnează

true dacă numărul este probabil prim, false dacă este sigur compus.

Exemple

Exemplul 1: Numere prime Mersenne (2^p − 1)

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        for (int p : new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 61, 89, 107, 127}) {
            BigInteger m = BigInteger.TWO.pow(p).subtract(BigInteger.ONE);
            if (m.isProbablePrime(50)) {
                System.out.println("2^" + p + " - 1 este prim, cifre: " + m.toString().length());
            }
        }
    }
}

Rezultat

2^2 - 1 este prim, cifre: 1
2^3 - 1 este prim, cifre: 1
2^5 - 1 este prim, cifre: 2
2^7 - 1 este prim, cifre: 3
2^13 - 1 este prim, cifre: 4
2^17 - 1 este prim, cifre: 6
2^19 - 1 este prim, cifre: 6
2^31 - 1 este prim, cifre: 10
2^61 - 1 este prim, cifre: 19
2^89 - 1 este prim, cifre: 27
2^107 - 1 este prim, cifre: 33
2^127 - 1 este prim, cifre: 39

Exemplul 2: Următorul număr prim

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger n = BigInteger.valueOf(2026);
        System.out.println("2026 este prim? " + n.isProbablePrime(50));
        System.out.println("Următorul prim după 2026: " + n.nextProbablePrime());
        BigInteger mare = BigInteger.TEN.pow(30);
        System.out.println("Primul prim după 10^30: " + mare.nextProbablePrime());
    }
}

Rezultat

2026 este prim? false
Următorul prim după 2026: 2027
Primul prim după 10^30: 1000000000000000000000000000057

Exemplul 3: Un prim aleatoriu de 64 de biți (cu sămânță fixă)

import java.math.BigInteger;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        BigInteger p = BigInteger.probablePrime(64, new Random(12));
        System.out.println("Prim: " + p);
        System.out.println("Biți: " + p.bitLength() + ", prim? " + p.isProbablePrime(100));
    }
}

Rezultat

Prim: 13878367907911923707
Biți: 64, prim? true

Greșeli frecvente

• Interpretezi true ca dovadă matematică. Este „aproape sigur”; pentru o dovadă exactă ai nevoie de alt algoritm.
• Folosești probablePrime cu new Random(sămânță) pentru chei de criptare. Pentru securitate folosește SecureRandom.

Comenzi înrudite

• BigInteger: Întreg fără limită de mărime (cât îl lasă memoria); BigInteger.valueOf(n) îl creează dintr-un long.
• BigInteger.pow: pow ridică la putere (2^100 exact); mod dă restul împărțirii, mereu pozitiv; modPow calculează rapid (a^b) mod m.
• Random: Generator de numere pseudo-aleatorii; nextInt(n) dă un întreg între 0 și n-1. Cu o sămânță fixă, șirul se repetă.