Python 中的大整数运算
Large integer operation in Python
我正在尝试解决密码学 CTF 挑战，该挑战涉及采用 RSA 密钥对（两个大素数）的构建块和消息的加密密码数。为了解密此消息，我需要执行我认为标准加密库不支持的操作，因为使用的 public 指数未知，但我确实有值 dp 和dq，意思是我要进行以下操作：
所以本质上我是将非常大的整数乘以非常大整数的幂，而 pow(x,y) 的标准选项导致 Python 看似无限期地挂起。如果不使用加密库，我如何在 Python 中执行这些操作？
编辑：
这是导致 Python 挂起
的具体代码和值
p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871
m1 = pow(c,dp)%p
pow 采用可选的第三个参数 z，它执行模运算，但比使用 % 运算符快得多：
>>> pow(c, dp, p)
49437413074993986257824490238275931180994249527518860068137626874351971280859988288289074
我正在尝试解决密码学 CTF 挑战，该挑战涉及采用 RSA 密钥对（两个大素数）的构建块和消息的加密密码数。为了解密此消息，我需要执行我认为标准加密库不支持的操作，因为使用的 public 指数未知，但我确实有值 dp 和dq，意思是我要进行以下操作：
所以本质上我是将非常大的整数乘以非常大整数的幂，而 pow(x,y) 的标准选项导致 Python 看似无限期地挂起。如果不使用加密库，我如何在 Python 中执行这些操作？
编辑： 这是导致 Python 挂起
的具体代码和值p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871
m1 = pow(c,dp)%p
pow 采用可选的第三个参数 z，它执行模运算，但比使用 % 运算符快得多：
>>> pow(c, dp, p)
49437413074993986257824490238275931180994249527518860068137626874351971280859988288289074