課程名稱︰應用代數
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰
考試日期（年月日）︰2007/1/15
考試時限（分鐘）：about 3 hours
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
上課課本：Darel W.Hardy/Carol L.Walker Applied Algebra
Part I (3 points each)
(每一題都有第五個選項"以上皆非"，懶得打了)
1.Which polynomial over GF5 has the splitting field GF625?
(A)x^25-1
(B)x^25-x
(C)X^625-1
(D)x^625-x^5
2.Which is the generation polynomial of a one-error correcting Reed-Solomon
code over GF17? Note that a 3 is a primitive element of GF17.
(A)x^2+11x+15
(B)x^2+4x+13
(C)x^2+12x+15
(D)x^2+5x+10
3.Which relation between the coefficient vector x=[x_0 x_1 ... x_n-1]^T
(T for transpose) and the function value vector
y=[f(ω^0) f(ω^1) ... f(ω^n)]^T is correct?
Here f(t)=(x0)+(x1)*t+...(x_n-1)*t^(n-1),ω is a primitive n-th root of 1,
and V(u) denotes the Vandermonde matrix generated by u.
(A)x = n^(-1)V(ω^(-1))y
(B)y = n^(-1)V(ω)x
(C)x = V(ω)y
(D)y = V(ω^(-1))x
4.Which problem has been proved to be in the class P?
(A)General Knapsack
(B)Factoring
(C)Primality proving
(D)Graph isomorphism
5.Which operaion is the last one in the Rijndael encryption algorithm?
(A)Shift Row
(B)Mix Column
(C)Add Round Key
(D)Sub Byte
6.Which quotient ring is isomorphic to GF343?
(A)GF7[x]/<x^3+3x+6>
(B)GF7[x]/<x^3+3x+5>
(C)GF7[x]/<x^3+3x+4>
(D)GF7[x]/<x^3+3x+3>
7.α屬於GF8 is a root of x^3+x+1.Whose monimal polynomial is x^3+x^2+1?
(A)α^3
(B)α^4
(C)α^2+α
(D)α^3+α
8.Which statement is FALSE about RSA with modulus n=pq, public exponent e,
and private exponent d?
(A)Breaking RSA is equivalent to factoring n.
(B)Knowing d is equivalent to factoring n.
(C)Knowing ψ(n) is equivalent to factoring n.
(D)Its security relies on the difficulty of finding d from n and e.
9.Which statement about BCH code is FALSE?
(A)A primitive element α in GFq is chosen,where q=p^n
(B)To correct t errors,the generating polynomial
g(x)= lcm[m1(x),m2(x)...mt(x)] is set, where mi(x) is the minimal
polynomial of α^i
(C)The plaintext polynomial a(x) is of degree at most q-deg(g(x))-2
(D)Reed-Solomon code is a special case of BCH code
10.Which is NOT one of the basic operaions of the IDEA encryption?
(A)Addition modulo 2^16
(B)Multiplication modulo 2^16+1
(C)Bitwise eXclusive OR
(D)Multiplicative inverse molulo 2^16+1
PartII (3 points each)
● A toy RSA signature scheme has the public key n=143 and e=7
(a) Verifying a signature s1=5, we obtain the value m1=_____
(b) To sign a message, we need its private key d=_____
(c) Signing a message m2=67, we obtain its signature s2=_____
● J={ 364a+455b+585c | a,b,c屬於Z } = <g> is a principle ideal in the
integer ring Z. The positive generator g = _____
● Fill in the data block size of IDEA and the number of rounds of DES
(表格省略，整題其實只要考生填出DES的number of rounds和IDEA的Block size)
●The following is a part of the reference code of AES from the book
"The Design of Rijndael" written by J.Daemon and V.Rijmen:
(底下給了兩個array，分別是GF256以x+1為generator的對數表與反對數表)
In AES, m(x)=x^8+x^4+x^3+x+1 is selected to generate GF256.
As we mentioned in class, the above tables LogTable and ALogTable
are constructed by the primitive element x+1 of GF2[x]/<m(x)>
(a) (x+1)^n mod m(x) = x^2, then n = _____
(b) (x+1)^199 mod m(x) = _____ (a polynomial in GF2[x] of degree<8)
(c) (x^6-x)^(-1) mod m(x) = _____ (a polynomial in GF2[x] of degree<8)
(d) Finish the subroutine computing patched multiplicative inverses:
word8 inverse(word8 a){
if (a) return ALogTable[_____]
else return 0;
}
(註：word8是上面那兩個array內存物的datatype)
●Being multiplied by 31 modulo 105, the super-increasing sequence
{2.3.6,13,27,52} is transformed to {62,93,81,88,102,37}, which is the
public key of a toy Merkle-Hellman Knapsack cryptosystem.
(a) The plaintext 100101 is encrypted to the ciphertext _____
(b) With the private key 31^-1≡61 (mod 105), the ciphertext 268 is
decrypted to the plaintext _____ (a string of 6 bits)
●Assume that q(x)=x^4+x+1 is used to construct a BCH code that corrects
a single error with plaintext polynomial a(x)屬於GF2[x].
(a) The largest possible degre for a(x) is _____.
(b) Suppose that the polynomial x^9+x^7+x^6+x^3+1 is received,
then the decoded plaintext is _____ (bit string)
●[Integer Factoring]
(a)33221 = _____×_____ Hint:19845^2=5250^2 (mod33221)
(b)36391 = _____×_____ Hint:ψ(36391)=36000
●[Lagrange Interpolation and Shamir's Secret Sharing]
(a) p(x) is a polynomial of degree ≦ k passing through k+1 points (i,t_i)
for i=1,2,3...,k+1, then p(x) = _____
(b) Consider a toy secret sharing scheme over GF17. Suppose the secret"11"
is hidden as the constant of p(x)=ax^2+bx+11. The points (1,14) and
(2,4) are distributed to two participants. Then the point given to the
third participant is (3,_____).
PartIII
●Classify each of the following polynomials in GF5[x] as (A)reducible,
(B)irreducible but not primitive, or(C)irreducible and primitive.
Prove your answers.
(1) x^2+x+1 (2)x^2+x+2 (3)x^2+x+3
●K=GF2[x]/<x^3+x+1> which is isomorphic to GF8 is a finite field. For
each of the following mapping from K into itself, prove or disprove that
it is an automorphism.
(1) f(x)=x^2+1 (2)f(x)=x^2+x
--
＠＠＠＠ real◇temper ◣
＠＠ ＠＠ ～● ○～ ～○●～ ◢◤
＠◤□ □＠ ～○ ～●○～ ～●○～ ～○ ◢◤
◣ """◢
◤ ◣◢ ◥ 2 3 4 1
｜ ◆ ｜ 1Ｄ ＋ 1Ｔ ─→ 2Ｈｅ ＋ 0ｎ ＋ 18.06MeV
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.102.171