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

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.

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

Lm¹%³k>

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`
  ¹%     # 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)

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!

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

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

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

ＮθＩ⊕⌕﹪ＸＮ…·¹θθＮ

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

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!