garoupa 1.210328.11

Cryptographic hash, abstract algebra and operators (previously known as 'hoshy') - see package hosh for a faster, native (compiled) hash/ops approach

garoupa

Cryptographic hash, abstract algebra and operators - see package hosh for a faster, native (compiled) hash/ops approach.

Latest version

Garoupa hosts also some niceties for group theory experimentation.

Python installation

from package

# Set up a virtualenv. 
python3 -m venv venv
source venv/bin/activate

# Install from PyPI
pip install garoupa

from source

cd my-project
git clone https://github.com/davips/garoupa ../garoupa
pip install -e ../garoupa

Examples

Basic operations

from garoupa import Hash

# Hashes can be multiplied.
from garoupa.hash import identity

a = Hash(blob=b"Some large binary content...")
b = Hash(blob=b"Some other binary content. Might be, e.g., an action or another large content.")
c = a * b
print(f"{a} * {b} = {c}")
"""
3dJZQ80zDmZ1hyah8Bj14GFU4gxRr7N2RY5My0iKJn0 * XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 = bGkIRaQg4OOT21Ux5GBiP71v06XGkoiZQei1n3g9Izh
"""

print(~b)
# Multiplication can be reverted by the inverse hash. Zero is the identity hash.
print(f"{b} * {~b} = {b * ~b} = 0")
"""
R4J9jUDTFmjZqI7IpD3rrvVR4SA7opVCpZAu7ZnMID6
XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 * R4J9jUDTFmjZqI7IpD3rrvVR4SA7opVCpZAu7ZnMID6 = 0000000000000000000000000000000000000000000 = 0
"""

print(f"{b} * {identity} = {b * identity} = b")
"""
XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 * 0000000000000000000000000000000000000000000 = XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 = b
"""

print(f"{c} * {~b} = {c * ~b} = {a} = a")
"""
bGkIRaQg4OOT21Ux5GBiP71v06XGkoiZQei1n3g9Izh * R4J9jUDTFmjZqI7IpD3rrvVR4SA7opVCpZAu7ZnMID6 = 3dJZQ80zDmZ1hyah8Bj14GFU4gxRr7N2RY5My0iKJn0 = 3dJZQ80zDmZ1hyah8Bj14GFU4gxRr7N2RY5My0iKJn0 = a
"""

print(f"{~a} * {c} = {~a * c} = {b} = b")
"""
v4QJKocAsbzzSMQre5nY8gxZvRtBgXkYQPn1d5wld4i * bGkIRaQg4OOT21Ux5GBiP71v06XGkoiZQei1n3g9Izh = XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 = XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 = b
"""

# Division is shorthand for reversion.
print(f"{c} / {b} = {c / b} = a")
"""
bGkIRaQg4OOT21Ux5GBiP71v06XGkoiZQei1n3g9Izh / XdQj1SPgqbpRK2uFx4ShKttP6Mc0qHZgLdo6GTk6FO6 = 3dJZQ80zDmZ1hyah8Bj14GFU4gxRr7N2RY5My0iKJn0 = a
"""

# Hash multiplication is not expected to be commutative.
print(f"{a * b} != {b * a}")
"""
bGkIRaQg4OOT21Ux5GBiP71v06XGkoiZQei1n3g9Izh != bGkIRaQg4OOT21Ux5GBiP7gof9J9FBHFaFtRUHFijIu
"""

# Hash multiplication is associative.
print(f"{a * (b * c)} = {(a * b) * c}")
"""
Dpki8EEC2ODuthyLOEqrbQBqQnXEv7LZ5GWUBy9Xr7s = Dpki8EEC2ODuthyLOEqrbQBqQnXEv7LZ5GWUBy9Xr7s
"""

Abstract algebra module

from itertools import islice
from math import factorial

from garoupa.algebra.cyclic import Z
from garoupa.algebra.dihedral import D
from garoupa.algebra.symmetric import Perm
from garoupa.algebra.symmetric import S

# Direct product between:
#   symmetric group S4;
#   cyclic group Z5; and,
#   dihedral group D4.
G = S(4) * Z(5) * D(4)
print(G)
"""
S4×Z5×D4
"""

# Operating over 5 sampled pairs.
for a, b in islice(zip(G, G), 0, 5):
    print(a, "*", b, "=", a * b, sep="\t")
"""
«[1, 0, 3, 2], 3, s6»	*	«[2, 1, 0, 3], 1, s0»	=	«[3, 0, 1, 2], 4, r2»
«[0, 1, 3, 2], 3, s7»	*	«[2, 0, 3, 1], 3, s3»	=	«[3, 0, 2, 1], 1, r0»
«[2, 1, 0, 3], 1, s7»	*	«[0, 1, 2, 3], 0, s2»	=	«[2, 1, 0, 3], 1, r1»
«[0, 2, 1, 3], 1, r4»	*	«[3, 0, 2, 1], 3, r2»	=	«[3, 0, 1, 2], 4, r2»
«[0, 3, 1, 2], 2, r6»	*	«[3, 1, 0, 2], 1, r4»	=	«[2, 3, 0, 1], 3, r2»
"""

# Operator ~ is another way of sampling.
G = S(12)
print(~G)
"""
[0, 11, 8, 2, 1, 9, 7, 4, 10, 6, 3, 5]
"""

