回分類題庫
d008: 99年彰雲嘉區第三題
關鍵字: 99年彰雲嘉區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 103 Times / 99 Users | Submit : 221 Times / 103 Users | Accepted rate : 96%
題目加入時間 : 2011-09-09 23:19

Content: 简体中文

希爾加密法(Hill Cipher)是運用矩陣乘法計算的替代性加密技術(substitution cipher),由Lester S. Hill在1929年發明。其轉換的方式為:

  1. 首先,將明文(plaintext)的內容分割,每 n 個字視為一小組,分割成許多向量 Pnx1 。若明文長度不為 n 之倍數,則於不足部分均填入字母 X。
  2. 將英文字不分大小寫以整數表示,其中 A=0, B=1, C=2, …, Z=25,找出每個英文字所對應的數字。
  3. 將已知或給定的 Knxn 與每一小組的向量 Pnx1 相乘(作矩陣對向量的乘法)。
  4. 將步驟3計算所得向量的每一個元素均求除以26之餘數(mod 26)。
  5. 將4所得的數字反推找出所對應的英文字即為密文(ciphertext)。

簡單來說,希爾加密法可用下列方式表示:Cnx1=KnxnPnx1,其中 Cnx1 是密文(ciphertext)分割後所形成的向量,Knxn 是加密矩陣,Pnx1 是明文(plaintext)向量。本程式設計題僅需考慮 n=2 的情形,並假設加密矩陣為

範例1.
利用希爾加密法可以將明文:HI TH ER EE  轉成密文 FQOODIQI。轉換的計算過程說明如下:

1.找出各英文字對應之數字並以2個字為一組分作分割,若輸入之字串長度為奇數則於最後加上英文字 X。(例如明文字串為 CHINA 則加上 X 變成 CHINAX )。本範例明文數為偶數故不需加入 X 僅需作切割,如下:

2.字組 HI 經過矩陣對向量的乘法轉換爲 FQ,計算過程如下:

 字組 TH 經過矩陣運算轉換爲 OO,其餘類推。

範例2.
明文為 HSIUPING 時所對應的數字陣列為 [7, 18, 8, 20, 15, 8, 13, 6],經過希爾加密法轉換後,字串 HSIUPING 被加密成字串 JKQONQFM。

輸入資料第一列的數字代表所要加密的字串數,其後每列為一個明文字串。請利用希爾加密法對每一個明文字串加密後輸出。

Input:

輸入資料第一行有一個正整數 N,代表要加密的字串數,之後有 N 行明文字串。

Output:

請輸出加密後的字串。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
HITHEREE
HSIUPING

Sample Output :

FQOODIQI
JKQONQFM

Hint :

Author :

99年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum