使用關鍵字生成排列

Question

我必須實現以下算法，該算法將通過爬山在特定密碼的密碼分析中運行數十億次。 該算法產生的標準字母表的置換{A，B，C，...，Y，Z}具有相同字母的7個字母一密鑰K，如下所示：

• 假設K = INGXNDM = {9，14，7，24，14，4，13}
• 從右到左，計數K1 = 9位置在字母表上。 R已到達，所以排列的第一個元素是R：P = {R，...}
• 標記R如前所述，我們將不得不在稍後「跳過」它。
• 從R中，向左計數K2 = 14個位置，我們到達D並將其標記爲已使用。 P = {R，D，...}
• 下一個計數是7，當達到A時，我們循環並考慮Z遵循A，所以我們達到W：將它標記爲已用，P = {R，D， W，...}
• 下一個計數爲24，所以我們達到了V，因爲我們跳過了R，D和W.
• 等等......當K7 = 13已被使用時，我們用K1 = 9
• 所獲得的轉置字母表：RDWVGBL ZHUKNFI PJSAMXT CQOYE

事實上，我需要在解密代碼的逆置換。 我的代碼實現了一個鏈接列表，用於跳過使用的字母。 它在基數0中，所以A = 0，... Z = 25並且返回逆置換Pinv（i）= j，這意味着字母i位於位置j。

#define ALPHALEN 26 
void KeyToPermut(int *K, int * Pinv); 
int previnit[ALPHALEN], prev[ALPHALEN], nextinit[ALPHALEN], next[ALPHALEN]; 

int main() { 
    int l, Pinv[ALPHALEN], K[7] = { 8, 13, 6, 23, 13, 3, 12 }, P[ALPHALEN]; 
    // precalculate links between letters, ordered right to left , from Z to A 
    for (l = 0; l < ALPHALEN; l++) { 
     previnit[l] = l + 1; // prev[A] = B 
     if (previnit[l] >= ALPHALEN) previnit[l] -= ALPHALEN; // prev[Z] = A 
     nextinit[l] = l - 1; // next[B] = A 
     if (nextinit[l] < 0) nextinit[l] += ALPHALEN; // next[A] = Z 
    } 

    KeyToPermut(K, Pinv); // this is the code to be optimized 

    for (l = 0; l < ALPHALEN; l++) P[Pinv[l]] = l; // calculate direct permutation 
    for (l = 0; l < ALPHALEN; l++) printf("%c", P[l] + 65); 
    printf("\n"); 
} 

void KeyToPermut(int *K, int * Permut) { 
    int l, keyptr=0, cnt=0, p=0; 
    // copy prev[] and next[] from precalculated arrays previnit[] and nextinit[] 
    for (l = 0; l < ALPHALEN; l++) { 
     prev[l] = previnit[l]; 
     next[l] = nextinit[l]; 
    } 

    while (1) { 
     for (l = 0; l <= K[keyptr] % (ALPHALEN-cnt); l++) p = next[p]; 

     Permut[p] = cnt++; 
     if (cnt < ALPHALEN) 
     { 
      prev[next[p]] = prev[p];  // link previous and next positions 
      next[prev[p]] = next[p]; 
      keyptr++; 
      if (keyptr >= 7) keyptr = 0; // re-use K1 after K7 
     } 
     else 
      break; 
    } 
} 

我有2個問題：

1. 我怎麼能優化KeyToPermut的代碼？剖析器顯然表明跨鏈的for循環是瓶頸。可能有一種方法避免鏈接列表...？
2. 顯然關鍵空間不是26！但要小得多：26^7，所以只有26的一個子集！可以生成。你知道生成的排列有多特殊嗎？他們屬於已知類別的排列嗎？例如，我無法確定（迄今爲止）這些排列週期中的任何模式。

我使用VS2013和C，項目的其他部分都是CUDA代碼。 （x64平臺）

謝謝您的關注。

背景信息：密碼使用的加密方案使用長度爲7的4個密鑰K.因此，要查找明文的理論密鑰空間是26^28，即131位。該方法可以使用其他密鑰長度：從1到25的任何值都可以工作。

Answer 1

我該如何優化KeyToPermut中的代碼？分析器顯然是 表示跨鏈的for循環是瓶頸。 可能有避免鏈接列表的方法...？

我沒有找到一個更好的方法避免了鏈表，但我們可以用一個單獨而不是雙向鏈表一個做，因爲需要以前的位置可以從for循環的最後一次迭代中獲得。

void KeyToPermut(int *K, int *Permut) 
{ 
    int l, keyptr=0, cnt=0, p=0, prev; 
    // copy next[] from precalculated array nextinit[] 
    for (l = 0; l < ALPHALEN; l++) next[l] = nextinit[l]; 
    while (1) 
    { 
     for (l = 0; l <= K[keyptr] % (ALPHALEN-cnt); l++) prev = p, p = next[p]; 
     Permut[p] = cnt++; 
     if (cnt < ALPHALEN) 
     { 
      next[prev] = next[p];   // link previous to next position 
      p = prev; 
      keyptr++; 
      if (keyptr >= 7) keyptr = 0; // re-use K1 after K7 
     } 
     else 
      break; 
    } 
} 

這節省了大約10％的功能運行時間。