While loop with power.

5 views (last 30 days)
Niklas Kurz
Niklas Kurz on 19 Jan 2021
Commented: John D'Errico on 21 Jan 2021
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.

Accepted Answer

John D'Errico
John D'Errico on 19 Jan 2021
Edited: John D'Errico on 19 Jan 2021
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 Comments
Niklas Kurz
Niklas Kurz on 20 Jan 2021
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 on 21 Jan 2021
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)
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.

Sign in to comment.

More Answers (0)

Categories

Find more on MATLAB in Help Center and File Exchange

Tags

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!