QUESTION B

b) Eve is given a large composite number n =p xq. She attempts a brute force approach to finding a factor of n by testing whether p divides n for p = 2,3, 5, 7, ... until she finds a factor pln. Prove that Eve has to test at most 26/2+1 d= b In 2 factors until she finds p|n, where b = log2(n) is the approximate number of bits in n. Hint: Use the Prime Number Theorem to approximate the number of tests required. [3 marks] c) Assume Eve has a computer that can check 100 million factors in a second. How many days could it potentially take Eve to find a prime factor for a number n with b = 100? Use the estimate from b). [2 marks] b) Eve is given a large composite number n =p xq. She attempts a brute force approach to finding a factor of n by testing whether p divides n for p = 2,3, 5, 7, ... until she finds a factor pln. Prove that Eve has to test at most 26/2+1 d= b In 2 factors until she finds p|n, where b = log2(n) is the approximate number of bits in n. Hint: Use the Prime Number Theorem to approximate the number of tests required. [3 marks] c) Assume Eve has a computer that can check 100 million factors in a second. How many days could it potentially take Eve to find a prime factor for a number n with b = 100? Use the estimate from b). [2 marks]