我想在Crystal中计算1_299_709 ** 1_300_751 % 104_729
。
在Python中,pow
函数允许将模作为第三个参数传递:
❯ python
>>> pow(1_299_709, 1_300_751, 104_729)
90827
在Ruby中,相同:
❯ irb
irb(main):001:0> 1_299_709.pow(1_300_751, 104_729)
=> 90827
但是在Crystal中,似乎没有这样的功能,自然地,使用**
运算符会迅速溢出:
❯ crystal eval "1_299_709 ** 1_300_751 % 104_729"
Unhandled exception: Arithmetic overflow (OverflowError)
from /usr/lib/crystal/int.cr:0:9 in '**'
from /eval:1:1 in '__crystal_main'
from /usr/lib/crystal/crystal/main.cr:97:5 in 'main_user_code'
from /usr/lib/crystal/crystal/main.cr:86:7 in 'main'
from /usr/lib/crystal/crystal/main.cr:106:3 in 'main'
from __libc_start_main
from _start
from ???
如何在Crystal中计算模幂?
编辑:为了明确起见,我已经在使用BigInt
,但这不起作用。为了简单起见,我从最小的工作示例中删除了BigInt。
以下Python代码包含我程序中的实际数字:
>>> pow(53583115773616729421957814870755484980404298242901134400501331255090818409243, 28948022309329048855892746252171976963317496166410141009864396001977208667916, 115792089237316195423570985008687907853269984665640564039457584007908834671663)
75711134420273723792089656449854389054866833762486990555172221523628676983696
它易于执行,并返回正确的结果。但是,Crystal:
a = BigInt.new 53583115773616729421957814870755484980404298242901134400501331255090818409243
e = BigInt.new 28948022309329048855892746252171976963317496166410141009864396001977208667916
p = BigInt.new 115792089237316195423570985008687907853269984665640564039457584007908834671663
y = a ** e % p # overflows with and without BigInt
导致:
gmp: overflow in mpz type
Program received and didn't handle signal IOT (6)
如何在Crystal中计算如此庞大的模幂?
使用BigInt:
require "big/big_int"
BigInt.new(1_299_709) ** 1_300_751 % 104_729 #=> 90827