![](https://scientia-potentia-est.com/wp-content/uploads/2023/06/Eulers_totient_function.png)
最大公因數: ,可以利用gcd判斷兩個整數是不是互質:
,若兩數互質代表兩數的最大公因數就是1。
一個合成數可以拆成質數分解:
,每個
都只會出現一次。
有了前面幾種工具,就可以建構出尤拉函數:
尤拉函數能夠幫助我們快速找出在之下所有與
互質的整數個數。
最大公因數: ,可以利用gcd判斷兩個整數是不是互質:
,若兩數互質代表兩數的最大公因數就是1。
一個合成數可以拆成質數分解:
,每個
都只會出現一次。
有了前面幾種工具,就可以建構出尤拉函數:
尤拉函數能夠幫助我們快速找出在之下所有與
互質的整數個數。
在數論當中群(Group)是其中一種重要的概念,代數最基本由三種結構組成:群 Group, 環 Ring, 體 Field,而群作為最基本的代數結構,也是我們在密碼系統中常常使用的,故需要先了解群的定義對於後續密碼系統分析會比較方便。
首先需要一個問題叫做布林公式(Boolean formula)會像:
裡面的每一個符號稱作variable,每一個variable可以給0或1的值就像在做.