Thanks for the $powmod. And also the $gcd
I was hoping that the cause of my slowness was due to the overhead from the scripting engine, and a compiled version would do it in much less time. The shorter time for $powmod increases the places it can be used for, but is still high enough to limit where it can be used.
For example, in that challenge script for moonmoon, if the RSA length were 4096, there would be 2 of the 2048 powmods that would take a combined 15 seconds during ON CONNECT, plus the other calculations that it would do. The challenge would also need something that can do $base(4096-bit,16,10), and so far base isn't always accurate above 256-bit or so, and I'm afraid that increasing float precision to support larger integers would just slow a lot of other things down, including $powmod itself. I'm worried that getting useful big number calculations of from a floating point library that tries to use float calculations to perform them - would just make the calculations for both areas be slower than they'd otherwise need to be.
- -
The $gcd was actually one of the the other big number functions I was hoping to get, but I wasn't sure how much I could trust the GCD I saw in MAPM, considering the issues with ^ and % operators for larger numbers, as well as the speed of imitiation-of-base scripts as they were fed larger numbers. i.e. if there are cases where 'close math' is returning the GCD between 'A' and 'almost-B'.
The $gcd is actually sister to another math function that I was interested in, which is the modular multiplicative inverse.
- -
This is the $ModInverse function I referenced in the updated validating of $powmod should $powmod handle negative exponents eventually. And to be clear, I wasn't wanting ModInverse for usage just as a parameter in powmod, that's just a place where it can plug in.
The mod_inverse is closely related to GCD, because when you have 2 positive numbers A,B you'll either be able to get a valid inverse from mod_inverse(A,B) or else you'll have GCD(A,B) being greater than 1. But you won't get both and you won't get neither.
I have a slow script that can calculate the $ModInverse and $Gcd the same way, but my algorithm is different than the way MAPM calculated their GCD, so I need to figure out how to script their GCD to see how the speed of the 2 methods compares, and if it turns out that the MAPM design of GCD was faster as a script, then I'd try to see if there's a way to modify the faster GCD design to find the Inverse instead.
It's hard to benchmark how long this takes, because it depends on the combo of (A,B). It looks like their method repeats a loop B times for a B-bit number, but the math inside the loop is different. But my other method can sometimes be as few as a dozen loops for some (A,B) pairs while other pairs could require somewhere close to B * 60%. Also making the time harder to judge is how the modulus gets whittled down shorter each loop, unlike $powmod where it remains the same
Or, if I'm lucky, the Inverse could be borrowed from OpenSSL as I mentioned in the .bf thread. Here's the reference where OpenSSL has the inverse function.
It's kind of like the m_apm_reciprocal used by MAPM, except this is for integers only, and can only returns an integer instead of a long fraction.
inverse(5,7) = 3, because 3*5 % 7 = 1
inverse(21,35) = error, because there's no possible inverse
inverse(-3,11) means A is 3 less than B, so is inverse(8,11)=7 because 8*7 % 11 = 1
--
Since there's 2 terms and no exponent, the validation rules for negative/0/1 are shorter and simpler, and I'm not sure how OpenSSL would validate them. If OpenSSL handles all of these, there's no need to validate them other than making them be integers. After the subroutine returns the result, if there is no valid inverse, an identifier return value of 0 seems appropriate, since that's not a valid inverse for anything.
modulo always ignores the sign in the modulus
if (B < 0), B = 0 - B
now: A=any B>=0
divide by zero
if (B = 0) return $calc(0/0)
now: A=any B>0
negative -> [0,B-1] by adding B until >= 0
if (A < 0), A = B - (B % abs(A)) = range [0,B-1]
now: A>=0 B>0
if needing to prevent A=0, must first ensure A < B
otherwise the 1st loop makes A<B then no need for pre-check
if (A >= B) A = A % B
now: A=[0,B-1] B>0
0 * anything cannot be 1 greater than a multiple of anything
if (A = 0) return $calc(0/0)
now: A=[1,B-1] B>0
- -
The reason this is so closely related to GCD is that, when GCD is greater than 1, that means (A,B) share a factor other than 1, and it would be impossible to find an inverse to multiply by A that would be 1 greater than a multiple of B. But on the other hand, when there are no shared factors between A and B, you're guaranteed to eventually be able to multiply A by something that's 1 greater than a multiple of B.
Just like with GCD, if there are MAPM approximations during the calculation, that could end up finding either of
value * almost-A % B = 1
value * A % almost-B = 1
