NPTEL Computational Number Theory and Algebra Assignment 9 Answer

Let f=x3+13x2+50x+56f=x3+13×2+50x+56. In LLL algorithm, the first step involves computing f (mod p), where p is a “suitable” prime. Which of the following primes will LLL algorithm choose?

Let L{v1;v2}L{v1;v2} be the lattice generated by vectors v1,v2v1,v2. Then, which of the following is true?

Let f(x)∈Fp[x]f(x)∈Fp[x] be a non-constant univariate polynomial where pp is prime. For any a∈Fpa∈Fp, call f(x+a)f(x+a) the ‘shift of ff by aa‘. Which of the following is true?

1. If ff is reducible then every shift of ff is reducible.

2. If ff is irreducible then some shift of ff may not be irreducible.

Let f:=x−y2f:=x−y2 and g:=x2−yg:=x2−y are two polynomials in Fp[x,y]Fp[x,y] with pp prime. Which of the following is true about any common zero (a,b)∈F2p(a,b)∈Fp2 of ff and gg?

The L3L3 algorithm to factor a univariate polynomial f∈Q[x]f∈Q[x] (as discussed in lectures) requires?

1. Factoring in finite fields.

2. Hensel’s lifting.