Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Time consumption in loop

Subject: Time consumption in loop

From: Dhivya

Date: 20 Sep, 2013 06:28:09

Message: 1 of 20

In my work using Chinese remainder theorem as

C = num2cell(reshape(n, 4, 65536), 1); % n is an array of 262144 elements
for i=1:65536
l=length(C{i});
ba=C{i}';
ga=[311 313 317 293];
[bx by] = meshgrid(ba, ba);
bb = gcd(bx,by)-diag(ba);
pp = ~sum(sum(bb>1));
xo = by-diag(ba-1);
Mk = prod(xo);
[Gk, nk, Nk] = gcd ( ba, Mk ) ;
Sum_ga_Nk_Mk = sum ( (ga .* Nk) .* Mk ) ;
f1(i) = mod(Sum_ga_Nk_Mk,prod(ba));
end

The time consumption for this loop is quite long as the loop is repeated for 65536 times
Can you help me for reducing it??

Subject: Time consumption in loop

From: Roger Stafford

Date: 21 Sep, 2013 00:46:08

Message: 2 of 20

"Dhivya " <dhivya.n91@gmail.com> wrote in message <l1gptp$7nf$1@newscl01ah.mathworks.com>...
> In my work using Chinese remainder theorem as
>
> C = num2cell(reshape(n, 4, 65536), 1); % n is an array of 262144 elements
> for i=1:65536
> l=length(C{i});
> ba=C{i}';
> ga=[311 313 317 293];
> [bx by] = meshgrid(ba, ba);
> bb = gcd(bx,by)-diag(ba);
> pp = ~sum(sum(bb>1));
> xo = by-diag(ba-1);
> Mk = prod(xo);
> [Gk, nk, Nk] = gcd ( ba, Mk ) ;
> Sum_ga_Nk_Mk = sum ( (ga .* Nk) .* Mk ) ;
> f1(i) = mod(Sum_ga_Nk_Mk,prod(ba));
> end
>
> The time consumption for this loop is quite long as the loop is repeated for 65536 times
> Can you help me for reducing it??
- - - - - - - - -
I've made several changes to your code that might make it more efficient. I have kept 'ba' as a column vector. Your procedures for computing 'Mk' and 'pp' seem unnecessarily complicated. You don't seem to make use of this 'pp' quantity, so I have added provision to store it in an array. I see no reason for converting the original 'n' to a cell array, 'C'. It is important to do a preallocation for arrays 'f1' (and 'pp' which I have added.) I have assumed here that the length of C columns was a fixed value of 4. If not, there is an easy way of generating the ix1 and ix2 arrays in the general case.

 C = reshape(n,4,65536);
 f1 = zeros(65536,1);
 pp = zeros(65536,1);
 ga=[311 313 317 293];
 ix1 = [1 1 1 2 2 3]; % <-- This assumes the columns of C are of length 4
 ix2 = [2 3 4 3 4 4];
 for i = 1:65536
   ba = C(:,i);
   pba = prod(ba);
   Mk = pba./ba;
   [~,nk,Nk] = gcd(ba,Mk);
   f1(i) = mod(ga*(Nk.*Mk),pba);
   pp(i) = all(gcd(ba(ix1),ba(ix2))==1); % True if ba is pairwise coprime
 end

Roger Stafford

Subject: Time consumption in loop

From: Roger Stafford

Date: 21 Sep, 2013 01:26:06

Message: 3 of 20

"Roger Stafford" wrote in message <l1iq8g$9su$1@newscl01ah.mathworks.com>...
> for i = 1:65536
> .....
- - - - - - -
Try this instead:

 ba = reshape(n,4,65536);
 ga=[311 313 317 293]';
 ix1 = [1 1 1 2 2 3]; % <-- This assumes the columns of ba are of length 4
 ix2 = [2 3 4 3 4 4];
 pp = all(gcd(ba(ix1,:),ba(ix2,:))==1,1);
 pba = prod(ba,1);
 Mk = bsxfun(@rdivide,pba,ba);
 [~,nk,Nk] = gcd(ba,Mk);
 f1 = mod(sum(bsxfun(@times,ga,Nk.*Mk),1),pba);

(Note: This assumes the column length of ba is 4. If not, there is an easy way of generalizing the 'ix1' and 'is2' indices. You would also have to generalize 'ga'.)

