NPTEL Computational Number Theory and Algebra Assignment 2 Answer

Next Week Assignment Answers

CHECK HERE OTHERS NPTEL ASSIGNMENTS ANSWERS 

BELOW YOU CAN GET YOUR NPTEL Computational Number Theory and Algebra Assignment 2 Answer 2022? :

1 point

Given two integers  aa and bb with |a|>|b||a|>|b|. In lectures, you saw that in each round Euclid’s gcd algorithm computes two integers cc and dd such that gcd(a,b)=gcd(c,d)gcd(a,b)=gcd(c,d).

Which of the following gives the best estimate on the number of rounds the algorithm takes (⌈n⌉⌈n⌉ denotes the least integer greater than or equal to nn)?

⌈loga⌉⌈log⁡a⌉

⌈logb⌉⌈log⁡b⌉

⌈loga⌉+⌈logb⌉⌈log⁡a⌉+⌈log⁡b⌉

⌈loga⌉⋅⌈logb⌉⌈log⁡a⌉⋅⌈log⁡b⌉

ans –  b

1 point

Euclid’s gcd algorithm is a very efficient algorithm with lots of applications. Let aa and bb are given co-prime integers. Which of the following problems can be solved efficiently using Euclid’s gcd algorithm?

1. Computing a−1modba−1modb.
2. Computing the parameters in Bezout’s identity for aa and bb.

Only 1.

Only 2.

Both 1 and 2.

None of 1 and 2.

ans –  b

1 point

You have seen the definition of an ideal of a ring. Given two integers aa and bb, you can generate an ideal ⟨a,b⟩⟨a,b⟩ of ring of integers ZZ by adding each element of ideal ⟨a⟩⟨a⟩ to each element of ideal ⟨b⟩⟨b⟩, formally written as ⟨a,b⟩={ca+db|∀c,d∈Z}⟨a,b⟩={ca+db|∀c,d∈Z}.

Let a=14a=14 and b=21b=21, which of the following ideals is same as the ideal ⟨14,21⟩⟨14,21⟩?

⟨2⟩⟨2⟩

⟨3⟩⟨3⟩

⟨14,28⟩⟨14,28⟩

⟨7⟩⟨7⟩

ans –  c

1 point

In lectures, you learned about Chinese Remainder Theorem (CRT). Which of the following can be deduced by CRT (ZZ be the ring of integers)?

Z/⟨36⟩≅Z/⟨2⟩×Z/⟨18⟩Z/⟨36⟩≅Z/⟨2⟩×Z/⟨18⟩

Z/⟨36⟩≅Z/⟨3⟩×Z/⟨12⟩Z/⟨36⟩≅Z/⟨3⟩×Z/⟨12⟩

Z/⟨36⟩≅Z/⟨4⟩×Z/⟨9⟩Z/⟨36⟩≅Z/⟨4⟩×Z/⟨9⟩

Z/⟨36⟩≅Z/⟨6⟩×Z/⟨6⟩Z/⟨36⟩≅Z/⟨6⟩×Z/⟨6⟩

ans –  b

1 point

Compute 7−1(mod 5)7−1(mod 5) and 5−1(mod 7)5−1(mod 7) respectively.

3, 3

3, 5

2, 2

4, 3

ans –  b

1 point

Let x=3(mod 5)x=3(mod 5) and x=2(mod 7)x=2(mod 7). Using CRT, compute x(mod 35)x(mod 35).

13

23

30

33

ans –  b

1 point

Let x=3(mod 5)x=3(mod 5) and x=2(mod 7)x=2(mod 7). Compute x(1023+2)(mod 35)x(1023+2)(mod 35). Hint: Use power of CRT to simplify calculations.

23

29

17

0

ans –  a

1 point

Find an efficient algorithm for evaluating a polynomial. In how many R (ring) operations can you evaluate a polynomial of degree n on a single point from R using this algorithm? How much time does it take to evaluate the polynomial on n+1 points using this algorithm n+1 times? In the options (x,y) below – x should be the answer of first question and y should be the answer of second question. As a thinking exercise, compare this with the DFT step of fast multiplication algorithm done in class.

O(n2),O(n3)O(n2),O(n3)

O(n2),O(n2logn)O(n2),O(n2log⁡n)

O(1),O(n)O(1),O(n)

O(n),O(n2)

ans –  b

Yhaa You have done it but next? if YOU Want to your Others NPTEL Computational Number Theory and Algebra Assignment 2 Answer Then Follow US HEREand Join Telegram.