Due to the significant time involved in calculating them using an iterative script, I'm hoping that at least 1 additional identifier common to big integer libraries, perhaps more, could be made available.

This 1st one is almost exactly like the m_apm_integer_pow_nr functions already in the MAPM library, and is designed to work only with integer inputs.

These would be functions for integer-only, that do not want or need any fractions, as calling any function designed to support fractions would just slow these down.

If one of the forum members is able to code an additional integer function into this MAPM library's language, and can PM me, I can explain the other identifier I have in mind, that I hope would be simple for someone who knows C coding better than I do. I also have a simple alias that can perform the other function's calculation too. The other alias is not much longer than the example alias I posted at the bottom here, but it also needs to loop an iteration many times, and as a script it's a lot slower than it should be. It only needs to replicate the $calc functions for add/subtract/multiply/divide/modulo

--

The primary function I'm interested in, I'm hoping would be easy for Khaled to modify an existing MAPM function into the new $identifier. It looks it would be almost exactly like the m_apm_integer_pow_nr in mapm_pwr2.c, except for a minor difference, which is that there would be a 3rd positive integer functioning as the modulus that would be used in 2 places inside the loop, but I don't understand how to insert it. It looks like the modulo operation would use m_apm_integer_div_rem but I'm not sure how.

Inside the source code on github, the function.ref file describes M_pow_mod, which is exactly what I'm looking for, but when I search the rest of the source code I can't find it mentioned anywhere else. This does look unusual, in that it uses the parameters as (exponent,base,modulus) instead of the normal (base,exponent,modulus)

Hopefully the cause of $calc(2^103) returning the wrong result is using m_apm_integer_pow instead of m_apm_integer_pow_nr, and switching to the other function would fix the $calc ^ operator when used with integers. (nr = not rounding)

Below is a copypaste of the m_apm_integer_pow_nr function in mapm_pwr2.c, where I've indicated the 2 places where the 'r' result be would replaced by the remainder from dividing itself by the 3rd parm modulus immeidately after the multiply and squares.

If the cause of the $calc(10^10360) gpf is caused by this library function, modifying it to use a modulus should be able to keep this variant from having the problem that $calc has. This modulo ensures the output result is always smaller than 3rd parameter, and would never create an internal subtotal greater than parm3^squared, so there shouldn't need to be any slowdown to defend against an overflow, other than possibly verifying that the bit length of the 3rd parm modulus does not exceed half the 'safe' answer length.

The library function has an early exit if the exponent is 0 or 1, and when using a modulus parm it should do the same for that too.

I tried to add the modified early exit checks for the 3 variables into the quoted code below. The 1st check is if the modulus is < 2, and should return zero for the same reasons that $calc(9 % 0) and $calc(9 % 1) do. The next check for the exponent is slightly different than in the unmodified. It would continue returning 1 if the exponent is zero, just like $calc(anything^0)==1 but for exponent=1 it should return (%Parm1 % Parm3) in case the 'base' is greater than the modulo.

This variant and the original should probably both have an early-exit check for the base being 0 or 1. Since the $calc(0^0) case has already been handled, this check just needs to handle $calc(0^positive)==0 and $calc(1^positive)==1, so if the base is less than 2, the 'base' is the value to be returned.

At the bottom of this post is the alias I scripted that works perfectly in BF mode except for being super slow due to needing to loop N times for an N bit number. Yes this can be slow for very big modulus numbers, but shouldn't be nearly this slow. When I use the scripted alias equivalent of (m_apm_integer_pow_nr with modulo) against the example 4096-bit modulus, the script takes 32 seconds to finish, and I'm hoping that a compiled equivalent would be much quicker.

For this to work, it looks like 't1' needs to be pulling a '1' off the stack

Quote
void m_apm_integer_pow_nr(M_APM r, M_APM x, unsigned n)
{
if (parm3_modulus < 2) { m_apm_copy(r,MM_Zero); return; }
; if (n < 2) {m_apm_copy(r, n ? x : MM_One); return;}
if (n < 2) {m_apm_copy(r, n ? (x mod parm3_modulus) : MM_One); return;}
if (x < 2) {m_apm_copy(r, x); return;}
M_APM t1 = M_get_stack_var();
m_apm_integer_pow_nr(t1, x, n>>1);
if (n & 1) {
M_APM t2 = M_get_stack_var();
m_apm_multiply(t2, x, t1);
m_apm_multiply(r, t1, t2);
r = r % parm3_modulus
M_restore_stack(2);
return;
}
m_apm_square(r, t1);
r = r % parm3_modulus
M_restore_stack(1);
}
--

One of the uses for these common BigInteger functions is in this 'challenge' scheme...

https://forums.mirc.com/ubbthreads.php/topics/270513/challenge-or-additional-crypto-identifiers

