Primality Testing - Introduction to Cryptography with Java Applets - page 215

2. Fail to be able to divide y by 2 any further

passes the test. At no point can you generate a square root of 1
that is congruent to neither 1 nor

Either way, the prime n

1 modulo n , for this is demanded by Proposition 34.

E XAMPLES .
1. Take the prime n = 29 and a base b = 5; we will see that n passes Miller's test. Start with

1)/2 = 14 and compute 5 14 the exponent y = ( n 1)/2 = (29 1 (mod 29). So far, this

= 7 and compute 5 7 is a pass; divide 1 (mod 29). This is also a

pass, and we can continue no further since we obtained a residue of

y by 2 to get y 28

1. (Had we obtained

a residue of 1, we still could not have proceeded since y cannot be halved any further;

regardless, n = 7 passes Miller's test for the base 5.)

2. Take the prime n = 257, and the base b = 22, and note the progression of Miller's test in

Table 11.2.

]} TABLE 11.2

Exponent y 22 y

≡ ?(mod 257)

Conclusion

1

128 Pass-continue

1

64 Pass-continue

-1

32 Pass-STOP

3. We repeat the above test for n = 257, but using a different base b = 17. (See Table 11.3.)

]}

TABLE 11.3

17 y Exponent y

≡ ?(mod 257)

Conclusion

128 1 Pass-continue

64 1 Pass-continue

32 1 Pass-continue

16 -1 Pass-STOP

4. We repeat the test one more time for n = 257, but using a base b = 4. (See Table 11.4.)

]} TABLE 11.4

4 y Exponent y ≡ ?(mod 257) Conclusion

128 1 Pass-continue

64 1 Pass-continue

32 1 Pass-continue

16 1 Pass-continue

8 1 Pass-continue

4 -1 Pass-STOP