While loop with power.
显示 更早的评论
I'd really be curious to know how to code the statement:
, 
thus finding p until the euqation becomes true.
Sounds to me like
while and mod()
come in handy. Of course u can follow another approach
Generally I've heard this problem consumes a lot of time.
采纳的回答
John D'Errico
2021-1-19
编辑：John D'Errico
2021-1-19
1 个投票
This is the discrete logarithm problem.
In general, there is no simple solution, but using a while loop seems a poor choice. There is a list of better schemes available, but nothing trivially written. Do some reading based on the links on the wiki page. For example...
But no. You don't want to use a while loop. That would be a bad idea. There is no tool in the symbolic toolbox for this purpose, nor is there a tool I have written in my toolboxes. It looks like the worse case will probably arise when N is a prime.
2 个评论
Niklas Kurz
2021-1-20
Yea, I was confident that a solution wouldn't be easy to find. It's a part of Shore's algorithm, that I just try to code.
so an reasonable step coding in order to get closer to the core of the problem goes like:
- guess a number G smaller than N (implemented)
A = (1:N-1);
G = randi(numel(A));
- compute
whereas I'd set x = 1 : N - if b repeats: stop, print steps taken to get again to b
I'm already left behind on this part. Guesses?
Its been a little while since I played with these things. It seems you are trying to code Shor's algorithm, to find the factors of N? (There is no e in the name, at least in the references I can find.)
Of course, you will only be doing this for composite numbers, and it is relatively cheap to verify that a large integer N is in fact composite. But the cycles may be quite long.
N = 123247;
factor(N)
X = 3;
Xp = X;
for n = 2:N-1
Xp = mod(Xp*X,N);
if Xp == 1
n
break
end
end
That is not TOO bad when N IS SMALL. I could have done it more simply by use of powermod, but that is much slower too. And had I chosen X=2 as a more lucky guess, the loop will terminate quickly. But that is just a lucky guess.
Anyway, if N were something like 99999971*99999989, then I don't want to try brute force. And if N is that large of a number, then you cannot even use double precision to do the computation.
N = 99999971*99999989
N > flintmax
This is when you will have problems, when you have large rough numbers. (A rough number is one with no small prime factors.) Large rough numbers will be your downfall, as they are for almost any factoring scheme. Schemes like this are fine if you have a nice powerful quantum computer on your desk. I don't, nor do I expect you do either.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
产品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