# Manual element creation.
last_perm_i = factorial(12) - 1
a = Perm(i=last_perm_i, n=12)
print("Last element of S35:", a)
"""
Last element of S35: [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
"""

# Inverse element. Group S4.
a = Perm(i=21, n=4)
b = Perm(i=17, n=4)
print(a, "*", ~a, "=", (a * ~a).i, "=", a * ~a, "= identity")
"""
[1, 3, 2, 0] * [3, 0, 2, 1] = 0 = [0, 1, 2, 3] = identity
"""

print(a, "*", b, "=", a * b)
"""
[1, 3, 2, 0] * [1, 2, 3, 0] = [3, 2, 0, 1]
"""

print(a, "*", b, "*", ~b, "=", a * b * ~b, "= a")
"""
[1, 3, 2, 0] * [1, 2, 3, 0] * [3, 0, 1, 2] = [1, 3, 2, 0] = a
"""

Commutativity degree of groups

from garoupa.algebra.cyclic import Z
from garoupa.algebra.dihedral import D
from garoupa.algebra.matrix.m import M


def traverse(G):
    i, count = G.order, G.order
    for idx, a in enumerate(G.sorted()):
        for b in list(G.sorted())[idx + 1:]:
            if a * b == b * a:
                count += 2
            i += 2
    print(f"|{G}| = ".rjust(20, ' '),
          f"{G.order}:".ljust(10, ' '),
          f"{count}/{i}:".rjust(15, ' '), f"  {G.bits} bits",
          f"\t{100 * count / i} %", sep="")


# Dihedral
traverse(D(8))
"""
             |D8| = 16:              112/256:  4.0 bits	43.75 %
"""

traverse(D(8) ^ 2)
"""
          |D8×D8| = 256:         12544/65536:  8.0 bits	19.140625 %
"""

# Z4!
traverse(Z(4) * Z(3) * Z(2))
"""
       |Z4×Z3×Z2| = 24:              576/576:  4.584962500721157 bits	100.0 %
"""

# M 3x3 %4
traverse(M(3, 4))

# Large groups (sampling is needed).
Gs = [D(8) ^ 3, D(8) ^ 4, D(8) ^ 5]
for G in Gs:
    i, count = 0, 0
    for a, b in zip(G, G):
        if a * b == b * a:
            count += 1
        if i >= 10_000:
            break
        i += 1
    print(f"|{G}| = ".rjust(20, ' '),
          f"{G.order}:".ljust(10, ' '),
          f"{count}/{i}:".rjust(15, ' '), f"  {G.bits} bits",
          f"\t~{100 * count / i} %", sep="")
"""
           |M3%4| = 64:            2560/4096:  6.0 bits	62.5 %
       |D8×D8×D8| = 4096:          854/10000:  12.0 bits	~8.54 %
    |D8×D8×D8×D8| = 65536:         351/10000:  16.0 bits	~3.51 %
 |D8×D8×D8×D8×D8| = 1048576:       164/10000:  20.0 bits	~1.64 %
"""

Tendence of commutativity on Mn

from itertools import chain

from garoupa.algebra.matrix.m import M
from garoupa.algebra.matrix.m8bit import M8bit


def traverse(G):
    i, count = G.order, G.order
    for idx, a in enumerate(G.sorted()):
        for b in list(G.sorted())[idx + 1:]:
            if a * b == b * a:
                count += 2
            i += 2
    print(f"|{G}| = ".rjust(20, ' '),
          f"{G.order}:".ljust(10, ' '),
          f"{count}/{i}:".rjust(15, ' '), f"  {G.bits} bits",
          f"\t{100 * count / i} %", sep="")


M1_4 = map(M, range(1, 5))
for G in chain(M1_4, [M8bit(), M(5)]):
    traverse(G)
# ...
for G in map(M, range(6, 11)):
    i, count = 0, 0
    for a, b in zip(G, G):
        if a * b == b * a:
            count += 1
        i += 1
        if i >= 1_000_000:
            break
    print(f"|{G}| = ".rjust(20, ' '),
          f"{G.order}:".ljust(10, ' '),
          f"{count}/{i}:".rjust(15, ' '), f"  {G.bits} bits",
          f"\t~{100 * count / i} %", sep="")

"""
|M1| = 1:                        1/1:  0 bits	100.0 %
|M2| = 2:                        4/4:  1 bits	100.0 %
|M3| = 8:                      40/64:  3 bits	62.5 %
|M4| = 64:                 1024/4096:  6 bits	25.0 %
|M8bit| = 256:              14848/65536:  8 bits	22.65625 %
|M5| = 1024:           62464/1048576:  10 bits	5.95703125 %
|M6| = 32768:              286/32768:  15 bits	0.872802734375 %
|M7| = 2097152:          683/1000000:  21 bits	0.0683 %
|M8| = 268435456:         30/1000000:  28 bits	0.003 %
|M9| = 68719476736:        1/1000000:  36 bits	0.0001 %
|M10| = 35184372088832:     0/1000000:  45 bits	0.0 %
"""

Groups benefit from methods from module 'hash'

from garoupa.algebra.matrix import M
m = ~M(23)
print(repr(m.hash))

Features