Method and apparatus for data permutation/division and recording medium with data permutation/division program recorded thereon

A data permutation/division method in which 4 k-bit long registers are provided, k being an integer, and 16 pieces of k-bit data {a4i+j}, where 0≦i≦3, 0≦j≦3, are permuted and divided into a set {a4(i+j mod 4)+j}, where 0≦i≦1, 0≦j≦3, and a set {a4(i+j mod 4)+j}, where 2≦i≦3, 0≦j≦3, said method comprising the steps of:

• (a) storing {a4i+j} in a register Ti for each i, where 0≦j≦3 and 0≦i≦3;
• (b) rotating the value of each of registers T0 and T2 in one direction for k bits;
• (c) concatenating said registers T0 and T2 into a virtual 8 k-bit long register, shifting its stored data in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T4;
• (d) concatenating registers T1 and T3 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T5;
• (e) concatenating registers T2 and T0 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T6;
• (f) concatenating registers T3 and T1 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T7;
• and
• (g) outputting the data of said registers T4, T5 and the data of said registers T6, T7 as two groups.

A data permutation/division apparatus which permutes and divides 16 pieces of k-bit data {a4i+j}, where 0≦i≦3, 0≦j≦3, are into a set {a4(i+j mod 4)+j}, where 0≦i≦1, 0≦j≦3, and a set {a4(i+j mod 4)+j}, where 2≦i≦3, 0≦j≦3, said apparatus comprising:

• four 4 k-bit long registers Ti each having stored therein data {a4i+j} in a register Ti for each i, where 0≦j≦3 and i=0, 1, 2, 3;
• means for storing the AND of the value of a register T0 with a value (23k−2k) in a register T0′, the AND of the value of a register T2 with a value (24k−23k+2k−1) in register T2′ and the OR of the values of said registers T0′ and T2′ in a register T4;
• means for storing the AND of the value of a register T1 with a value (22k−1) in a register T1′, the AND of the value of a register T3 with a value (24k−22k) in a register T3′ and the OR of the values of said registers T1′ and T3′ in a register T5;
• means for storing the AND of the value of said register T0 with said value (24k−23k+2k−1) in a register T0″, the AND of the value of said register T2 with said value (23k−22k) in a register T2″ and the OR of the values of said registers T0″ and T2″ in a register T6;
• means for storing the AND of the value of said register T1 with said value (24k−22k) in a register T1″, the AND of the value of said register T3 with said value (22k−1) in a register T3″ and the OR of the values of said registers T1″ and T3″ in a register T7;
• and
• (f) outputting the data of said registers T4, T5 and the data of said registers T6, T7 as two groups.

A data permutation/division apparatus which permutes and divides 16 pieces of k-bit data {a4i+j}, where 0≦i≦3, 0≦j≦3, are into a set {a4(i+j mod 4)+j}, where 0≦i≦1, 0≦j≦3, and a set {a4(i+j mod 4)+j}, where 2≦i≦3, 0≦j≦3, said apparatus comprising:

• four 4 k-bit long registers Ti each having stored therein data {a4i+j} in a register Ti for each i, where 0≦j≦3 and i=0, 1, 2, 3;
• means for rotating the value of each of registers T0 and T2 in one direction for k bits;
• means for concatenating said registers T0 and T2 into a virtual 8 k-bit long register, shifting its stored data in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T4;
• means for concatenating registers T1 and T3 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T5;
• means for concatenating registers T2 and T0 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T6;
• means for concatenating registers T3 and T1 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T7;
• and
• means for outputting the data of said registers T4, T5 and the data of said registers T6, T7 as two groups.

A recording medium having recorded thereon a data permutation/division program in which 4 k-bit long registers are provided, k being an integer, and 16 pieces of k-bit data {a4i+j}, where 0≦i≦3 and 0≦j≦3, are permuted and divided into a set {a4(i+j mod 4)+j}, where 0≦i≦1 and 0≦j≦3, and a set {a4(i+j mod 4)+j} where 2≦i≦3 and 0≦j≦3, said program comprising the steps of:

