Trending News: 群之可解性威脅情報指標 Indicators of compromise (IoC)Palo Alto Firewall URL過濾以及 Application Block Page群NP-Completeness異常檢測的問題分類異常檢測的方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道

Scientia Potentia Est

保持好奇心並付諸行動

尤拉函數 Euler’s totient function

Scientia
密碼理論
2 6 月, 2023
0 Comments

最大公因數: $gcd(a, b)$ ，可以利用gcd判斷兩個整數是不是互質: $a \perp b: gcd(a, b) = 1$ ，若兩數互質代表兩數的最大公因數就是1。

一個合成數 $n$ 可以拆成質數分解: $n = p_{1}^{e_{1}-1}p_{}2^{e_{2}-1}\cdot\cdot\cdot p_{k}^{e_{k}}$ ，每個 $p$ 都只會出現一次。

有了前面幾種工具，就可以建構出尤拉函數:

$\varphi(n) = \| \{x | x \perp n, 1 \leq x \leq n-1 \} \| = p_{1}^{e_{1}-1}p_{}2^{e_{2}-1}\cdot\cdot\cdot p_{k}^{e_{k}-1}(p_{1}-1)(p_{2}-1) \cdot\cdot\cdot (p_{k}-1)$

尤拉函數能夠幫助我們快速找出在 $n$ 之下所有與 $n$ 互質的整數個數。

Scientia

我是Scientia，研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Hardware Security以及Anomaly Detection.