Question

1 1 point Consider the following algorithm for factoring an integer N provided as input (in binary): For i = 2 to [VN.17 i divides N, then output (i, N/). Which of the following statements is true? This algorithm is correct, but it runs in exponential time. This algorithm is not correct, because it will sometimes fail to find a factorization of Neven if N is composite This algorithm runs in sub-linear time, and always factors N it Nis composite This algorithm is not correct, because it will sometimes output a non-trivial factorization of N even when N is prime. 2. Which of the following is NOT a group? 1 point The integers under addition The integers under multiplication. The set {1,3,7,9) under multiplication modulo 10 The set {0, 1, 2,..., 27) under addition modulo 28. 3. Which of the following is the multiplicative inverse of 10 modulo 157 1 point O 10 There is none, since ged(10.15) - 1 5

Answer 1

an of - Consider the following algorithm for factoring integer N for i=2 to TN if N% i ==0 output (i N/8) ans Running time this algorithm O VN) thes as the loop runs for (TVN7-1) times. Therefore the algorithm runs in sub-linear time Ci.e. less than 0(N)) This algorithm is correct as all the divisors exist pairs & the first ets when the first element of the pain reaches TvNl, the pairs starts to repeat but now their order is reversed. Let us see example : N=100 (as loop runs from 2, therefore 1&100 are trivia ones. & hence (e,n/a) :- 1,100 ignored) are 2,50 4, 25 5,20 10,10 20,5 as, 4 (repeated 50, 2 divisors/ factors 100,1 So the correct option is c)

TWTFS Date 2. Which of the following is not a groupo a) integers under addition, b> integers under multiplication a The set {1,3,7,93 under multiplication modulo 10 d) The set {0, 1,2,.,27} under addition modulo as And properties of a group - (A) Closure ce) Associativity (c) Identity elem exists call in verse existe for all the elemente (a) ta, bez & closure satisfied Ha, b, c EZ a+b+c) & Assoc. satisfied [associativity prop. 17 atb E Z (atbtc addition VaEZ ato= a so, o ez is the additive identity Identity elem exists 7 bez sit. atb=0 (6=ra) Oo ta EZ g or in other words qvaez g-a Ez inverse exists for alle elements

(b) integers under multiplication tab E Z atb EZ 8. closure satisfied ta, brez a* (betc) Associstivity (multiplication is satisfied (atbc o associative) Hatz a * Z or 'l is the multiplicative identity for all the elements of & Identity dement exists och let aE Z now, for atb = 1 (b= inverse of a) So, b=1/a now, of a=262 b =%2¢2 Therefore, inverse does not exist for all elements Hence, Entegers under multiplication donot form Group So, correct ansever is (6)