• (a) storing {a4i+j} in a register Ti for each i, where 0≦j≦3 and i=0, 1, 2, 3;
• (b) storing the AND of the value of a register T0 with a value (23k−2k) in a register T0′, the AND of the value of a register T2 with a value (24k−23k+2k−1) in register T2′ and the OR of the values of said registers T0′ and T2′ in a register T4;
• (c) storing the AND of the value of a register T1 with a value (22k−1) in a register T1′, the AND of the value of a register T3 with a value (24k−22k) in a register T3′ and the OR of the values of said registers T1′ and T3′ in a register T5;
• (d) storing the AND of the value of said register T0 with said value (24k−23k+2k−1) in a register T0″, the AND of the value of said register T2 with said value (23k−2k) in a register T2″ and the OR of the values of said registers T0″ and T2″ in a register T6;
• (e) storing the AND of the value of said register T1 with said value (24k−22k) in a register T1″, the AND of the value of said register T3 with said value (22k−1) in a register T3″ and the OR of the values of said registers T1″ and T3″ in a register T7;
• and
• (f) outputting the data of said registers T4, T5 and the data of said registers T6, T7 as two groups.

A recording medium having recorded thereon a data permutation/division program in which 4 k-bit long registers are provided, k being an integer, and 16 pieces of k-bit data {a4i+j}, where 0≦i≦3 and 0≦j≦3, are permuted and divided into a set {a4(i+j mod 4)+j} where 0≦i≦1 and 0≦j≦3, and a set {a4(i+j mod 4)+j}, where 2≦i≦3 and 0≦j≦3, said program comprising the steps of:

• (a) storing {a4i+j} in a register Ti for each i, where 0≦j≦3 and 0≦i≦3;
• (b) rotating the value of each of registers T0 and T2 in one direction for k bits;
• (c) concatenating said registers T0 and T2 into a virtual 8 k-bit long register, shifting its stored data in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T4;
• (d) concatenating registers T1 and T3 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T5;
• (e) concatenating registers T2 and T0 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T6;
• (f) concatenating registers T3 and T1 into a virtual 8 k-bit long register, shifting its stored contents in an arbitrary direction for 2 k bits, then extracting therefrom 4 k-bit data at the end thereof in the shift direction, and storing said extracted 4 k-bit data in a register T7;
• and
• (g) outputting the data of said registers T4, T5 and the data of said registers T6, T7 as two groups.

A data permutation method in which 16-byte input data set, in units of 4 bytes, in 4 k-bit long registers is permuted, where 1 byte is k-bit, k being an integer equal to or greater than 1, said method comprising the steps of:

• (a) calculating the AND of 4-byte long first mask data with the data of said first register and the AND of 4-byte long second mask data with the data of said third register, and ORing said two ANDs to obtain first output data;
• (b) calculating the AND of 4-byte long third mask data with the data of said second register and the AND of 4-byte long fourth mask data with the data of said fourth register, and ORing said two ANDs to obtain second output data;
• (c) calculating the AND of said second mask data with the data of said first register and the AND of said first mask data with the data of said third register, and ORing said two ANDs to obtain third output data;
• (d) calculating the AND of said fourth mask data with the data of said second register and the AND of said third mask data with the data of said fourth register, and ORing said two ANDs to obtain fourth output data;
• and
• (e) outputting said first to fourth output data as permuted data;
• wherein all bits of predetermined two of four bytes of said first mask data are “1s,” all bits of the remaining two bytes are “0s,” said second mask data is complementary to said first mask data, said third mask data is a 1-byte rotated version of said first mask data, and said fourth mask data is complementary to said third mask data.

A data permutation method in which 16-byte input data set, in units of 4 bytes, in 4 k-bit long registers is permuted, where 1 byte is k-bit, k being an integer equal to or greater than 1, said method comprising the steps of:

• (a) rotating the data of said first and third registers in one direction for 1 byte and concatenating them into first concatenated data;
• (b) concatenating the data of said second and fourth registers into second concatenated data;
• (c) shifting said first and second concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as first and second output data;
• (d) concatenating said shifted data of said third and first registers into third concatenated data;
• (e) concatenated the data of said fourth and second registers into fourth concatenated data;
• (f) shifting said third and fourth concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as third and fourth output data;
• and
• (g) outputting said first to fourth output data as permuted data.

A data permutation method in which 16-byte input data set, in units of 4 bytes, in 4 k-bit long registers is permuted, where 1 byte is k-bit, k being an integer equal to or greater than 1, said method comprising the steps of:

• (a) calculating the AND of 4-byte long first mask data with the data of said first register and the AND of 4-byte long second mask data with the data of said third register, and ORing said two ANDs to obtain first output data;
• (b) concatenating the data of said second and fourth registers into first concatenated data;
• (c) shifting said first concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as second output data;
• (d) calculating the AND of 4-byte long second mask data with the data of said first register and the AND of said first mask data with the data of said third register, and ORing said two ANDs to obtain third output data;
• (e) concatenating the data of said fourth and second register into second concatenated data;
• (f) shifting said second concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as fourth output data;
• and
• (g) outputting said first to fourth output data as permuted data;
• wherein all bits of predetermined two of four bytes of said first mask data are “1s,” all bits of the remaining two bytes are “0s,” and said second mask data is complementary to said first mask data.

