decaf377 0.10.1

A prime-order group designed for use in SNARKs over BLS12-377
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

import sys

GENERATORS = {
    0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001: 15,
    0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001: 22,
    0x4aad957a68b2955982d1347970dec005293a3afc43c8afeb95aee9ac33fd9ff: 5
}


class Properties:
    def __init__(self, p: int):
        self.p = p

    def one(self):
        return 1

    def modulus(self):
        return self.p

    def modulus_plus_1(self):
        return self.p + 1

    def modulus_minus_1(self):
        return self.p - 1

    def modulus_minus_5(self):
        return self.p - 5

    def modulus_bit_size(self):
        return self.p.bit_length()

    def modulus_plus_1_div_4(self):
        return (self.p + 1) // 4

    def two_adicity(self) -> int:
        """
        Calculate the two-adicity of this field.
        """
        acc = self.p - 1
        count = 0
        while acc & 1 == 0:
            count += 1
            acc >>= 1
        return count

    def trace(self):
        """
        (self - 1) / 2^two_adicity
        """
        return (self.p - 1) >> self.two_adicity()

    def trace_minus_one_div_two(self):
        return (self.trace() - 1) >> 1

    def mod_exp(self, a, e):
        insert = a
        acc = 1
        while e != 0:
            if e & 1 == 1:
                acc = acc * insert % self.p
            insert = (insert * insert) % self.p
            e = e >> 1
        return acc

    def legendre_symbol(self, x):
        return self.mod_exp(x, (self.p - 1) >> 1)

    def quadratic_non_residue(self):
        acc = 1
        while self.legendre_symbol(acc) == 1:
            acc += 1
        return acc

    def quadratic_non_residue_to_trace(self):
        return self.mod_exp(self.quadratic_non_residue(), self.trace())

    def modulus_minus_one_div_two(self):
        return ((self.p - 1) >> 1)

    def generator(self):
        if self.p in GENERATORS:
            return GENERATORS[self.p]
        raise ValueError(f"no known generator for {hex(self.p)}")

    def two_adic_root_of_unity(self):
        return self.mod_exp(self.generator(), self.trace())


def to_le_limbs(x, size=64, expected_limb_count=0):
    """
    Convert a number to little endian limbs, with a certain bit size.
    """
    acc = []
    while x > 0:
        acc.append(x & ((1 << size) - 1))
        x >>= size
    while len(acc) < expected_limb_count:
        acc.append(0)
    return acc


def to_monty(x, size, p):
    shift = len(to_le_limbs(p - 1, size)) * size
    return (x << shift) % p


def main(size: int, p: int, what_to_generate: str, mode):
    properties = Properties(p)
    prop = eval(what_to_generate, locals())
    expected_limb_count = (
        properties.modulus_minus_1().bit_length() + size - 1) // size
    if not isinstance(prop, list):
        prop = [prop]
    for x in prop:
        if mode == "hex":
            print(hex(x))
        elif mode == "monty":
            print(to_le_limbs(to_monty(x, size, p), size, expected_limb_count))
        elif mode == "monty_hex":
            print(hex(to_monty(x, size, p)))
        else:
            print(to_le_limbs(x, size, expected_limb_count))


if __name__ == '__main__':
    main(int(sys.argv[1]), int(sys.argv[2], 16),
         sys.argv[3], sys.argv[4] if len(sys.argv) >= 5 else None)