Repository navigation
Expand file tree
/
Copy pathoods.rs
More file actions
78 lines (73 loc) · 2.9 KB
/
Copy pathoods.rs
File metadata and controls
78 lines (73 loc) · 2.9 KB
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
use itertools::enumerate;
use super::backend::cpu::CPUCircleEvaluation;
use super::circle::CirclePoint;
use super::constraints::{complex_conjugate_line, pair_vanishing, point_vanishing};
use super::fields::m31::BaseField;
use super::fields::qm31::SecureField;
use super::fields::ComplexConjugate;
use super::poly::circle::CircleEvaluation;
use super::poly::{BitReversedOrder, NaturalOrder};
use super::utils::bit_reverse_index;
/// Evaluates the OODS quotient polynomial on a single point.
pub fn eval_oods_quotient_at_point(
point: CirclePoint<BaseField>,
value: SecureField,
oods_point: CirclePoint<SecureField>,
oods_value: SecureField,
) -> SecureField {
let num = value - oods_value;
let denom: SecureField = point_vanishing(oods_point, point);
num / denom
}
/// Evaluates the pair OODS quotient polynomial on a single point.
/// See `get_pair_oods_quotient` for more details.
pub fn eval_pair_oods_quotient_at_point(
point: CirclePoint<BaseField>,
value: BaseField,
oods_point: CirclePoint<SecureField>,
oods_value: SecureField,
) -> SecureField {
let num = value - complex_conjugate_line(oods_point, oods_value, point);
let denom = pair_vanishing(oods_point, oods_point.complex_conjugate(), point.into_ef());
num / denom
}
/// Returns the OODS quotient polynomial evaluation over the whole domain.
/// Note the resulting polynomial's highest monomial might increase by one.
pub fn get_oods_quotient(
oods_point: CirclePoint<SecureField>,
oods_value: SecureField,
eval: &CPUCircleEvaluation<SecureField, BitReversedOrder>,
) -> CPUCircleEvaluation<SecureField, NaturalOrder> {
let mut values = Vec::with_capacity(eval.domain.size());
for (i, point) in enumerate(eval.domain.iter()) {
let index = bit_reverse_index(i, eval.domain.log_size());
values.push(eval_oods_quotient_at_point(
point,
eval.values[index],
oods_point,
oods_value,
));
}
CircleEvaluation::new(eval.domain, values)
}
/// Returns the pair OODS quotient (i.e quotienting out both the oods point and its complex
/// conjugate) polynomial evaluation over the whole domain. Used in case we don't want the highest
/// monomial of the resulting quotient polynomial to increase which might take it out of the fft
/// space.
pub fn get_pair_oods_quotient(
oods_point: CirclePoint<SecureField>,
oods_value: SecureField,
eval: &CPUCircleEvaluation<BaseField, BitReversedOrder>,
) -> CPUCircleEvaluation<SecureField, NaturalOrder> {
let mut values = Vec::with_capacity(eval.domain.size());
for (i, point) in enumerate(eval.domain.iter()) {
let index = bit_reverse_index(i, eval.domain.log_size());
values.push(eval_pair_oods_quotient_at_point(
point,
eval.values[index],
oods_point,
oods_value,
));
}
CircleEvaluation::new(eval.domain, values)
}