BigInteger e uso del metodo isProbablePrime()

[maurizio2]

Ciao, non riesco a capire cosa fa esattamente il metodo istanza
isProbablePrime(ERR_VAL); della classe BigInteger, restituisce un valore booleano
ma non ne capisco la finalita', di seguito vi mostro iil piccolo programma
che lo utilizza:

public class Primes {
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = new BigInteger("2");
    
    // Likelihood of false prime is less than 1/2^ERR_VAL.
    // Presumably BigInteger uses the Miller-Rabin test or
    // equivalent, and thus is NOT fooled by Carmichael numbers.
    // See section 33.8 of Cormen et al.'s Introduction to
    // Algorithms for details.
    private static final int ERR_VAL = 100;
    
    
    
    
    public static BigInteger nextPrime(BigInteger start) {
        if (isEven(start))
            start = start.add(ONE);
        else
            start = start.add(TWO);
        
        
        if (start.isProbablePrime(ERR_VAL))
            return(start);
        else
            return(nextPrime(start));
    }
    
    
    private static boolean isEven(BigInteger n) {
        return(n.mod(TWO).equals(ZERO));
    }
    
    private static StringBuffer[] digits =
    { new StringBuffer("0"), new StringBuffer("1"),
      new StringBuffer("2"), new StringBuffer("3"),
      new StringBuffer("4"), new StringBuffer("5"),
      new StringBuffer("6"), new StringBuffer("7"),
      new StringBuffer("8"), new StringBuffer("9") };
    
    private static StringBuffer randomDigit(boolean isZeroOK) {
        int index;
        if (isZeroOK) {
            index = (int)Math.floor(Math.random() * 10);
        } else {
            index = 1 + (int)Math.floor(Math.random() * 9);
        }
        return(digits[index]);
    }
    
    /** Create a random big integer where every digit is
     *  selected randomly (except that the first digit
     *  cannot be a zero).
     */
    public static BigInteger random(int numDigits) {
        StringBuffer s = new StringBuffer("");
        for(int i=0; i<numDigits; i++) {
            if (i == 0) {
                // First digit must be non-zero.
                s.append(randomDigit(false));
            } else {
                s.append(randomDigit(true));
            }
        }
        return(new BigInteger(s.toString()));
    }
    
    public static void main(String[] args) {
        int numDigits;
        try {
            numDigits = Integer.parseInt(args[0]);
        } catch (Exception e) { // No args or illegal arg.
            numDigits = 2;
        }
        BigInteger start = random(numDigits);
        for(int i=0; i<50; i++) {
            start = nextPrime(start);
            System.out.println("Prime " + i + " = " + start);
        }
    }   
    
}

[floyd]

la spiegazione è abbastanza chiara
doc
non lo conoscevo ma sembra che se ritorna false, il numero è sicuramente composto, se ritorna true è probabile che sia primo e la probabilità è 1-1/2^certainty

[maurizio2]

Quindi non si ha la certezza che i numeri restituiti dal programma siano primi!!
E la probabilita 1-1/2^certainty e' un indice di "sicurezza", guisto??
Sapresti spiegarmi matematicamente questa formula??
Perche' non si puo' sapere matemeticamente se un numero e' primo o no??

[Andrea1979]

Si può sapere se un numero è primo o no... basta fare la prova (metodo semplice semplice, se il numero in questione è disapri - fosse pari e diverso da 2 il problema nemmeno si pone - lo dividi per tutti i numeri dispari compresi tra 3 e la radice quadrata del numero stesso arrotondata per eccesso).

La cosa in questo modo è fattibile con numeri "piccoli" se non si vuole entrare nel regno dei tempi biblici... altrimenti ci sono dei metodi statistici come quelli adottati dalla classe BigDecimal per trattare la primalità di numeri grandi. Se hai il sorgente del jdk puoi andare a leggere i vari metodi adottati (Qui alcuni dei metodi coinvolti)

public boolean isProbablePrime(int certainty) {
	if (certainty <= 0)
	    return true;
	BigInteger w = this.abs();
	if (w.equals(TWO))
	    return true;
	if (!w.testBit(0) || w.equals(ONE))
	    return false;

        return w.primeToCertainty(certainty);
    }

boolean primeToCertainty(int certainty) {
        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);
        }

        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) && passesLucasLehmer();
    }

