算法和雪崩效应

快捷方式: 差异，相似，杰卡德相似系数，参考。

算法和雪崩效应之间的区别

算法 vs. 雪崩效应

-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。. 在密码学中，雪崩效应（avalanche effect）指加密算法（尤其是块密码和加密散列函数）的一种理想属性。雪崩效应是指当输入发生最微小的改变（例如，反转一个二进制位）时，也会导致输出的不可区分性改变（输出中每个二进制位有50%的概率发生反转）。合格块密码中，无论密钥或明文的任何细微变化都必须引起密文的不可区分性改变。该术语最早由Horst Feistel使用，尽管其概念最早可以追溯到克劳德·香农提出的扩散（diffusion）。 若某种块密码或加密散列函数没有显示出一定程度的雪崩特性，那么它被认为具有较差的随机化特性，从而密码分析者得以仅仅从输出推测输入。这可能导致该算法部分乃至全部被破解。因此，从加密算法或加密设备的设计者角度来说，满足雪崩效应乃是必不可缺的圭臬。 构造一个具备良好雪崩效应的密码或散列是至关重要的设计目标之一。这正是绝大多数块密码采用了乘积密码的原因，也是大多数散列函数使用大数据块的原因。这些特性均使得微小的变化得以通过算法的迭代迅速增殖，造成输出的每一个二进制位在算法终止前均受到输入的每一个二进制位的影响。.