Exponential Congruences - Introduction to Cryptography with Java Applets - page 244

TABLE 13.2

Column

1 2 3 4 5 6 7 8 9 10

1 257 464 186 379 539 290 873 363 463 938

2 924 353 920 334 73 599 575 461 424 1005

3 990 162 265 502 871 858 544 566 166 284

4 340 606 356 682 717 631 727 174 322 16

5 76 361 958 10 552 604 851 763 345 882

6 658 603 594 299 159 503 119 313 730 945

7 705 574 204 969 819 611 632 984 638 508

8 395 615 651 822 373 6 533 766 107 256

9 207 731 193 160 760 583 499 100 475 995

10 438 567 423 748 526 985 895 972 581 994

11 181 103 237 369

This example alone should suggest to you that exhaustive search is obviously not the
way we want to go about finding discrete logs. However, an exhaustive search may be
worthwhile if the base is an integer of low order modulo n .

Java Algorithm I have written a method to calculate discrete logs using exhaustive
search. The code is in the BigIntegerMath class:

public static BigInteger logExhaustiveSearch
(BigInteger base, BigInteger residue, BigInteger modulus) {
//This algorithm solves base^x = residue (mod modulus) for x using exhaustive
//search
BigInteger basePow=BigInteger.valueOf(1);
BigInteger j;
for (j=BigInteger.valueOf(1);j.compareTo(modulus)<0;j=j.add(ONE)) {
basePow=basePow.multiply(base).mod(modulus);
if (basePow.equals(residue)) break;

}
if (j.equals(modulus)) throw new NoSuchElementException(“No solution”);
return j;

}