no more details complete it in these details

The problems on this assignment are intended as food for thought about the adequacy of the omputational model that we introduced in class. 1. (20 points) This sequence of exercises is supposed to illustrate that certain restrictions that we put on our RAM model are really necessary. If they were not imposed then some problems that are believed to be very difficult could be solved easily. In particular you are to show that the problem of factoring a large integer into its prime components becomes quite easy, if no restrictions on the sizes of integers stored in a RAM are made (or if you allow a floor function for a RAM with real numbers). Many methods in cryptography, e.g. the security of the RSA crypto system, rely on the assumption that factoring is hard. The following subproblems should lead to this result. The underlying model is an integer RAM with no size restriction and unit cost operations +,,, div. (a) Show that given integers A and N the number AN can be computed in O(logN) time. (b) Show that given natural numbers N and K the binomial coefficient (NK) can be compute in O(logN) time. Hint: Consider (A+1)N for large A. (c) Show that given natural number N the number N ! can be computed in O(log2N) time. (d) Show that in O(log2N) time it can be tested whether N is a prime number. (e) Show that in O(log3N) time a non-trivial factor of N can be found, provided N is not prime. For this you may assume the existence of a routine that computes the GCD (Greatest Common Divisor) of two numbers X and Y in time O(log(min{X,Y})). (f) Show that the prime factorization of N can be found in time O(log4N). (g) Can you improve some of the indicated asymptotic running times? The problems on this assignment are intended as food for thought about the adequacy of the omputational model that we introduced in class. 1. (20 points) This sequence of exercises is supposed to illustrate that certain restrictions that we put on our RAM model are really necessary. If they were not imposed then some problems that are believed to be very difficult could be solved easily. In particular you are to show that the problem of factoring a large integer into its prime components becomes quite easy, if no restrictions on the sizes of integers stored in a RAM are made (or if you allow a floor function for a RAM with real numbers). Many methods in cryptography, e.g. the security of the RSA crypto system, rely on the assumption that factoring is hard. The following subproblems should lead to this result. The underlying model is an integer RAM with no size restriction and unit cost operations +,,, div. (a) Show that given integers A and N the number AN can be computed in O(logN) time. (b) Show that given natural numbers N and K the binomial coefficient (NK) can be compute in O(logN) time. Hint: Consider (A+1)N for large A. (c) Show that given natural number N the number N ! can be computed in O(log2N) time. (d) Show that in O(log2N) time it can be tested whether N is a prime number. (e) Show that in O(log3N) time a non-trivial factor of N can be found, provided N is not prime. For this you may assume the existence of a routine that computes the GCD (Greatest Common Divisor) of two numbers X and Y in time O(log(min{X,Y})). (f) Show that the prime factorization of N can be found in time O(log4N). (g) Can you improve some of the indicated asymptotic running times