diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index b35701fb3..a182c43e8 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -3269,34 +3269,20 @@ namespace Org.BouncyCastle.Math
break;
}
- // Based on algorithm 1a from chapter 4.4 in Seminumerical Algorithms (Knuth)
-
- // Work out the largest power of 'rdx' that is a positive 64-bit integer
- // TODO possibly cache power/exponent against radix?
- long limit = Int64.MaxValue / radix;
- long power = radix;
- int exponent = 1;
- while (power <= limit)
+ // TODO Could cache the moduli for each radix (soft reference?)
+ IList moduli = Platform.CreateArrayList();
+ BigInteger R = BigInteger.ValueOf(radix);
+ while (R.CompareTo(q) <= 0)
{
- power *= radix;
- ++exponent;
+ moduli.Add(R);
+ R = R.Square();
}
- BigInteger bigPower = BigInteger.ValueOf(power);
+ int scale = moduli.Count;
+ sb.EnsureCapacity(sb.Length + (1 << scale));
- IList S = Platform.CreateArrayList();
- while (q.CompareTo(bigPower) >= 0)
- {
- BigInteger[] qr = q.DivideAndRemainder(bigPower);
- S.Add(Convert.ToString(qr[1].LongValue, radix));
- q = qr[0];
- }
+ ToString(sb, radix, moduli, scale, q);
- sb.Append(Convert.ToString(q.LongValue, radix));
- for (int i = S.Count - 1; i >= 0; --i)
- {
- AppendZeroExtendedString(sb, (string)S[i], exponent);
- }
break;
}
}
@@ -3304,6 +3290,28 @@ namespace Org.BouncyCastle.Math
return sb.ToString();
}
+ private static void ToString(StringBuilder sb, int radix, IList moduli, int scale, BigInteger pos)
+ {
+ if (pos.BitLength < 64)
+ {
+ string s = Convert.ToString(pos.LongValue, radix);
+ if (sb.Length > 1 || (sb.Length == 1 && sb[0] != '-'))
+ {
+ AppendZeroExtendedString(sb, s, 1 << scale);
+ }
+ else if (pos.SignValue != 0)
+ {
+ sb.Append(s);
+ }
+ return;
+ }
+
+ BigInteger[] qr = pos.DivideAndRemainder((BigInteger)moduli[--scale]);
+
+ ToString(sb, radix, moduli, scale, qr[0]);
+ ToString(sb, radix, moduli, scale, qr[1]);
+ }
+
private static void AppendZeroExtendedString(StringBuilder sb, string s, int minLength)
{
for (int len = s.Length; len < minLength; ++len)
|