boost :: multiprecision :: powm отличается от BigInteger # modPow в Java

Question

boost :: multiprecision :: powm отличается от BigInteger # modPow в Java

Я пытаюсь переопределить протокол SRP для AWS Cognito в C ++ с Boost и смотрю на реализацию Android от Amazon.

Я столкнулся с проблемой, когда 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

Где проблема?

ОБНОВИТЬ:

питон pow(base,exp,mod) возвращает так же, как Java.
Похоже, ошибка в Boost, или я использую ее неправильно?

1

aws-cognito boost c++java srp-protocol

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это задокументированное различие в том, как реализовано знаковое по модулю.

Пытаться -3 mod 5 ради забавы.

В качестве немедленного решения вы можете выбрать другой бэкэнд (например, gmp):
Жить на Колиру

Анализ

Существует небольшое несоответствие между бэкэндом 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;
}

Жить на Колиру

#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

1