Re: mp_montgomery_reduce Bug?

On Tue, 25 Jan 2011 12:25:30 -0800 (PST), dilloD <duat66@xxxxxxxxx>
Still have not managed to make the values match with the library
digit_bit cryptopp is also in 32:
const unsigned int * WORD_SIZE WORD_BITS =3D 8, =3D 32
I think I'm doing something wrong.

Let's use the name N for the modulus instead of the long "module". In
most implementations the Montgomery representative of a is Mr(a) = a*R
mod N, where R=2^k normally is a convenient power of two larger than
N. MPArith uses an exponent that is a multiple of DIGIT_BIT.

The Montgomery representative of the a squared mod N is Mr(a^2) =
a^2*R mod N. Since for N=0x90FADE67 the bitsize of N is 32, MPArith
uses two mp_digits for R if DIGIT_BIT=30 or 31 and three mp_digits if
DIGIT_BIT=15, i.e. R is 2^60, 2^62, or 2^45 resp.

With a=0x70F98E5E and N=0x90FADE67 you can calculate Mr(a^2) directly
without invoking mp_montgomery_reduce as

a^2 * 2^60 mod N = 0x4d4e7be5
a^2 * 2^62 mod N = 0x134432c6
a^2 * 2^45 mod N = 0x3b197d29

And these are exactly the values given in my first post.

On the other hand, I found no power of two up to k=200 with
a^2 * 2^k mod N = 0x354910f5, so either Crypto++ is not using this
kind of Montgomery representation, or maybe you do not use it as

In the Crypto++ docs you find "the Montgomery representation
represents each congruence class [a] as a*r % n, where r is a
convenient power of 2"; therefore the first alternative can be
excluded. Unfortunately the automatically generated docs are rather
Greek for me: maybe s = m.Square(r) assumes a valid Montgomery
representative as argument and/or you should use ConvertIn before
calling it, cf. e.g. function Lucas in nbtheory.cpp.

Anyway, I still have no clue, why you want to tinker with the internal
Montgomery representatives.