19
\$\begingroup\$

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

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Mathematica has a built in that does exactly this... MultiplicativeOrder reference.wolfram.com/language/ref/MultiplicativeOrder.html \$\endgroup\$
    – ZaMoC
    Commented Jul 3, 2020 at 9:40
  • 4
    \$\begingroup\$ The restriction against an output of zero feels to me like a corner case gotcha. \$\endgroup\$
    – xnor
    Commented Jul 3, 2020 at 9:43
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jul 3, 2020 at 10:26
  • \$\begingroup\$ Could you add a few more test cases that fall within 2**53-1 please? \$\endgroup\$
    – Shaggy
    Commented Jul 3, 2020 at 19:24

16 Answers 16

10
\$\begingroup\$

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.

\$\endgroup\$
11
  • \$\begingroup\$ 57 bytes without the p= at the end, if it's Ok to output m for 'no solution exists'. \$\endgroup\$ Commented Jul 3, 2020 at 11:23
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Noodle9
    Commented Jul 3, 2020 at 12:44
  • 1
    \$\begingroup\$ 53 bytes? \$\endgroup\$
    – Arnauld
    Commented Jul 3, 2020 at 22:57
  • 1
    \$\begingroup\$ @Dominic van Essen And we're there! Very nice - thanks! :D \$\endgroup\$
    – Noodle9
    Commented Jul 4, 2020 at 11:22
  • 1
    \$\begingroup\$ @Floris Yes, it's part of the syntax of a for loop.. \$\endgroup\$
    – Noodle9
    Commented Jul 17, 2020 at 13:11
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ a==b<c with side effects is definitely evil syntax \$\endgroup\$ Commented Jul 6, 2020 at 12:15
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
7
  • \$\begingroup\$ arguably, you can just use ordinary integers and save yourself the call to as.bigz \$\endgroup\$
    – JDL
    Commented Jul 6, 2020 at 12:01
  • \$\begingroup\$ and it's more efficient to use which(...) rather than match(T,...) (you will get NA if there isn't one) \$\endgroup\$
    – JDL
    Commented Jul 6, 2020 at 12:02
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jul 6, 2020 at 12:04
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jul 6, 2020 at 12:06
  • \$\begingroup\$ a*1 would turn a into a double-precision — is that big enough? \$\endgroup\$
    – JDL
    Commented Jul 7, 2020 at 8:15
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 53 bytes by syntax guesswork... \$\endgroup\$ Commented Jul 4, 2020 at 11:26
  • 1
    \$\begingroup\$ @DominicvanEssenThanks. And we can even omit the x=0 in that case. \$\endgroup\$
    – Abigail
    Commented Jul 4, 2020 at 11:57
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 14 bytes

NθI⊕⌕﹪XN…·¹θθ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`
        …·¹θ    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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.