Labs Homeworks |
## Lab3## Lab3: Primality Testing Due: Feb 7th, During Lab Section## Part 1Implement the ## Part 2Implement the randomized primality testing algorithm in Fig 1.8
using the ## What to turn inYou can test your code on arbitrary integers N to test if they are prime or not. In general, with k trials the probability of returning a wrong answer is \(\frac{1}{2^k}\). However, Carmichael numbers are composite numbers that pass fermat's little theorem for all integers \(a\) relatively prime to \(N\). For each of the following Carmichael numbers determine the probability of failure in k trials, using k=1000. That is, the probability that the number is determined to be a prime when in fact it is not. The first 32 Carmichael numbers are: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881. Verify that these probabilities are much higher than \(\frac{1}{2^k}\). |

Page last modified on January 31, 2018, at 07:49 PM