Question 41

Question

Question 41

BlackTom AI · Accepted Answer

The security of RSA and many public-key cryptosystems rests on the difficulty of integer factorization.

1) Relevant knowledge points and concepts
- Public-key cryptography (e.g., RSA) uses a modulus N = p * q, where p and q are large primes. The private key depends on knowing p and q.
- Integer factorization: given N, find its prime factors p and q. For sufficiently large N this is believed to be computationally hard for classical computers.
- Complexity of competing tasks: sorting has well-known efficient algorithms (O(n log n)), dividing by zero is undefined (not a computational hardness problem), and face recognition is a machine-learning task (practical but not a cryptographic hardness assumption).

2) Reasoning process step by step
- In RSA, the public key contains N but not p and q. If an attacker can factor N, they can compute phi(N) and derive the private key. Therefore cryptographic security depends on factoring being hard.
- Conversely, if factoring were easy, RSA would be broken. Thus “the difficulty of integer factorization” is the specific hardness assumption underlying RSA-style cryptosystems.

3) Calculations / intermediate steps (complexity context)
- Naive trial division requires checking divisors up to sqrt(N): about O(sqrt(N)) steps.
- The best classical general-purpose algorithm known for large integers is the General Number Field Sieve with heuristic complexity roughly exp((c + o(1))(ln N)^{1/3} (ln ln N)^{2/3}), which grows sub-exponentially and is still infeasible for appropriately large key sizes (e.g., 2048-bit RSA).
- This demonstrates why factoring large N is computationally infeasible in practice.

4) Why the correct answer is correct
- The question targets the fundamental hardness assumption behind many cryptographic systems: integer factorization. That is precisely what secures RSA-like encryption.

5) Why the other options are incorrect
- a) Recognizing human faces is a machine-learning problem, not a cryptographic hardness assumption.
- b) Dividing by zero is undefined, not a computational hardness property.
- c) Sorting very large arrays has well-understood efficient algorithms (O(n log n)); it is not the cryptographic foundation.

6) Conclusion
The correct answer is d. The difficulty of integer factorization. This matches the provided answer.

Question 41单项选择题

类似问题

Which of the following statements are TRUE about an NP‑Hard problem? Select all that apply.

Pick all currently known NP problems that are not in the class P.

When considering P, NP, NP complete, and NP hard

Find the BEST Match for computational complexity with respect to PER LAYER complexity (ie. what is the complexity of a single layer of each wrt the variables below). n denotes sequence length d denotes representation dimension 1: Self-Attention (vanilla) 2: Recurrent (vanilla)

zyBooks_15_2 (Context: ZyBooks Ch. 15.6.2 discusses comparing algorithm performance.) According to the ZyBooks activity you completed, computational complexity analysis allows the efficiency of algorithms to be compared.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单