Skip to main content

gr_ntru/
lib.rs

1//! NTRU-style experiments over finite group algebras.
2//!
3//! Classical NTRU works in `Z[x] / (x^N - 1)`, which is the group algebra
4//! `Z[C_N]`. This crate replaces the cyclic group by an explicit finite group
5//! and runs the same left-sided NTRU-style construction over `Z[G]`.
6
7use std::collections::BTreeMap;
8use std::error::Error;
9use std::fmt;
10
11/// Errors returned by the research implementation.
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub enum NtruError {
14    /// A modulus was not usable.
15    InvalidModulus,
16    /// A group or coefficient vector had the wrong shape.
17    Shape,
18    /// A modular inverse does not exist.
19    NotInvertible,
20    /// Parameters are inconsistent.
21    InvalidParameters(String),
22    /// Optional FFT backend rejected the input.
23    Backend(String),
24}
25
26impl fmt::Display for NtruError {
27    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28        match self {
29            Self::InvalidModulus => write!(f, "invalid modulus"),
30            Self::Shape => write!(f, "shape mismatch"),
31            Self::NotInvertible => write!(f, "element is not invertible"),
32            Self::InvalidParameters(message) => write!(f, "invalid parameters: {message}"),
33            Self::Backend(message) => write!(f, "backend error: {message}"),
34        }
35    }
36}
37
38impl Error for NtruError {}
39
40/// A deterministic pseudo-random generator used to keep examples reproducible
41/// without adding a dependency.
42#[derive(Clone, Debug)]
43pub struct Lcg {
44    state: u64,
45}
46
47impl Lcg {
48    /// Construct a generator from a seed.
49    pub fn new(seed: u64) -> Self {
50        Self { state: seed }
51    }
52
53    /// Return the next `u64`.
54    pub fn next_u64(&mut self) -> u64 {
55        self.state = self
56            .state
57            .wrapping_mul(6_364_136_223_846_793_005)
58            .wrapping_add(1_442_695_040_888_963_407);
59        self.state
60    }
61
62    /// Return a value in `0..upper`.
63    pub fn gen_range(&mut self, upper: usize) -> usize {
64        assert!(upper > 0);
65        (self.next_u64() as usize) % upper
66    }
67}
68
69/// Group families currently implemented by the crate.
70#[derive(Clone, Debug, PartialEq, Eq)]
71pub enum GroupKind {
72    /// The cyclic group `C_n`.
73    Cyclic,
74    /// The dihedral group with rotation order `n`, of order `2n`.
75    Dihedral,
76    /// The symmetric group `S_n`.
77    Symmetric,
78}
79
80/// An explicit finite group with a fixed coefficient ordering.
81#[derive(Clone, Debug)]
82pub struct FiniteGroup {
83    kind: GroupKind,
84    n: usize,
85    name: String,
86    elements: Vec<Vec<usize>>,
87}
88
89impl FiniteGroup {
90    /// Construct the cyclic group `C_n`.
91    pub fn cyclic(n: usize) -> Result<Self, NtruError> {
92        if n == 0 {
93            return Err(NtruError::InvalidParameters("n must be positive".into()));
94        }
95        Ok(Self {
96            kind: GroupKind::Cyclic,
97            n,
98            name: format!("C{n}"),
99            elements: (0..n).map(|i| vec![i]).collect(),
100        })
101    }
102
103    /// Construct the dihedral group with rotation order `n`.
104    pub fn dihedral(n: usize) -> Result<Self, NtruError> {
105        if n < 3 {
106            return Err(NtruError::InvalidParameters(
107                "dihedral rotation order must be at least 3".into(),
108            ));
109        }
110        Ok(Self {
111            kind: GroupKind::Dihedral,
112            n,
113            name: format!("D{n} (order {})", 2 * n),
114            elements: (0..2 * n).map(|i| vec![i]).collect(),
115        })
116    }
117
118    /// Construct the symmetric group `S_n`.
119    pub fn symmetric(n: usize) -> Result<Self, NtruError> {
120        if n == 0 {
121            return Err(NtruError::InvalidParameters("n must be positive".into()));
122        }
123        let elements = all_permutations(n);
124        Ok(Self {
125            kind: GroupKind::Symmetric,
126            n,
127            name: format!("S{n}"),
128            elements,
129        })
130    }
131
132    /// Return the group family.
133    pub fn kind(&self) -> &GroupKind {
134        &self.kind
135    }
136
137    /// Return the group parameter.
138    pub fn n(&self) -> usize {
139        self.n
140    }
141
142    /// Return the display name.
143    pub fn name(&self) -> &str {
144        &self.name
145    }
146
147    /// Return the group order.
148    pub fn order(&self) -> usize {
149        self.elements.len()
150    }
151
152    /// Return the coefficient ordering.
153    pub fn elements(&self) -> &[Vec<usize>] {
154        &self.elements
155    }
156
157    /// Return the product index for two basis indices.
158    pub fn multiply_index(&self, lhs: usize, rhs: usize) -> usize {
159        match self.kind {
160            GroupKind::Cyclic => (lhs + rhs) % self.n,
161            GroupKind::Dihedral => self.multiply_dihedral(lhs, rhs),
162            GroupKind::Symmetric => self.multiply_symmetric(lhs, rhs),
163        }
164    }
165
166    fn multiply_dihedral(&self, lhs: usize, rhs: usize) -> usize {
167        let n = self.n;
168        let lhs_reflection = lhs >= n;
169        let rhs_reflection = rhs >= n;
170        let lhs_k = if lhs_reflection { lhs - n } else { lhs };
171        let rhs_k = if rhs_reflection { rhs - n } else { rhs };
172
173        match (lhs_reflection, rhs_reflection) {
174            (false, false) => (lhs_k + rhs_k) % n,
175            (false, true) => n + ((rhs_k + n - lhs_k) % n),
176            (true, false) => n + ((lhs_k + rhs_k) % n),
177            (true, true) => (rhs_k + n - lhs_k) % n,
178        }
179    }
180
181    fn multiply_symmetric(&self, lhs: usize, rhs: usize) -> usize {
182        let lhs_images = &self.elements[lhs];
183        let rhs_images = &self.elements[rhs];
184        let product: Vec<_> = rhs_images.iter().map(|image| lhs_images[*image]).collect();
185        self.elements
186            .iter()
187            .position(|candidate| *candidate == product)
188            .expect("product permutation is in S_n")
189    }
190}
191
192fn all_permutations(n: usize) -> Vec<Vec<usize>> {
193    let mut current: Vec<_> = (0..n).collect();
194    let mut out = vec![current.clone()];
195    while next_permutation(&mut current) {
196        out.push(current.clone());
197    }
198    out
199}
200
201fn next_permutation(values: &mut [usize]) -> bool {
202    if values.len() < 2 {
203        return false;
204    }
205    let mut pivot = values.len() - 2;
206    while values[pivot] >= values[pivot + 1] {
207        if pivot == 0 {
208            values.reverse();
209            return false;
210        }
211        pivot -= 1;
212    }
213    let mut successor = values.len() - 1;
214    while values[successor] <= values[pivot] {
215        successor -= 1;
216    }
217    values.swap(pivot, successor);
218    values[pivot + 1..].reverse();
219    true
220}
221
222/// Backend call counters from a run.
223#[derive(Clone, Debug, Default, PartialEq, Eq)]
224pub struct BackendStats {
225    counts: BTreeMap<String, usize>,
226}
227
228impl BackendStats {
229    fn record(&mut self, name: &str) {
230        *self.counts.entry(name.to_string()).or_insert(0) += 1;
231    }
232
233    /// Return all backend counters.
234    pub fn counts(&self) -> &BTreeMap<String, usize> {
235        &self.counts
236    }
237
238    /// Format counters as a compact comma-separated string.
239    pub fn format(&self) -> String {
240        self.counts
241            .iter()
242            .map(|(name, count)| format!("{name}={count}"))
243            .collect::<Vec<_>>()
244            .join(", ")
245    }
246}
247
248/// A private key for the NTRU-style construction.
249#[derive(Clone, Debug)]
250pub struct PrivateKey {
251    /// Small private element.
252    pub f: Vec<i64>,
253    /// Inverse of `f` modulo `p`.
254    pub f_p: Vec<u64>,
255    /// Inverse of `f` modulo `q`.
256    pub f_q: Vec<u64>,
257    /// Number of ternary samples tried.
258    pub attempts: usize,
259}
260
261/// Result of one trial.
262#[derive(Clone, Debug)]
263pub struct TrialResult {
264    /// Whether decryption recovered the plaintext.
265    pub success: bool,
266    /// Whether the centered lift matched `pgr + fm` over the integers.
267    pub no_wrap: bool,
268    /// Private-key search attempts.
269    pub key_attempts: usize,
270}
271
272/// Summary for repeated trials.
273#[derive(Clone, Debug)]
274pub struct TrialSummary {
275    /// Requested trial count.
276    pub requested_trials: usize,
277    /// Completed trial count.
278    pub completed_trials: usize,
279    /// Successful decryptions.
280    pub successes: usize,
281    /// No-wrap checks passed.
282    pub no_wraps: usize,
283    /// Key generation failures.
284    pub keygen_failures: usize,
285    /// Average key search attempts.
286    pub avg_key_attempts: Option<f64>,
287    /// Maximum key search attempts.
288    pub max_key_attempts: Option<usize>,
289    /// Backend counters.
290    pub backend_stats: BackendStats,
291}
292
293/// NTRU-style experiment state over a group algebra.
294#[derive(Clone, Debug)]
295pub struct GroupAlgebraNtru {
296    group: FiniteGroup,
297    p: u64,
298    q: u64,
299    d: usize,
300    stats: BackendStats,
301}
302
303impl GroupAlgebraNtru {
304    /// Construct a scheme instance.
305    pub fn new(group: FiniteGroup, p: u64, q: u64, d: usize) -> Result<Self, NtruError> {
306        if !is_prime(p) {
307            return Err(NtruError::InvalidParameters("p must be prime".into()));
308        }
309        if q <= 1 {
310            return Err(NtruError::InvalidParameters(
311                "q must be greater than 1".into(),
312            ));
313        }
314        if gcd(p, q) != 1 {
315            return Err(NtruError::InvalidParameters(
316                "p and q must be coprime".into(),
317            ));
318        }
319        if group.order() < 2 * d + 1 {
320            return Err(NtruError::InvalidParameters(
321                "group is too small for the requested ternary density".into(),
322            ));
323        }
324        Ok(Self {
325            group,
326            p,
327            q,
328            d,
329            stats: BackendStats::default(),
330        })
331    }
332
333    /// Return the group.
334    pub fn group(&self) -> &FiniteGroup {
335        &self.group
336    }
337
338    /// Return `p`.
339    pub fn p(&self) -> u64 {
340        self.p
341    }
342
343    /// Return `q`.
344    pub fn q(&self) -> u64 {
345        self.q
346    }
347
348    /// Return `d`.
349    pub fn d(&self) -> usize {
350        self.d
351    }
352
353    /// Return backend counters.
354    pub fn backend_stats(&self) -> &BackendStats {
355        &self.stats
356    }
357
358    /// Return the multiplicative identity as residues modulo `modulus`.
359    pub fn one_mod(&self, modulus: u64) -> Vec<u64> {
360        let mut out = vec![0; self.group.order()];
361        out[0] = 1 % modulus;
362        out
363    }
364
365    /// Sample an element in `T(d1,d2)`.
366    pub fn random_ternary(
367        &self,
368        rng: &mut Lcg,
369        d1: usize,
370        d2: usize,
371    ) -> Result<Vec<i64>, NtruError> {
372        let support = d1 + d2;
373        if support > self.group.order() {
374            return Err(NtruError::InvalidParameters(
375                "ternary support too large".into(),
376            ));
377        }
378        let mut positions: Vec<_> = (0..self.group.order()).collect();
379        for i in 0..support {
380            let j = i + rng.gen_range(self.group.order() - i);
381            positions.swap(i, j);
382        }
383        let mut out = vec![0; self.group.order()];
384        for &idx in &positions[..d1] {
385            out[idx] = 1;
386        }
387        for &idx in &positions[d1..support] {
388            out[idx] = -1;
389        }
390        Ok(out)
391    }
392
393    /// Sample a centered plaintext modulo `p`.
394    pub fn random_plaintext(&self, rng: &mut Lcg) -> Vec<i64> {
395        let half_width = ((self.p - 1) / 2) as i64;
396        (0..self.group.order())
397            .map(|_| rng.gen_range((2 * half_width + 1) as usize) as i64 - half_width)
398            .collect()
399    }
400
401    /// Multiply two modular coefficient vectors.
402    pub fn multiply_mod(
403        &mut self,
404        lhs: &[u64],
405        rhs: &[u64],
406        modulus: u64,
407    ) -> Result<Vec<u64>, NtruError> {
408        if lhs.len() != self.group.order() || rhs.len() != self.group.order() || modulus == 0 {
409            return Err(NtruError::Shape);
410        }
411
412        if let Some(product) = self.try_fft_multiply(lhs, rhs, modulus)? {
413            return Ok(product);
414        }
415
416        self.stats.record("naive:multiply");
417        self.naive_multiply_mod(lhs, rhs, modulus)
418    }
419
420    /// Invert a modular coefficient vector.
421    pub fn inverse_mod(&mut self, element: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
422        if element.len() != self.group.order() || modulus == 0 {
423            return Err(NtruError::Shape);
424        }
425
426        if let Some(inverse) = self.try_fft_inverse(element, modulus)? {
427            return Ok(inverse);
428        }
429
430        match self.group.kind() {
431            GroupKind::Cyclic => {
432                let inverse = cyclic_inverse_mod(element, modulus)?;
433                self.stats.record("cyclic:invert");
434                self.verify_inverse(element, &inverse, modulus)?;
435                Ok(inverse)
436            }
437            GroupKind::Dihedral => {
438                match dihedral_inverse_via_cyclic(element, self.group.n(), modulus) {
439                    Ok(inverse) => {
440                        self.stats.record("dihedral-cyclic:invert");
441                        self.verify_inverse(element, &inverse, modulus)?;
442                        Ok(inverse)
443                    }
444                    Err(error) => {
445                        if is_prime(modulus) && gcd(2 * self.group.n() as u64, modulus) == 1 {
446                            return Err(error);
447                        }
448                        let inverse = self.linear_solve_inverse(element, modulus)?;
449                        self.stats.record("linear-solve:invert");
450                        self.verify_inverse(element, &inverse, modulus)?;
451                        Ok(inverse)
452                    }
453                }
454            }
455            GroupKind::Symmetric => {
456                let inverse = self.linear_solve_inverse(element, modulus)?;
457                self.stats.record("linear-solve:invert");
458                self.verify_inverse(element, &inverse, modulus)?;
459                Ok(inverse)
460            }
461        }
462    }
463
464    /// Try to invert, returning `None` for noninvertible elements.
465    pub fn try_inverse_mod(&mut self, element: &[u64], modulus: u64) -> Option<Vec<u64>> {
466        self.inverse_mod(element, modulus).ok()
467    }
468
469    /// Generate an NTRU-style private key.
470    pub fn random_private_key(
471        &mut self,
472        rng: &mut Lcg,
473        max_tries: usize,
474    ) -> Result<PrivateKey, NtruError> {
475        for attempts in 1..=max_tries {
476            let f = self.random_ternary(rng, self.d + 1, self.d)?;
477            let f_mod_p = signed_to_mod(&f, self.p);
478            let f_p = match self.try_inverse_mod(&f_mod_p, self.p) {
479                Some(inverse) => inverse,
480                None => continue,
481            };
482            let f_mod_q = signed_to_mod(&f, self.q);
483            let f_q = match self.try_inverse_mod(&f_mod_q, self.q) {
484                Some(inverse) => inverse,
485                None => continue,
486            };
487            return Ok(PrivateKey {
488                f,
489                f_p,
490                f_q,
491                attempts,
492            });
493        }
494        Err(NtruError::NotInvertible)
495    }
496
497    /// Compute the public key `h = F_q g mod q`.
498    pub fn public_key(&mut self, f_q: &[u64], g: &[i64]) -> Result<Vec<u64>, NtruError> {
499        self.multiply_mod(f_q, &signed_to_mod(g, self.q), self.q)
500    }
501
502    /// Encrypt `m` as `e = p h r + m mod q`.
503    pub fn encrypt(&mut self, m: &[i64], h: &[u64], r: &[i64]) -> Result<Vec<u64>, NtruError> {
504        let hr = self.multiply_mod(h, &signed_to_mod(r, self.q), self.q)?;
505        let m_mod_q = signed_to_mod(m, self.q);
506        Ok(hr
507            .iter()
508            .zip(m_mod_q.iter())
509            .map(|(value, message)| {
510                add_mod(mul_mod(self.p % self.q, *value, self.q), *message, self.q)
511            })
512            .collect())
513    }
514
515    /// Decrypt by computing `F_p * center_lift(f e) mod p`.
516    pub fn decrypt(&mut self, e: &[u64], f: &[i64], f_p: &[u64]) -> Result<Vec<i64>, NtruError> {
517        let a_q = self.multiply_mod(&signed_to_mod(f, self.q), e, self.q)?;
518        let a_lift = center_lift_vector(&a_q, self.q);
519        let b_p = self.multiply_mod(f_p, &signed_to_mod(&a_lift, self.p), self.p)?;
520        Ok(center_lift_vector(&b_p, self.p))
521    }
522
523    /// Run one randomized trial.
524    pub fn trial(&mut self, rng: &mut Lcg, max_key_tries: usize) -> Result<TrialResult, NtruError> {
525        let private = self.random_private_key(rng, max_key_tries)?;
526        let g = self.random_ternary(rng, self.d, self.d)?;
527        let r = self.random_ternary(rng, self.d, self.d)?;
528        let m = self.random_plaintext(rng);
529        let h = self.public_key(&private.f_q, &g)?;
530        let e = self.encrypt(&m, &h, &r)?;
531        let decrypted = self.decrypt(&e, &private.f, &private.f_p)?;
532
533        let a_q = self.multiply_mod(&signed_to_mod(&private.f, self.q), &e, self.q)?;
534        let a_lift = center_lift_vector(&a_q, self.q);
535        let expected = add_i64_vectors(
536            &scalar_mul_i64(self.p as i64, &self.multiply_integer(&g, &r)),
537            &self.multiply_integer(&private.f, &m),
538        );
539
540        Ok(TrialResult {
541            success: decrypted == m,
542            no_wrap: a_lift == expected,
543            key_attempts: private.attempts,
544        })
545    }
546
547    /// Run repeated randomized trials.
548    pub fn run_trials(&mut self, trials: usize, max_key_tries: usize, seed: u64) -> TrialSummary {
549        let mut rng = Lcg::new(seed);
550        let mut results = Vec::new();
551        let mut keygen_failures = 0;
552        for _ in 0..trials {
553            match self.trial(&mut rng, max_key_tries) {
554                Ok(result) => results.push(result),
555                Err(NtruError::NotInvertible) => keygen_failures += 1,
556                Err(_) => keygen_failures += 1,
557            }
558        }
559        let successes = results.iter().filter(|result| result.success).count();
560        let no_wraps = results.iter().filter(|result| result.no_wrap).count();
561        let attempts: Vec<_> = results.iter().map(|result| result.key_attempts).collect();
562        let avg_key_attempts = if attempts.is_empty() {
563            None
564        } else {
565            Some(attempts.iter().sum::<usize>() as f64 / attempts.len() as f64)
566        };
567        let max_key_attempts = attempts.into_iter().max();
568        TrialSummary {
569            requested_trials: trials,
570            completed_trials: results.len(),
571            successes,
572            no_wraps,
573            keygen_failures,
574            avg_key_attempts,
575            max_key_attempts,
576            backend_stats: self.stats.clone(),
577        }
578    }
579
580    /// Multiply over the integers without modular reduction.
581    pub fn multiply_integer(&self, lhs: &[i64], rhs: &[i64]) -> Vec<i64> {
582        let mut out = vec![0; self.group.order()];
583        for (lhs_index, lhs_value) in lhs.iter().enumerate() {
584            if *lhs_value == 0 {
585                continue;
586            }
587            for (rhs_index, rhs_value) in rhs.iter().enumerate() {
588                if *rhs_value == 0 {
589                    continue;
590                }
591                let product_index = self.group.multiply_index(lhs_index, rhs_index);
592                out[product_index] += lhs_value * rhs_value;
593            }
594        }
595        out
596    }
597
598    fn naive_multiply_mod(
599        &self,
600        lhs: &[u64],
601        rhs: &[u64],
602        modulus: u64,
603    ) -> Result<Vec<u64>, NtruError> {
604        let mut out = vec![0; self.group.order()];
605        for (lhs_index, lhs_value) in lhs.iter().enumerate() {
606            let lhs_value = *lhs_value % modulus;
607            if lhs_value == 0 {
608                continue;
609            }
610            for (rhs_index, rhs_value) in rhs.iter().enumerate() {
611                let rhs_value = *rhs_value % modulus;
612                if rhs_value == 0 {
613                    continue;
614                }
615                let product_index = self.group.multiply_index(lhs_index, rhs_index);
616                out[product_index] = add_mod(
617                    out[product_index],
618                    mul_mod(lhs_value, rhs_value, modulus),
619                    modulus,
620                );
621            }
622        }
623        Ok(out)
624    }
625
626    fn try_fft_multiply(
627        &mut self,
628        lhs: &[u64],
629        rhs: &[u64],
630        modulus: u64,
631    ) -> Result<Option<Vec<u64>>, NtruError> {
632        match self.group.kind() {
633            GroupKind::Dihedral => self.try_dihedral_fft_multiply(lhs, rhs, modulus),
634            GroupKind::Symmetric => self.try_symmetric_fft_multiply(lhs, rhs, modulus),
635            GroupKind::Cyclic => Ok(None),
636        }
637    }
638
639    fn try_fft_inverse(
640        &mut self,
641        element: &[u64],
642        modulus: u64,
643    ) -> Result<Option<Vec<u64>>, NtruError> {
644        match self.group.kind() {
645            GroupKind::Dihedral => self.try_dihedral_fft_inverse(element, modulus),
646            GroupKind::Symmetric => self.try_symmetric_fft_inverse(element, modulus),
647            GroupKind::Cyclic => Ok(None),
648        }
649    }
650
651    #[cfg(feature = "fft")]
652    fn try_dihedral_fft_multiply(
653        &mut self,
654        lhs: &[u64],
655        rhs: &[u64],
656        modulus: u64,
657    ) -> Result<Option<Vec<u64>>, NtruError> {
658        if self.group.n() < 3
659            || !self.group.n().is_power_of_two()
660            || gcd(2 * self.group.n() as u64, modulus) != 1
661        {
662            return Ok(None);
663        }
664        if is_prime(modulus) && !(modulus - 1).is_multiple_of(self.group.n() as u64) {
665            return Ok(None);
666        }
667        let omega = match fft_dihedral::root_of_unity(self.group.n(), modulus) {
668            Ok(root) => root,
669            Err(_) => return Ok(None),
670        };
671        let n = self.group.n();
672        match fft_dihedral::dihedral_multiply_fft(
673            &lhs[..n],
674            &lhs[n..],
675            &rhs[..n],
676            &rhs[n..],
677            modulus,
678            omega,
679        ) {
680            Ok((rotations, reflections)) => {
681                self.stats.record("fft-dihedral:multiply");
682                Ok(Some(rotations.into_iter().chain(reflections).collect()))
683            }
684            Err(_) => Ok(None),
685        }
686    }
687
688    #[cfg(not(feature = "fft"))]
689    fn try_dihedral_fft_multiply(
690        &mut self,
691        _lhs: &[u64],
692        _rhs: &[u64],
693        _modulus: u64,
694    ) -> Result<Option<Vec<u64>>, NtruError> {
695        Ok(None)
696    }
697
698    #[cfg(feature = "fft")]
699    fn try_dihedral_fft_inverse(
700        &mut self,
701        element: &[u64],
702        modulus: u64,
703    ) -> Result<Option<Vec<u64>>, NtruError> {
704        if self.group.n() < 3
705            || !self.group.n().is_power_of_two()
706            || gcd(2 * self.group.n() as u64, modulus) != 1
707        {
708            return Ok(None);
709        }
710        if is_prime(modulus) && !(modulus - 1).is_multiple_of(self.group.n() as u64) {
711            return Ok(None);
712        }
713        let omega = match fft_dihedral::root_of_unity(self.group.n(), modulus) {
714            Ok(root) => root,
715            Err(_) => return Ok(None),
716        };
717        let n = self.group.n();
718        match fft_dihedral::dihedral_invert_fft(&element[..n], &element[n..], modulus, omega) {
719            Ok((rotations, reflections)) => {
720                let inverse: Vec<_> = rotations.into_iter().chain(reflections).collect();
721                self.stats.record("fft-dihedral:invert");
722                self.verify_inverse(element, &inverse, modulus)?;
723                Ok(Some(inverse))
724            }
725            Err(_) if is_prime(modulus) => Err(NtruError::NotInvertible),
726            Err(_) => Ok(None),
727        }
728    }
729
730    #[cfg(not(feature = "fft"))]
731    fn try_dihedral_fft_inverse(
732        &mut self,
733        _element: &[u64],
734        _modulus: u64,
735    ) -> Result<Option<Vec<u64>>, NtruError> {
736        Ok(None)
737    }
738
739    #[cfg(feature = "fft")]
740    fn try_symmetric_fft_multiply(
741        &mut self,
742        lhs: &[u64],
743        rhs: &[u64],
744        modulus: u64,
745    ) -> Result<Option<Vec<u64>>, NtruError> {
746        if !is_prime(modulus) || modulus <= self.group.n() as u64 {
747            return Ok(None);
748        }
749        let plan = match fft_symmetric::SymmetricFft::new(self.group.n(), modulus) {
750            Ok(plan) => plan,
751            Err(_) => return Ok(None),
752        };
753        match plan.multiply(lhs, rhs) {
754            Ok(product) => {
755                self.stats.record("fft-symmetric:multiply");
756                Ok(Some(product))
757            }
758            Err(_) => Ok(None),
759        }
760    }
761
762    #[cfg(not(feature = "fft"))]
763    fn try_symmetric_fft_multiply(
764        &mut self,
765        _lhs: &[u64],
766        _rhs: &[u64],
767        _modulus: u64,
768    ) -> Result<Option<Vec<u64>>, NtruError> {
769        Ok(None)
770    }
771
772    #[cfg(feature = "fft")]
773    fn try_symmetric_fft_inverse(
774        &mut self,
775        element: &[u64],
776        modulus: u64,
777    ) -> Result<Option<Vec<u64>>, NtruError> {
778        if !is_prime(modulus) || modulus <= self.group.n() as u64 {
779            return Ok(None);
780        }
781        let plan = match fft_symmetric::SymmetricFft::new(self.group.n(), modulus) {
782            Ok(plan) => plan,
783            Err(_) => return Ok(None),
784        };
785        match plan.invert(element) {
786            Ok(inverse) => {
787                self.stats.record("fft-symmetric:invert");
788                self.verify_inverse(element, &inverse, modulus)?;
789                Ok(Some(inverse))
790            }
791            Err(_) => Err(NtruError::NotInvertible),
792        }
793    }
794
795    #[cfg(not(feature = "fft"))]
796    fn try_symmetric_fft_inverse(
797        &mut self,
798        _element: &[u64],
799        _modulus: u64,
800    ) -> Result<Option<Vec<u64>>, NtruError> {
801        Ok(None)
802    }
803
804    fn linear_solve_inverse(&self, element: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
805        let matrix = self.left_multiplication_matrix(element, modulus);
806        solve_modular_linear_system(&matrix, &self.one_mod(modulus), modulus)
807    }
808
809    fn left_multiplication_matrix(&self, element: &[u64], modulus: u64) -> Vec<Vec<u64>> {
810        let mut matrix = vec![vec![0; self.group.order()]; self.group.order()];
811        for (column, _) in self.group.elements().iter().enumerate() {
812            for (index, coeff) in element.iter().enumerate() {
813                let coeff = *coeff % modulus;
814                if coeff == 0 {
815                    continue;
816                }
817                let row = self.group.multiply_index(index, column);
818                matrix[row][column] = add_mod(matrix[row][column], coeff, modulus);
819            }
820        }
821        matrix
822    }
823
824    fn verify_inverse(
825        &mut self,
826        element: &[u64],
827        inverse: &[u64],
828        modulus: u64,
829    ) -> Result<(), NtruError> {
830        let identity = self.one_mod(modulus);
831        if self.multiply_mod(element, inverse, modulus)? != identity {
832            return Err(NtruError::NotInvertible);
833        }
834        if self.multiply_mod(inverse, element, modulus)? != identity {
835            return Err(NtruError::NotInvertible);
836        }
837        Ok(())
838    }
839}
840
841/// Return whether `value` is prime.
842pub fn is_prime(value: u64) -> bool {
843    if value < 2 {
844        return false;
845    }
846    const SMALL: [u64; 12] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
847    for prime in SMALL {
848        if value == prime {
849            return true;
850        }
851        if value.is_multiple_of(prime) {
852            return false;
853        }
854    }
855    let mut d = value - 1;
856    let mut s = 0;
857    while d.is_multiple_of(2) {
858        s += 1;
859        d /= 2;
860    }
861    for base in SMALL {
862        if base >= value {
863            continue;
864        }
865        let mut x = pow_mod(base, d, value);
866        if x == 1 || x == value - 1 {
867            continue;
868        }
869        let mut probably_prime = false;
870        for _ in 0..s - 1 {
871            x = mul_mod(x, x, value);
872            if x == value - 1 {
873                probably_prime = true;
874                break;
875            }
876        }
877        if !probably_prime {
878            return false;
879        }
880    }
881    true
882}
883
884/// Greatest common divisor.
885pub fn gcd(mut a: u64, mut b: u64) -> u64 {
886    while b != 0 {
887        let r = a % b;
888        a = b;
889        b = r;
890    }
891    a
892}
893
894/// Modular addition.
895pub fn add_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
896    ((lhs as u128 + rhs as u128) % modulus as u128) as u64
897}
898
899/// Modular subtraction.
900pub fn sub_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
901    ((lhs as u128 + modulus as u128 - rhs as u128) % modulus as u128) as u64
902}
903
904/// Modular multiplication.
905pub fn mul_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
906    ((lhs as u128 * rhs as u128) % modulus as u128) as u64
907}
908
909/// Modular exponentiation.
910pub fn pow_mod(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
911    let mut acc = 1 % modulus;
912    base %= modulus;
913    while exp > 0 {
914        if exp & 1 == 1 {
915            acc = mul_mod(acc, base, modulus);
916        }
917        base = mul_mod(base, base, modulus);
918        exp >>= 1;
919    }
920    acc
921}
922
923fn extended_gcd(a: i128, b: i128) -> (i128, i128, i128) {
924    if b == 0 {
925        (a, 1, 0)
926    } else {
927        let (g, x, y) = extended_gcd(b, a % b);
928        (g, y, x - (a / b) * y)
929    }
930}
931
932/// Multiplicative inverse modulo `modulus`.
933pub fn inv_mod(value: u64, modulus: u64) -> Option<u64> {
934    let (g, x, _) = extended_gcd(value as i128, modulus as i128);
935    if g != 1 {
936        None
937    } else {
938        Some(x.rem_euclid(modulus as i128) as u64)
939    }
940}
941
942/// Center lift one residue.
943pub fn center_lift(value: u64, modulus: u64) -> i64 {
944    let residue = value % modulus;
945    if residue > modulus / 2 {
946        residue as i64 - modulus as i64
947    } else {
948        residue as i64
949    }
950}
951
952/// Center lift a vector.
953pub fn center_lift_vector(values: &[u64], modulus: u64) -> Vec<i64> {
954    values
955        .iter()
956        .map(|value| center_lift(*value, modulus))
957        .collect()
958}
959
960/// Convert signed coefficients to canonical residues.
961pub fn signed_to_mod(values: &[i64], modulus: u64) -> Vec<u64> {
962    values
963        .iter()
964        .map(|value| (*value as i128).rem_euclid(modulus as i128) as u64)
965        .collect()
966}
967
968fn add_i64_vectors(lhs: &[i64], rhs: &[i64]) -> Vec<i64> {
969    lhs.iter().zip(rhs.iter()).map(|(a, b)| a + b).collect()
970}
971
972fn scalar_mul_i64(scalar: i64, values: &[i64]) -> Vec<i64> {
973    values.iter().map(|value| scalar * value).collect()
974}
975
976/// Solve a modular linear system over `Z/modulus Z` using unit pivots.
977pub fn solve_modular_linear_system(
978    matrix: &[Vec<u64>],
979    rhs: &[u64],
980    modulus: u64,
981) -> Result<Vec<u64>, NtruError> {
982    let size = rhs.len();
983    if matrix.len() != size || matrix.iter().any(|row| row.len() != size) || modulus <= 1 {
984        return Err(NtruError::Shape);
985    }
986    let mut rows: Vec<Vec<u64>> = matrix
987        .iter()
988        .zip(rhs.iter())
989        .map(|(row, rhs)| {
990            let mut augmented: Vec<_> = row.iter().map(|value| value % modulus).collect();
991            augmented.push(*rhs % modulus);
992            augmented
993        })
994        .collect();
995
996    for col in 0..size {
997        let pivot_row = (col..size).find(|row| gcd(rows[*row][col], modulus) == 1);
998        let Some(pivot_row) = pivot_row else {
999            return Err(NtruError::NotInvertible);
1000        };
1001        if pivot_row != col {
1002            rows.swap(col, pivot_row);
1003        }
1004        let pivot_inv = inv_mod(rows[col][col], modulus).ok_or(NtruError::NotInvertible)?;
1005        for entry in &mut rows[col] {
1006            *entry = mul_mod(*entry, pivot_inv, modulus);
1007        }
1008        let pivot = rows[col].clone();
1009        for (row_index, row) in rows.iter_mut().enumerate() {
1010            if row_index == col {
1011                continue;
1012            }
1013            let factor = row[col];
1014            if factor == 0 {
1015                continue;
1016            }
1017            for (idx, entry) in row.iter_mut().enumerate().take(size + 1) {
1018                *entry = sub_mod(*entry, mul_mod(factor, pivot[idx], modulus), modulus);
1019            }
1020        }
1021    }
1022
1023    Ok(rows.into_iter().map(|row| row[size] % modulus).collect())
1024}
1025
1026/// Multiply in `(Z/mZ)[x] / (x^n - 1)`.
1027pub fn cyclic_convolution_mod(
1028    lhs: &[u64],
1029    rhs: &[u64],
1030    modulus: u64,
1031) -> Result<Vec<u64>, NtruError> {
1032    if lhs.len() != rhs.len() || modulus == 0 {
1033        return Err(NtruError::Shape);
1034    }
1035    let n = lhs.len();
1036    let mut out = vec![0; n];
1037    for (i, lhs_value) in lhs.iter().enumerate() {
1038        let lhs_value = *lhs_value % modulus;
1039        if lhs_value == 0 {
1040            continue;
1041        }
1042        for (j, rhs_value) in rhs.iter().enumerate() {
1043            let rhs_value = *rhs_value % modulus;
1044            if rhs_value == 0 {
1045                continue;
1046            }
1047            out[(i + j) % n] = add_mod(
1048                out[(i + j) % n],
1049                mul_mod(lhs_value, rhs_value, modulus),
1050                modulus,
1051            );
1052        }
1053    }
1054    Ok(out)
1055}
1056
1057/// Apply `x -> x^-1` in `(Z/mZ)[x] / (x^n - 1)`.
1058pub fn cyclic_involution(values: &[u64], modulus: u64) -> Vec<u64> {
1059    let n = values.len();
1060    let mut out = vec![0; n];
1061    for (index, value) in values.iter().enumerate() {
1062        out[(n - index) % n] = *value % modulus;
1063    }
1064    out
1065}
1066
1067/// Invert an element of `(Z/mZ)[x] / (x^n - 1)`.
1068pub fn cyclic_inverse_mod(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1069    if values.is_empty() || modulus <= 1 {
1070        return Err(NtruError::Shape);
1071    }
1072    let normalized: Vec<_> = values.iter().map(|value| value % modulus).collect();
1073    if is_prime(modulus) {
1074        cyclic_inverse_prime_field(&normalized, modulus)
1075    } else {
1076        cyclic_inverse_linear_solve(&normalized, modulus)
1077    }
1078}
1079
1080fn cyclic_inverse_linear_solve(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1081    let n = values.len();
1082    let mut matrix = vec![vec![0; n]; n];
1083    for row in 0..n {
1084        for col in 0..n {
1085            matrix[row][col] = values[(row + n - col) % n] % modulus;
1086        }
1087    }
1088    let mut rhs = vec![0; n];
1089    rhs[0] = 1 % modulus;
1090    solve_modular_linear_system(&matrix, &rhs, modulus)
1091}
1092
1093fn cyclic_inverse_prime_field(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1094    let n = values.len();
1095    let mut modulus_poly = vec![0; n + 1];
1096    modulus_poly[0] = (modulus - 1) % modulus;
1097    modulus_poly[n] = 1;
1098    let inverse = polynomial_inverse_mod(values, &modulus_poly, modulus)?;
1099    Ok(polynomial_mod_xn_minus_1(&inverse, n, modulus))
1100}
1101
1102fn polynomial_inverse_mod(
1103    values: &[u64],
1104    modulus_poly: &[u64],
1105    modulus: u64,
1106) -> Result<Vec<u64>, NtruError> {
1107    let mut old_r = trim_polynomial(modulus_poly, modulus);
1108    let mut r = trim_polynomial(values, modulus);
1109    let mut old_t = Vec::new();
1110    let mut t = vec![1];
1111    while !r.is_empty() {
1112        let (quotient, remainder) = polynomial_divmod(&old_r, &r, modulus)?;
1113        old_r = r;
1114        r = remainder;
1115        let next_t = polynomial_sub(&old_t, &polynomial_mul(&quotient, &t, modulus), modulus);
1116        old_t = t;
1117        t = next_t;
1118    }
1119    if old_r.len() != 1 || old_r[0] == 0 {
1120        return Err(NtruError::NotInvertible);
1121    }
1122    let scale = inv_mod(old_r[0], modulus).ok_or(NtruError::NotInvertible)?;
1123    Ok(old_t
1124        .into_iter()
1125        .map(|coeff| mul_mod(scale, coeff, modulus))
1126        .collect())
1127}
1128
1129fn polynomial_divmod(
1130    numerator: &[u64],
1131    denominator: &[u64],
1132    modulus: u64,
1133) -> Result<(Vec<u64>, Vec<u64>), NtruError> {
1134    let mut remainder = trim_polynomial(numerator, modulus);
1135    let denominator = trim_polynomial(denominator, modulus);
1136    if denominator.is_empty() {
1137        return Err(NtruError::Shape);
1138    }
1139    if remainder.len() < denominator.len() {
1140        return Ok((Vec::new(), remainder));
1141    }
1142    let mut quotient = vec![0; remainder.len() - denominator.len() + 1];
1143    let denominator_lead_inv =
1144        inv_mod(*denominator.last().unwrap(), modulus).ok_or(NtruError::NotInvertible)?;
1145    while !remainder.is_empty() && remainder.len() >= denominator.len() {
1146        let shift = remainder.len() - denominator.len();
1147        let coeff = mul_mod(*remainder.last().unwrap(), denominator_lead_inv, modulus);
1148        quotient[shift] = coeff;
1149        for (index, denominator_coeff) in denominator.iter().enumerate() {
1150            remainder[shift + index] = sub_mod(
1151                remainder[shift + index],
1152                mul_mod(coeff, *denominator_coeff, modulus),
1153                modulus,
1154            );
1155        }
1156        remainder = trim_polynomial(&remainder, modulus);
1157    }
1158    Ok((trim_polynomial(&quotient, modulus), remainder))
1159}
1160
1161fn polynomial_mul(lhs: &[u64], rhs: &[u64], modulus: u64) -> Vec<u64> {
1162    if lhs.is_empty() || rhs.is_empty() {
1163        return Vec::new();
1164    }
1165    let mut out = vec![0; lhs.len() + rhs.len() - 1];
1166    for (i, lhs_value) in lhs.iter().enumerate() {
1167        let lhs_value = *lhs_value % modulus;
1168        if lhs_value == 0 {
1169            continue;
1170        }
1171        for (j, rhs_value) in rhs.iter().enumerate() {
1172            let rhs_value = *rhs_value % modulus;
1173            if rhs_value == 0 {
1174                continue;
1175            }
1176            out[i + j] = add_mod(out[i + j], mul_mod(lhs_value, rhs_value, modulus), modulus);
1177        }
1178    }
1179    trim_polynomial(&out, modulus)
1180}
1181
1182fn polynomial_sub(lhs: &[u64], rhs: &[u64], modulus: u64) -> Vec<u64> {
1183    let size = lhs.len().max(rhs.len());
1184    let mut out = vec![0; size];
1185    for (index, entry) in out.iter_mut().enumerate() {
1186        let lhs_value = lhs.get(index).copied().unwrap_or(0);
1187        let rhs_value = rhs.get(index).copied().unwrap_or(0);
1188        *entry = sub_mod(lhs_value, rhs_value, modulus);
1189    }
1190    trim_polynomial(&out, modulus)
1191}
1192
1193fn polynomial_mod_xn_minus_1(values: &[u64], n: usize, modulus: u64) -> Vec<u64> {
1194    let mut out = vec![0; n];
1195    for (index, coeff) in values.iter().enumerate() {
1196        out[index % n] = add_mod(out[index % n], *coeff % modulus, modulus);
1197    }
1198    out
1199}
1200
1201fn trim_polynomial(values: &[u64], modulus: u64) -> Vec<u64> {
1202    let mut out: Vec<_> = values.iter().map(|value| value % modulus).collect();
1203    while out.last() == Some(&0) {
1204        out.pop();
1205    }
1206    out
1207}
1208
1209/// Invert in a dihedral group algebra via a cyclic-ring inverse.
1210pub fn dihedral_inverse_via_cyclic(
1211    element: &[u64],
1212    n: usize,
1213    modulus: u64,
1214) -> Result<Vec<u64>, NtruError> {
1215    if element.len() != 2 * n || n < 3 || modulus <= 1 {
1216        return Err(NtruError::Shape);
1217    }
1218    let rotations: Vec<_> = element[..n].iter().map(|value| value % modulus).collect();
1219    let reflections: Vec<_> = element[n..].iter().map(|value| value % modulus).collect();
1220    let rotation_bar = cyclic_involution(&rotations, modulus);
1221    let reflection_bar = cyclic_involution(&reflections, modulus);
1222    let rotation_norm = cyclic_convolution_mod(&rotations, &rotation_bar, modulus)?;
1223    let reflection_norm = cyclic_convolution_mod(&reflection_bar, &reflections, modulus)?;
1224    let determinant: Vec<_> = rotation_norm
1225        .iter()
1226        .zip(reflection_norm.iter())
1227        .map(|(lhs, rhs)| sub_mod(*lhs, *rhs, modulus))
1228        .collect();
1229    let determinant_inverse = cyclic_inverse_mod(&determinant, modulus)?;
1230    let inverse_rotations = cyclic_convolution_mod(&rotation_bar, &determinant_inverse, modulus)?;
1231    let neg_reflections: Vec<_> = reflections
1232        .iter()
1233        .map(|value| if *value == 0 { 0 } else { modulus - *value })
1234        .collect();
1235    let inverse_reflections =
1236        cyclic_convolution_mod(&neg_reflections, &determinant_inverse, modulus)?;
1237    Ok(inverse_rotations
1238        .into_iter()
1239        .chain(inverse_reflections)
1240        .collect())
1241}
1242
1243/// Check that `Z[C_N]` multiplication is cyclic polynomial multiplication.
1244pub fn verify_cyclic_group_algebra_model(n: usize) -> Result<bool, NtruError> {
1245    let group = FiniteGroup::cyclic(n)?;
1246    let scheme = GroupAlgebraNtru::new(group, 3, 41, 2)?;
1247    for i in 0..n {
1248        for j in 0..n {
1249            if scheme.group.multiply_index(i, j) != (i + j) % n {
1250                return Ok(false);
1251            }
1252        }
1253    }
1254    Ok(true)
1255}
1256
1257#[cfg(test)]
1258mod tests {
1259    use super::*;
1260
1261    #[test]
1262    fn cyclic_model_matches_quotient_ring() {
1263        assert!(verify_cyclic_group_algebra_model(7).unwrap());
1264    }
1265
1266    #[test]
1267    fn dihedral_cyclic_inverse_handles_small_fields() {
1268        let group = FiniteGroup::dihedral(16).unwrap();
1269        let mut fast = GroupAlgebraNtru::new(group.clone(), 3, 97, 3).unwrap();
1270        let dense = GroupAlgebraNtru::new(group, 3, 97, 3).unwrap();
1271        let mut rng = Lcg::new(20260506);
1272        for _ in 0..100 {
1273            let element = fast.random_ternary(&mut rng, 4, 3).unwrap();
1274            let element_mod = signed_to_mod(&element, 3);
1275            let dense_inverse = dense.linear_solve_inverse(&element_mod, 3);
1276            if let Ok(expected) = dense_inverse {
1277                let inverse = fast.inverse_mod(&element_mod, 3).unwrap();
1278                assert_eq!(inverse, expected);
1279                assert!(fast
1280                    .backend_stats()
1281                    .counts()
1282                    .contains_key("dihedral-cyclic:invert"));
1283                return;
1284            }
1285        }
1286        panic!("could not find an invertible sample");
1287    }
1288
1289    #[cfg(feature = "fft")]
1290    #[test]
1291    fn dihedral_fft_inverse_backend_is_used_when_compatible() {
1292        let group = FiniteGroup::dihedral(8).unwrap();
1293        let mut scheme = GroupAlgebraNtru::new(group, 3, 97, 2).unwrap();
1294        let mut element = vec![0; scheme.group().order()];
1295        element[0] = 5;
1296
1297        let inverse = scheme.inverse_mod(&element, 97).unwrap();
1298        assert_eq!(
1299            scheme.multiply_mod(&element, &inverse, 97).unwrap(),
1300            scheme.one_mod(97)
1301        );
1302        assert!(scheme
1303            .backend_stats()
1304            .counts()
1305            .contains_key("fft-dihedral:invert"));
1306    }
1307
1308    #[cfg(feature = "fft")]
1309    #[test]
1310    fn symmetric_fft_inverse_backend_is_used_when_compatible() {
1311        let group = FiniteGroup::symmetric(3).unwrap();
1312        let mut scheme = GroupAlgebraNtru::new(group, 5, 67, 2).unwrap();
1313        let mut element = vec![0; scheme.group().order()];
1314        element[0] = 2;
1315
1316        let inverse = scheme.inverse_mod(&element, 5).unwrap();
1317        assert_eq!(
1318            scheme.multiply_mod(&element, &inverse, 5).unwrap(),
1319            scheme.one_mod(5)
1320        );
1321        assert!(scheme
1322            .backend_stats()
1323            .counts()
1324            .contains_key("fft-symmetric:invert"));
1325    }
1326
1327    #[test]
1328    fn symmetric_s3_round_trips() {
1329        let group = FiniteGroup::symmetric(3).unwrap();
1330        let mut scheme = GroupAlgebraNtru::new(group, 5, 67, 2).unwrap();
1331        let summary = scheme.run_trials(3, 50, 20260506);
1332        assert_eq!(summary.completed_trials, 3);
1333        assert_eq!(summary.successes, 3);
1334        assert_eq!(summary.no_wraps, 3);
1335    }
1336
1337    #[test]
1338    fn dihedral_trials_round_trip() {
1339        let group = FiniteGroup::dihedral(8).unwrap();
1340        let mut scheme = GroupAlgebraNtru::new(group, 3, 97, 2).unwrap();
1341        let summary = scheme.run_trials(2, 100, 20260506);
1342        assert_eq!(summary.completed_trials, 2);
1343        assert_eq!(summary.successes, 2);
1344    }
1345}