Trial multiplication stop condition for discrete logarithm

Asked Jan 06 '22 at 08:09

Active Jan 06 '22 at 08:09

Viewed 23 times

I wrote a very simple algorithm to find the discrete logarithm of a certain number, it simply starts at p=1 and increments it until it finds a value of p that satisfies (b^p) % m = x.

The problem I have is that while this algorithm works when there exists a value to the discrete logarithm fo x, I reckon it would loop infinitely if it didn't. Is there s simple stop condition that I can use in my loop to know there is no result?

Thank you

EDIT: I am aware there exists more efficient algorithms but the trial multiplication algorithm is good enough for my use case.

asked Jan 06 '22 at 08:09

Pop Flamingo

If $p$ exist, then $p\equiv k\pmod h$, where $k$ is minimal discret log, and $h=ord_m(b)$ is multiplicative order of $b$ modulo $m$. I.e. need stop bruteforce after $h-1$. – Dmitry Ezhov Jan 06 '22 at 15:00
@DmitryEzhov Thank you – Pop Flamingo Jan 09 '22 at 13:46

Trial multiplication stop condition for discrete logarithm

0 Answers0