CODEWITHSUNDEEP
cprecisiongnugmp
Why_Is_This_Hard
Why_Is_This_Hard

Reputation: 119

Understanding mpz_invert

im fairly new to Multiple Precision Arithmetic, and after a few days of trying to figure this out im at a loss. im trying to take the inverse of a number to a high number of deciaml places and have been attempting to work out how to do this using GMP or the mpz/mpf package. however i am a little lost with understanding the example from this link:

http://sepwww.stanford.edu/sep/claudio/Research/Prst_ExpRefl/ShtPSPI/intel/mkl/10.0.3.020/examples/gmp/source/mpz_invert_example.c

/* to compute the inverse of op1 modulo op2 and put result in rop    */
/*                 p*x = s*n + 1    ( rop = p, op1 = x, op2 = n )    */
/*                                                                   */
    n = mpz_invert ( rop, op1, op2 );

I have duplicated this example in my ide complied and run and im getting the correct output:

/* rop =  2288                                                       */
/* n = 1

However i dont understand what 2288 is? i.e. compute the inverse of op1 modulo op2 and put result in rop

could anyone explain how this number is obtained?

or a simple example to say taking:

1875 ^ -6

or w.r.t the following link: How does one calculate 2 ^ -18 using GMP?

taking:

1 / (1875 ^ 6)

Any help would be much appreciated!

Upvotes: 2

Views: 3462

Answers (2)

Why_Is_This_Hard
Why_Is_This_Hard

Reputation: 119

Ok so after some consultation on the mathematics q&a it seems that calculating the Modular multiplicative inverse is going to be of no use to me.

The problem then is, how do i calculate the inverse of a large integer to >16 d.p. in C ? w.r.t the above example, how do i calculate 1/12682271391376756984 for a value of:

4.263162382267667173889615631246062574813592315276851 × 10^-16

that can be represented in an extended format float?

Upvotes: 1

Jack
Jack

Reputation: 133557

mpz_invert is used to calculate a very specific value which is the modular multiplicative inverse of a mod b.

Basically rop is an integer such that op1*rop ≡ 1 (mod op2) which implies that (op1*rop - 1) mod op2 = 0.

Indeed that's the case, with

op1 = 12682271391376756984
op2 = 3527
rop = 2288

op1 * rop = 29017036943470019979392
(op1 * rop - 1) mod op2 = 29017036943470019979391 % 3527 = 0

Upvotes: 7

Related Questions