arcium-primitives 0.7.0

Arcium primitives
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

use std::{
    fmt::Debug,
    hash::Hash,
    ops::{Mul, MulAssign},
};

use ff::Field;
use hybrid_array::{Array, ArraySize};
use serde::{Deserialize, Serialize};
use subtle::Choice;
use wincode::{SchemaRead, SchemaWrite};

use crate::{
    algebra::{
        ops::{AccReduce, DotProduct, MulAccReduce},
        uniform_bytes::FromUniformBytes,
    },
    random::Random,
    types::{identifiers::Named, Positive},
};

pub type ByteSize<F> = <F as FieldExtension>::FieldBytesSize;
pub type BitSize<F> = <F as FieldExtension>::FieldBitSize;
pub type FieldDegree<F> = <F as FieldExtension>::Degree;
pub type Subfield<F> = <F as FieldExtension>::Subfield;

/// A generic trait for field extensions
pub trait FieldExtension:
    Field
    + Ord
    + Debug
    + PartialEq
    + Hash
    + Random
    + Mul<Self::Subfield, Output = Self>
    + MulAssign<Self::Subfield>
    + Serialize
    + for<'de> Deserialize<'de>
    + SchemaWrite<Src = Self>
    + for<'a> SchemaRead<'a, Dst = Self>
    + FromUniformBytes
    + From<u64>
    + From<u128>
    + AccReduce
    + MulAccReduce
    + MulAccReduce<Self, Self::Subfield>
    + DotProduct
    + for<'a> DotProduct<Self, &'a Self>
    + for<'a> DotProduct<&'a Self, &'a Self>
    + DotProduct<Self, Self::Subfield>
    + for<'a> DotProduct<&'a Self, Self::Subfield>
    + Unpin
    + Named
{
    // The underlying prime subfield
    type Subfield: FieldExtension<Subfield = Self::Subfield>;

    type Degree: ArraySize + Positive;
    type FieldBitSize: ArraySize + Positive;
    type FieldBytesSize: ArraySize + Positive;

    fn to_subfield_elements(&self) -> Array<Self::Subfield, Self::Degree>;
    fn from_subfield_elements(elems: Array<Self::Subfield, Self::Degree>) -> Self;
    /// Lift a field element to this extension field.
    ///
    /// Default implementation calls `Self::from_subfield_elements(Array::from([elem, 0, 0, ...]))`.
    fn from_subfield_element(elem: Self::Subfield) -> Self {
        let mut elems = Array::from_fn(|_| Self::Subfield::ZERO);
        elems[0] = elem;
        Self::from_subfield_elements(elems)
    }
    fn to_le_bytes(&self) -> Array<u8, Self::FieldBytesSize>;
    fn from_le_bytes(bytes: &[u8]) -> Option<Self>;

    // TODO[next-gen-trait-solver]: Replace this by a higher-rank trait bound
    // (`for<'a> Mul<&'a Self::Subfield, Output = Self>`) when it is stabilized
    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self;

    fn generator() -> Self;

    /// Applies a linear orthomorphism to the current value.
    ///
    /// * Note: * σ is linear if σ(x + y) = σ(x) + σ(y) and an orthomorphism if σ is a permutation
    ///   then σ'(x) = σ(x) + x is also a permutation.
    fn linear_orthomorphism(&self) -> Self {
        *self * Self::from(2u64)
    }

    /// Computes `(is_square, sqrt(num / div))`, equivalent to [`Field::sqrt_ratio`].
    ///
    /// The default delegates to the generic [`Field::sqrt_ratio`], but fields whose modulus admits
    /// a faster closed form (e.g. primes ≡ 3 mod 4 or ≡ 5 mod 8) can override this to avoid the
    /// generic Tonelli–Shanks path.
    fn sqrt_ratio_ext(num: &Self, div: &Self) -> (Choice, Self) {
        <Self as Field>::sqrt_ratio(num, div)
    }
}

pub trait PrimeFieldExtension: FieldExtension<Subfield = Self> {}

impl<F: FieldExtension<Subfield = Self>> PrimeFieldExtension for F {}