Modular exponentiation
Find the last 40 decimal digits of , where
A computer is too slow to find the entire value of . Instead, the program must use a fast algorithm for modular exponentiation: .
The algorithm must work for any integers where and .
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);
- 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 */
- 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
<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 = 100000000000000000000; 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