Integer

LWR_rounding(a, q, p)

LWR rounding function, that maps elements from \(\mathbb{Z}_q\) to elements from \(\mathbb{Z}_p\) for some positive integers \(p\) and \(q\).

Parameters:

Name	Type	Description	Default
a	int	Integer to be rounded.	required
q	int	Modulus of domain ring \(\mathbb{Z}_q\).	required
p	int	Modulus of codomain ring \(\mathbb{Z}_p\).	required

Returns:

Type	Description
ModInt	Integer \(c \in [0,p)\).

Source code in src/lbpqc/primitives/integer/integer_ring.py

@np.vectorize
def LWR_rounding(a: int, q: int, p: int) -> ModInt:
    r'''
    **LWR** rounding function, that maps elements from $\mathbb{Z}_q$ to elements from $\mathbb{Z}_p$ for some positive integers $p$ and $q$.

    Args:
        a: Integer to be rounded.
        q: Modulus of domain ring $\mathbb{Z}_q$.
        p: Modulus of codomain ring $\mathbb{Z}_p$.

    Returns:
        Integer $c \in [0,p)$.
    '''
    return math.floor((p/q) * a) % p

center_mod_reduce(a, m, right_closed=True)

Reduces integer \(a\) to it's equivalence class modulo \(m\) represented as an interval centered around zero. Depending on the right_closed parameter, the interval is either $$ \left(-\frac{m}{2}, \frac{m}{2}\right] $$ or $$ \left[-\frac{m}{2}, \frac{m}{2}\right) $$

Parameters:

Name	Type	Description	Default
a	int	integer or numpy array to be reduced.	required
m	int	positive modulus for the congruence relation.	required
right_closed	bool	parameter deciding which side of half-open interval is closed.	True

Returns:

Type	Description
CenteredModInt	Integer or numpy array with entries reduced around zero.

Source code in src/lbpqc/primitives/integer/integer_ring.py