When I had taken a look at this before the MAPM beta, I was fairly certain I could script something to perform the calculation, except for the lack of an identifier that could perform a modular exponentiation calculation, and it also needed something that can quickly and accurately translate between base10 and hex. And, also must be able to do them without taking a lot of time.

And now the BigFloat mode looks like it can reach most of the way there, except for a couple of issues. One of them is the loss of precision when $base tries to translate between base 10/16, which I assume is a problem that goes away when the ^ operator in $calc is fixed, possibly even using the original m_apm_integer_pow_nr without the modulus.

However, it should be possible to perform $base() math without needing to use a pow() where the exponent can grow with the size of the input number, regardless which of the 36 outbases is involved. It should be possible to calculate results by chopping the number into pieces, and perform math based on which chunk something is in, without using a large exponent created by repeated multiplications.

Translation between base 10 and 16 should be able to have a quick shortcut, at least in the 10->16 direction. It looks like the library stores integer input into some kind of format where the value is divided into 32-bit values, and binary storage should be able to turn into a hex string very quickly, and $base(bignumber,10,16) should be able to be much quicker than when outbase is 15 or 17.

And same story when translating from base16 to base10, where it could convert a hex input string to binary storage, then use its normal integer-print routine immediately, and outbase=10 would be much faster than =9 or =11.

Of course these assume the shortcut of bases 10 and 16 not recognizing the base36 alphabet.

---

The other issue preventing scripting a 'challenge' alias is that the calculation time from scripting the Modular Exponentiation is very long.

A while ago, I had already made an alias that worked in doubles mode to perform the modular exponentiation calculation, but because it involved squaring before dividing by the modulus, it couldn't be guaranteed to be accurate within the doubles limit when the modulus was larger than sqrt(2^53).

It turned out I had reinvented the wheel, because my alias was basically the same thing as m_apm_integer_pow_nr except for having a 3rd parameter modulus applied against the result of the multiplication and squarings.

I adapted the alias to work in BigFloat mode, and once I replaced (Base^2) with (Base*Base), I found - yay! - that in BigFloat=on I've not been able to find it returning inaccurate calculation even when I had the 3 inputs being 8192-bit integers.

However, the script can't do the calculation in a reasonable time. It can be quite slow because it needs to loop the BigFloat calculations 'B' times for an exponent whose bit length is 'B'. The command here below creates sample sumbers of the designated bit length, and then calls the alias to performs the modular exponentiation calculation on them, and it's accurate for all the numbers I've tested, regardless how huge. However, when the bit size of the inputs is 2048 bits, it takes a little more than 4 seconds, which is too slow to be a usable script, and that's just 1 part of the 'challenge' calculation that the script would need to handle. And when the bit length doubles to 4096 by editing the 2048, the time increases 8-fold to 32 seconds, yikes.

//var -s %len $calc(2048*$log(2)/$log(10)//1) - 2, %base.bf 7 $+ $str(2,%len) $+ 1, %exp.bf 8 $+ $str(4,%len) $+ 1, %mod.bf 9 $+ $str(6,%len) $+ 1 , %t $ticksqpc | var %result $bf_modpow(%base.bf,%exp.bf,%mod.bf) | echo -a time $calc($ticksqpc - %t) ticks

---

Below is the alias that's identical to m_apm_integer_pow_nr except it uses a 3rd parameter as a modulus which keeps the result from growing in spite of very huge exponent. The original alias was a little longer in order to handle negative parameters according to the modulo math rules, but I took them out to make this as close to the MAPM function as possible.

There's no general concensus over what to name this function. The Wikipedia page names several names, including ModPow PowMod PowerMod ModPower ModExp etc. In some cases they staple this as an optional 3rd parameter onto the normal exponent function that takes only 2 parameters. The mysteriously missing library function was named M_pow_mod.

Code
alias bf_modpow {
  var %base.bf $1 , %exponent.bf $2 , %modulus.bf $3
  var %answer.bf 1
  if (!$regex($1-3,^\d+ \d+ \d+$)) goto syntax
  if (%modulus.bf < 2) return 0
  if (%exponent.bf < 2) {
    if (%exponent.bf == 0) return 1
    if (%exponent.bf == 1) return $calc( %base.bf % %modulus.bf)
  }
  if (%base.bf < 2) return %base.bf
  ; echo -s base: %base.bf exp: %exponent.bf modulus: %modulus.bf
  while (%exponent.bf != 0) {
    if ($calc(%exponent.bf % 2)) { var %answer.bf $calc( (%answer.bf * %base.bf) % %modulus.bf ) }
    ; this next calc multiplies base*base because base^2 returns the wrong result in .bf mode
    var %base.bf $calc( (%base.bf * %base.bf) % %modulus.bf ) , %exponent.bf $calc(%exponent.bf //2)
  }
  return %answer.bf
  :syntax
  echo -sc info *$bf_modpow(base,exponent,modulus)
  halt
}