Scientia- Computational Complexity
- Space Complexity
- 10 11 月, 2023
- 0 Comments
Scientia空間複雜度
定義1：存在一組Deterministic Turing Machine M對於所有的輸入language會停住，M的space complexity可以用一個function f表達，f:[latex]N \rightarrow N[/latex], 而[latex]f(n)..
- Scientia
- Computational Complexity
- NP-Complete
- 9 11 月, 2023
- 0 Comments
NP-completeness
首先需要一個問題叫做布林公式(Boolean formula)會像：$$\phi = (\overline{x} \wedge y) \vee (x \wedge \overline{z})$$裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做布..
時間複雜度
通長在測量複雜度的時候會使用兩種分析方法：Worst-case analysisAverage-case analysis定義一個M是Deterministic Turing Machine並且會根據輸入決定停止規範M的執行時間或者時間複雜度可以表示成一個function…
- Scientia
- Enumerator
- Non-Deterministic
- 5 11 月, 2023
- 0 Comments
不同的Turing Machine
讓Turing Machine擁有多組tape
[latex]\delta: Q \times \Gamma^{k} \rightarrow Q \times \Gamma^{k} \times {L, R}^{k}, k[/latex]: tapes的數量…
- Scientia
- Computational Complexity
- Turing Machine
- 4 11 月, 2023
- 0 Comments
Turing Machine
圖靈機是由Alan Turing在1936年提出的概念，現今世界上所有的計算機不管是多複雜的架構都可以使用圖靈機的概念設計出來，其主要核心精神如下圖
- Scientia
- Chinese Remainder Theorem
- Isomorphism
- 3 6 月, 2023
- 0 Comments
中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性
中國餘式定理Chinese Remainder Theorem(CRT)在密碼理論當中屬於重要的概念，尤其在RSA密碼系統裡也扮演重要的角色，而符合CRT的聯立方程式具有同構的特性。
- Scientia
- Algorithm
- Modular Arithmetic
- 3 6 月, 2023
- 0 Comments
Square Multiply 演算法
此演算法主要是針對a^b mod n在b很大而計算機通常算不太出來的時候使用的方法。
- Scientia
- Euler Totient Function
- 尤拉函數
- 2 6 月, 2023
- 0 Comments
尤拉函數 Euler’s totient function
最大公因數:gcd(a, b)，可以利用gcd判斷兩個整數是不是互質: gcd(a, b) = 1，若兩數互質代表兩數的最大公因數就是1。
- Scientia
- Complexity
- Measure
- 2 6 月, 2023
- 0 Comments
整數複雜度量測
我們在密碼理論(Theory of Cryptology)又或者計算理論(Theory of Computation)裡需要去測量輸入的整數複雜度，通常會用整數的長度(bits)當作標準。
