PUMaC 2016 · 加试 · 第 1 题

PUMaC 2016 — Power Round — Problem 1

Your solutions are to be turned in when your team checks in on the morning of PUMaC or emailed to us at pumac2016power@gmail.com by 8AM Eastern Standard Time on the morning of PUMaC, November 19, 2016 with the subject line “PUMaC 2016 Power Round.” Please staple your solutions together, including the power round cover sheet (the last page of this document) as the first page. Each page should also have on it the team number (not team name) and problem number . This team number, which was emailed to your team, is a “T” followed by a three-digit number (for example: “T100”). Solutions to problems may span multiple pages, but staple them in continuing order of proof.

解析

Similarly, A can find the third bit of x , and so on. − 1 − 1 (c) Note that ( k ) ≡ k (mod p ). So there are two possibilities: either f cannot be computed in polynomial time (this is in fact not the case) in which case f is clearly not a one-way function; or f can be computed in polynomial time, in which case A can simply run f on its own input and return the result. 7.2. Number-Theoretic One-Way Functions and Assumptions 7.3. Hard-Core Bits