@np.vectorize
def center_mod_reduce(a: int, m: int, right_closed: bool = True) -> CenteredModInt:
    r'''
    Reduces integer $a$ to it's equivalence class modulo $m$ represented as an interval **centered around zero**.
    Depending on the `right_closed` parameter, the interval is either
    $$
    \left(-\frac{m}{2}, \frac{m}{2}\right]
    $$
    or
    $$
    \left[-\frac{m}{2}, \frac{m}{2}\right)
    $$

    Args:
        a: integer or numpy array to be reduced.
        m: positive modulus for the congruence relation.
        right_closed: parameter deciding which side of half-open interval is closed.

    Returns:
        Integer or numpy array with entries reduced around zero.
    '''
    if right_closed:
        return ((a + m // 2) % m) - m // 2
    else:
        return ((a + 1 + m // 2) % m) - m // 2 - 1

eea(a, b)

Implementation of extended Euclidean algorithm, i.e. algorithm that for integers \(a\) and \(b\) computes their \(\gcd\) and coefficients of Bézout's identity, which are integers \(s\) and \(t\) such that $$ sa + tb = \gcd(a,b) $$

Parameters:

Name	Type	Description	Default
a	int	integer a.	required
b	int	integer b.	required

Returns:

Type	Description
Tuple[int, int, int]	Tuple (gcd(a,b), s, t).

Source code in src/lbpqc/primitives/integer/integer_ring.py

def eea(a: int, b: int) -> Tuple[int,int,int]:
    r'''
    Implementation of **extended Euclidean algorithm**, i.e. algorithm that for integers $a$ and $b$ computes their $\gcd$ and
    coefficients of **Bézout's identity**, which are integers $s$ and $t$ such that
    $$
    sa + tb = \gcd(a,b)
    $$

    Args:
        a: integer a.
        b: integer b.

    Returns:
        Tuple (gcd(a,b), s, t).
    '''
    old_s, s = 1, 0
    old_r, r = a, b
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s

    t = 0 if b == 0 else (old_r - old_s * a) // b
    s = old_s
    gcd = old_r
    return gcd, s, t

mod_reduce(a, m)

Reduces integer \(a\) to it's equivalence class modulo \(m\) represented as integer in the interval \([0,m)\).

Parameters:

Name	Type	Description	Default
a	int	integer or numpy array to be reduced.	required
m	int	positive modulus for the congruence relation.	required

Returns:

Type	Description
ModInt	Integer or numpy array with entries from interval \([0, \text{m})\).

Source code in src/lbpqc/primitives/integer/integer_ring.py

@np.vectorize
def mod_reduce(a: int, m: int) -> ModInt:
    r'''
    Reduces integer $a$ to it's equivalence class modulo $m$ represented as integer in the interval $[0,m)$.

    Args:
        a: integer or numpy array to be reduced.
        m: positive modulus for the congruence relation.

    Returns:
        Integer or numpy array with entries from interval $[0, \text{m})$.
    '''
    return a % m

modinv(a, modulus)

Computes multiplicative modular inverse of integer \(a\) for a given modulus. If the inverse does not exists, i.e. \(\gcd(a, \text{modulus}) \neq 1\) then raises ValueError.

Parameters:

Name	Type	Description	Default
a	int	integer, which inverse we want to calculate.	required
modulus	int	positive modulus.	required

Returns:

Type	Description
ModInt	Integer \(r\) from interval \([0, \text{modulus})\) that satisfies \(a \cdot r \equiv 1 \mod \text{modulus}\).

Raises:

Type	Description
ValueError	If \(\gcd(a, \text{modulus}) \neq 1\).

Source code in src/lbpqc/primitives/integer/integer_ring.py

def modinv(a: int, modulus: int) -> ModInt:
    r'''Computes multiplicative modular inverse of integer $a$ for a given modulus.
    If the inverse does not exists, i.e. $\gcd(a, \text{modulus}) \neq 1$ then raises `ValueError`.

    Args:
        a: integer, which inverse we want to calculate.
        modulus: positive modulus.

    Returns:
        Integer $r$ from interval $[0, \text{modulus})$ that satisfies $a \cdot r \equiv 1 \mod \text{modulus}$.

    Raises:
        ValueError: If $\gcd(a, \text{modulus}) \neq 1$.
    '''
    gcd, a_inv, _ = eea(a, modulus)
    if gcd != 1:
        raise ValueError(f"Modular inverse of {a} mod {modulus} does not exist gcd is equal to {gcd}")

    return a_inv % modulus

modpow(a, r, modulus)

Computes $$ a^{r} \mod \text{modulus} $$ using multiply and halve powering algorithm for groups.

Parameters:

Name	Type	Description	Default
a	int	Base.	required
r	int	Exponent.	required
modulus	int	Positive modulus.	required

Returns:

Type	Description
ModInt	Integer \(c \in [0, \text{modulus})\) such that \(c \equiv a^r \mod \text{modulus}\).

Source code in src/lbpqc/primitives/integer/integer_ring.py

def modpow(a: int, r: int, modulus: int) -> ModInt:
    r'''Computes
    $$
    a^{r} \mod \text{modulus}
    $$
    using *multiply and halve* powering algorithm for groups.

    Args:
        a: Base.
        r: Exponent.
        modulus: Positive modulus.

    Returns:
        Integer $c \in [0, \text{modulus})$ such that $c \equiv a^r \mod \text{modulus}$.

    '''
    if r < 0:
        return modpow(modinv(a, modulus), -r, modulus)

    y, z = 1, a
    while r != 0:
        if r % 2 == 1:
            y = (y * z) % modulus
        r //= 2
        z = (z * z) % modulus
    return y

fermat_primality_test(p, s, int_gen=None)

Fermat's primality test

Parameters:

Name	Type	Description	Default
p	int	.	required
s	int	.	required

Source code in src/lbpqc/primitives/integer/prime.py

def fermat_primality_test(p: int, s: int, int_gen= None):
    r'''Fermat's primality test

    Args:
        p:.
        s:.
        int_gen.
    '''

    if p in SMALL_PRIMES:
        return True

    if int_gen is None:
        int_gen = lambda a, b: random.randint(a, b - 1)

    for _ in range(s):
        a = int_gen(2, p - 2)
        if integer_ring.modpow(a, p - 1, p) == 1:
            return False
    return True

is_prime(p)

Equivalent to miller_rabin_primality_test(p, 20).

Parameters:

Name	Type	Description	Default
p	int	Prime candidate.	required

Returns:

Type	Description
bool	True if p is prime (at least according to miller rabin test) False otherwise.

Source code in src/lbpqc/primitives/integer/prime.py

def is_prime(p: int) -> bool:
    r'''
    Equivalent to `miller_rabin_primality_test(p, 20)`.

    Args:
        p: Prime candidate.

    Returns:
        True if p is prime (at least according to miller rabin test) False otherwise.
    '''

    if p in SMALL_PRIMES:
        return True

    return miller_rabin_primality_test(p, 20, lambda a, b: random.randint(a, b - 1))

miller_rabin_primality_test(p, s, int_gen=None)

Miller-Rabin primality test

Parameters:

Name	Type	Description	Default
p	int	.	required
s	int	.	required
int_gen		.	None

Returns:

Type	Description
	.

Source code in src/lbpqc/primitives/integer/prime.py

def miller_rabin_primality_test(p: int, s: int, int_gen= None):
    r''' Miller-Rabin primality test

    Args:
        p:.
        s:.
        int_gen:.

    Returns:
        .
    '''
    if p in SMALL_PRIMES:
        return True

    if p == 1 or p % 2 == 0 or p % 3 == 0 or p % 5 == 0:
        return False

    if int_gen is None:
        int_gen = lambda a, b: random.randint(a, b - 1)

    u = 0
    r = p - 1
    while r % 2 == 0:
        u += 1
        r //= 2

    for _ in range(s):
        a = int_gen(2, p - 2)
        z = integer_ring.modpow(a, r, p)
        if z != 1 and z != p - 1:
            for _ in range(u - 1):
                z = (z * z) % p
                if z == 1:
                    return False
            if z != p - 1:
                return False
        return True