Chaotic transformation of a vector

  AAA Matilda Europe

1. General


The suggested transformation transforms a vector of dimension n into a "chaotic vector" of the same dimension, i.e. in a vector whose components are permutated in pseudo-random way with an algorithm which generates a chaotic succession of numbers.
This transformation is reversible.


2. Transformation of a vector into a chaotic vector


If one describes a vector like a succession of n components Ci of value Vi. Each component has a position Ai =i.
The original vector can be written:

C1, Ci...,Cn of values V1, Vi,Vn
 
i { 1.. n }



The transformation works on the position of the successive components of the vector: the series of the positions undergoes a permutation which delocalizes the components of the original vector while preserving their value.


For each component Ci of address Ai, one calculates a new address A'i which corresponds to the position of this component in the transformed vector.

A'i = i * b mod (n+1)
 
i { 1..n }
b , (n+1) incommensurable numbers




If one calculates the address A'i starting from the address A' i-1, the series of A'i can be written:

A'i = (A' i-1 + b) mod (n+1)
 
A' 0 = 0
i{ 1.. n }
b , (n+1) incommensurable numbers




It is noticed that this series is a particular form of

Ai = (a * Ai-1 + b) mod (n+1)
 
a = 1
i { 1.. n }
b , (n+1) incommensurable numbers



which generates the succession of the numbers of 1 to n in a chaotic order [DEW87]. given n, this series is different for each value of parameter b, but recurrences appear when the number of possible permutations is reached (n-1).


3. Examples


A- Value of b lower than n+1: b = 3 and n = 6,

the transformed vector

C'1, C'2, C'3, C'4, C'5, C'6


is obtained by permutation of the components of the original vector:

A' 1 = (1*3) mod 7 = 3
A' 2 = (2*3) mod 7 = 6
A' 3 = (3*3) mod 7 = 9-7 = 2
A' 4 = (4*3) mod 7 = 12-7 = 5
A' 5 = (5*3) mod 7 = 15-7*2 = 1
A' 6 = (6*3) mod 7 = 18-7*2 = 4


B- value of b higher than n+1: b = 23 and n = 6,

A' 1 = (1*23) mod 7 = 23-7*3 = 2
A' 2 = (2*23) mod 7 = 46-7*6 = 4
A' 3 = (3*23) mod 7 = 69-7*9 = 6
A' 4 = (4*23) mod 7 = 92-7*13 = 1
A' 5 = (5*23) mod 7 = 115-7*16 = 3
A' 6 = (6*23) mod 7 = 138-7*19 = 5



let us visualize this last transformation:

4. Transformation matrix


This vectorial transformation is a permutation which is characterized by a matrix of permutation n x n (P) built starting from the chaotic sequence corresponding with a parameter b given.

example with b = 3:

5. Reverse transformation



The transformation is bi-univocal and the reverse transformation is obtained while multiplying the vector transformed by the opposite matrix.

[DEW87] Dewdney A., Explorez le monde étrange du chaos, Récréations informatiques, in Pour la Science , N 119, Sept 87, p 13-16

http://www.mupad.de/schule/en/Worksheets/notebooks/Linear_congruence_generator.html

http://crypto.mat.sbg.ac.at/results/karl/server/node3.html





 

To download examples Excel V4:

Matrix of permutation

Recurrences

To download an example Excel V5:

scrambling a text

Image processing:

Video transmission

scrambling an image

preprocessing of vectors before storage on associative memory

storage of information on a circular structure

Chaotic interpolation

To turn over to the banner page

Reception