boost::multiprecision::powm与Java中的BigInteger#modPow不同

2020年11月29日 43点热度 0条评论

我正在尝试使用Boost将C++中的AWS Cognito重新实现SRP协议(protocol),并从Amazon看Android实现。

我遇到一个问题,即带有相同参数的powm函数在Java和C++中返回不同的结果。以下是要重现的实际变量。

base = -60069516222067934465050534050924735913259123336604003695277708341824332895413979944668873920813978546728706494838542031539374089411576323557683032079456300479576399686088457834323998789559447280306593096633556722918700757880790576568543160534527724248702686289473589204691773279466673778290317667494679021095759596587143108565755917479750768759519224411507201300590256025341023717379667034891896621559345748879219694808586783746072343055239350628677886152249850829448959449884027507137715617906830580188376921330347491783964930384160916882168844833991645809121747349916283613126899731249980617076083650399040055004037242145087844202129219022561806749382444723981250548071098932686072865117465590944246091868534389708960372902345012028512996301150892770425867448873457573540209290963648133766450038070701366521974251173331552053367466421294567346255207594293174647572109245024389844295595423148975431938500850550834122854589221010198699007954971109000609845414067610786404346462923082635417069420150663

exp = 146462318780050704398491824679577877249637357233997958820955798606849034089055435560888738746472653803474347785215052176587544928236521681250726410243117146638424272590451021577470339456543664816801048455555325077949491666342480646917362501726371391429930610071051177605862191601117139467049042192421315075925

mod = 5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807

Java(所有变量均为BigInteger):

BigInteger x = base.modPow(exp, mod);

x: 1230568615184131985239346694446825655892733339973705775794155717290665406519709910407387531042376274634783342677355212818101752559959454003565957987129773506359982415765799964505534198533317147147330259998210157489219128947077927164476066764792878755295287228542190650053716328463274779372118557925988198416352338648543137326490077853579150463484865391556678099929526143587731521332343634512569891817217753866541107231323752824752313183429346607264168653584884607177140562811376873489718089411252979981686946488318076743666882294457424784508392043142317072588165582750606934742360106685332345292776496954791945874043489368333919203276279792510478642311867043688320756550623809890002329790942184110903137973601678472100031271022409063644536472615014574455126844337240082531858482475302880382827055687831445880729409121007713054522708302456617762637870271318479897319132492452505220079651903923918555883332563223829904474269679 

C++(所有变量均为cpp_int):

using namespace boost::multiprecision;

cpp_int x = boost::multiprecision::powm(base, exp, mod);

x: -4579037380185826077552569271192375746283878886929194757908745165489070771371280951064707243434963306512590067508291165509941977240791016094644966500737161552804389172402247576438447445983315607920171366436346240703967500042993321496343294440326914938690146068493927582860693843413532757085272719931023651481057868870562196029311043255777746995941406453914719852746433297205761550296050488267940232801270478735923542645526706036493471057499911819023531051727699902448278950652228281938299076303212383112334662802243007282226780266765148417574473754679548198402979499450050043434832720339206644947192678591398824771642404069677795227150129546165836101259287493453710816453652618811430706590859521197756692777588674473925450788908897507360190889864673841119575752609217687752289953513826752471091336430166026751963668992122173432876639494526155021977994961302809759625151724372106098630112631228588798233012140546168609674074128

问题出在哪里?

更新:

Python
pow(base,exp,mod)与Java返回相同。

看起来像Boost中的错误,还是我以错误的方式使用它?

解决方案如下:

这是有符号的模数实现方式的书面差异。

尝试-3 mod 5玩得开心。

作为立即的解决方法,您可以选择其他后端(例如gmp):
Live On Coliru

分析

在cpp_int后端和GMP后端之间有轻微的不一致,例如测试:

----
CppInt: -3 mod  5 = consistently -3
----
MpzInt: -3 mod  5 = -3
MpzInt: -3 powm 5 = 2
MpzInt: -3 mypm 5 = -3
mismatch
----
CppInt: -3 mod  17 = consistently -3
----
MpzInt: -3 mod  17 = -3
MpzInt: -3 powm 17 = 14
MpzInt: -3 mypm 17 = -3
mismatch

如您所见,Boost选择了自己的类型一致。

请注意,Boost方法在客观上似乎更好,因为它可以确保
身份
(a/b)*b + powm(a,1,b)始终成立。

固定

作为一个简单的解决方法,如果返回值为负,则只需添加除数:

template <class T> T my_powm(const T& a, const T& p, const T& c) {
    using std::abs; // summon the god of ADL
    T r = powm(a, p, c);
    return r<0? r + abs(c) : r;
}


Live On Coliru

#include <boost/multiprecision/cpp_int.hpp>

template <class T> T my_powm(const T& a, const T& p, const T& c) {
    using std::abs; // summon the god of ADL
    T r = powm(a, p, c);
    return r<0? r + abs(c) : r;
}

int main() {
    boost::multiprecision::cpp_int
        base{"-60069516222067934465050534050924735913259123336604003695277708341824332895413979944668873920813978546728706494838542031539374089411576323557683032079456300479576399686088457834323998789559447280306593096633556722918700757880790576568543160534527724248702686289473589204691773279466673778290317667494679021095759596587143108565755917479750768759519224411507201300590256025341023717379667034891896621559345748879219694808586783746072343055239350628677886152249850829448959449884027507137715617906830580188376921330347491783964930384160916882168844833991645809121747349916283613126899731249980617076083650399040055004037242145087844202129219022561806749382444723981250548071098932686072865117465590944246091868534389708960372902345012028512996301150892770425867448873457573540209290963648133766450038070701366521974251173331552053367466421294567346255207594293174647572109245024389844295595423148975431938500850550834122854589221010198699007954971109000609845414067610786404346462923082635417069420150663"},
        exp{"146462318780050704398491824679577877249637357233997958820955798606849034089055435560888738746472653803474347785215052176587544928236521681250726410243117146638424272590451021577470339456543664816801048455555325077949491666342480646917362501726371391429930610071051177605862191601117139467049042192421315075925"},
        mod{"5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807"};

    std::cout << my_powm(base, exp, mod) << "\n";
}

版画

1230568615184131985239346694446825655892733339973705775794155717290665406519709910407387531042376274634783342677355212818101752559959454003565957987129773506359982415765799964505534198533317147147330259998210157489219128947077927164476066764792878755295287228542190650053716328463274779372118557925988198416352338648543137326490077853579150463484865391556678099929526143587731521332343634512569891817217753866541107231323752824752313183429346607264168653584884607177140562811376873489718089411252979981686946488318076743666882294457424784508392043142317072588165582750606934742360106685332345292776496954791945874043489368333919203276279792510478642311867043688320756550623809890002329790942184110903137973601678472100031271022409063644536472615014574455126844337240082531858482475302880382827055687831445880729409121007713054522708302456617762637870271318479897319132492452505220079651903923918555883332563223829904474269679