`Natural.mod` incorrectly returns 0 for large numbers

[dantb]

Hi. Think I’ve found an issue with the Natural.mod term (and therefore probably div, divMod too, since they depend on divImpl to do the heavy lifting).

For context, I’m trying to implement RSA (the cryptography algo) which is why the numbers are huge. This example was taken from a public / private key pair I’ve been using to test the algorithm.

The watch statement below returns Right (Just "0") when it should return a large number. I checked in a couple of other languages just to be sure before reporting this 😅  Haskell and Scala REPL examples which produce the correct value are also below. (It might have nothing to do with the size of the numbers, just guessing as I can see it working for smaller ones.)

Unison watch statement

``` > catch 'let raiseOpt : Optional a -> Text -> {Exception} a raiseOpt opt msg = match opt with Just a -> a None -> Exception.raise (failure msg opt) dividend = raiseOpt (Natural.parse 10 "8295858117270898904167630747870567812334073831093368944563134854802638470945541398974313929422388505238722181902016463236754242294637156049330258919287785866337012777062890948594667586672756399967069615454375306714162789778577555346516173247948113303136865560605391567382284154819032544128187510766707744339939737923993821501716732781649646091640288276621237198129350951796001354227004216930877552494358857830120127158906656766698335694642138957137800044966618035894747347325554251243878626991535842504588114937527609463231297775546404124500539249410821247858756964623345752113943705115802405595931283430228246720553620780527366765705962032414733646037995464837150259053996312163818115932476352641966654526565507693651624889340127618247674832070912750706211674575776963639446198877003000017595144840586631924875228139415656203441229525472239878364369400487960772730826849280157747582613691852987896553808172079840939252907721290451587951919661864166027571969249540310901816948553934928662973283219713683053807534763295581553877845407141832438780068492989137599111517775811371654759502039865655772927003145038146635575055842213949217077553891269866190245821736480382989549141644024787737408318734336") "Bad natural" Debug.trace "Dividend is " $ toDecimalText dividend modulo = raiseOpt (Natural.parse 10 "25995799060019582862645614852685040023056697316737279550883082460077695508875694235238189010112287460427747529259005043044827772094037969227750514390175248942034715929614031392673554828189920550587829193529046986064269886147764883252430488042674919068735364858310115636603675166903997488197802785267082453437689050724683470063283148561164860481528873658075483042928499113618532220138188796742322306575876894748558690474494674896561593422472481454833001789791598182507431137948200801735887018104318514342438158015847853902254990097881823574767284479063859029712108263878574626837039411673163646799040911277114092480543") "Bad natural" Debug.trace "Modulo is " $ toDecimalText modulo Optional.map Natural.toDecimalText $ Natural.mod dividend modulo ```

Haskell REPL

``` Prelude> mod 8295858117270898904167630747870567812334073831093368944563134854802638470945541398974313929422388505238722181902016463236754242294637156049330258919287785866337012777062890948594667586672756399967069615454375306714162789778577555346516173247948113303136865560605391567382284154819032544128187510766707744339939737923993821501716732781649646091640288276621237198129350951796001354227004216930877552494358857830120127158906656766698335694642138957137800044966618035894747347325554251243878626991535842504588114937527609463231297775546404124500539249410821247858756964623345752113943705115802405595931283430228246720553620780527366765705962032414733646037995464837150259053996312163818115932476352641966654526565507693651624889340127618247674832070912750706211674575776963639446198877003000017595144840586631924875228139415656203441229525472239878364369400487960772730826849280157747582613691852987896553808172079840939252907721290451587951919661864166027571969249540310901816948553934928662973283219713683053807534763295581553877845407141832438780068492989137599111517775811371654759502039865655772927003145038146635575055842213949217077553891269866190245821736480382989549141644024787737408318734336 25995799060019582862645614852685040023056697316737279550883082460077695508875694235238189010112287460427747529259005043044827772094037969227750514390175248942034715929614031392673554828189920550587829193529046986064269886147764883252430488042674919068735364858310115636603675166903997488197802785267082453437689050724683470063283148561164860481528873658075483042928499113618532220138188796742322306575876894748558690474494674896561593422472481454833001789791598182507431137948200801735887018104318514342438158015847853902254990097881823574767284479063859029712108263878574626837039411673163646799040911277114092480543 10374016621317638531031414935582427546233451132033863257669476820960913470067553798702297426896484184083719948753385948567757928127279308191082859398695666853966014385334404318656480087804602287861129720419231762606602772672874382997674386585371281608359646287375141973900906117836978039129128526821428984615323193496505269837219302240121846919543116971487969909344048024165277921059591080750004839390928747772123720007372433269283444674932495883842387314608983231084697850384713249321741526505407081097903773588570805896332135447059274037657517460423535387078445068745987895838546110658338975379656871657222782560425 Prelude> ```

