search

relic-toolkit / relic

Code
Other
458 stars 179 forks source link

Modulo functions hang with negative inputs #237

Closed guidovranken closed 2 years ago

guidovranken commented 2 years ago

The following programs hang:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(R); bn_new(R);

    const char* s1 = "-1213068231205668105605951854731130201903688064935528161870475730456060070523760888303587358590872539742605952062685689665790050881449002400974595736054710391122725343761246087108658616520069928832916521834833064485749676372705687317616286200865841564734708220159183429426211335541881119911308190957320877289346138223714721568038679909052494886888022494203752030856787987707512755313314280152942595573707787122148021787625342354581082645042923315484649160404052803109269034978674143327235378262617002698633275859799321409037763323997676106640677625699577000911688607471705774084284990619753737228796994575823351214750208332407673635154629636709530166795821103027127729954996811818355717460773619973829308267605586998608948975220841497023200590894302928108995492582138636826665966599321135363639920646752319375021202246285253852671364357824456633559541003030826211048431431301779118852450786305821429328758108112291384193519985827160549160338880430266425017606351739356733787672718870460573389547159376410277431646947036506297411287370264891554596434157687158928779590666910862366299003488880365538679591478039479609436953398977464454067378402345076819820755511650607752190021240448387531424291118625293239413064";
    const char* s2 = "-6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057148";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_monty_conv(R, A, B);

    bn_free(A);
    bn_free(B);
    bn_free(R);
    return 0;
}
#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, T, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(T); bn_new(T);
    bn_null(R); bn_new(R);

    const char* s1 = "-20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000014644087040737095516181010";
    const char* s2 = "1970543761890640310119143205433388";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_pmers(T, B);
    bn_mod_pmers(R, A, B, T);

    bn_free(A);
    bn_free(B);
    bn_free(R);
    return 0;
}
#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, T, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(T); bn_new(T);
    bn_null(R); bn_new(R);

    const char* s1 = "-100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000569494856176035326322058057570659331026192708460314150258592864177116729943603718461857357598351150301582835151321971577101803084265674677361251235429363707753237390378853789689048722376702214444444444444444440000000000000000000000000000000000000000000000000000000001844674407370805161150014444441444444";
    const char* s2 = "-774489073332422264746762737228245463180563652011842689807700501272605474199110031554603315973690329757183510955159367506136085073393317761750232570166776031223348568436363314249342217027064344837956894529272549773666000000000000000000000000000000665218444648388169361275462716342615773447084655377011384967431421365707827750201244838394107708406069460519079271847031880783647089926782480741028141120000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000052838058721772159177448907333242226474676273722824546318056365201184268980770050127260547419911003155460331597669032975718351095515936750613608507339331776175023257016677603122334856843636331424934221702706434483795689452927254977366600000000000000000000000000000066521844464838816936127546271634261577344708465537701138496743142136570782775020124483839410770840606946051907927184703188078364708992678248074102814112105806298450223418232068897786551226364110895291587250241802870684197672922365551263705633361655940536021198366288079668278664294850531627150027134760542207000000000000000000000";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_barrt(T, B);
    bn_mod_barrt(R, A, B, T);

    bn_free(A);
    bn_free(B);
    bn_free(R);
    return 0;
}
guidovranken commented 2 years ago

Fixed for the initial test cases but here are several more:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, T, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(T); bn_new(T);
    bn_null(R); bn_new(R);

    const char* s1 = "-40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    const char* s2 = "1000000008085565626950052485339";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_pmers(T, B);
    bn_mod_pmers(R, A, B, T);

    bn_free(A);
    bn_free(B);
    bn_free(R);
    return 0;
}
#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(R); bn_new(R);

    const char* s1 = "-84188714582398424282924837971525302416121644922532904925719910019730366406692145110910451835370677729009982225231537055482344448449494885992079184439080332650492164152024663316259825979114307745219612418660284477206115556017824207836080543415311256999882374573159840575656433390608937570598427225641138811639454618650623237752360321314683560644900656599159998199749784085136636574828755016837198390014053526162457207985313600482369516893453082425634394004035335600569252309342416667058081447309620082759166647721269538581019712937621797680559640478496612342652277971109816641580333453482774934852375430692160643135049372888765762165530901971661913725898008658893736894874410534574770449458104177534565559388040836484430924799911717958648713731258999232626735298645735304006829211593568383492884994715657316401309906170433440078999797386221264638417290776658723938149657917146350646324468364465878782400130619013500564960683051374492818846097783886050431223924920699908387300315865416213231111936508705291748466891577917854198678534647458343121019346820914608258814413442523087232358976263373209362231989459316427654414280233542798437213660397336495805933003144615626216049445562764275564828503587502395165374737568774205340587663190940331526317941044593632864632144165988778533616246667557287090971693878867492395002278968114321981230329283446451073926284733984950374113246880140663243845491443596667469929782549825438957838178740840746290917393928846712857736826153391806687725210764591297970686102806697348325779234582508868778839501393805462143256161991386601225931803177511244663297274967418506906266916109930198988848122532326574508661086728535806312040359321477852460341601556456821094939468762188063205348209305385548433547694225729904545303508164657500258806738689379264053590776128829553009925193782431877555300022969045813190025846726122856689053438166852880708223696488750669697316370921052677402039092729424126274483962879414581976975356285057961826549432614715834366979652717717215386096642885981603909015660729590204835586680218489427212462405730888900102452764241395089004219157215756345661327922021225621250219058168656225771985211325604168363967789471992209627972563557139641630308154822856005581588974718094696685636924336678523303672869195685245680408395385497659076056116488370533082414805096459600494622216377813638298446871252424195649712";
    const char* s2 = "100300000000000000000255";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_monty_conv(R, A, B);

    bn_free(A);
    bn_free(B);
    bn_free(R);
    return 0;
}