math - 如何在 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
它很容易执行并返回正确的结果。红宝石也一样:
irb(main):001:0> 53583115773616729421957814870755484980404298242901134400501331255090818409243.pow(2894802230932904885589274625217197696331749616641014100986
4396001977208667916, 115792089237316195423570985008687907853269984665640564039457584007908834671663)
=> 75711134420273723792089656449854389054866833762486990555172221523628676983696
然而,水晶:
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 中计算如此庞大的模幂?
编辑:提出问题以确保它不是错误:水晶朗/水晶#8612
解决方案
正如 Github 问题中所述,这可以通过绑定mpz_powm_sec
from轻松规避gmp
:
这很简单: https ://carc.in/#/r/89qh
require "big/big_int" a = BigInt.new "53583115773616729421957814870755484980404298242901134400501331255090818409243" e = BigInt.new "28948022309329048855892746252171976963317496166410141009864396001977208667916" p = BigInt.new "115792089237316195423570985008687907853269984665640564039457584007908834671663" @[Link("gmp")] lib LibGMP fun mpz_powm_sec = __gmpz_powm_sec(rop : MPZ*, base : MPZ*, exp : MPZ*, mod : MPZ*) end #y = a ** e % p y = BigInt.new LibGMP.mpz_powm_sec(y, a, e, p) puts y # > 75711134420273723792089656449854389054866833762486990555172221523628676983696
推荐阅读
- spring - 启动 ApplicationContext 时出错。要显示条件报告,请在启用“调试”的情况下重新运行您的应用程序。
- python - 将一组模型分配给另一个模型
- windows - 在 Windows 10 上找不到 docker-machine 命令
- elasticsearch - Lucene/Solr 搜索文档创建
- c++ - 我不断收到 UE4 FPS 第 3.1 节教程的错误。我应该怎么办?
- python - 如何让 tkinter OptionMenu 显示所选选项的名称?
- excel - 如何知道 Windows 资源管理器预览窗格正在启动 VSTO Word 和 Excel 插件?
- python - 错误:您无权访问此服务器上的“url”。在美丽的汤
- reactjs - 不能在带有 Next.js 的模块外部使用 import 语句
- python - 将项目列表与短语匹配以隔离单词