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