pyecsca.ec.mod.base module

gcd(a, b)

Euclid’s greatest common denominator algorithm.

Return type:

int

extgcd(a, b)

Compute the extended Euclid’s greatest common denominator algorithm.

Return type:

Tuple[int, int, int]

jacobi(x, n)

Jacobi symbol.

Return type:

int

square_roots(x)

Compute all square roots of x.

Parameters:

x (TypeVar(M, bound= Mod))

Return type:

Set[TypeVar(M, bound= Mod)]

Returns:

cube_roots(x)

Compute all cube roots of x.

Parameters:

x (TypeVar(M, bound= Mod))

Return type:

Set[TypeVar(M, bound= Mod)]

Returns:

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

The result of the action.

inside: bool

class Mod(x, n)

Bases: Generic[M]

An element x of ℤₙ.

Has all the usual special methods that upcast integers automatically:

>>> a = mod(3, 5)
>>> b = mod(2, 5)
>>> a + b
0
>>> a * 2
1
>>> a == 3
True
>>> a == -2
True
>>> -a
2

Plus some additional useful things:

>>> a.inverse()
2
>>> a.is_residue()
False
>>> (a**2).is_residue()
True
>>> (a**2).sqrt() in (a, -a)
True

x: Any

n: Any

bit_length()

Compute the bit length of this element (in its positive integer representation).

Return type:

int

Returns:

The bit-length.

inverse()

Invert the element.

Return type:

TypeVar(M, bound= 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:

TypeVar(M, bound= Mod)

is_cubic_residue()

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

Return type:

bool

cube_root()

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

Uses the Adleman-Manders-Miller algorithm (which is adapted Tonelli-Shanks).

Return type:

TypeVar(M, bound= Mod)

classmethod random(n)

Generate a random Mod in ℤₙ.

Parameters:

n (int) – The order.

Return type:

Mod

Returns:

The random Mod.

class Undefined

Bases: Mod[Undefined]

A special undefined element.

x: Any

n: Any

bit_length()

Compute the bit length of this element (in its positive integer representation).

Returns:

The 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).

cube_root()

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

Uses the Adleman-Manders-Miller algorithm (which is adapted Tonelli-Shanks).

is_cubic_residue()

Whether this element is a cubic 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.

mod(x, n)

Construct a Mod.

Note

This function dispatches to one of RawMod, GMPMod or FlintMod based on what packages are installed and what implementation is configured (see pyecsca.misc.cfg).

Parameters:

• x (int) – The value.

• n (int) – The modulus.

Return type:

Mod

Returns:

A selected Mod implementation object.

Raises:

ValueError in case a working Mod implementation cannot be found.