mersenneforum.org (https://www.mersenneforum.org/index.php)
-   PARI/GP (https://www.mersenneforum.org/forumdisplay.php?f=155)
-   -   How does this compute (https://www.mersenneforum.org/showthread.php?t=24530)

 tServo 2019-06-19 01:06

How does this compute

Can someone please explain how this Mod is computed?
TIA

[CODE](20:02) gp > (Mod(2633043,8388607)/9)
%1 = Mod(5884965, 8388607)
(20:02) gp > lift(%1)
%2 = 5884965][/CODE]

 paulunderwood 2019-06-19 01:15

[QUOTE=tServo;519565]Can someone please explain how this Mod is computed?
TIA

[CODE](20:02) gp > (Mod(2633043,8388607)/9)
%1 = Mod(5884965, 8388607)
(20:02) gp > lift(%1)
%2 = 5884965][/CODE][/QUOTE]

It computes 2633043 mod 8388607

Then 2633043/9 mod 8388607

Then "lifts" it to an integer.

It does the division by some kind of extended euclidian algorithm. Note that gcd(8388607,9)==1 must be so.

9 * 5884965 == 2633043 mod 8388607

That is 8388607 divides 9 * 5884965 - 2633043

 hansl 2019-06-19 01:17

[url]https://en.wikipedia.org/wiki/Modular_multiplicative_inverse[/url]

[code]
? Mod(2633043,8388607)/9
%5 = Mod(5884965, 8388607)
? Mod(9,8388607)^-1
%6 = Mod(1864135, 8388607)
? Mod(1/9,8388607)
%7 = Mod(1864135, 8388607)
? Mod(2633043*1864135, 8388607)
%8 = Mod(5884965, 8388607)
?
[/code]

 tServo 2019-06-22 14:48

Thanks ! I appreciate your time.

 All times are UTC. The time now is 07:44.