A data permutation method in which 16-byte input data set, in units of 4 bytes, in 4 k-bit long registers is permuted, where 1 byte is k-bit, k being an integer equal to or greater than 1, said method comprising the steps of:

• (a) rotating the data of said first and third registers in one direction for 1 byte and concatenating them into first concatenated data;
• (b) shifting said first concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as first output data;
• (c) calculating the AND of 4-byte long first mask data with the data of said second register and the AND of 4-byte long second mask register with the data of said fourth register, and ORing the two ANDs to obtain second output data;
• (d) concatenating said rotated data of said third and first registers into second concatenated data;
• (e) shifting said second concatenated data in an arbitrary direction for 2 bytes and extracting therefrom 4-byte data at one end thereof in the shift direction as third output data;
• (f) calculating the AND of said second mask data with the data of said second register and the AND of said first mask data with the data of said fourth register, and ORing the two ANDs to obtain fourth output data;
• and
• (g) outputting said first to fourth output data as permuted data;
• wherein all bits of predetermined two of four bytes of said first mask data are “1s,” all bits of the remaining two bytes are “0s” and said second mask data is complementary to said first mask data.

An inverse calculating apparatus comprising:

• input means for storing an input x in storage means;
• storage means for storing integers n and i and 2n-bit integers x, y and c, where said integers n and i are equal to or greater than 1;
• first b-initializing means for calculating [x/2] using said x stored in said storage means and storing the calculation result as said b in said storage means, where [x] is the maximum integer not exceeding x;
• a-initializing means for storing the least significant bit of said b as a in said storage means;
• second b-initializing means for calculating [(ax+b)/2] using said a, x and b stored in said storage means and updating said b stored in said storage means with the calculation result;
• y-initializing means for acquiring low-order two bits of said x stored in said storage means and storing them as said y in said storage means;
• i-initializing means for setting said i in said storage means to 1;
• a-updating for calculating by using said b and y stored in said storage means and updating said a stored in said storage means with the calculation result;
• b-updating means for calculating [(b+ax)/(2{circumflex over ( )}(2i))] using said a, b, x and i stored in said storage means and updating said b stored in said storage means with the calculation result, where p{circumflex over ( )}q represents the q-th power of p;
• y-updating means for calculating y+a×2{circumflex over ( )}(2i) using said a, y and i stored in said storage means and updating said y stored in said storage means with the calculation result;
• i-updating means for updating said i stored in said storage means to i+1;
• control means for reading out said i and n from said storage means and actuating said a-updating means, said b-updating means, said y-updating means and said i-updating means one after another until i=n;
• and
• output means for outputting said y stored in said storage means.

A recording medium having recorded thereon a program for the execution by a computer of an inverse calculating apparatus, said program comprising the steps of:

• (a) storing an input 2n-bit integer x in storage means, n being an intger equal to or greater than 1;
• (b) reading out said x from said storage means, calculating [x/2] and storing the calculation result as a 2n-bit integer b in said storage means, where [x] is the maximum integer not exceeding x;
• (c) reading out said b from said storage means and storing the least significant bit of said b as a 2n-bit integer a in said storage means;
• (d) reading out said a, x and b from said storage means, calculating [(ax+b)/2], and storing the calculation result as said b in said storage means;
• (e) reading out said x from said storage means, acquiring low-order two bits of said x, and storing said low-order two bits as a 2n-bit integer y in said storage means;
• (f) initializing an integer to 1 and storing it in said storage means;
• (g) reading out said b and y from said storage means, calculating −by, and updating said a stored in said storage means with the calculation result;
• (h) reading out said a, b, x and i from said storage means, calculating [(b+ax)/(2{circumflex over ( )}(2i))], and updating said b stored in said storage means with the calculation result, p{circumflex over ( )}q representing the q-th power of p;
• (i) reading out said a, y and i from said storage means, calculating y+a×2{circumflex over ( )}(2i), and updating said y stored in said storage, means with the calculation result;
• (j) reading out said i from said storage means and updating said i to i+1;
• (k) reading out said i and n from said storage means and performing said a-updating step, said b-updating step, said y-updating step and said I-updating step one after another until i=n;
• and
• (l) reading out said y from said storage means for output.

