fhe_math/rq/
convert.rs

1//! Implementation of conversions from and to polynomials.
2
3use super::{traits::TryConvertFrom, Context, Poly, Representation};
4use crate::{
5    proto::rq::{Representation as RepresentationProto, Rq},
6    Error, Result,
7};
8use itertools::{izip, Itertools};
9use ndarray::{Array2, ArrayView, Axis};
10use num_bigint::BigUint;
11use std::borrow::Cow;
12use std::sync::Arc;
13use zeroize::{Zeroize, Zeroizing};
14
15impl From<&Poly> for Rq {
16    fn from(p: &Poly) -> Self {
17        assert!(!p.has_lazy_coefficients);
18
19        let needs_transform = p.representation != Representation::PowerBasis;
20        let q: Cow<'_, Poly> = if needs_transform {
21            let mut owned = p.clone();
22            owned.change_representation(Representation::PowerBasis);
23            Cow::Owned(owned)
24        } else {
25            Cow::Borrowed(p)
26        };
27
28        let mut proto = Rq::default();
29        match p.representation {
30            Representation::PowerBasis => {
31                proto.representation = RepresentationProto::Powerbasis as i32;
32            }
33            Representation::Ntt => {
34                proto.representation = RepresentationProto::Ntt as i32;
35            }
36            Representation::NttShoup => {
37                proto.representation = RepresentationProto::Nttshoup as i32;
38            }
39        }
40        let serialization: Vec<u8> = izip!(q.coefficients.outer_iter(), p.ctx.q.iter())
41            .flat_map(|(v, qi)| qi.serialize_vec(v.as_slice().unwrap()))
42            .collect();
43        proto.coefficients = serialization;
44        proto.degree = p.ctx.degree as u32;
45        proto.allow_variable_time = p.allow_variable_time_computations;
46        proto
47    }
48}
49
50impl TryConvertFrom<Vec<u64>> for Poly {
51    fn try_convert_from<R>(
52        mut v: Vec<u64>,
53        ctx: &Arc<Context>,
54        variable_time: bool,
55        representation: R,
56    ) -> Result<Self>
57    where
58        R: Into<Option<Representation>>,
59    {
60        let repr = representation.into();
61        match repr {
62            Some(Representation::Ntt) => {
63                if let Ok(coefficients) = Array2::from_shape_vec((ctx.q.len(), ctx.degree), v) {
64                    Ok(Self {
65                        ctx: ctx.clone(),
66                        representation: repr.unwrap(),
67                        allow_variable_time_computations: variable_time,
68                        coefficients,
69                        coefficients_shoup: None,
70                        has_lazy_coefficients: false,
71                    })
72                } else {
73                    Err(Error::Default(
74                        "In Ntt representation, all coefficients must be specified".to_string(),
75                    ))
76                }
77            }
78            Some(Representation::NttShoup) => {
79                if let Ok(coefficients) = Array2::from_shape_vec((ctx.q.len(), ctx.degree), v) {
80                    let mut p = Self {
81                        ctx: ctx.clone(),
82                        representation: repr.unwrap(),
83                        allow_variable_time_computations: variable_time,
84                        coefficients,
85                        coefficients_shoup: None,
86                        has_lazy_coefficients: false,
87                    };
88                    p.compute_coefficients_shoup();
89                    Ok(p)
90                } else {
91                    Err(Error::Default(
92                        "In NttShoup representation, all coefficients must be specified"
93                            .to_string(),
94                    ))
95                }
96            }
97            Some(Representation::PowerBasis) => {
98                if v.len() == ctx.q.len() * ctx.degree {
99                    let coefficients =
100                        Array2::from_shape_vec((ctx.q.len(), ctx.degree), v).unwrap();
101                    Ok(Self {
102                        ctx: ctx.clone(),
103                        representation: repr.unwrap(),
104                        allow_variable_time_computations: variable_time,
105                        coefficients,
106                        coefficients_shoup: None,
107                        has_lazy_coefficients: false,
108                    })
109                } else if v.len() <= ctx.degree {
110                    let mut out = Self::zero(ctx, repr.unwrap());
111                    if variable_time {
112                        unsafe {
113                            izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(
114                                |(mut w, qi)| {
115                                    let wi = w.as_slice_mut().unwrap();
116                                    wi[..v.len()].copy_from_slice(&v);
117                                    qi.reduce_vec_vt(wi);
118                                },
119                            );
120                            out.allow_variable_time_computations();
121                        }
122                    } else {
123                        izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(
124                            |(mut w, qi)| {
125                                let wi = w.as_slice_mut().unwrap();
126                                wi[..v.len()].copy_from_slice(&v);
127                                qi.reduce_vec(wi);
128                            },
129                        );
130                        v.zeroize();
131                    }
132                    Ok(out)
133                } else {
134                    Err(Error::Default("In PowerBasis representation, either all coefficients must be specified, or only coefficients up to the degree".to_string()))
135                }
136            }
137            None => Err(Error::Default(
138                "When converting from a vector, the representation needs to be specified"
139                    .to_string(),
140            )),
141        }
142    }
143}
144
145impl TryConvertFrom<&Rq> for Poly {
146    fn try_convert_from<R>(
147        value: &Rq,
148        ctx: &Arc<Context>,
149        variable_time: bool,
150        representation: R,
151    ) -> Result<Self>
152    where
153        R: Into<Option<Representation>>,
154    {
155        let repr = value
156            .representation
157            .try_into()
158            .map_err(|_| Error::Default("Invalid representation".to_string()))?;
159        let representation_from_proto = match repr {
160            RepresentationProto::Powerbasis => Representation::PowerBasis,
161            RepresentationProto::Ntt => Representation::Ntt,
162            RepresentationProto::Nttshoup => Representation::NttShoup,
163            _ => return Err(Error::Default("Unknown representation".to_string())),
164        };
165
166        let variable_time = variable_time || value.allow_variable_time;
167
168        if let Some(r) = representation.into() as Option<Representation> {
169            if r != representation_from_proto {
170                return Err(Error::Default("The representation asked for does not match the representation in the serialization".to_string()));
171            }
172        }
173
174        let degree = value.degree as usize;
175        if degree % 8 != 0 || degree < 8 {
176            return Err(Error::Default("Invalid degree".to_string()));
177        }
178
179        let mut expected_nbytes = 0;
180        ctx.q
181            .iter()
182            .for_each(|qi| expected_nbytes += qi.serialization_length(degree));
183        if value.coefficients.len() != expected_nbytes {
184            return Err(Error::Default("Invalid coefficients".to_string()));
185        }
186
187        let mut index = 0;
188        let power_basis_coefficients: Vec<u64> = ctx
189            .q
190            .iter()
191            .flat_map(|qi| {
192                let size = qi.serialization_length(degree);
193                let v = qi.deserialize_vec(&value.coefficients[index..index + size]);
194                index += size;
195                v
196            })
197            .collect();
198
199        let mut p = Poly::try_convert_from(
200            power_basis_coefficients,
201            ctx,
202            variable_time,
203            Representation::PowerBasis,
204        )?;
205        p.change_representation(representation_from_proto);
206        Ok(p)
207    }
208}
209
210impl TryConvertFrom<Array2<u64>> for Poly {
211    fn try_convert_from<R>(
212        a: Array2<u64>,
213        ctx: &Arc<Context>,
214        variable_time: bool,
215        representation: R,
216    ) -> Result<Self>
217    where
218        R: Into<Option<Representation>>,
219    {
220        if a.shape() != [ctx.q.len(), ctx.degree] {
221            Err(Error::Default(
222                "The array of coefficient does not have the correct shape".to_string(),
223            ))
224        } else if let Some(repr) = representation.into() {
225            let mut p = Self {
226                ctx: ctx.clone(),
227                representation: repr,
228                allow_variable_time_computations: variable_time,
229                coefficients: a,
230                coefficients_shoup: None,
231                has_lazy_coefficients: false,
232            };
233            if p.representation == Representation::NttShoup {
234                p.compute_coefficients_shoup()
235            }
236            Ok(p)
237        } else {
238            Err(Error::Default("When converting from a 2-dimensional array, the representation needs to be specified".to_string()))
239        }
240    }
241}
242
243impl<'a> TryConvertFrom<&'a [u64]> for Poly {
244    fn try_convert_from<R>(
245        v: &'a [u64],
246        ctx: &Arc<Context>,
247        variable_time: bool,
248        representation: R,
249    ) -> Result<Self>
250    where
251        R: Into<Option<Representation>>,
252    {
253        Poly::try_convert_from(v.to_vec(), ctx, variable_time, representation)
254    }
255}
256
257impl<'a> TryConvertFrom<&'a [i64]> for Poly {
258    fn try_convert_from<R>(
259        v: &'a [i64],
260        ctx: &Arc<Context>,
261        variable_time: bool,
262        representation: R,
263    ) -> Result<Self>
264    where
265        R: Into<Option<Representation>>,
266    {
267        if representation.into() != Some(Representation::PowerBasis) {
268            Err(Error::Default(
269                "Converting signed integer require to import in PowerBasis representation"
270                    .to_string(),
271            ))
272        } else if v.len() <= ctx.degree {
273            let mut out = Self::zero(ctx, Representation::PowerBasis);
274            if variable_time {
275                unsafe { out.allow_variable_time_computations() }
276            }
277            izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(|(mut w, qi)| {
278                let wi = w.as_slice_mut().unwrap();
279                if variable_time {
280                    unsafe { wi[..v.len()].copy_from_slice(&qi.reduce_vec_i64_vt(v)) }
281                } else {
282                    wi[..v.len()].copy_from_slice(Zeroizing::new(qi.reduce_vec_i64(v)).as_ref());
283                }
284            });
285            Ok(out)
286        } else {
287            Err(Error::Default("In PowerBasis representation with signed integers, only `degree` coefficients can be specified".to_string()))
288        }
289    }
290}
291
292impl<'a> TryConvertFrom<&'a Vec<i64>> for Poly {
293    fn try_convert_from<R>(
294        v: &'a Vec<i64>,
295        ctx: &Arc<Context>,
296        variable_time: bool,
297        representation: R,
298    ) -> Result<Self>
299    where
300        R: Into<Option<Representation>>,
301    {
302        Poly::try_convert_from(v.as_ref() as &[i64], ctx, variable_time, representation)
303    }
304}
305
306impl<'a> TryConvertFrom<&'a [BigUint]> for Poly {
307    fn try_convert_from<R>(
308        v: &'a [BigUint],
309        ctx: &Arc<Context>,
310        variable_time: bool,
311        representation: R,
312    ) -> Result<Self>
313    where
314        R: Into<Option<Representation>>,
315    {
316        let repr = representation.into();
317
318        if v.len() > ctx.degree {
319            Err(Error::Default(
320                "The slice contains too many big integers compared to the polynomial degree"
321                    .to_string(),
322            ))
323        } else if repr.is_some() {
324            let mut coefficients = Array2::zeros((ctx.q.len(), ctx.degree));
325
326            izip!(coefficients.axis_iter_mut(Axis(1)), v).for_each(|(mut c, vi)| {
327                c.assign(&ArrayView::from(&ctx.rns.project(vi)));
328            });
329
330            let mut p = Self {
331                ctx: ctx.clone(),
332                representation: repr.unwrap(),
333                allow_variable_time_computations: variable_time,
334                coefficients,
335                coefficients_shoup: None,
336                has_lazy_coefficients: false,
337            };
338
339            match p.representation {
340                Representation::PowerBasis => Ok(p),
341                Representation::Ntt => Ok(p),
342                Representation::NttShoup => {
343                    p.compute_coefficients_shoup();
344                    Ok(p)
345                }
346            }
347        } else {
348            Err(Error::Default(
349                "When converting from a vector, the representation needs to be specified"
350                    .to_string(),
351            ))
352        }
353    }
354}
355
356impl<'a> TryConvertFrom<&'a Vec<u64>> for Poly {
357    fn try_convert_from<R>(
358        v: &'a Vec<u64>,
359        ctx: &Arc<Context>,
360        variable_time: bool,
361        representation: R,
362    ) -> Result<Self>
363    where
364        R: Into<Option<Representation>>,
365    {
366        Poly::try_convert_from(v.to_vec(), ctx, variable_time, representation)
367    }
368}
369
370impl<'a, const N: usize> TryConvertFrom<&'a [u64; N]> for Poly {
371    fn try_convert_from<R>(
372        v: &'a [u64; N],
373        ctx: &Arc<Context>,
374        variable_time: bool,
375        representation: R,
376    ) -> Result<Self>
377    where
378        R: Into<Option<Representation>>,
379    {
380        Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
381    }
382}
383
384impl<'a, const N: usize> TryConvertFrom<&'a [BigUint; N]> for Poly {
385    fn try_convert_from<R>(
386        v: &'a [BigUint; N],
387        ctx: &Arc<Context>,
388        variable_time: bool,
389        representation: R,
390    ) -> Result<Self>
391    where
392        R: Into<Option<Representation>>,
393    {
394        Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
395    }
396}
397
398impl<'a, const N: usize> TryConvertFrom<&'a [i64; N]> for Poly {
399    fn try_convert_from<R>(
400        v: &'a [i64; N],
401        ctx: &Arc<Context>,
402        variable_time: bool,
403        representation: R,
404    ) -> Result<Self>
405    where
406        R: Into<Option<Representation>>,
407    {
408        Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
409    }
410}
411
412impl From<&Poly> for Vec<u64> {
413    fn from(p: &Poly) -> Self {
414        p.coefficients.as_slice().unwrap().to_vec()
415    }
416}
417
418impl From<&Poly> for Vec<BigUint> {
419    fn from(p: &Poly) -> Self {
420        izip!(p.coefficients.axis_iter(Axis(1)))
421            .map(|c| p.ctx.rns.lift(c))
422            .collect_vec()
423    }
424}
425
426#[cfg(test)]
427mod tests {
428    use crate::{
429        proto::rq::Rq,
430        rq::{traits::TryConvertFrom, Context, Poly, Representation},
431        Error as CrateError,
432    };
433    use num_bigint::BigUint;
434    use rand::rng;
435    use std::{error::Error, sync::Arc};
436
437    static MODULI: &[u64; 3] = &[1153, 4611686018326724609, 4611686018309947393];
438
439    #[test]
440    fn proto() -> Result<(), Box<dyn Error>> {
441        let mut rng = rng();
442        for modulus in MODULI {
443            let ctx = Arc::new(Context::new(&[*modulus], 16)?);
444            let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
445            let proto = Rq::from(&p);
446            assert_eq!(Poly::try_convert_from(&proto, &ctx, false, None)?, p);
447            assert_eq!(
448                Poly::try_convert_from(&proto, &ctx, false, Representation::PowerBasis)?,
449                p
450            );
451            assert_eq!(
452				Poly::try_convert_from(&proto, &ctx, false, Representation::Ntt)
453					.expect_err("Should fail because of mismatched representations"),
454					CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
455			);
456            assert_eq!(
457				Poly::try_convert_from(&proto, &ctx, false, Representation::NttShoup)
458					.expect_err("Should fail because of mismatched representations"),
459					CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
460			);
461        }
462
463        let ctx = Arc::new(Context::new(MODULI, 16)?);
464        let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
465        let proto = Rq::from(&p);
466        assert_eq!(Poly::try_convert_from(&proto, &ctx, false, None)?, p);
467        assert_eq!(
468            Poly::try_convert_from(&proto, &ctx, false, Representation::PowerBasis)?,
469            p
470        );
471        assert_eq!(
472			Poly::try_convert_from(&proto, &ctx, false, Representation::Ntt)
473				.expect_err("Should fail because of mismatched representations"),
474				CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
475		);
476        assert_eq!(
477			Poly::try_convert_from(&proto, &ctx, false, Representation::NttShoup)
478				.expect_err("Should fail because of mismatched representations"),
479				CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
480		);
481
482        let ctx = Arc::new(Context::new(&MODULI[0..1], 16)?);
483        assert_eq!(
484            Poly::try_convert_from(&proto, &ctx, false, None)
485                .expect_err("Should fail because of incorrect context"),
486            CrateError::Default("Invalid coefficients".to_string())
487        );
488
489        Ok(())
490    }
491
492    #[test]
493    fn try_convert_from_slice_zero() -> Result<(), Box<dyn Error>> {
494        for modulus in MODULI {
495            let ctx = Arc::new(Context::new(&[*modulus], 16)?);
496
497            // Power Basis
498            assert_eq!(
499                Poly::try_convert_from(&[0u64], &ctx, false, Representation::PowerBasis)?,
500                Poly::zero(&ctx, Representation::PowerBasis)
501            );
502            assert_eq!(
503                Poly::try_convert_from(&[0i64], &ctx, false, Representation::PowerBasis)?,
504                Poly::zero(&ctx, Representation::PowerBasis)
505            );
506            assert_eq!(
507                Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
508                Poly::zero(&ctx, Representation::PowerBasis)
509            );
510            assert_eq!(
511                Poly::try_convert_from(&[0i64; 16], &ctx, false, Representation::PowerBasis)?,
512                Poly::zero(&ctx, Representation::PowerBasis)
513            );
514            assert!(Poly::try_convert_from(
515                &[0u64; 17], // One too many
516                &ctx,
517                false,
518                Representation::PowerBasis,
519            )
520            .is_err());
521
522            // Ntt
523            assert!(Poly::try_convert_from(&[0u64], &ctx, false, Representation::Ntt).is_err());
524            assert!(Poly::try_convert_from(&[0i64], &ctx, false, Representation::Ntt).is_err());
525            assert_eq!(
526                Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::Ntt)?,
527                Poly::zero(&ctx, Representation::Ntt)
528            );
529            assert!(Poly::try_convert_from(&[0i64; 16], &ctx, false, Representation::Ntt).is_err());
530            assert!(Poly::try_convert_from(
531                &[0u64; 17], // One too many
532                &ctx,
533                false,
534                Representation::Ntt,
535            )
536            .is_err());
537        }
538
539        let ctx = Arc::new(Context::new(MODULI, 16)?);
540        assert_eq!(
541            Poly::try_convert_from(
542                Vec::<u64>::default(),
543                &ctx,
544                false,
545                Representation::PowerBasis,
546            )?,
547            Poly::zero(&ctx, Representation::PowerBasis)
548        );
549        assert!(
550            Poly::try_convert_from(Vec::<u64>::default(), &ctx, false, Representation::Ntt)
551                .is_err()
552        );
553
554        assert_eq!(
555            Poly::try_convert_from(&[0u64], &ctx, false, Representation::PowerBasis)?,
556            Poly::zero(&ctx, Representation::PowerBasis)
557        );
558        assert!(Poly::try_convert_from(&[0u64], &ctx, false, Representation::Ntt).is_err());
559
560        assert_eq!(
561            Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
562            Poly::zero(&ctx, Representation::PowerBasis)
563        );
564        assert!(Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::Ntt).is_err());
565
566        assert!(
567            Poly::try_convert_from(&[0u64; 17], &ctx, false, Representation::PowerBasis).is_err()
568        );
569        assert!(Poly::try_convert_from(&[0u64; 17], &ctx, false, Representation::Ntt).is_err());
570
571        assert_eq!(
572            Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
573            Poly::zero(&ctx, Representation::PowerBasis)
574        );
575        assert_eq!(
576            Poly::try_convert_from(&[0u64; 48], &ctx, false, Representation::Ntt)?,
577            Poly::zero(&ctx, Representation::Ntt)
578        );
579
580        Ok(())
581    }
582
583    #[test]
584    fn try_convert_from_vec_zero() -> Result<(), Box<dyn Error>> {
585        for modulus in MODULI {
586            let ctx = Arc::new(Context::new(&[*modulus], 16)?);
587            assert_eq!(
588                Poly::try_convert_from(vec![], &ctx, false, Representation::PowerBasis)?,
589                Poly::zero(&ctx, Representation::PowerBasis)
590            );
591            assert!(Poly::try_convert_from(vec![], &ctx, false, Representation::Ntt).is_err());
592
593            assert_eq!(
594                Poly::try_convert_from(vec![0], &ctx, false, Representation::PowerBasis)?,
595                Poly::zero(&ctx, Representation::PowerBasis)
596            );
597            assert!(Poly::try_convert_from(vec![0], &ctx, false, Representation::Ntt).is_err());
598
599            assert_eq!(
600                Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::PowerBasis)?,
601                Poly::zero(&ctx, Representation::PowerBasis)
602            );
603            assert_eq!(
604                Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::Ntt)?,
605                Poly::zero(&ctx, Representation::Ntt)
606            );
607
608            assert!(
609                Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::PowerBasis)
610                    .is_err()
611            );
612            assert!(Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::Ntt).is_err());
613        }
614
615        let ctx = Arc::new(Context::new(MODULI, 16)?);
616        assert_eq!(
617            Poly::try_convert_from(vec![], &ctx, false, Representation::PowerBasis)?,
618            Poly::zero(&ctx, Representation::PowerBasis)
619        );
620        assert!(Poly::try_convert_from(vec![], &ctx, false, Representation::Ntt).is_err());
621
622        assert_eq!(
623            Poly::try_convert_from(vec![0], &ctx, false, Representation::PowerBasis)?,
624            Poly::zero(&ctx, Representation::PowerBasis)
625        );
626        assert!(Poly::try_convert_from(vec![0], &ctx, false, Representation::Ntt).is_err());
627
628        assert_eq!(
629            Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::PowerBasis)?,
630            Poly::zero(&ctx, Representation::PowerBasis)
631        );
632        assert!(Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::Ntt).is_err());
633
634        assert!(
635            Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::PowerBasis).is_err()
636        );
637        assert!(Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::Ntt).is_err());
638
639        assert_eq!(
640            Poly::try_convert_from(vec![0; 48], &ctx, false, Representation::PowerBasis)?,
641            Poly::zero(&ctx, Representation::PowerBasis)
642        );
643        assert_eq!(
644            Poly::try_convert_from(vec![0; 48], &ctx, false, Representation::Ntt)?,
645            Poly::zero(&ctx, Representation::Ntt)
646        );
647
648        Ok(())
649    }
650
651    #[test]
652    fn biguint() -> Result<(), Box<dyn Error>> {
653        let mut rng = rng();
654        for _ in 0..100 {
655            for modulus in MODULI {
656                let ctx = Arc::new(Context::new(&[*modulus], 16)?);
657                let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
658                let p_coeffs = Vec::<BigUint>::from(&p);
659                let q = Poly::try_convert_from(
660                    p_coeffs.as_slice(),
661                    &ctx,
662                    false,
663                    Representation::PowerBasis,
664                )?;
665                assert_eq!(p, q);
666            }
667
668            let ctx = Arc::new(Context::new(MODULI, 16)?);
669            let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
670            let p_coeffs = Vec::<BigUint>::from(&p);
671            assert_eq!(p_coeffs.len(), ctx.degree);
672            let q = Poly::try_convert_from(
673                p_coeffs.as_slice(),
674                &ctx,
675                false,
676                Representation::PowerBasis,
677            )?;
678            assert_eq!(p, q);
679        }
680        Ok(())
681    }
682}