# Find the discrete logarithm

Write a program/function that when given 3 positive integers $$\a, b\$$ and $$\m\$$ as input outputs a positive integer $$\x\$$ such that $$\a^x\equiv b\ (\text{mod}\ m)\$$ or that no such $$\x\$$ exists.

A reference implementation can be found here.

# Constraints

You can expect $$\a\$$ and $$\b\$$ to be less than $$\m\$$.

# Scoring

This is so shortest bytes wins.

# Sample Testcases

# a, b, m -> x

10, 10, 50 -> 1
10, 100, 200 -> 2
10, 1, 127 -> 42
35, 541, 1438 -> 83
35, 541, 1438 -> 1519
1816, 2629, 3077 -> 223
3306, 4124, 5359 -> 1923
346, 406, 430 -> None
749430, 2427332, 2500918 -> 8025683
3442727916, 3990620294, 6638635157 -> 5731137125


Note: in the third testcase the solution cannot be 0 since the solution has to be a positive number

• Mathematica has a built in that does exactly this... MultiplicativeOrder reference.wolfram.com/language/ref/MultiplicativeOrder.html – ZaMoC Jul 3 '20 at 9:40
• The restriction against an output of zero feels to me like a corner case gotcha. – xnor Jul 3 '20 at 9:43
• @xnor It indeed is. Without that edge case, both my 05AB1E and MathGolf answers would have been a byte shorter by using a list in the range $[0,m]$ instead of $[1,m]$ and removing the final increment to convert the 0-based to a 1-based index. Then again, using just positive integers for $a,b,m,x$ is a reasonable additional requirement, even if it doesn't add much to the core challenge itself except for a minor edge case. – Kevin Cruijssen Jul 3 '20 at 10:26
• Could you add a few more test cases that fall within 2**53-1 please? – Shaggy Jul 3 '20 at 19:24

# C (gcc), 59 53 51 bytes

Saved 6 bytes thanks to the man himself Arnauld!!!

Saved 2 bytes thanks Dominic van Essen!!!

p;x;f(a,b,m){for(p=a,x=1;p-b&&++x<m;)p=p*a%m;x%=m;}


Try it online!

Inputs positive integers $$\a,b,m\$$ with $$\a,b.
Outputs a positive integer $$\x\$$ such that $$\a^x\equiv b\ (\text{mod}\ m)\$$ or $$\0\$$ if no such $$\x\$$ exists.

• 57 bytes without the p= at the end, if it's Ok to output m for 'no solution exists'. – Dominic van Essen Jul 3 '20 at 11:23
• @DominicvanEssen Sure, but the kicker's that it's a positive integer and it's not a solution. It requires extra work outside of the function to deduce what the output actually means. – Noodle9 Jul 3 '20 at 12:44
• – Arnauld Jul 3 '20 at 22:57
• @Dominic van Essen And we're there! Very nice - thanks! :D – Noodle9 Jul 4 '20 at 11:22
• @Floris Yes, it's part of the syntax of a for loop.. – Noodle9 Jul 17 '20 at 13:11

# Python 2, 55 51 bytes

def f(a,b,m,x=1):a**x%m==b<exit(x);x<m<f(a,b,m,x+1)


Try it online!

A recursive function that simply tests all exponents from $$\1\$$ to $$\m\$$. Returns through exit code: a positive exponent $$\x\$$, or $$\0\$$ if no such $$\x\$$ exists.

• a==b<c with side effects is definitely evil syntax – user253751 Jul 6 '20 at 12:15

# JavaScript (Node.js),  38  33 bytes

Expects (a,m)(b) as 3 BigInts. Throws RangeError if there's no solution.

(a,m,x=m)=>g=b=>a**--x%m-b?g(b):x


Try it online!

# JavaScript (Node.js), 39 bytes

Expects (a,m)(b) as 3 BigInts. Returns false if there's no solution.

NB: This version always returns the smallest solution.

(a,m,x=0n)=>g=b=>a**++x%m-b?x<m&&g(b):x


Try it online!

# 05AB1E, 10 7 bytes

Lm¹%³k>


Inputs in the order $$\m,a,b\$$; outputs 0 if no $$\x\$$ is found.

Explanation:

L        # Push a list of values x in the range [1, (implicit) input m]
m       # Take the (implicit) input a to the power of each of these x
¹%     # Take each modulo the first input m
³k   # Get the 0-based index of the first occurrence of the third input b
# (-1 if there are none)
>  # And increase it by 1 to make it a 1-based index
# (after which it is output implicitly as result)


# APL (Dyalog Extended), 23 bytes

{⍺(∊×⍳⍨)(⍺⍺|⍵×⊢)⌂traj⍵}


Try it online!

Dyalog APL can't handle large integers, so a modulo should be performed after each iteration.

### How it works

{⍺(∊×⍳⍨)(⍺⍺|⍵×⊢)⌂traj⍵}  ⍝ dop; ⍵ ⍺ ⍺⍺ ← a b m
(      )⌂traj    ⍝ Collect all iterations until duplicate is found
⍵   ⍝   starting from a:
⍵×⊢          ⍝     Multiply a
⍺⍺|             ⍝     Modulo m
⍺(  ⍳⍨)                 ⍝ Find the 1-based index of b in the result,


# MathGolf, 8 bytes

_╒k▬\%=)


Port of my 05AB1E answer, so also:
Inputs in the order $$\m,a,b\$$; outputs 0 if no $$\x\$$ is found.

Try it online.

Explanation:

_         # Duplicate the first (implicit) input m
╒        # Pop one and push a list in the range [1, m]
k       # Push the second input a
▬      # For each value x in the list, take a to the power x
\     # Swap so the originally duplicated m is at the top of the stack
%    # Take modulo-m on each value in the list
=   # Get the first 0-based index of the value that equals the third (implicit)
# input b (-1 if there are none)
)  # And increase it by 1 to make it a 1-based index
# (after which the entire stack joined together is output implicitly as result)


# R+gmp, 47 46 bytes

Or only 37 bytes by requiring input in the form of bigz big integer.

function(a,b,m)match(T,as.bigz(a)^(1:m)%%m==b)


Try it online!

• arguably, you can just use ordinary integers and save yourself the call to as.bigz – JDL Jul 6 '20 at 12:01
• and it's more efficient to use which(...) rather than match(T,...) (you will get NA if there isn't one) – JDL Jul 6 '20 at 12:02
• @JDL Unfortunately, without the bigz big integer, it fails by going out of the integer range for all except the first (smallest) two test cases. – Dominic van Essen Jul 6 '20 at 12:04
• @JDL and the reason that I ended-up using match(T,...) instead of which(...) is because many discrete logarithms have more-than-one solution (for instance, the fourth test case), so which needs an extra  at the end to only output one of them, which makes it longer. – Dominic van Essen Jul 6 '20 at 12:06
• a*1 would turn a into a double-precision — is that big enough? – JDL Jul 7 '20 at 8:15

# Ruby, 41 bytes

->a,b,m,x=0{(a**x+=1)%m==b&&x||x<m&&redo}


Try it online!

The logic is straightforward: increment the exponent $$\x\$$ and return it if it satisfies the required equation, otherwise repeat while $$\x\$$ is less than $$\m\$$. Outputs the smallest solution for $$\x\$$, or false if no solution exists.

# Java 8, 97 bytes

(a,b,m)->{for(int x=0;x++<m;)if(a.modPow(b.valueOf(x),b.valueOf(m)).equals(b))return x;return-1;}


$$\a\$$ and $$\b\$$ are both java.math.BigInteger; $$\m\$$ and the output $$\x\$$ are both int.
Outputs -1 if no $$\x\$$ is found.

Try it online.

Explanation:

(a,b,m)->{            // Method with 2 BigInteger & integer parameters and integer return
for(int x=0;x++<m;) //  Loop x in the range (0,m]:
if(a.modPow(b.valueOf(x),b.valueOf(m))
//   If a to the power x, modulo m
.equals(b))    //   equals b:
return x;       //    Return x as result
return-1;}          //  If the loop has ended without result, return -1 instead


# Brachylog, 19 bytes

Takes in a list of [A,M,B], output is either X or false. The [3306, 5359, 4124] test case times out on TIO, but returns the correct result locally. First Brachylog answer, so probably not the best solution. :-)

bhM>.>0&h;.^;M%~t?∧


Try it online!

### How it works

bhM>.>0&h;.^;M%~t?∧
bhM                 set the second item to M
>.>0             output must be between M and 0
&h           input's first item (A)
;.^        A^output
;M%     A^output mod M
~t?  must unify with the tail from the input (B)
∧ return the output


(a#m)b=last$0:[x|x<-[1..m],mod(a^x-b)m==0]  Try it online! The function (a # m) b returns a positive integer x such that a ^ x == b (mod m). If no such x exists, it returns 0. This is done by the brute force method. # bc, 58 50 bytes define f(a,b,m){for(;x<m;)if(a^++x%m==b)return(x)}  Try it online! This just tries the integers from 1 to m, and outputs the first one which satisfies being a discrete log. Otherwise, the function returns 0 (default return value). • 53 bytes by syntax guesswork... – Dominic van Essen Jul 4 '20 at 11:26 • @DominicvanEssenThanks. And we can even omit the x=0 in that case. – Abigail Jul 4 '20 at 11:57 # R, 61 bytes function(a,b,m){for(i in c(1:m,0))if((T=(a*T)%%m)==b)break;i}  Try it online! The base form of R doesn't support arbitrary-precision arithmetic (see my other 'R+gmp' answer for a solution using the 'gmp' library that allows this). But, pleasingly, the step-by-step calculation of (a^x)mod m comes-out at only 14 bytes longer than the brute-force approach, and it's much faster. # Charcoal, 14 bytes ＮθＩ⊕⌕﹪ＸＮ…·¹θθＮ  Try it online! Link is to verbose version of code. Takes input in the order m, a, b and outputs 0 if there is no solution. Explanation: Ｎθ Store m …·¹θ Range from 1 to m inclusive ＸＮ Take powers of a ﹪ θ Reduce modulo m ⌕ Ｎ Find index of b ⊕ Convert to 1-indexing Ｉ Cast to string Implicitly print  # Retina, 84 bytes \d+ * "$+"{,(?=(_+))((_+),)+
,$.1*$3$& )^(_+),\1+$1,
L$.*(,_+)(,_+)+$(?<=\1)
$#2  Try it online! Sadly no test suite as this uses "$+", and I can't figure out how to emulate that with multiple sets of inputs (Retina just crashes when I try). Takes input in the order m, a, b and produces no output if there is no solution. Explanation:

\d+
*


Convert to unary.

"$+"{ )  Repeat m times... ,(?=(_+))((_+),)+ ,$.1*$3$&


... multiply the second number by the second last number and insert it between the first two numbers...

^(_+),\1+
$1,  ... and reduce it modulo m. L$.*(,_+)(,_+)+$(?<=\1)$#2


Count the position of the power matching b starting from the end.

# Io, 57 bytes

method(a,b,m,x :=1;for(i,1,m,if((x=x*a%m)==b,return i))0)


Try it online!