A substitution-permutation apparatus which, by the following substitution-permutation over a ring R

• 56 [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ] ⁢ ⁢ where ⁢ ⁢ P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ]
• pijεR, sj:
• R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi), said apparatus comprising:
• storage means for storing:
• precalculated values of vi (whose dimensions are up to m and may differ individually) over said ring R necessary for said substitution-permutation, obtained by swapping rows or columns of said matrix P for which some of pij or sj are the same values;
• a precalculated value of a function Sk:R→Rm;
• precalculated values of n vectors wk εRm;
• and an integer k;
• input means for storing said input data sequence (xj) in said storage means;
• k-initialization means for setting said integer k to 0;
• k-updating means for updating said k in said storage means to k+1;
• Sk calculating means for reading out each Sk and input data (xk) from said storage means to obtain the result of calculation of a vector Sk (xk) and for storing said vector as a vector wk in said storage means;
• means for reading out of said storage means a set of vectors {v1} necessary for forming a k-th column of said matrix P and for generating a vector uk;
• uk*Sk calculating means for reading out said wk from said storage means and calculating the product for each element and for updating said wk with the calculation result;
• control means for reading out said k stored in said storage means and for actuating said Sk calculating means, said uk*Sk calculating means and said k-updating means one after another until k=n;
• and
• output means for reading out each wk stored in said storage means and for calculating and outputting their sum.

A substitution-permutation apparatus which, by the following substitution-permutation over a ring R

• 57 [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ] ⁢ ⁢ where ⁢ ⁢ P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ]
• pijεR, sj:R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi), said apparatus comprising:
• storage means for storing:
• a precalculated value of the following equation with rows of a matrix P rearranged
• 58 SP 1 ⁢ ⁢ j ⁡ ( x j ) = [ p t ⁡ ( q1 ) ⁢ j ⁢ s j ⁡ ( x j ) p t ⁡ ( q1 + 1 ) ⁢ j ⁢ s j ⁡ ( x j ) ⋮ p t ⁡ ( r1 ) ⁢ j ⁢ s j ⁡ ( x j ) ]
• where b(j) is a natural number equal to or greater than 1 but equal to or smaller than n, l=1,2, . . . , b(j), t:{1, 2, . . . , m}→{1, 2, . . . , m} is a permutation, and ql and rl are natural numbers greater than 1 but smaller than m+1, where ql≦rl;
• precalculated values of n vectors wkεRm;
• and an integer k;
• input means for storing said input data sequence (xj) in said storage means;
• k-initialization means for setting said integer k to 0;
• k-updating means for updating said k stored in said storage means to k+1;
• SPk calculating means for reading out input data xk and SPlj(xk) from said storage means, for calculating said SPlj(xk) for each l and concatenating the calculated results in correspondence to a k-th column of said rearranged matrix P to obtain an m-dimensional vector, and for updating said wk stored in said storage means with said m-dimensional vector as wk, where l=1, 2, . . . , b(j);
• control means for reading out said k stored in said storage means and for actuating said SPk calculating means and said k-updating means one after the other until k=n;
• and
• output means for reading out each wk stored in said storage means and for calculating and outputting their sum.

A recording medium having recorded thereon a program for the execution by a computer of a substitution-permutation apparatus which, by the following substitution-permutation over a ring R

• 59 [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ] ⁢ ⁢ where ⁢ ⁢ P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ]
• pijεR, sj:
• R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi) and in which storage means has stored therein:
• precalculated values of vi (whose dimensions are up to m and may differ individually) over said ring R necessary for said substitution-permutation, obtained by swapping rows or columns of said matrix P for which some of pij or sj are the same values;
• a precalculated value of a function Sk:R→Rm;
• precalculated values of n vectors wk εRm;
• and an integer k;
• said program comprising the steps of:
• (a) storing said input data sequence xj in said storage means;
• (b) initializing said integer k to 0;
• (c) updating said k in said storage means to k+1;
• (d) reading out each Sk and input data (xk) from said storage means to obtain the result of calculation of a vector Sk (xk) and storing said vector as a vector wk in said storage means;
• (e) reading out of said storage means a set of vectors {v1} necessary for forming a k-th column of said matrix P and generating a vector uk;
• (f) reading out said wk from said storage means and calculating the product for each element and updating said wk with the calculation result;
• (g) reading out said k stored in said storage means and performing said Sk calculating step, said wk updating steps and said k-updating step one after another until k=n;
• and
• (h) reading out each wk stored in said storage means and calculating and outputting their sum.

