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 Jul 3 '20 at 9:40
  • 4
    \$\begingroup\$ The restriction against an output of zero feels to me like a corner case gotcha. \$\endgroup\$ – xnor Jul 3 '20 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\$ – Kevin Cruijssen Jul 3 '20 at 10:26
  • \$\begingroup\$ Could you add a few more test cases that fall within 2**53-1 please? \$\endgroup\$ – Shaggy Jul 3 '20 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\$ – Dominic van Essen Jul 3 '20 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 Jul 3 '20 at 12:44
  • 1
    \$\begingroup\$ 53 bytes? \$\endgroup\$ – Arnauld Jul 3 '20 at 22:57
  • 1
    \$\begingroup\$ @Dominic van Essen And we're there! Very nice - thanks! :D \$\endgroup\$ – Noodle9 Jul 4 '20 at 11:22
  • 1
    \$\begingroup\$ @Floris Yes, it's part of the syntax of a for loop.. \$\endgroup\$ – Noodle9 Jul 17 '20 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\$ – user253751 Jul 6 '20 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 Jul 6 '20 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 Jul 6 '20 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\$ – Dominic van Essen Jul 6 '20 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\$ – Dominic van Essen Jul 6 '20 at 12:06
  • \$\begingroup\$ a*1 would turn a into a double-precision — is that big enough? \$\endgroup\$ – JDL Jul 7 '20 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\$ – Dominic van Essen Jul 4 '20 at 11:26
  • 1
    \$\begingroup\$ @DominicvanEssenThanks. And we can even omit the x=0 in that case. \$\endgroup\$ – Abigail Jul 4 '20 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, privacy policy and cookie policy

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