cat map method
1 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(3 个)
Walter Roberson
2011-5-6
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 个评论
Walter Roberson
2011-5-6
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
2011-5-6
web('http://2.bp.blogspot.com/_xuKCVllHCh4/RtA9fq_lgAI/AAAAAAAADcg/eXU0YxZ9Pg0/s1600-h/map.jpg')
0 个评论
Walter Roberson
2011-5-6
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 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!