Cryptography Reference
In-Depth Information
TABLE 13.4
y
i
y in table?
0
140
No
1
136
No
2
290
No
3
194
No
4
206
Yes (index 15)
Java Algorithm The BigIntegerMath class also contains a method to compute discrete
logs using baby-step giant-step. The code follows:
public static BigInteger logBabyStepGiantStep
(BigInteger base, BigInteger residue, BigInteger modulus) {
//This algorithm solves base^x = residue (mod modulus) for x using baby step
//giant step
BigInteger m=sqrt(modulus).add(ONE);
//Use a hash table to store the entries-use Java Hashtable class
Hashtable h=new Hashtable();
BigInteger basePow=BigInteger.valueOf(1);
//Build the hash table base^j is the key, index j is the value
for (BigInteger j=BigInteger.valueOf(0);j.compareTo(m)<0;j=j.add(ONE)) {
h.put(basePow,j);
basePow=basePow.multiply(base).mod(modulus);
}
//Compute an inverse of base^m modulo p
BigInteger basetotheminv=base.modPow(m,modulus).modInverse(modulus);
BigInteger y=new BigInteger(residue.toByteArray());
//Search the hashtable for a base^j such that y=base^j for some j
BigInteger target;
for (BigInteger i=BigInteger.valueOf(0);i.compareTo(m)<0;i=i.add(ONE)) {
target = (BigInteger)h.get(y);
if (target!=null) return i.multiply(m).add(target);
y=y.multiply(basetotheminv).mod(modulus);
}
throw new NoSuchElementException(“No solution”);
}
I have written TestDiscreteLogApplet to test these log finding methods. It can be run
from the topic's website. Figures 13.2 and 13.3 show two screen shots.
Search WWH ::




Custom Search