IDA

It is implementation of Information Dispersal Algorithm.

Information Dispersal Algorithm (IDA) which breaks a file F of length L = |F| into n pieces F i , 1 ≤ i ≤ n, each of length |F i | = L/m, so that every m pieces suffice for reconstructing F.

Source: Michael O. Rabin, Efficient Dispersal of Information for Security

Encoding

Let F= b1,b2, ………..bN be a file that is string of character.

The character bi may be considered as integers taken from a certain range[0………..p-1]. Now, F is a string of residues mod p, that is, a string of elements in the finite field Zp(p is a large prime number).

Choose n vectors ai = (ai1, . . . , aim,) € Zmp, 1<=i<=n, such that every subset of m different vectors are linearly independent. Alternatively, it will suffice to assume that with high probability, a randomly chosen subset of m vectors in (ai ,……..,an ) is linearly independent.

The file F is segmented into sequences of length m. Thus F = (b1…………bm), (bm+1………..b2m) , …….. Denote S = (b1,………bm), etc . For i=1,………..,n, Fi = Ci1, Ci2,…….CiN/m, Where Cik =ai.Sk=ai1.b(k-1)(m+1)+………..aim.bkm. It follows that |Fi=|F|/m.|.

For simplicity i have considered message consists of space separated integers.

Decoding

If m pieces of F ,say F1, …….Fm are given, we reconstruct F as follows. Let A=(a ij ) 1<=i,j<=m be the m*n matrix whose ith row is ai. It is radially seen that

A.[b1……..bm]^T^ =[C11………Cm1]^T^ And hence [b1………bm] ^T^= A-1.[C __……..Cm1]^T^.

Preview

Note: Prime has no meaning.