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.

gcd(a, b)

Euclid’s greatest common denominator algorithm.

extgcd(a, b)

Compute the extended Euclid’s greatest common denominator algorithm.

jacobi(x, n)

Jacobi symbol.

Return type:

int

miller_rabin(n, rounds=50)

Miller-Rabin probabilistic primality test.

Return type:

bool

class RandomModAction(order)

Bases: ResultAction

A random sampling from Z_n.

order: int

exit(result)

property result: Any

inside: bool

class Mod(*args, **kwargs)

Bases: object

An element x of ℤₙ.

x: Any

n: Any

bit_length()

inverse()

Invert the element.

Return type:

Mod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()

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

Return type:

bool

sqrt()

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

Uses the Tonelli-Shanks algorithm.

Return type:

Mod

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class RawMod(x, n)

Bases: Mod

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

x: int

n: int

bit_length()

inverse()

Invert the element.

Return type:

RawMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()

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

sqrt()

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 Undefined(*args, **kwargs)

Bases: Mod

A special undefined element.

x: Any

n: Any

bit_length()

inverse()

Invert the element.

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

sqrt()

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

Uses the Tonelli-Shanks algorithm.

is_residue()

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 SymbolicMod(x, n)

Bases: Mod

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

x: Expr

n: int

bit_length()

inverse()

Invert the element.

Return type:

SymbolicMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

sqrt()

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

Uses the Tonelli-Shanks algorithm.

Return type:

SymbolicMod

is_residue()

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 GMPMod(x, n, ensure=True)

Bases: Mod

An element x of ℤₙ. Implemented by GMP.

n: mpz

x: mpz

bit_length()

inverse()

Invert the element.

Return type:

GMPMod

Returns:

The inverse.

Raises:

NonInvertibleError if the element is not invertible.

is_residue()

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

Return type:

bool

sqrt()

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.