Scala REPL

``` scala> import java.math._ import java.math._ scala> val dividend = new BigInteger("8295858117270898904167630747870567812334073831093368944563134854802638470945541398974313929422388505238722181902016463236754242294637156049330258919287785866337012777062890948594667586672756399967069615454375306714162789778577555346516173247948113303136865560605391567382284154819032544128187510766707744339939737923993821501716732781649646091640288276621237198129350951796001354227004216930877552494358857830120127158906656766698335694642138957137800044966618035894747347325554251243878626991535842504588114937527609463231297775546404124500539249410821247858756964623345752113943705115802405595931283430228246720553620780527366765705962032414733646037995464837150259053996312163818115932476352641966654526565507693651624889340127618247674832070912750706211674575776963639446198877003000017595144840586631924875228139415656203441229525472239878364369400487960772730826849280157747582613691852987896553808172079840939252907721290451587951919661864166027571969249540310901816948553934928662973283219713683053807534763295581553877845407141832438780068492989137599111517775811371654759502039865655772927003145038146635575055842213949217077553891269866190245821736480382989549141644024787737408318734336", 10) val dividend: java.math.BigInteger = 829585811727089890416763074787056781233407383109336894456313485480263847094554139897431392942238850523872218190201646323675424229463715604933025891928778586633701277706289094859466758667275639996706961545437530671416278977857755534651617324794811330313686556060539156738228415481903254412818751076670774433993973792399382150171673278164964609164028827662123719812935095179600135422700421693087755249435885783012012715890665676669833569464213895713780004496661803589474734732555425124387862699153584250458811493752760946323129777554640412450053924941082124785875696462334575211394370511580240559593128343022824672055362078052736676570596203241473364603799546483715025905399631216381811593247635264196665452656550769365162488934012761824767... scala> val modulo = new BigInteger("25995799060019582862645614852685040023056697316737279550883082460077695508875694235238189010112287460427747529259005043044827772094037969227750514390175248942034715929614031392673554828189920550587829193529046986064269886147764883252430488042674919068735364858310115636603675166903997488197802785267082453437689050724683470063283148561164860481528873658075483042928499113618532220138188796742322306575876894748558690474494674896561593422472481454833001789791598182507431137948200801735887018104318514342438158015847853902254990097881823574767284479063859029712108263878574626837039411673163646799040911277114092480543", 10) val modulo: java.math.BigInteger = 25995799060019582862645614852685040023056697316737279550883082460077695508875694235238189010112287460427747529259005043044827772094037969227750514390175248942034715929614031392673554828189920550587829193529046986064269886147764883252430488042674919068735364858310115636603675166903997488197802785267082453437689050724683470063283148561164860481528873658075483042928499113618532220138188796742322306575876894748558690474494674896561593422472481454833001789791598182507431137948200801735887018104318514342438158015847853902254990097881823574767284479063859029712108263878574626837039411673163646799040911277114092480543 scala> dividend.mod(modulo) val res0: java.math.BigInteger = 10374016621317638531031414935582427546233451132033863257669476820960913470067553798702297426896484184083719948753385948567757928127279308191082859398695666853966014385334404318656480087804602287861129720419231762606602772672874382997674386585371281608359646287375141973900906117836978039129128526821428984615323193496505269837219302240121846919543116971487969909344048024165277921059591080750004839390928747772123720007372433269283444674932495883842387314608983231084697850384713249321741526505407081097903773588570805896332135447059274037657517460423535387078445068745987895838546110658338975379656871657222782560425 ```

[ceedubs]

Sorry for the really slow reply, but thanks for reporting this @dantb!

There was a bit of discussion about this on Slack and the consensus seems to be that Natural should probably be removed from base. It may become a builtin in the Unison language, or it might be extracted into a separate library.