﻿﻿ 靠谱数学作业代写✔️数学代写✔️专业Math代考
2023-01-04

# Instructions

Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn in a physical copy in class, 3) write answers by hand and send a scanned PDF file. We prefer to read succinct and precise answers. If you can be precise while being succinct with your answers, please try.   How multiple choice is graded. Multiple choice questions may have multiple correct answers.  If there are multiple correct answers, then each correct answer is worth 1/N of the total points for the question. You lose 1/N points for every wrong answer you circle. The total cannot go negative.  In code, score points * max(num correct – num wrong) / total correct

Indistinguishability [6 pts]

1. (3 pts) If {Xn}n is computationally indistinguishable from {Yn}n, {Yn}n is computationally indistin- guishable from {Zn}nthen (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n

(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}n

2.  If Xn n can be distinguished from Yn nYn n can be distinguished from Zn nthen (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n

(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}n

# 2 Useful Asymptotical Notations [6points]

(No need to prove throughout this question.)

## 2.1 [2pts]

Among the following functions in n, please select all that are negligible functions in n:

a. 12 b. 1 c. 1

d. n3 e. n log log log n f. 2n g. nlog log n

2n 2n

nlog log n

## 2.2 [2pts]

Suppose that f1(n), f2(n) are negligible functions in n. Let g(n) denote some fixed polynomial in n. Whicof the following must be negligible functions in n: a. f1(n) + f2(n) b. f1(n)f2(n) c. f1(n)g(n) d. g(n) e. f1(n) f. f1(n)g(n)

## 2.3 [2pts]

(Let g1(n), g2(n) denote two fixed polynomials in n. Which of the following must be polynomial in n:

a. g1(n) + g2(n) b. g1(n)g2(n) c. g1(n)g2(n) d. g1(n) + 203942 e. g1(n) + 2n f. g1(n)100

g. 2g1(n)

# 3 Pseudorandomness [10pts]

## 3.1 Pseudorandom Generators [5pts]

Let tt {01}λ → {01}λ be a PRG. Circle all PRGs below. (No need to prove)

a. ttj(s) = if |s1024 then tt(selse 0A(|s|)

b. ttj(s1 || s2tt(s1⊕ tt(s2), where |s1|s2λ c. ttj(s1

### 在线提交订单 