Nhiều chương trình mã hóa và các giao thức, đặc biệt là những người dựa trên công keycryptography, có cơ bản hoặc cái gọi là "sách giáo khoa mật mã" phiên bản, như các versionsare thường các đối tượng cho nhiều sách giáo khoa về mật mã. | able to prove if this is necessary . to prove . Also no one has so far been able to demonstrate the opposite case . to prove . The question V . MP is a well-known open question in theoretic computer science. Definition Lower and Upper Complexity BoundsA quantity B is said to be the lower complexity bound for a problem P if any algorithm A solving P has a complexity cost C A B. A quantity U is said to be an upper bound for a problem P if there exists an algorithm A solving P and A has a complexity cost C A -U. It is usually possible and easy to identify the lower bound for any problem in namely to pinpoint precisely the polynomial bound that declares the necessary number of steps needed for solving the problem. Machine Div3 Example provides such an example it recognizes an n-bit string in precisely n steps . using the least possible number of steps permitted by the way of writing the input instance. 1 r rTT However for problems in it is always difficult to identify the lower complexity bound or even finding a new . lowered upper bound. Known complexity bounds for NP problems are V ỈV all upper bounds. For example we have demonstrated that L J is an upper bound for answering Problem SQUARE-FREENESS with input N via trial division . An upper bound essentially says only this number of steps are needed for solving this problem without adding an important untold part but fewer steps may be possible. In fact for Problem SQUARE-FREENESS the Number Field Sieve method for factoring N has complexity given by . VN . which has much fewer steps than L but is still an upper bound. One should not be confused by the lower bound and a lower bound. The latter often appears in the literature . used by Cook in his famous article 80 that discovered Satisfiability Problem being NP-complete to mean a newly identified complexity cost which is lower than all known ones hence a lower bound . Even the identification of a not the lower bound usually requires a .
