Сгенерировать подстановку с помощью ключевого слова

Question

Я должен реализовать следующий алгоритм, который будет выполняться несколько миллионов раз в криптоанализе определенного шифрования, путем восхождения на холм. Алгоритм производит перестановку стандартного алфавита {А, В, С, ..., Y, Z} с ключом K 7 букв алфавита же, следующим образом:

• Пусть K = INGXNDM = {9, 14, 7, 24, 14, 4, 13}
• Слева направо, K1 = 9 позиций на алфавите. R достигается, поэтому первым элементом перестановки является R: P = {R, ...}
• Mark 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)

Благодарим за внимание.

Фоновая информация: схема шифрования, используемая шифром, использует 4 ключа K длины 7. Таким образом, теоретическое пространство ключей, которое нужно изучить для поиска открытого текста, составляет 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% времени выполнения функции.