- 22 10 If 1 Mod M Then Fermat S Little Theorem Tells Us That M Is Composite On The Other Hand Even If L Mod M 1 (22.23 KiB) Viewed 76 times
- 22 10 If 1 Mod M Then Fermat S Little Theorem Tells Us That M Is Composite On The Other Hand Even If L Mod M 2 (89.52 KiB) Viewed 76 times
22.10. If "- #1 (mod m), then Fermat's Little Theorem tells us that m is composite. On the other hand, even if =l (mod m) am-1
for some (or all) a's satisfying gcd(a,m) 1, we cannot conclude that m is prime. This exercise describes a way to use Quadratic Reciprocity to check if a number is probably prime. (You might compare this method with the Rabin-Miller test described in Chap- ter 19.) (a) Euler's criterion says that if p is prime then q(P-1)/2 = (mod p). Use successive squaring to compute 11864 (mod 1729) and use Quadratic Recipro- city to compute (129). Do they agree? What can you conclude concerning the possible primality of 1729? (b) Use successive squaring to compute the quantities 2(1293337–1)/2 (mod 1293337) and 21293336 (mod 1293337). What can you conclude concerning the possible primality of 1293337?