Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 4176

FINAL EXAM

Due 11 AM, 05/05/2023

1.  By using Solovay-Strassen algorithm, verify whether n = 804509 is a prime or composite number .

2.  Suppose that n = 90581 and b = 17993 in the RSA Cryptosystem .  Factor n by using Wiener’s algorithm .

3.  By using Pollard p − 1 algorithm, factor 49349 .  Write all your steps clearly.  Simply writing down the factors, without any work, will not get any credit .

4.  Consider p = 353 where 3 is a primitive element modulo 353 .  Using Pohlig-Hellmann algorithm, solve 3x  ≡ 135 mod 353 for the exponent x modulo 352 .

5.  Consider p = 383 .   It can be checked that α = 2 has order  191 in Z3(*)83 .   Use  Pollard rho discrete logarithm algorithm to compute log2 228 in Z3(*)83 .

6.  Given that 5 is a primitive element modulo 47, solve 10 ≡ 5a    mod 47 by using Shank’s algorithm .

7.  Consider the elliptic curve E defined by y2  = x3  + 1 .  It is known that the only points on this curve that have integer coordinates are (−1, 0) , (0 , ±1) , (2 , ±3) .Take these five points, along with the sixth point O that is the “point at infinity”  as defined in the class .  Show that these six points, under the point-addition operation defined in class, form a group by constructing a group table for these six points .

8.  Let E be the elliptic curve y2  = x3  + x + 26 defined over Z127  and consider the point P = (2 , 6) on E . Using the NAF representation of 27, compute 27P with the help of Double-and-Add or Subtract algorithm .  Show the partial results during each iteration of the algorithm .

9. Alice sets up an NTRU system with numerical keys (that is, a congruential cryptosystem), with q = 918293817 and private keys (f,g) = (19928 , 18643) .

(a) What is Alice’s public key h?

(b) Alice receives the ciphertext c = 619168806 from Bob . What is the plaintext?

(c)  Bob sends Alice a second message by encrypting the plaintext m = 10220 using the random element r =

19564 . What is the ciphertext that Bob sends to Alice?

10.   (a) Alice and Bob agree to communicate using NTRUEncrypt with (N,p,q) = (7 , 3, 37) .  Alice’s private key is f (x) = −1 + x − x3 + x4 + x5 . You can check that F3 (x) = 1 + x − x2 + x4 + x5 + x6  in R3 . Alice receives the ciphertext:

c(x) = 2 + 8x2 − 16x3 − 9x4 − 18x5 − 3x6

from Bob .  Decipher the message and find the plaintext .

(b) Alice and Bob decide to communicate using NTRUEncrypt with parameters (N,p,q) = (7 , 3 , 29) .  Alice’s public key is:  h(x) = 3 + 14x − 4x2  + 13x3  − 6x4  + 2x5  + 7x6 .   Bob sends Alice the plaintext message m(x) = 1 + x − x2  − x3  − x6  using the random element r(x) = −1 + x2  − x5 + x6 .  What ciphertext does

Bob send to Alice?

11.  Bonus Problem (5 points): Are ’ellipses’ related to ’elliptic curves’ ? As it turns out, there is actually a beautiful story here! To see this, go to

https://www.maa.org/sites/default/files/pdf/upload_library/2/Rice-2013.pdf or click here

and read the attached paper .  Write a couple of paragraphs summary (in less than 200 words) of this paper to explain how these terms are related .