private boolean passesMillerRabin(int iterations) {
	// Find a and m such that m is odd and this == 1 + 2**a * m
        BigInteger thisMinusOne = this.subtract(ONE);
	BigInteger m = thisMinusOne;
	int a = m.getLowestSetBit();
	m = m.shiftRight(a);

	// Do the tests
        Random rnd = new Random();
	for (int i=0; i<iterations; i++) {
	    // Generate a uniform random on (1, this)
	    BigInteger b;
	    do {
		b = new BigInteger(this.bitLength(), rnd);
	    } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

	    int j = 0;
	    BigInteger z = b.modPow(m, this);
	    while(!((j==0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
		if (j>0 && z.equals(ONE) || ++j==a)
		    return false;
		z = z.modPow(TWO, this);
	    }
	}
	return true;
    }

private boolean passesLucasLehmer() {
        BigInteger thisPlusOne = this.add(ONE);

        // Step 1
        int d = 5;
        while (jacobiSymbol(d, this) != -1) {
            // 5, -7, 9, -11, ...
            d = (d<0) ? Math.abs(d)+2 : -(d+2);
        }
        
        // Step 2
        BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);

        // Step 3
        return u.mod(this).equals(ZERO);
    }

    /**
     * Computes Jacobi(p,n).
     * Assumes n is positive, odd.
     */
    int jacobiSymbol(int p, BigInteger n) {
        if (p == 0)
            return 0;

        // Algorithm and comments adapted from Colin Plumb's C library.
	int j = 1;
	int u = n.mag[n.mag.length-1];

        // Make p positive
        if (p < 0) {
            p = -p;
            int n8 = u & 7;
            if ((n8 == 3) || (n8 == 7))
                j = -j; // 3 (011) or 7 (111) mod 8
        }

	// Get rid of factors of 2 in p
	while ((p & 3) == 0)
            p >>= 2;
	if ((p & 1) == 0) {
            p >>= 1;
            if (((u ^ u>>1) & 2) != 0)
                j = -j;	// 3 (011) or 5 (101) mod 8
	}
	if (p == 1)
	    return j;
	// Then, apply quadratic reciprocity
	if ((p & u & 2) != 0)	// p = u = 3 (mod 4)?
	    j = -j;
	// And reduce u mod p
	u = n.mod(BigInteger.valueOf(p)).intValue();

	// Now compute Jacobi(u,p), u < p
	while (u != 0) {
            while ((u & 3) == 0)
                u >>= 2;
            if ((u & 1) == 0) {
                u >>= 1;
                if (((p ^ p>>1) & 2) != 0)
                    j = -j;	// 3 (011) or 5 (101) mod 8
            }
            if (u == 1)
                return j;
            // Now both u and p are odd, so use quadratic reciprocity
            if (u < p) {
                int t = u; u = p; p = t;
                if ((u & p & 2)	!= 0)// u = p = 3 (mod 4)?
                    j = -j;
            }
            // Now u >= p, so it can be reduced
            u %= p;
	}
	return 0;
    }

    private static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) {
        BigInteger d = BigInteger.valueOf(z);
        BigInteger u = ONE; BigInteger u2;
        BigInteger v = ONE; BigInteger v2;

        for (int i=k.bitLength()-2; i>=0; i--) {
            u2 = u.multiply(v).mod(n);

            v2 = v.square().add(d.multiply(u.square())).mod(n);
            if (v2.testBit(0)) {
                v2 = n.subtract(v2);
                v2.signum = - v2.signum;
            }
            v2 = v2.shiftRight(1);

            u = u2; v = v2;
            if (k.testBit(i)) {
                u2 = u.add(v).mod(n);
                if (u2.testBit(0)) {
                    u2 = n.subtract(u2);
                    u2.signum = - u2.signum;
                }
                u2 = u2.shiftRight(1);
                
                v2 = v.add(d.multiply(u)).mod(n);
                if (v2.testBit(0)) {
                    v2 = n.subtract(v2);
                    v2.signum = - v2.signum;
                }
                v2 = v2.shiftRight(1);

                u = u2; v = v2;
            }
        }
        return u;
    }

e qui se invece vuoi approfondire la teoria che ci sta dietro
http://mathworld.wolfram.com

[maurizio2]

ok accetto il metodo cosi come e' cio' che sta dietro e' gia' sufficiente per entrare
nel regno dei tempi biblici :maLOL: :

start.isProbablePrime(ERR_VAL)) == true //e' primo
start.isProbablePrime(ERR_VAL)) == false //non e' primo

Ottimo concetto di riusabilita senza dilaniarsi
Ciao