چه حکایت از فراقت که نداشتم ولیکن
آخرین مطالب
امکانات وب
I can think of four major hurdles which are not entirely independent:
- NP-hardness only gives you information about complexity in the limit. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any fixed problem size (e.g. a given "key"), the problem is not necessarily hard just because it is NP-hard.
- NP-hardness only considers worst-case time. Many, even most of all instances may be easy to solve with existing algorithms. Even if we knew how to characterise the hard instances (afaik, we don't), we'd still have to find them.
- You need to have huge instances that are hard to solve. Searching for (products of) large prime numbers is easy in the sense that the search space is flat: one number is either suited or not. Imagine using graphs: out of all 2n(n−1)2n(n−1) graphs of size for large , you have to find those that have nice properties.
- You need some kind of reversability. For example, any integer is uniquely described by its prime factorisation. Image we would want to use TSP as encryption method; given all shortest tours, can you (re)construct the graph they came from uniquely?
Note that I have no expertise in cryptography; these are merely algorithmic resp. complexity-theoretic objections.
چه حکایت از فراقت که نداشتم ولیکن...ما را در سایت چه حکایت از فراقت که نداشتم ولیکن دنبال میکنید
برچسب: نویسنده: بازدید: 191