pyecsca.ec.mod module

Provides several implementations of an element of ℤₙ.

The base class Mod dynamically dispatches to the implementation chosen by the runtime configuration of the library (see pyecsca.misc.cfg.Config). A Python integer based implementation is available under RawMod. A symbolic implementation based on sympy is available under SymbolicMod. If gmpy2 is installed, a GMP based implementation is available under GMPMod.

pyecsca.ec.mod.gcd(a, b)[source]

Euclid’s greatest common denominator algorithm.

pyecsca.ec.mod.extgcd(a, b)[source]

Compute the extended Euclid’s greatest common denominator algorithm.

pyecsca.ec.mod.jacobi(x, n)[source]

Jacobi symbol.

Return type:

int

pyecsca.ec.mod.miller_rabin(n, rounds=50)[source]

Miller-Rabin probabilistic primality test.

Return type:

bool

class pyecsca.ec.mod.RandomModAction(order)[source]

Bases: ResultAction

A random sampling from Z_n.

order: int
exit(result)
property result: Any
inside: bool
class pyecsca.ec.mod.Mod(*args, **kwargs)[source]

Bases: object

An element x of ℤₙ.

x: Any
n: Any
inverse()[source]

Invert the element.

Return type:

Mod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()[source]

Whether this element is a quadratic residue (only implemented for prime modulus).

Return type:

bool

sqrt()[source]

Compute the modular square root of this element (only implemented for prime modulus).

Uses the Tonelli-Shanks algorithm.

Return type:

Mod

classmethod random(n)[source]

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class pyecsca.ec.mod.RawMod(x, n)[source]

Bases: Mod

An element x of ℤₙ (implemented using Python integers).

x: int
n: int
inverse()[source]

Invert the element.

Return type:

RawMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()[source]

Whether this element is a quadratic residue (only implemented for prime modulus).

sqrt()[source]

Compute the modular square root of this element (only implemented for prime modulus).

Uses the Tonelli-Shanks algorithm.

Return type:

RawMod

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class pyecsca.ec.mod.Undefined(*args, **kwargs)[source]

Bases: Mod

A special undefined element.

x: Any
n: Any
inverse()[source]

Invert the element.

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

sqrt()[source]

Compute the modular square root of this element (only implemented for prime modulus).

Uses the Tonelli-Shanks algorithm.

is_residue()[source]

Whether this element is a quadratic residue (only implemented for prime modulus).

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class pyecsca.ec.mod.SymbolicMod(x, n)[source]

Bases: Mod

A symbolic element x of ℤₙ (implemented using sympy).

x: Expr
n: int
inverse()[source]

Invert the element.

Return type:

SymbolicMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

sqrt()[source]

Compute the modular square root of this element (only implemented for prime modulus).

Uses the Tonelli-Shanks algorithm.

Return type:

SymbolicMod

is_residue()[source]

Whether this element is a quadratic residue (only implemented for prime modulus).

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class pyecsca.ec.mod.GMPMod(x, n, ensure=True)[source]

Bases: Mod

An element x of ℤₙ. Implemented by GMP.

n: mpz
x: mpz
inverse()[source]

Invert the element.

Return type:

GMPMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()[source]

Whether this element is a quadratic residue (only implemented for prime modulus).

Return type:

bool

sqrt()[source]

Compute the modular square root of this element (only implemented for prime modulus).

Uses the Tonelli-Shanks algorithm.

Return type:

GMPMod

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.