A recording medium having recorded thereon a program for the execution by a computer of a substitution-permutation apparatus which, by the following substitution-permutation over a ring R

• 60 [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ] ⁢ ⁢ where ⁢ ⁢ P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ]
• pijεR, sj:R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi) and in which storage means has recorded therein a precalculated value of the following equation with rows of a matrix P rearranged
• 61 SP lj ⁡ ( x j ) = [ p t ⁡ ( q ⁢ ⁢ l ) ⁢ j ⁢ s j ⁡ ( x j ) p t ⁡ ( q ⁢ ⁢ l + 1 ) ⁢ j ⁢ s j ⁡ ( x j ) ⋮ p t ⁡ ( r ⁢ ⁢ l ) ⁢ j ⁢ s j ⁡ ( x j ) ]
• where b(j) is a natural number equal to or greater than 1 but equal to or smaller than n, l=1,2, . . . ,b(j), t:
• {1, 2, . . . , m}→{1, 2, . . . , m} is a permutation, and ql and rl are natural numbers equal to or greater than 1 but equal to or smaller than m, where ql≦rl, together with;
• precalculated values of n vectors wkεRm and an integer k, said program comprising the steps of;
• (a) storing said input data sequence (xj) in said storage means;
• (b) initializating said integer k to 0;
• (c) updating said k stored in said storage means to k+1;
• (d) reading out input data xk from said storage means, calculating SPlj(xk) for each l, concatenating the calculated results in correspondence to a k-th column of said rearranged matrix P to obtain an m-dimensional vector, and updating said wk stored in said storage means with said m-dimensional vector as wk, where l=1, 2, . . . , b(j);
• (e) reading out said k stored in said storage means and performing said SPk calculating step and said k-updating step one after the other until k=n;
• and
• (f) reading out each wk stored in said storage means and calculating and outputting their sum.

A permutation method in which an operating apparatus including an accumulator based CPU and registers is used to permute input data u1,u2, . . . ,un by the following equation using an m by n matrix P of predetermined {0, 1} elements to obtain permuted data (u1′, u2′, . . . , um′)

• 62 [ u 1 ′ u 2 ′ ⋮ u m ′ ] = P ⁡ [ u 1 u 2 ⋮ u n ]
• said method comprising the steps of:
• (a) setting each piece of said permuted data uj′ by the following equation using already calculated ui′
• uj′=ui′+Di
• where j≈i, i and j are integers equal to or greater than 1 but equal to or smaller than m, m is an integer equal to or greater than 2 and Di is given by the difference Di=uj′−ui′ between said permuted data uj′ and ui′ defined by said matrix P using said input data u1,u2, . . . ,un;
• and
• (b) calculating said uj′ for all of said j.

A recording medium having recorded thereon as a program executable by a compuer a permutation method by an operating apparatus including an accumulator based CPU and registers is used to permute input data u1,u2, . . . ,un by the following equation using an m by n matrix P of predetermined {0, 1} elements to obtain permuted data (u1′, u2′, . . . , um′)

• 63 [ u 1 ′ u 2 ′ ⋮ u m ′ ] = P ⁡ [ u 1 u 2 ⋮ u n ]
• said program comprising the steps of:
• (a) setting each piece of said permuted data uj′ by the following equation using already calculated ui′
• uj′=ui′+Di
• where j≈i, i and j are integers equal to or greater than 1 but equal to or smaller than m, m is an integer equal to or greater than 2 and Di is given by the difference Di=uj′−ui′ between said permuted data uj′ and ui′ defined by said matrix P using said input data u1,u2, . . . ,un;
• and
• (b) calculating said uj′ for all of said j.

A permutation apparatus in which an operating apparatus including an accumulator based CPU and registers is used to permute input data u1,u2, . . . ,un by the following equation using an m by n matrix P of predetermined {0, 1} elements to obtain permuted data (u1′, u2′, . . . , um′)

• 64 [ u 1 ′ u 2 ′ ⋮ u m ′ ] = P ⁡ [ u 1 u 2 ⋮ u n ]
• said apparatus comprising:
• storage means for storing previous calculated permuted data ui′;
• calculating means for calculating the next permuted data uj′ by the following equation using said previous permuted data ui′ read out of said storage means
• uj′=ui′+Di
• where j≈i, i and j are integers greater than 1 and smaller than m, m being an integer equal to or greater than 2, and Di is given by the difference Di=uj′−ui′ between said permuted data uj′ and ui′ defined by said matrix P using said input data u1,u2, . . . ,un;
• and
• control means for controlling said calculating means to repeat the calculation of said permuted data for all of said j.