Azzera filtri
Azzera filtri

While loop with power.

11 visualizzazioni (ultimi 30 giorni)
Niklas Kurz
Niklas Kurz il 19 Gen 2021
Commentato: John D'Errico il 21 Gen 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.

Risposta accettata

John D'Errico
John D'Errico il 19 Gen 2021
Modificato: John D'Errico il 19 Gen 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 Commenti
Niklas Kurz
Niklas Kurz il 20 Gen 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 il 21 Gen 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;
ans = 1×2
37 3331
X = 3;
Xp = X;
for n = 2:N-1
Xp = mod(Xp*X,N);
if Xp == 1
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
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.

Accedi per commentare.

Più risposte (0)


Scopri di più su MATLAB in Help Center e File Exchange



Community Treasure Hunt

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

Start Hunting!

Translated by