Re: Modular exponentiation with a noninteger base
Message #11 Posted by Oliver Unter Ecker on 31 Oct 2011, 9:58 a.m.,
in response to message #1 by Oliver Unter Ecker
Ok. Notwithstanding the WolframAlpha bug, the problem remains how to calculate the modular result, without calculating the whole number.
When I hear "exponentiation" and "8 digits", I hear modpow with 10^8.
A 50g will easily tell you the result for 4^98 mod 100:
<< 100 MODSTO 4 98 POWMOD >>
If I try this with '19/5' instead of 4, "No solution in ring" is returned. (3.8 yields "Bad Argument Type".)
It returns a negative number (?) for "4^987654321 mod 100000000" (i.e. 100000000 MODSTO 4 987654321 POWMOD) but WolframAlpha and my other calc return the correct result, in no time.
If I do modpow(3.8, 98, 100), with a standard implementation for modpow
// credit: book "Applied Cryptography" by Bruce Schneier
result = 1;
while (exponent > 0) {
if ((exponent & 1))
result = (result * base) % modulus;
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
an incorrect result is returned. (Note, for floats, "%" becomes an "fmod" and that may be the catch here.)
This works correctly for integer bases.
It also works for a small power (such as 9), suggesting that precision issues could be the problem.
(123.456 mod 100 == 23.456000000000003 in IEEE 754.)
For solving this PE problem, this is likely a wrong attack angle altogether. Brute-force hardly suffices with these problems, and the roots will likely not do, expressed as reals. Purely symbolic solutions are rare in PE, but I'm not optimistic that the task is as straightforward as it may look at first glance.
At any rate, I'd still like to know how to compute the last few digits of a fraction, or real, raised to a large power.
To spell out the PE problem, the complete calculation becomes:
floor(1/3*(4+16/(37+3*i*sqrt(303))^(1/3)+(37+3*i*sqrt(303))^(1/3)) ^ 987654321) mod 100000000
That's for the second(-simplest) root. The last term in full:
floor(1/3 * (1073741824+1152921504606846976/(1237940039285380274899123819+
9*i*sqrt(12379400392853802748991240215))^(1/3)+(1237940039285380274899123819+
9*i*sqrt(12379400392853802748991240215))^(1/3)) ^ 987654321) mod 100000000
WolframAlpha will not compute the results for these.
I'd like to do this on my calculator...
[EDIT: On reflection, as a noninteger float is multiplied the digits are spreading in both direction. So, a large exponent would cause an enormous amount of spread, and all digits needed to be retained to not cause wildly different results in the output. So... inaccurate representation reasons aside, I think it's safe to say this cannot be solved with floats. A fraction would require huge numbers, too, for the result to be accurate. The solution will be a different method, and I guess properties of those roots may well come into play.
Too bad PE doesn't let you "give up" and look at the solution thread to learn from it.]
Edited: 31 Oct 2011, 8:48 p.m.
| 
Go back to the main exhibit hall