Tutorialspoint.dev

PHP | gmp_invert() for inverse modulo

The gmp_invert() is a built-in function in PHP which is used to find the modular inverse of a GMP number (GNU Multiple Precision : For large numbers) under another GMP number.

The modular inverse is a number x such that:

a x ≡ 1 (mod b) 

The value of x should be in {0, 1, 2, … b-1}, i.e., in the ring of integer modulo b.



Syntax:

gmp_invert ( $a, $b )

Parameters: This function accepts two GMP numbers $a and $b as shown in the above syntax. This function finds the inverse of $a under modulo $b. These parameters can be a GMP object in PHP version 5.6 and later, or we are also allowed to pass a numeric string provided that it is possible to convert that string to a number.

Return Value: This function returns a GMP number which is the calculated inverse modulo of the two numbers passed to it as arguments. If it is not possible to find the inverse modulo for the given two numbers then this function returns FALSE.

Examples:



Input:  $a = 3, $b = 11
Output: 4
Since (4*3) mod 11 = 1, 4 is modulo inverse of 3
One might think, 15 also as a valid output as "(15*3) mod 11" 
is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not 
valid.

Input:  $a = 10, $b = 17
Output: 12
Since (10*12) mod 17 = 1, 12 is modulo inverse of 3

Below programs illustrate the gmp_invert() function in PHP :

Program 1: Program to calculate the inverse modulo when numeric strings as GMP numbers are passed as arguments.

<?php
// PHP program to calculate inverse modulo
  
// strings as GMP numbers 
$a = "3";
$b = "11";
  
// calculates the inverse modulo of a number
$invMod = gmp_invert($a, $b);
echo $invMod." ";
  
// calculates the inverse modulo of a number
$a = "10"; $b = "17";
$invMod = gmp_invert($a, $b);
echo $invMod." ";
  
?>

Output:

4
12

Program 2: Program to calculate the inverse modulo when GMP numbers are passed as arguments.

<?php
// PHP program to calculate inverse modulo
  
// creating GMP numbers using gmp_init() 
$a = gmp_init(3, 10);
$b = gmp_init(11, 10);
  
// calculates the inverse modulo of a number
$invMod = gmp_invert($a, $b);
echo $invMod." ";
  
// calculates the inverse modulo of a number
$a = gmp_init(10, 10); 
$b = gmp_init(17, 10);
$invMod = gmp_invert($a, $b);
echo $invMod." ";
  
?>

Output:

4
12

Reference:
http://php.net/manual/en/function.gmp-invert.php



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter