尋找初級需要很長時間JAVA

Question

我不知道我是否正確使用此代碼 - >主要。這是非常緩慢的。這是DDS算法。 是實現DSA的：http://en.wikipedia.org/wiki/Digital_Signature_Algorithm

這個循環需要很多時間

do { 
      pTemp = new BigInteger(l, primeCenterie, rand); 
      pTemp2 = pTemp.subtract(BigInteger.ONE); 
      pTemp = pTemp.subtract(pTemp2.remainder(q)); 
      System.out.println("1 " + i++); 
     } while (!pTemp.isProbablePrime(primeCenterie) 
       || pTemp.bitLength() != l); 

我加了一些printlns，甚至他們是緩慢的。

import java.math.BigInteger; 
import java.security.MessageDigest; 
import java.security.NoSuchAlgorithmException; 
import java.util.Random; 
import java.util.logging.Level; 
import java.util.logging.Logger; 

public class Key { 
    int primeCenterie = 20; 
    BigInteger q; 
    BigInteger p; 
    BigInteger g; 
    BigInteger y; 
    BigInteger x; 
    BigInteger k; 
    Random rand = new Random(); 

    Key() { 
    } 

    public void generateKey() { 
     q = new BigInteger(160, primeCenterie, rand); 
     p = generateP(q, 512); 
     g = generateG(p, q); 
     do { 
      x = new BigInteger(q.bitCount(), rand); 
     } while (x.compareTo(BigInteger.ZERO) != 1 && x.compareTo(q) != -1); 
     y = g.modPow(x, p); 
    } 

    private BigInteger generateP(BigInteger q, int l) { 
     if (l % 64 != 0) { 
      throw new IllegalArgumentException("L value is wrong"); 
     } 
     BigInteger pTemp; 
     BigInteger pTemp2; 
     int i = 0; 
     do { 
      pTemp = new BigInteger(l, primeCenterie, rand); 
      pTemp2 = pTemp.subtract(BigInteger.ONE); 
      pTemp = pTemp.subtract(pTemp2.remainder(q)); 
      System.out.println("1 " + i++); 
     } while (!pTemp.isProbablePrime(primeCenterie) 
       || pTemp.bitLength() != l); 
     return pTemp; 
    } 

    private BigInteger generateG(BigInteger p, BigInteger q) { 
     BigInteger aux = p.subtract(BigInteger.ONE); 
     BigInteger pow = aux.divide(q); 
     BigInteger gTemp; 
     int i = 0; 
     do { 
      gTemp = new BigInteger(aux.bitLength(), rand); 
      System.out.println("2 " + i++); 
     } while (gTemp.compareTo(aux) != -1 
       && gTemp.compareTo(BigInteger.ONE) != 1); 
     return gTemp.modPow(pow, p); 
    } 

    public BigInteger generateK(BigInteger q) { 
     BigInteger tempK; 
     int i = 0; 
     do { 
      tempK = new BigInteger(q.bitLength(), rand); 
      System.out.println("3 " + i++); 
     } while (tempK.compareTo(q) != -1 
       && tempK.compareTo(BigInteger.ZERO) != 1); 
     return tempK; 
    } 

    public BigInteger generateR() { 
     k = generateK(q); 
     BigInteger r = g.modPow(k, p).mod(q); 
     return r; 
    } 

    public BigInteger generateS(BigInteger r, byte[] data) { 
     MessageDigest md; 
     BigInteger s = BigInteger.ONE; 
     try { 
      md = MessageDigest.getInstance("SHA-1"); 
      md.update(data); 
      BigInteger hash = new BigInteger(md.digest()); 
      s = (k.modInverse(q).multiply(hash.add(x.multiply(r)))).mod(q); 
     } catch (NoSuchAlgorithmException ex) { 
      Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex); 
     } 
     return s; 
    } 

    boolean verify(byte[] data, BigInteger r, BigInteger s) { 
     if (r.compareTo(BigInteger.ZERO) <= 0 || r.compareTo(q) >= 0) { 
      return false; 
     } 
     if (s.compareTo(BigInteger.ZERO) <= 0 || s.compareTo(q) >= 0) { 
      return false; 
     } 
     MessageDigest md; 
     BigInteger v = BigInteger.ZERO; 
     try { 
      md = MessageDigest.getInstance("SHA-1"); 
      md.update(data); 
      BigInteger hash = new BigInteger(md.digest()); 
      BigInteger w = s.modInverse(q); 
      BigInteger u1 = hash.multiply(w).mod(q); 
      BigInteger u2 = r.multiply(w).mod(q); 
      v = ((g.modPow(u1, p).multiply(y.modPow(u2, p))).mod(p)).mod(q); 
     } catch (NoSuchAlgorithmException ex) { 
      Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex); 
     } 
     return v.compareTo(r) == 0; 
    } 

    public static void main(String[] args) { 
     Key key = new Key(); 
     key.generateKey(); 
     byte[] data = "a".getBytes(); 
     BigInteger r = key.generateR(); 
     BigInteger s = key.generateS(r, data); 
     System.out.println(key.verify(data,r,s)); 
    } 

} 

Answer 1

分析器將是最好的，但我認爲你的問題是isProbablePrime。你在20點傳球，這基本上意味着你需要一個.9999999的確定性。嘗試更小的參數或使用其他方法進行素性測試...

isProbablePrime 

public boolean isProbablePrime(int certainty) 

    Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is <= 0, true is returned. 

    Parameters: 
     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/2certainty). The execution time of this method is proportional to the value of this parameter. 
    Returns: 
     true if this BigInteger is probably prime, false if it's definitely composite.