cat map method
1 view (last 30 days)
Show older comments
I is an image; size(I)=[N N];
A=[1 a; b a*b+1];
where a and b are positive integers and det(A)=1.
I want to change the position of a pixel according to this equation
[x(n+1) y(n+1)]'= (A* [x(n) y(n)]')mod N;
where x and y are the position of pixels (ie i and j)
We say that the equation has period T if the pixel at location (x, y) returns to its original position after being transformed T times. The period T depends on the parameters a, b and size N of the original image.
how can I determine this period with a quick execution? you can see my test code proposed 4 days ago.
thank you
0 Comments
Answers (3)
Walter Roberson
on 6 May 2011
This is equivalent to Discrete Logarithm, about which it is said, "No efficient classical algorithm for computing general discrete logarithms logb g is known."
Thus, you should not expect to be able to solve this "with a quick execution".
See the reference for a list of algorithms.
4 Comments
Walter Roberson
on 6 May 2011
Well, Yes, that's the point. There is NO algorithm to do this that executes in polynomial time. No matter what you do, the program will get slower and slower the larger you make your matrix.
Sean de Wolski
on 6 May 2011
web('http://2.bp.blogspot.com/_xuKCVllHCh4/RtA9fq_lgAI/AAAAAAAADcg/eXU0YxZ9Pg0/s1600-h/map.jpg')
0 Comments
Walter Roberson
on 6 May 2011
Really, you are going about this the wrong way.
Any given pixel will return to its original position if and only if the net transformation matrices applied to it are equivalent to the identity matrix.
First of all, remember the properties of exponentiation and mod: ((x mod P) * (x mod P) * (x mod P) ... * (x mod P)) with a total of N terms, is always equal to (x^N) mod P.
Then, if you examine what you are doing, you will see that net transformation applied to [x,y] after T steps is
(A^T * [x;y]) mod N
and thus the condition that you need to satisfy is that (A^T) mod N is the identity matrix.
You do not need to transform any real matrices and compare them to the original: you just need to keep a running A^T matrix, multiply that by A, take the mod N, and see if you get the identity matrix out.
AI = eye(size(A));
AT = AI;
found = false;
numtries = 3*N;
for T = 1:numtries
AT = mod(AT * A,N);
if isequal(AT, AI); found = true; break;
end
if ~found
disp('did not find period')
else
fprintf('period was %d\n', T);
end
The periods can be tricky to predict by knowing "a" and "b", but perhaps I just did not look at it closely enough.
0 Comments
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!