Find the discrete logarithm

Question

Task

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 code-golf 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

• ZaMoC: Mathematica has a built in that does exactly this... MultiplicativeOrder reference.wolfram.com/language/ref/MultiplicativeOrder.html
• xnor: The restriction against an output of zero feels to me like a corner case gotcha.
• Kevin Cruijssen: @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.
• Shaggy: Could you add a few more test cases that fall within 2**53-1 please?

Answer 1

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<m\$.
Outputs a positive integer \$x\$ such that \$a^x\equiv b\ (\text{mod}\ m)\$ or \0ドル\$ if no such \$x\$ exists.

• Dominic van Essen: 57 bytes without the p= at the end, if it's Ok to output m for 'no solution exists'.
• Noodle9: @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.
• Arnauld: 53 bytes?
• Noodle9: @Dominic van Essen And we're there! Very nice - thanks! :D
• Noodle9: @Floris Yes, it's part of the syntax of a for loop..

Answer 2

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.

Answer 3

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!

Answer 4

05AB1E, (削除) 10 (削除ここまで) 7 bytes

Lm1%3k>

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

Try it online or verify all test cases.

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`
 1% # Take each modulo the first input `m`
 3k # 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)

Answer 5

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,
 ×ばつ ⍝ changing to 0 if not found

Answer 6

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)

Answer 7

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!

• JDL: arguably, you can just use ordinary integers and save yourself the call to as.bigz
• JDL: and it's more efficient to use which(...) rather than match(T,...) (you will get NA if there isn't one)
• Dominic van Essen: @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: @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 [1] at the end to only output one of them, which makes it longer.
• JDL: a*1 would turn a into a double-precision — is that big enough?

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

Haskell, 42 bytes

(a#m)b=last0ドル:[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.

Answer 12

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).

• Dominic van Essen: 53 bytes by syntax guesswork...
• Abigail: @DominicvanEssenThanks. And we can even omit the x=0 in that case.

Answer 13

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.

Answer 14

Charcoal, 14 bytes

NθI⊕⌕%XN...·1θθN

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:

Nθ Store `m`
 ...·1θ Range from 1 to `m` inclusive
 XN Take powers of `a`
 % θ Reduce modulo `m`
 ⌕ N Find index of `b`
 ⊕ Convert to 1-indexing
 I Cast to string
 Implicitly print

Answer 15

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.

Answer 16

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!