Roger Stafford

> Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 21 Sep, 2013 06:53:07

Message: 4 of 20

Sir,
Thanks for your reply
I tried your coding but it shows error in the line

[~, nk, Nk] = gcd ( ba, Mk ) ;
as
Expression or statement is incorrect--possibly unbalanced (, {, or [

How to overcome it?

Subject: Time consumption in loop

From: Dhivya

Date: 21 Sep, 2013 07:20:07

Message: 5 of 20

"Roger Stafford" wrote in message <l1isje$irq$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <l1iq8g$9su$1@newscl01ah.mathworks.com>...
> > for i = 1:65536
> > .....
> - - - - - - -
> Try this instead:
>
> ba = reshape(n,4,65536);
> ga=[311 313 317 293]';
> ix1 = [1 1 1 2 2 3]; % <-- This assumes the columns of ba are of length 4
> ix2 = [2 3 4 3 4 4];
> pp = all(gcd(ba(ix1,:),ba(ix2,:))==1,1);
> pba = prod(ba,1);
> Mk = bsxfun(@rdivide,pba,ba);
> [~,nk,Nk] = gcd(ba,Mk);
> f1 = mod(sum(bsxfun(@times,ga,Nk.*Mk),1),pba);
>
> (Note: This assumes the column length of ba is 4. If not, there is an easy way of generalizing the 'ix1' and 'is2' indices. You would also have to generalize 'ga'.)
>


The column length of ba is 4... That is fixed

Subject: Time consumption in loop

From: Roger Stafford

Date: 21 Sep, 2013 07:41:09

Message: 6 of 20

"Dhivya" wrote in message <l1jfoj$ahu$1@newscl01ah.mathworks.com>...
> Sir,
> Thanks for your reply
> I tried your coding but it shows error in the line
>
> [~, nk, Nk] = gcd ( ba, Mk ) ;
> as
> Expression or statement is incorrect--possibly unbalanced (, {, or [
>
> How to overcome it?
- - - - - - - -
  I am not sure what matlab is objecting to. Which version of my suggestions produced that error, the first or the second? Possibly it is complaining about the missing first output argument, 'Gk'. Perhaps the two arrays 'ba' and 'Mk' are not the same size? You can check that. Are all the elements of 'n' positive integers?

  I notice that the blank spaces in the quoted error message are those of your coding and not mine. Does this mean you used some combination of our respective codes?

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 21 Sep, 2013 08:21:09

Message: 7 of 20

"Roger Stafford" wrote in message <l1jiil$qom$1@newscl01ah.mathworks.com>...
> "Dhivya" wrote in message <l1jfoj$ahu$1@newscl01ah.mathworks.com>...
> > Sir,
> > Thanks for your reply
> > I tried your coding but it shows error in the line
> >
> > [~, nk, Nk] = gcd ( ba, Mk ) ;
> > as
> > Expression or statement is incorrect--possibly unbalanced (, {, or [
> >
> > How to overcome it?
> - - - - - - - -
> I am not sure what matlab is objecting to. Which version of my suggestions produced that error, the first or the second? Possibly it is complaining about the missing first output argument, 'Gk'. Perhaps the two arrays 'ba' and 'Mk' are not the same size? You can check that. Are all the elements of 'n' positive integers?
>
> I notice that the blank spaces in the quoted error message are those of your coding and not mine. Does this mean you used some combination of our respective codes?
>
> Roger Stafford

-----------

Yes, This is a part of my coding actually..
Yes 'n' contains positive integers..
Your first suggestion has produced the error..
And in the second, you din mention about loop..
Can you give your mail id so that I'll mail my exact problem

Subject: Time consumption in loop

From: Roger Stafford

Date: 23 Sep, 2013 00:12:09

Message: 8 of 20

"Dhivya" wrote in message <l1jktl$c8h$1@newscl01ah.mathworks.com>...
> Yes, This is a part of my coding actually..
> Yes 'n' contains positive integers..
> Your first suggestion has produced the error..
> And in the second, you din mention about loop..
> Can you give your mail id so that I'll mail my exact problem
- - - - - - -
  In my second suggestion have you tried replacing the line

 [~,nk,Nk] = gcd(ba,Mk);

with

 [Gk,nk,Nk] = gcd(ba,Mk);

in case you have an older version of matlab.

  In this second suggestion code there is no for-loop. It is all "vectorized". For that reason it may be faster than your original code. Also it simplifies some of the complicated processing you do in obtaining 'pp' and 'Mk'.

  I have compared my second version of code with your code on my computer and they always seem to agree as to the values in 'pp' and 'f1' using random positive integers in 'n'.

  I would prefer it if you would use this newsgroup thread to explain what your "exact problem" is. There may be others who are interested in this subject.

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 25 Sep, 2013 10:11:09

Message: 9 of 20

"Roger Stafford" wrote in message <l1o10p$lo1$1@newscl01ah.mathworks.com>...
> "Dhivya" wrote in message <l1jktl$c8h$1@newscl01ah.mathworks.com>...
> > Yes, This is a part of my coding actually..
> > Yes 'n' contains positive integers..
> > Your first suggestion has produced the error..
> > And in the second, you din mention about loop..
> > Can you give your mail id so that I'll mail my exact problem
> - - - - - - -
> In my second suggestion have you tried replacing the line
>
> [~,nk,Nk] = gcd(ba,Mk);
>
> with
>
> [Gk,nk,Nk] = gcd(ba,Mk);
>
> in case you have an older version of matlab.
>
> In this second suggestion code there is no for-loop. It is all "vectorized". For that reason it may be faster than your original code. Also it simplifies some of the complicated processing you do in obtaining 'pp' and 'Mk'.
>
> I have compared my second version of code with your code on my computer and they always seem to agree as to the values in 'pp' and 'f1' using random positive integers in 'n'.
>
> I would prefer it if you would use this newsgroup thread to explain what your "exact problem" is. There may be others who are interested in this subject.
>
> Roger Stafford

--------------------

I tried with
[Gk,nk,Nk] = gcd(ba,Mk);
and its running..
But my output is wrong!!!
Wt i exactly need is The Chinese Remainder theorem with MINIMUM TIME CONSUMPTION..
I have to convert an array with 262144 elements into an array with 65536 elements..

Subject: Time consumption in loop

From: Roger Stafford

Date: 25 Sep, 2013 21:28:07

Message: 10 of 20

"Dhivya" wrote in message <l1ucrt$84l$1@newscl01ah.mathworks.com>...
> I tried with
> [Gk,nk,Nk] = gcd(ba,Mk);
> and its running..
> But my output is wrong!!!
- - - - - - - - - -
  The magnitudes of the integers in 'ga' suggests a possible explanation for why your results have come out incorrect. This could be true whether you used the code suggestions I made or your original code. You are using matlab's double precision floating point numbers as your integers, and there is a definite limit to the size that 'double' integers can represent accurately. That limit is the integer 2^53. It cannot for example represent 2^53+1 but must round it off to the nearest multiple of 2. Larger numbers of necessity round off to multiples of larger powers of 2. Therefore, if any of your computations involving [Gk,nk,Nk] = gcd(ba,Mk) encounter integers of a larger size than that limit, even intermediate results, they will be inaccurate. I have no way of telling just how large your values are in 'n', but if they were in the hundreds or thousands, it would be very easy for
this trouble to occur. I would suggest that you try doing a small number of these involving your largest numbers step-by-step using symbolic integers in the symbolic toolbox to see the magnitudes involved in the computations to see if they ascend to unacceptably high values.

Roger Stafford

Subject: Time consumption in loop

From: Roger Stafford

Date: 26 Sep, 2013 02:26:09

Message: 11 of 20

"Roger Stafford" wrote in message <l1vkh7$bsd$1@newscl01ah.mathworks.com>...
> "Dhivya" wrote in message <l1ucrt$84l$1@newscl01ah.mathworks.com>...
> > I tried with
> > [Gk,nk,Nk] = gcd(ba,Mk);
> > and its running..
> > But my output is wrong!!!
> - - - - - - - - - -
> The magnitudes of the integers in 'ga' suggests a possible explanation for why your results have come out incorrect. This could be true whether you used the code suggestions I made or your original code. You are using matlab's double precision floating point numbers as your integers, and there is a definite limit to the size that 'double' integers can represent accurately. That limit is the integer 2^53. It cannot for example represent 2^53+1 but must round it off to the nearest multiple of 2. Larger numbers of necessity round off to multiples of larger powers of 2. Therefore, if any of your computations involving [Gk,nk,Nk] = gcd(ba,Mk) encounter integers of a larger size than that limit, even intermediate results, they will be inaccurate. I have no way of telling just how large your values are in 'n', but if they were in the hundreds or thousands, it would be very easy for
> this trouble to occur. I would suggest that you try doing a small number of these involving your largest numbers step-by-step using symbolic integers in the symbolic toolbox to see the magnitudes involved in the computations to see if they ascend to unacceptably high values.
>
> Roger Stafford
- - - - - - - - - -
  I thought of two possible ways in which you might be misinterpreting your results. First, the four numbers in each vector 'ba' should be pairwise coprime for you to get the results you expect. That is indicated by the 'pp' variable being true. Second, the value in 'f1' when taken modulo each value in 'ba' won't necessarily be equal to the corresponding value in 'ga'. They are only equal modulo those values in 'ba'. That is, if you take the 'f1' value modulo a value in 'ba' you should get the same result as the corresponding 'ga' taken modulo that 'ba' value.

  If these don't explain your difficulties, could you please give a single concrete set of four pairwise coprime values as a column of 'ba' which aren't giving you what you expect for your 'ga'.

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 26 Sep, 2013 05:44:07

Message: 12 of 20

"Roger Stafford" wrote in message <l20601$5js$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <l1vkh7$bsd$1@newscl01ah.mathworks.com>...
> > "Dhivya" wrote in message <l1ucrt$84l$1@newscl01ah.mathworks.com>...
> > > I tried with
> > > [Gk,nk,Nk] = gcd(ba,Mk);
> > > and its running..
> > > But my output is wrong!!!
> > - - - - - - - - - -
> > The magnitudes of the integers in 'ga' suggests a possible explanation for why your results have come out incorrect. This could be true whether you used the code suggestions I made or your original code. You are using matlab's double precision floating point numbers as your integers, and there is a definite limit to the size that 'double' integers can represent accurately. That limit is the integer 2^53. It cannot for example represent 2^53+1 but must round it off to the nearest multiple of 2. Larger numbers of necessity round off to multiples of larger powers of 2. Therefore, if any of your computations involving [Gk,nk,Nk] = gcd(ba,Mk) encounter integers of a larger size than that limit, even intermediate results, they will be inaccurate. I have no way of telling just how large your values are in 'n', but if they were in the hundreds or thousands, it would be very easy for

> > this trouble to occur. I would suggest that you try doing a small number of these involving your largest numbers step-by-step using symbolic integers in the symbolic toolbox to see the magnitudes involved in the computations to see if they ascend to unacceptably high values.
> >
> > Roger Stafford
> - - - - - - - - - -
> I thought of two possible ways in which you might be misinterpreting your results. First, the four numbers in each vector 'ba' should be pairwise coprime for you to get the results you expect. That is indicated by the 'pp' variable being true. Second, the value in 'f1' when taken modulo each value in 'ba' won't necessarily be equal to the corresponding value in 'ga'. They are only equal modulo those values in 'ba'. That is, if you take the 'f1' value modulo a value in 'ba' you should get the same result as the corresponding 'ga' taken modulo that 'ba' value.
>
> If these don't explain your difficulties, could you please give a single concrete set of four pairwise coprime values as a column of 'ba' which aren't giving you what you expect for your 'ga'.
>
> Roger Stafford

--------------------

Sir as i am new to coding, your explanation seems a bit complex for me..
My coding is as follows..

clc;
clear variables;
close all;
a=imread('lena.png');
a=double(a);
f1=zeros(1,65536);
g1=zeros(1,65536);
x1=zeros(1,262144);
y1=zeros(1,262144);
b=reshape(a,[1 262144]);
% Grouping the elements for using chinese remainder theorem
C = num2cell(reshape(b, 4, 65536), 1);
% Using CRT
tic
for i=1:65536
r=C{i};
p=[311;313;317;293];
f1(i)=CRT(r,p); %instead of this CRT i need less time consuming code without any
                          loop or function
end
toc
%Modifying the values to produce cipher text
for i=1:65536
g1(i)=mod(f1(i),256);
s(i)=floor(f1(i)/256);
end
f2=reshape(g1,[256 256]);
f2=uint8(f2);
o=uint8(a);
subplot(2,2,1);
imshow(o);
subplot(2,2,2);
imshow(f2);

Am using matab R2009a.

Subject: Time consumption in loop

From: Roger Stafford

Date: 26 Sep, 2013 16:16:05

Message: 13 of 20

"Dhivya" wrote in message <l20hj7$eu6$1@newscl01ah.mathworks.com>...
> Sir as i am new to coding, your explanation seems a bit complex for me..
> My coding is as follows..
- - - - - - - -
  Dhivya, my concern is about the statement you made earlier: "I tried with [Gk,nk,Nk] = gcd(ba,Mk); and its running But my output is wrong!!!". The question I am asking you is this: Is the output wrong from my vectorized code and correct for your code for the same data, or are they both wrong? In either case I am asking you to send the 'ba' data for a single column, (that is, a set of four values,) for which you feel that the final output is wrong.

  I feel that question deserves to be answered before the problem of timing can be properly treated. I cannot proceed any further with your problem without having this question settled.

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 27 Sep, 2013 06:40:05

Message: 14 of 20

"Roger Stafford" wrote in message <l21mk5$qie$1@newscl01ah.mathworks.com>...
> "Dhivya" wrote in message <l20hj7$eu6$1@newscl01ah.mathworks.com>...
> > Sir as i am new to coding, your explanation seems a bit complex for me..
> > My coding is as follows..
> - - - - - - - -
> Dhivya, my concern is about the statement you made earlier: "I tried with [Gk,nk,Nk] = gcd(ba,Mk); and its running But my output is wrong!!!". The question I am asking you is this: Is the output wrong from my vectorized code and correct for your code for the same data, or are they both wrong? In either case I am asking you to send the 'ba' data for a single column, (that is, a set of four values,) for which you feel that the final output is wrong.
>
> I feel that question deserves to be answered before the problem of timing can be properly treated. I cannot proceed any further with your problem without having this question settled.
>
> Roger Stafford

----------------------
Sir,
I used the Chinese remainder theorem(CRT) which was provided in the link
http://www.mathworks.com/matlabcentral/fileexchange/38112-chinese-remainder-theorem
(as in the coding i have sent you recently)
It is working (i am able to encrypt and reproduce the image i am giving as input).
But the time consumption is about 14 seconds..
So i tried a different thing..
Both the coding (which i posted initially and you suggested) are NOT working (ie. it is getting encrypted but i am not able to reproduce the original image).
'ba' is the image input..(for instance: a gray 512X512 image pixel values...say [95,146,171,97] you can understand that from the coding i recently posted)
If you suggest a CRT with minimum time consumption for my case(without repeated function calls or loops), it would be much helpful..

Subject: Time consumption in loop

From: Roger Stafford

Date: 27 Sep, 2013 16:41:05

Message: 15 of 20

"Dhivya" wrote in message <l23985$oid$1@newscl01ah.mathworks.com>...
> Sir,
> I used the Chinese remainder theorem(CRT) which was provided in the link
> http://www.mathworks.com/matlabcentral/fileexchange/38112-chinese-remainder-theorem
> (as in the coding i have sent you recently)
> It is working (i am able to encrypt and reproduce the image i am giving as input).
> But the time consumption is about 14 seconds..
> So i tried a different thing..
> Both the coding (which i posted initially and you suggested) are NOT working (ie. it is getting encrypted but i am not able to reproduce the original image).
> 'ba' is the image input..(for instance: a gray 512X512 image pixel values...say [95,146,171,97] you can understand that from the coding i recently posted)
> If you suggest a CRT with minimum time consumption for my case(without repeated function calls or loops), it would be much helpful..
- - - - - - - - - -
  Dhivya, it seems to me you have things backwards in your attempts to encrypt an image with the code you have presented in this thread. The fixed numbers you used for 'ga' (311, 313, 317, and 293) are all prime numbers and consequently suitable for use as your 'ba' quantities which are required to be pairwise coprime in order to apply the Chinese Remainder Theorem. The image pixels would then be suitable for use in the role of your 'ga' quantities. From a single number 'f1' obtained from a set of four pixel gray level values you could take it modulo each of the four fixed prime numbers and thereby restore your original image values.

  In your code just reverse the respective roles that 'ga' and 'ba' play there and it should work properly. And if this works. you might try using the vectorized code I showed you to see if it is appreciably faster.

  All during this thread I have been wondering how you could be so sure that all your 'ba' sets of four would be pairwise coprime and now I realize that you need only have one fixed set of four which are pairwise coprime. I didn't know you were trying to encrypt images.

Roger Stafford

Subject: Time consumption in loop

From: Roger Stafford

Date: 27 Sep, 2013 20:15:06

Message: 16 of 20

"Roger Stafford" wrote in message <l24cf1$561$1@newscl01ah.mathworks.com>...
> In your code just reverse the respective roles that 'ga' and 'ba' play there and it should work properly. And if this works. you might try using the vectorized code I showed you to see if it is appreciably faster.
- - - - - - -
  Here is my version of the code that could be used if you reverse the roles of 'ga' and 'ba'. Adopt a set of four pairwise coprime numbers for 'ga' which are each greater than 255 such as the one you gave in your first post in this thread. Let n be a double precision array for a gray image with maximum value of 255.

% Define 'ga'
ga = [311 313 317 293]; % These are pairwise coprime

% Process 'ga' (Done only once for each different 'ga')
pga = prod(ga);
M = pga./ga;
[t1,t2,N] = gcd(ga,M);
NM = N.*M;

% To encrypt n
f1 = mod(NM*reshape(n,4,[]),pga);

% To restore n
nn = reshape(bsxfun(@mod,f1,ga'),size(n));

If you don't have 'bsxfun' use this instead:
nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));

  The 'nn' array should be identical to the original 'n' array. Notice that the processing of 'ga' only needs to be done once for each different 'ga'. Any number of images 'n' can use the same results 'NM' and 'pga'.

  This method should be very much faster than the code you were using since 'gcd' needs to be called only once for each different 'ga'. Each image can be processed in just the one line above which produces 'f1'.

Note: I used [t1,t2,N] = gcd(ga,M); because you appear to have a very old version of matlab that doesn't allow [~,~,N] = gcd(ga,M);

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 28 Sep, 2013 09:15:07

Message: 17 of 20

--------
Thank you so much sir..
For my better understanding, an you please explain these three lines..
f1 = mod(NM*reshape(n,4,[]),pga);
nn = reshape(bsxfun(@mod,f1,ga'),size(n));
nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));

Subject: Time consumption in loop

From: Roger Stafford

Date: 28 Sep, 2013 21:18:07

Message: 18 of 20

"Dhivya" wrote in message <l266mr$3vi$1@newscl01ah.mathworks.com>...
> For my better understanding, an you please explain these three lines..
> f1 = mod(NM*reshape(n,4,[]),pga);
> nn = reshape(bsxfun(@mod,f1,ga'),size(n));
> nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));
- - - - - - - - -
  Rather than my giving you a detailed explanation of those lines, I think it would be more instructive for you to figure out how they work by yourself. It will possibly mean your carefully reading the documentation for the pertinent matlab functions, but that will help you to be more familiar with the language. I'll try to guide you by giving some of the intermediate results so you can check your understanding as you go along. You should also work these computations by hand (or calculator.)

 Starting with your definition of 'ga'
 
 ga = [311,313,317,293];
 pga = prod(ga);
 M = pga./ga;
 [t1,t2,N] = gcd(ga,M);
 NM = N.*M;

these lines should give you

 pga = 9041315183
 NM = [-1046583108,1299869595,2338762918,-2592049404]

See if you can figure out why. The above needs to be done only once for any given 'ga'.

  Next suppose you have an eight-pixel image 'n' defined as:

 n = [56,12,174,174,239,98,133,212]; % I chose these at random

which on reshaping becomes

 reshape(n,4,[]) = 56 239
                   12 98
                  174 133
                  174 212

In the line

 f1 = mod(NM*reshape(n,4,[]),pga)
 
the matrix multiplication in the first argument gives

 NM*reshape(n,4,[]) = [-87082067472,-361205148056]
 
and after the 'mod' operation on it we have

 f1 = [3331084358,447459264]

This is your encrypted version of n. The final step of

 nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));
 
or its 'bsxfun' equivalent, will then restore you to the same values as in 'n'. Note that this depends on all elements in 'ga' being larger than all elements in 'n' so that the 'mod' operation returns you to the original value and not something differing by a multiple of the element in 'ga'.

  Finally I would like to point out that such an encryption method as this using the Chinese Remainder Theorem with a four-element key does not seem to me to be very secure from code breaking. I can conceive of a sophisticated program deciphering such an encryption rather easily, particularly if the four-pixel groups are taken from adjacent pixels of the image as in the above reshaping.

Roger Stafford

Subject: Time consumption in loop

From: Dhivya

Date: 30 Sep, 2013 09:12:09

Message: 19 of 20

"Roger Stafford" wrote in message <l27h2f$snm$1@newscl01ah.mathworks.com>...
> "Dhivya" wrote in message <l266mr$3vi$1@newscl01ah.mathworks.com>...
> > For my better understanding, an you please explain these three lines..
> > f1 = mod(NM*reshape(n,4,[]),pga);
> > nn = reshape(bsxfun(@mod,f1,ga'),size(n));
> > nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));
> - - - - - - - - -
> Rather than my giving you a detailed explanation of those lines, I think it would be more instructive for you to figure out how they work by yourself. It will possibly mean your carefully reading the documentation for the pertinent matlab functions, but that will help you to be more familiar with the language. I'll try to guide you by giving some of the intermediate results so you can check your understanding as you go along. You should also work these computations by hand (or calculator.)
>
> Starting with your definition of 'ga'
>
> ga = [311,313,317,293];
> pga = prod(ga);
> M = pga./ga;
> [t1,t2,N] = gcd(ga,M);
> NM = N.*M;
>
> these lines should give you
>
> pga = 9041315183
> NM = [-1046583108,1299869595,2338762918,-2592049404]
>
> See if you can figure out why. The above needs to be done only once for any given 'ga'.
>
> Next suppose you have an eight-pixel image 'n' defined as:
>
> n = [56,12,174,174,239,98,133,212]; % I chose these at random
>
> which on reshaping becomes
>
> reshape(n,4,[]) = 56 239
> 12 98
> 174 133
> 174 212
>
> In the line
>
> f1 = mod(NM*reshape(n,4,[]),pga)
>
> the matrix multiplication in the first argument gives
>
> NM*reshape(n,4,[]) = [-87082067472,-361205148056]
>
> and after the 'mod' operation on it we have
>
> f1 = [3331084358,447459264]
>
> This is your encrypted version of n. The final step of
>
> nn = reshape(mod(repmat(f1,4,1),repmat(ga',1,length(f1))),size(n));
>
> or its 'bsxfun' equivalent, will then restore you to the same values as in 'n'. Note that this depends on all elements in 'ga' being larger than all elements in 'n' so that the 'mod' operation returns you to the original value and not something differing by a multiple of the element in 'ga'.
>
> Finally I would like to point out that such an encryption method as this using the Chinese Remainder Theorem with a four-element key does not seem to me to be very secure from code breaking. I can conceive of a sophisticated program deciphering such an encryption rather easily, particularly if the four-pixel groups are taken from adjacent pixels of the image as in the above reshaping.
>
> Roger Stafford

----------------

Thank you so much sir.. I worked out things manually as you said and it gave me good understanding..
I got two more questions,
Has compression achieved in this CRT?
If this is not so secure, can you suggest some other methods?

Subject: Time consumption in loop

From: Roger Stafford

Date: 30 Sep, 2013 17:11:05

Message: 20 of 20

"Dhivya" wrote in message <l2bf99$ir$1@newscl01ah.mathworks.com>...
> I got two more questions,
> Has compression achieved in this CRT?
> If this is not so secure, can you suggest some other methods?
- - - - - - - - - -
  In a basic sense I doubt there is significant compression achieved in this process. For each set of four values which each range from 0 to 255, you obtain a single value which ranges from 0 to 311*313*317*293-1. Bitwise, that is somewhat the opposite of compression, though the result still fits in a single double precision floating point number.

  I think significant compression can only be achieved when one takes advantage of the inherent correlations that exist between pixel values in typical images, but that is not what this CRT method does.

  However it does achieve a certain level of encryption. My statement about breaking this encryption had in mind the use of massive computer procedures that could use algorithms that are perhaps not practical on ordinary computers. It depends on what level of sophistication is brought to bear on the problem.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us