mpf_root?

hv at crypt.org hv at crypt.org
Sun Dec 23 18:37:42 CET 2007


Hi, I'm trying to convert some code from PARI/GP to C, using gmp-4.2.2.
The code requires only (big) integer arithmetic, except for one calculation:
  c = floor(1 / (sqrtn(p / q, n) - 1))
.. in which q < p < 2^128 and 3 <= n <= 8.

Now I have a fair amount of experience in integer calculations, but much
less in fp maths: in the above form I would need the equivalent of an
mpf_root() function, which of course isn't in the library.

I think I can see how to converge on the result using the inequality:
  p . c^n <= q . (c+1)^n
using integer arithmetic only, effectively doing a binary chop (though
I need to think whether I can find a way to calculate the upper bound
without another set of trial calculations). Can anyone suggest a better
way?

Hugo van der Sanden


More information about the gmp-discuss mailing list