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.

Answer 1

[John D'Errico]

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.

[Niklas Kurz]

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]

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.