Two 10-lines functions

gianrico.fini at gianrico.fini at
Thu Jan 21 13:11:40 CET 2010

>There is no function mpn_mulmod_2expp1 in any version of GMP.  (But an
>early version of mpn_mulmod_bnm1 was called something like that.)

I know that the function is not there yet. What is mpn_mulmod_bnm1 supposed to 

>  It computes the product of xp and yp modulo 2^b+1. It assumes that xp and 
>  have exactly b bits.
>What does it mean that "xp has exactly b bits"?  That 2^(b-1) <= xp <
>2^b?  It looks like your code does not handle any b value, or there

The function multiply two numbers modulo 2^b+1. xp points to one of them, and 
contains allways b bits of that number X.
The number can be smaller than 2^(b-1)! Not all bits are set, but the bits 
higher than b are zero.
If X is 2^b, then all the b bits are zero, and the parameter c is used for the 
last bit.
The same for yp and the result.

>I'd suspect mpn_mul_fft might be directly applicable for that.  It has
>existed in GMP since the dark ages...

Possible, but mpn_mul_fft is not documented. The 10-lines function works for 
any b, using only documented functions.

>I am not sure what do do with your contribution, and where it would fit

If you need my functions, I'm happy to give them to you. If you don't, no 
problems. I was challenged and I wrote them.


More information about the gmp-devel mailing list