Problem 1. The first part of the implementation is to write some preliminaries useful later. a) We're often going to need to use some form of trial division. Write a function that given a number n and a list of primes p1, . . ., p, computes a factorization 1 2 . . . Pr n = PI P2 ar . S. where god(p;, s) = 1. The function should return the vector Jaj, ...,a, and the number s (formatted however you want.). For example, when we have a list containing only the prime 2, this function should write n = 2''s where s is odd. You can use this in Tonelli's algorithm and the strong pseudoprime test. b) Before plugging a number into the quadratic sieve, you should probably check that it is not prime. Implement the strong pseudoprime test. (You can recycle some code here: you wrote fast exponentiatron on a previous homework, and to write a number in the form 2" . t you can use your function from (a) with the single prime p, = 2.) c) SUBMIT: Is the number 3004879 likely to be prime? Justify your answer by explaining what your program has discovered