While loop with power.

5 次查看（过去 30 天）
Niklas Kurz
Niklas Kurz 2021-1-19
评论： John D'Errico 2021-1-21
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
John D'Errico 2021-1-19
编辑：John D'Errico 2021-1-19
This is the discrete logarithm problem.
https://en.wikipedia.org/wiki/Discrete_logarithm#:~:text=Modular%20arithmetic.%20One%20of%20the%20simplest%20settings%20for,of%20the%20elements%20followed%20by%20reduction%20modulo%20p.
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...
https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms
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
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?
John D'Errico
John D'Errico 2021-1-21
Ran in:
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.)
https://wp.optics.arizona.edu/opti646/wp-content/uploads/sites/55/2020/12/OPTI_646_Final_Paper_Ian_Tillman.pdf
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)
ans = 1×2
37 3331
X = 3;
Xp = X;
for n = 2:N-1
Xp = mod(Xp*X,N);
if Xp == 1
n
break
end
end
n = 3330
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 = 1.0000e+16
N > flintmax
ans = logical
1
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 个）

类别

在 Help Center 和 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