codice:
import java.security.*;
import java.math.*;
import java.util.*;
/**
* Permette di ottenere un numero primo.
* */
public class PrimeGenerator {
//Per trovare numeri primi, bisogna specificare la lunghezza minima di quest'ultimi in //bit
int minBitLength;
//Numero di test di primalistà
int certainty;
SecureRandom sr;
/**
* Costruttore
* @param minBitLength di tipo int, rappresenta lunghezza minima in termini
di bit del numero primo
* @param certainty di tipo int, rappresenta il numero di tentativi
* @param sr di tipo SecureRandom, rappresenta l'oggetto che permette di
generare numeri casuali
* @exception, nel caso in cui si cerchi di instanziare un numero primo
minore di 64 byte
* */
public PrimeGenerator(int minBitLength, int certainty, SecureRandom sr) {
if (minBitLength<512)
throw new IllegalArgumentException("Un numero primo sicuro deve essere composto almeno da 64 byte.");
//Associa i valori
this.minBitLength=minBitLength;
this.certainty=certainty;
this.sr=sr;
}
/**
* @return Restituisce un numero primo sicuro
* */
public BigInteger getStrongPrime() {
//Il numero primo p sarà tale che p+1 sia composto da un grande fattore s
BigInteger s = new BigInteger(minBitLength/2-8,certainty,sr);
//t will be a large prime factor of r, which follows
//t sarà un grande fattore di r
BigInteger t=new BigInteger(minBitLength/2-8,certainty,sr);
BigInteger i=BigInteger.valueOf(1);
//p-1 avrà un grande fattore r
//r sarà il primo numero nella sequenza 2t+1, 2*2t+1, 2*3t+1,...
BigInteger r;
do {
r=BigInteger.TWO.multiply(i).multiply(t).add(BigInteger.ONE);
i=i.add(BigInteger.ONE);
} while (!r.isProbablePrime(certainty));
BigInteger z=s.modPow(r.subtract(BigInteger.TWO),r);
BigInteger
pstar=BigInteger.TWO.multiply(z).multiply(s).subtract(BigInteger.ONE);
BigInteger k=BigInteger.valueOf(1);
//Il numero primo p è il primo nella sequenza 2rs+p*, 2*2rs+p*, 2*3rs+p*,...
BigInteger p=BigInteger.TWO.multiply(r).multiply(s).add(pstar);
while (p.bitLength()<=minBitLength) {
k=k.multiply(BigInteger.TWO);
p=BigInteger.TWO.multiply(k).multiply(r).multiply(s).add(pstar);
}
while (!p.isProbablePrime(certainty)) {
k=k.add(BigInteger.ONE);
p=BigInteger.TWO.multiply(k).multiply(r).multiply(s).add(pstar);
}
return p;
}
/**
* @return un primo sicuro da 2rt+1 dove t è un grande primo
* */
public BigInteger getSafePrime() {
BigInteger p;
BigInteger r=BigInteger.valueOf(0x7fffffff);
BigInteger t=new BigInteger(minBitLength-30,certainty,sr);
//Il numero primo p è il primo nella sequenza 2rt+1, 2*2rt+1, 2*3rt+1,...
do {
r=r.add(BigInteger.ONE);
p=BigInteger.TWO.multiply(r).multiply(t).add(BigInteger.ONE);
} while (!p.isProbablePrime(certainty));
return p;
}
/**
* Restituisce un primo sicuro della forma 2rt+1 dove t è un grande primo
* e la fattorizzazione di r è nota.
* Inoltre restituisce un generatore per il primo sicuro.
* @return un array di due elementi di tipo BigInteger[], il quale nella
* posizione 0 c'è il numero primo, mentre nella posizione 1 c'è il suo
* generatore.
* */
public BigInteger[] getSafePrimeAndGenerator() {
BigInteger[] p=new BigInteger[2];
BigInteger r=BigInteger.valueOf(0x7fffffff);
BigInteger t=new BigInteger(minBitLength-30,certainty,sr);
//p è il numero primo nella sequenza 2rt+1, 2*2rt+1, 2*3rt+1,...
do {
r=r.add(BigIntegerMath.ONE);
p[0]=BigIntegerMath.TWO.multiply(r).multiply(t).add(BigIntegerMath.ONE);
} while (!p[0].isProbablePrime(certainty));
//Bisogna ottenere i fattori primi da p-1=2rt
//Inseriammo i fattori primi, presi una sola volta, in un Vector
Vector factors=new Vector();
//Aggiungiamo t nel vettore, ove t è un fattore primo di p-1=2rt
factors.addElement(t);
//Sappiamo che 2 è un fattore di p-1=2rt, così aggiungiamo 2 al vettore
factors.addElement(BigInteger.valueOf(2));
//r potrebbe non essere un fattore
if (r.isProbablePrime(10))
factors.addElement(r);
//diversamente, cerca i fattori di r e lo aggiungiamo al vettore
else {
//Riduce dutti e due i fattori di r e li aggiunge al vettore
while (r.mod(BigIntegerMath.TWO).equals(BigIntegerMath.ZERO)) {
r=r.divide(BigIntegerMath.TWO);
}
//Otteniamo ora i fattori primi di r, i quali dovrebbero essere sufficientemente piccoli
//partiamo con 3 - 2 che sono già nel vettore
BigInteger divisor=BigInteger.valueOf(3);
BigInteger square=divisor.multiply(divisor);
while (square.compareTo(r)<=0) {
//se questi divide r, lo aggiungiamo al vettore
if (r.mod(divisor).equals(BigIntegerMath.ZERO)) {
factors.addElement(divisor);
//Riduce il divisore
while (r.mod(divisor).equals(BigIntegerMath.ZERO))
r=r.divide(divisor);
}
divisor=divisor.add(BigIntegerMath.ONE);
square=divisor.multiply(divisor);
}
}
//Ora, partiamo con la ricerca del generatore
boolean isGenerator;
BigInteger pMinusOne=p[0].subtract(BigIntegerMath.ONE);
BigInteger x,z,lnr;
do {
//Ipotiziamo che il vaore di test sia un generatore
isGenerator=true;
//Scegliamo un piccolo intero casuale x più piccolo del primo p
x=new BigInteger(p[0].bitLength()-1,sr);
for (int i=0;i<factors.size();i++) {
//Calcoliamo z come p-1 dividendo con l'i-esimo fattore primo nel vettore
z=pMinusOne.divide((BigInteger)factors.elementAt(i));
//Calcoliamo x^z(mod p)
lnr=x.modPow(z,p[0]);
//Se questi è pari ad 1, non è un generatore
if (lnr.equals(BigIntegerMath.ONE)) {
isGenerator=false;
//Cerchiamo un nuovo generatore
break;
}
}
//Finche x non è un generatore, ritorniamo indietro e generiamo un nuovo x
} while (!isGenerator);
//Abbiamo trovato un insieme di generatori, e li restituiamo
p[1]=x;
return p;
}
}
Rispondi quotando