modinv: Modular Inverse and Square Root

In numbers: Number-Theoretic Functions

Modular Inverse and Square Root

Description

Computes the modular inverse of n modulo m.

Usage

modinv(n, m)

modsqrt(a, p)

Arguments

n, m	integer scalars.
a, p	integer modulo p, p a prime.

Details

The modular inverse of n modulo m is the unique natural number 0 < n0 < m such that n * n0 = 1 mod m. It is a simple application of the extended GCD algorithm.

The modular square root of a modulo a prime p is a number x such that x^2 = a mod p. If x is a solution, then p-x is also a solution module p. The function will always return the smaller value.

modsqrt implements the Tonelli-Shanks algorithm which also works for square roots modulo prime powers. The general case is NP-hard.

Value

A natural number smaller m, if n and m are coprime, else NA. modsqrt will return 0 if there is no solution.

See Also

extGCD

Examples

modinv(5, 1001)  #=> 801, as 5*801 = 4005 = 1 mod 1001

Modinv <- Vectorize(modinv, "n")
((1:10)*Modinv(1:10, 11)) %% 11     #=> 1 1 1 1 1 1 1 1 1 1

modsqrt( 8, 23)  # 10 because 10^2 = 100 = 8 mod 23
modsqrt(10, 17)  #  0 because 10 is not a quadratic residue mod 17

numbers documentation built on Dec. 29, 2022, 4:07 p.m.