無論在密碼學(xué)當(dāng)中還是在各種別的算法當(dāng)中，復(fù)雜度分析都是一個(gè)比較重要的用來衡量算法效率的概念。首先說一下歐幾里得算法和擴(kuò)展歐幾里得算法，無論歐幾里得算法還是擴(kuò)展歐幾里得算法他們的復(fù)雜度相同的，是由同一個(gè)問題引申出來的——找到兩個(gè)數(shù)的最大公因數(shù)問題。歐幾里得算法也就是輾轉(zhuǎn)相除法。對(duì)于歐幾里得算法的復(fù)雜度問題之前一直不明白，現(xiàn)在知道每經(jīng)過兩次相除，余數(shù)的位數(shù)必定會(huì)降低1位，由此得到的其復(fù)雜度為2lgn。在密碼學(xué)當(dāng)中的復(fù)雜度衡量經(jīng)常是按位來衡量的，比如說可能我們覺得一次加法的復(fù)雜度是O（1），可是當(dāng)按位衡量時(shí)就跟操作數(shù)位數(shù)有關(guān)了，例如說一個(gè)512位的數(shù)加法就是O（512），（這里的O應(yīng)該是按位算的O，Ob）。如何比較形式的表示加法，減法，乘除的復(fù)雜度呢，就是加法和減法相同為O（lga），而乘除就是O（lga平方），既然對(duì)于歐幾里得算法和擴(kuò)展歐幾里得算法要做2lga次，那么就可以得到歐幾里得和擴(kuò)展歐幾里得算法的復(fù)雜度是O（lga的立方）。但是根據(jù)歐幾里得算法本身的特點(diǎn)，其算法的復(fù)雜度可以降低到O（lga的平方），盡管說與乘除在一個(gè)量級(jí)上，但是還是要比乘除的時(shí)間要長(zhǎng)的，畢竟歐幾里得算法是由除法或者模運(yùn)算構(gòu)成的。

總結(jié)

以上是生活随笔為你收集整理的密码学——复杂度问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。