Modular exponentiation

Modular exponentiation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Find the last 40 decimal digits of $a^{b}$, where

• $a=2988348162058574136915891421498819466320163312926952423791023078876139$
• $b=2351399303373464486466122544523690094744975233415544072992656881240319$

A computer is too slow to find the entire value of $a^{b}$. Instead, the program must use a fast algorithm for modular exponentiation: $a^{b}\mod m$.

The algorithm must work for any integers $a,b,m$ where $b\geq 0$ and $m\neq 0$.

C

Given numbers are too big for even 64 bit integers, so might as well take the lazy route and use GMP: <lang c>#include <gmp.h>

int main() { mpz_t a, b, m, r;

mpz_init_set_str(a, "2988348162058574136915891421498819466320" "163312926952423791023078876139", 0); mpz_init_set_str(b, "2351399303373464486466122544523690094744" "975233415544072992656881240319", 0); mpz_init(m); mpz_ui_pow_ui(m, 10, 40);

1. if 0 /* Don't actually need these two lines: hopefully GMP does it. */

mpz_mod(a, a, m); /* obvious */ mpz_mod(b, b, m); /* Fermat's little theorem */

1. endif

mpz_init(r); mpz_powm(r, a, b, m);

gmp_printf("%Zd\n", r); /* 16808958343740453059 */

mpz_clear(a); mpz_clear(b); mpz_clear(m); mpz_clear(r); return 0; }</lang>

Go

<lang go>package main

import (

   "fmt"
   "math/big"

)

func main() {

   a, _ := new(big.Int).SetString(
     "2988348162058574136915891421498819466320163312926952423791023078876139", 10)
   b, _ := new(big.Int).SetString(
     "2351399303373464486466122544523690094744975233415544072992656881240319", 10)
   m, _ := new(big.Int).SetString("100000000000000000000", 10)
   
   r := new(big.Int).Exp(a, b, m)
   fmt.Println(r)

}</lang> Output:

16808958343740453059

Java

This example is in need of improvement: Tell algorithm it uses under the hood.

<lang java>import java.math.BigInteger;

public class PowMod {

   public static void main(String[] args){
       BigInteger a = new BigInteger(
     "2988348162058574136915891421498819466320163312926952423791023078876139");
       BigInteger b = new BigInteger(
     "2351399303373464486466122544523690094744975233415544072992656881240319");
       BigInteger m = new BigInteger("10000000000000000000000000000000000000000");
       
       System.out.println(a.modPow(b, m));
   }

}</lang> Output:

1527229998585248450016808958343740453059

Perl

<lang perl>use bigint;

my $a = 2988348162058574136915891421498819466320163312926952423791023078876139; my $b = 2351399303373464486466122544523690094744975233415544072992656881240319; my $m = 10000000000000000000000000000000000000000; print $a->bmodpow($b, $m), "\n";</lang> Output:

1527229998585248450016808958343740453059

PHP

<lang php><?php $a = '2988348162058574136915891421498819466320163312926952423791023078876139'; $b = '2351399303373464486466122544523690094744975233415544072992656881240319'; $m = '1' . str_repeat('0', 40); echo bcpowmod($a, $b, $m), "\n"; ?></lang> Output:

1527229998585248450016808958343740453059

Python

<lang python>a = 2988348162058574136915891421498819466320163312926952423791023078876139 b = 2351399303373464486466122544523690094744975233415544072992656881240319 m = 10 ** 40 print(pow(a, b, m))</lang> Output:

1527229998585248450016808958343740453059

TXR

<lang txr>@(bind result @(exptmod 2988348162058574136915891421498819466320163312926952423791023078876139

                       2351399303373464486466122544523690094744975233415544072992656881240319
                       (expt 10 40)))</lang>

$ ./txr rosetta/modexp.txr
result="1527229998585248450016808958343740453059"