fhe_util/
lib.rs

1#![crate_name = "fhe_util"]
2#![crate_type = "lib"]
3#![warn(missing_docs, unused_imports)]
4
5//! Utilities for the fhe.rs library.
6
7#[cfg(test)]
8extern crate proptest;
9
10use rand::{CryptoRng, RngCore};
11
12use num_bigint_dig::{prime::probably_prime, BigUint, ModInverse};
13use num_traits::{cast::ToPrimitive, PrimInt};
14
15/// Returns whether the modulus p is prime; this function is 100% accurate.
16pub fn is_prime(p: u64) -> bool {
17    probably_prime(&BigUint::from(p), 0)
18}
19
20/// Sample a vector of independent centered binomial distributions of a given
21/// variance. Returns an error if the variance is strictly larger than 16.
22pub fn sample_vec_cbd<R: RngCore + CryptoRng>(
23    vector_size: usize,
24    variance: usize,
25    rng: &mut R,
26) -> Result<Vec<i64>, &'static str> {
27    if !(1..=16).contains(&variance) {
28        return Err("The variance should be between 1 and 16");
29    }
30
31    let mut out = Vec::with_capacity(vector_size);
32
33    let number_bits = 4 * variance;
34    let mask_add = ((u64::MAX >> (64 - number_bits)) >> (2 * variance)) as u128;
35    let mask_sub = mask_add << (2 * variance);
36
37    let mut current_pool = 0u128;
38    let mut current_pool_nbits = 0;
39
40    for _ in 0..vector_size {
41        if current_pool_nbits < number_bits {
42            current_pool |= (rng.next_u64() as u128) << current_pool_nbits;
43            current_pool_nbits += 64;
44        }
45        debug_assert!(current_pool_nbits >= number_bits);
46        out.push(
47            ((current_pool & mask_add).count_ones() as i64)
48                - ((current_pool & mask_sub).count_ones() as i64),
49        );
50        current_pool >>= number_bits;
51        current_pool_nbits -= number_bits;
52    }
53
54    Ok(out)
55}
56
57/// Transcodes a vector of u64 of `nbits`-bit numbers into a vector of bytes.
58pub fn transcode_to_bytes(a: &[u64], nbits: usize) -> Vec<u8> {
59    assert!(0 < nbits && nbits <= 64);
60
61    let mask = (u64::MAX >> (64 - nbits)) as u128;
62    let nbytes = (a.len() * nbits).div_ceil(8);
63    let mut out = Vec::with_capacity(nbytes);
64
65    let mut current_index = 0;
66    let mut current_value = 0u128;
67    let mut current_value_nbits = 0;
68    while current_index < a.len() {
69        if current_value_nbits < 8 {
70            debug_assert!(64 - a[current_index].leading_zeros() <= nbits as u32);
71            current_value |= ((a[current_index] as u128) & mask) << current_value_nbits;
72            current_value_nbits += nbits;
73            current_index += 1;
74        }
75        while current_value_nbits >= 8 {
76            out.push(current_value as u8);
77            current_value >>= 8;
78            current_value_nbits -= 8;
79        }
80    }
81    if current_value_nbits > 0 {
82        assert!(current_value_nbits < 8);
83        assert_eq!(out.len(), nbytes - 1);
84        out.push(current_value as u8)
85    } else {
86        assert_eq!(out.len(), nbytes);
87        assert_eq!(current_value, 0);
88    }
89    out
90}
91
92/// Transcodes a vector of u8 into a vector of u64 of `nbits`-bit numbers.
93pub fn transcode_from_bytes(b: &[u8], nbits: usize) -> Vec<u64> {
94    assert!(0 < nbits && nbits <= 64);
95    let mask = (u64::MAX >> (64 - nbits)) as u128;
96
97    let nelements = (b.len() * 8).div_ceil(nbits);
98    let mut out = Vec::with_capacity(nelements);
99
100    let mut current_value = 0u128;
101    let mut current_value_nbits = 0;
102    let mut current_index = 0;
103    while current_index < b.len() {
104        if current_value_nbits < nbits {
105            current_value |= (b[current_index] as u128) << current_value_nbits;
106            current_value_nbits += 8;
107            current_index += 1;
108        }
109        while current_value_nbits >= nbits {
110            out.push((current_value & mask) as u64);
111            current_value >>= nbits;
112            current_value_nbits -= nbits;
113        }
114    }
115    if current_value_nbits > 0 {
116        assert_eq!(out.len(), nelements - 1);
117        out.push(current_value as u64);
118    } else {
119        assert_eq!(out.len(), nelements);
120        assert_eq!(current_value, 0);
121    }
122    out
123}
124
125/// Transcodes a vector of u64 of `input_nbits`-bit numbers into a vector of u64
126/// of `output_nbits`-bit numbers.
127pub fn transcode_bidirectional(a: &[u64], input_nbits: usize, output_nbits: usize) -> Vec<u64> {
128    assert!(0 < input_nbits && input_nbits <= 64);
129    assert!(0 < output_nbits && output_nbits <= 64);
130
131    let input_mask = (u64::MAX >> (64 - input_nbits)) as u128;
132    let output_mask = (u64::MAX >> (64 - output_nbits)) as u128;
133    let output_size = (a.len() * input_nbits).div_ceil(output_nbits);
134    let mut out = Vec::with_capacity(output_size);
135
136    let mut current_index = 0;
137    let mut current_value = 0u128;
138    let mut current_value_nbits = 0;
139    while current_index < a.len() {
140        if current_value_nbits < output_nbits {
141            debug_assert!(64 - a[current_index].leading_zeros() <= input_nbits as u32);
142            current_value |= ((a[current_index] as u128) & input_mask) << current_value_nbits;
143            current_value_nbits += input_nbits;
144            current_index += 1;
145        }
146        while current_value_nbits >= output_nbits {
147            out.push((current_value & output_mask) as u64);
148            current_value >>= output_nbits;
149            current_value_nbits -= output_nbits;
150        }
151    }
152    if current_value_nbits > 0 {
153        assert!(current_value_nbits < output_nbits);
154        assert_eq!(out.len(), output_size - 1);
155        out.push(current_value as u64)
156    } else {
157        assert_eq!(out.len(), output_size);
158        assert_eq!(current_value, 0);
159    }
160    out
161}
162
163/// Computes the modular multiplicative inverse of `a` modulo `p`. Returns
164/// `None` if `a` is not invertible modulo `p`.
165pub fn inverse(a: u64, p: u64) -> Option<u64> {
166    let p = BigUint::from(p);
167    let a = BigUint::from(a);
168    a.mod_inverse(p)?.to_u64()
169}
170
171/// Compute the sample variance of a list of values.
172/// Panics if the length of value is < 2.
173pub fn variance<T: PrimInt>(values: &[T]) -> f64 {
174    assert!(values.len() > 1);
175    let mean = values.iter().fold(0f64, |acc, i| acc + i.to_f64().unwrap()) / (values.len() as f64);
176    values.iter().fold(0f64, |acc, i| {
177        acc + (i.to_f64().unwrap() - mean) * (i.to_f64().unwrap() - mean)
178    }) / ((values.len() as f64) - 1.0)
179}
180
181#[cfg(test)]
182mod tests {
183    use itertools::Itertools;
184    use rand::RngCore;
185
186    use crate::variance;
187
188    use super::{
189        inverse, is_prime, sample_vec_cbd, transcode_bidirectional, transcode_from_bytes,
190        transcode_to_bytes,
191    };
192
193    #[test]
194    fn prime() {
195        assert!(is_prime(2));
196        assert!(is_prime(3));
197        assert!(is_prime(5));
198        assert!(is_prime(7));
199        assert!(is_prime(4611686018326724609));
200
201        assert!(!is_prime(0));
202        assert!(!is_prime(1));
203        assert!(!is_prime(4));
204        assert!(!is_prime(6));
205        assert!(!is_prime(8));
206        assert!(!is_prime(9));
207        assert!(!is_prime(4611686018326724607));
208    }
209
210    #[test]
211    fn sample_cbd() {
212        let mut rng = rand::rng();
213        assert!(sample_vec_cbd(10, 0, &mut rng).is_err());
214        assert!(sample_vec_cbd(10, 17, &mut rng).is_err());
215
216        for var in 1..=16 {
217            for size in 0..=100 {
218                let v = sample_vec_cbd(size, var, &mut rng).unwrap();
219                assert_eq!(v.len(), size);
220            }
221
222            // Verifies that the min, max are in absolute value smaller than 2 * var
223            let v = sample_vec_cbd(100000, var, &mut rng).unwrap();
224            assert!(v.iter().map(|vi| vi.abs()).max().unwrap() <= 2 * var as i64);
225
226            // Verifies that the variance is correct. We could probably refine the bound
227            // but for now, we will just check that the rounded value is equal to the
228            // variance.
229            assert!(variance(&v).round() == (var as f64));
230        }
231    }
232
233    #[test]
234    fn transcode_self_consistency() {
235        let mut rng = rand::rng();
236
237        for size in 1..=100 {
238            let input = (0..size).map(|_| rng.next_u64()).collect_vec();
239            for input_nbits in 1usize..63 {
240                let masked_input = input
241                    .iter()
242                    .map(|i| (*i) & (u64::MAX >> (64 - input_nbits)))
243                    .collect_vec();
244                let bytes = transcode_to_bytes(&masked_input, input_nbits);
245                let bytes_as_u64 = transcode_bidirectional(&masked_input, input_nbits, 8);
246                assert_eq!(bytes, bytes_as_u64.iter().map(|e| *e as u8).collect_vec());
247
248                let input_from_bytes = transcode_from_bytes(&bytes, input_nbits);
249                assert!(input_from_bytes.len() >= masked_input.len());
250                assert_eq!(input_from_bytes[..masked_input.len()], masked_input);
251
252                let input_from_u64 = transcode_bidirectional(&bytes_as_u64, 8, input_nbits);
253                assert!(input_from_u64.len() >= masked_input.len());
254                assert_eq!(input_from_u64[..masked_input.len()], masked_input);
255
256                for output_nbits in 1..63 {
257                    let output = transcode_bidirectional(&masked_input, input_nbits, output_nbits);
258                    let input_from_output =
259                        transcode_bidirectional(&output, output_nbits, input_nbits);
260                    assert!(input_from_output.len() >= masked_input.len());
261                    assert_eq!(input_from_output[..masked_input.len()], masked_input);
262                }
263            }
264        }
265    }
266
267    #[test]
268    fn inv_kats() {
269        // KATs for inversion generated in Sage using the following code.
270        /*
271        sage: for p in range(2, 1000, 7):
272        ....:     for a in range(1, 30, 3):
273        ....:         if gcd(a, p) == 1:
274        ....:             i = ZZ(a)^(-1) % p
275        ....:             print("assert_eq!(inverse({}, {}), Some({}));".format(a, p, i))
276        ....:         else:
277        ....:             print("assert!(inverse({}, {}).is_none());".format(a, p))
278         */
279        assert_eq!(inverse(1, 2), Some(1));
280        assert!(inverse(4, 2).is_none());
281        assert_eq!(inverse(7, 2), Some(1));
282        assert!(inverse(10, 2).is_none());
283        assert_eq!(inverse(13, 2), Some(1));
284        assert!(inverse(16, 2).is_none());
285        assert_eq!(inverse(19, 2), Some(1));
286        assert!(inverse(22, 2).is_none());
287        assert_eq!(inverse(25, 2), Some(1));
288        assert!(inverse(28, 2).is_none());
289        assert_eq!(inverse(1, 9), Some(1));
290        assert_eq!(inverse(4, 9), Some(7));
291        assert_eq!(inverse(7, 9), Some(4));
292        assert_eq!(inverse(10, 9), Some(1));
293        assert_eq!(inverse(13, 9), Some(7));
294        assert_eq!(inverse(16, 9), Some(4));
295        assert_eq!(inverse(19, 9), Some(1));
296        assert_eq!(inverse(22, 9), Some(7));
297        assert_eq!(inverse(25, 9), Some(4));
298        assert_eq!(inverse(28, 9), Some(1));
299        assert_eq!(inverse(1, 16), Some(1));
300        assert!(inverse(4, 16).is_none());
301        assert_eq!(inverse(7, 16), Some(7));
302        assert!(inverse(10, 16).is_none());
303        assert_eq!(inverse(13, 16), Some(5));
304        assert!(inverse(16, 16).is_none());
305        assert_eq!(inverse(19, 16), Some(11));
306        assert!(inverse(22, 16).is_none());
307        assert_eq!(inverse(25, 16), Some(9));
308        assert!(inverse(28, 16).is_none());
309        assert_eq!(inverse(1, 23), Some(1));
310        assert_eq!(inverse(4, 23), Some(6));
311        assert_eq!(inverse(7, 23), Some(10));
312        assert_eq!(inverse(10, 23), Some(7));
313        assert_eq!(inverse(13, 23), Some(16));
314        assert_eq!(inverse(16, 23), Some(13));
315        assert_eq!(inverse(19, 23), Some(17));
316        assert_eq!(inverse(22, 23), Some(22));
317        assert_eq!(inverse(25, 23), Some(12));
318        assert_eq!(inverse(28, 23), Some(14));
319        assert_eq!(inverse(1, 30), Some(1));
320        assert!(inverse(4, 30).is_none());
321        assert_eq!(inverse(7, 30), Some(13));
322        assert!(inverse(10, 30).is_none());
323        assert_eq!(inverse(13, 30), Some(7));
324        assert!(inverse(16, 30).is_none());
325        assert_eq!(inverse(19, 30), Some(19));
326        assert!(inverse(22, 30).is_none());
327        assert!(inverse(25, 30).is_none());
328        assert!(inverse(28, 30).is_none());
329        assert_eq!(inverse(1, 37), Some(1));
330        assert_eq!(inverse(4, 37), Some(28));
331        assert_eq!(inverse(7, 37), Some(16));
332        assert_eq!(inverse(10, 37), Some(26));
333        assert_eq!(inverse(13, 37), Some(20));
334        assert_eq!(inverse(16, 37), Some(7));
335        assert_eq!(inverse(19, 37), Some(2));
336        assert_eq!(inverse(22, 37), Some(32));
337        assert_eq!(inverse(25, 37), Some(3));
338        assert_eq!(inverse(28, 37), Some(4));
339        assert_eq!(inverse(1, 44), Some(1));
340        assert!(inverse(4, 44).is_none());
341        assert_eq!(inverse(7, 44), Some(19));
342        assert!(inverse(10, 44).is_none());
343        assert_eq!(inverse(13, 44), Some(17));
344        assert!(inverse(16, 44).is_none());
345        assert_eq!(inverse(19, 44), Some(7));
346        assert!(inverse(22, 44).is_none());
347        assert_eq!(inverse(25, 44), Some(37));
348        assert!(inverse(28, 44).is_none());
349        assert_eq!(inverse(1, 51), Some(1));
350        assert_eq!(inverse(4, 51), Some(13));
351        assert_eq!(inverse(7, 51), Some(22));
352        assert_eq!(inverse(10, 51), Some(46));
353        assert_eq!(inverse(13, 51), Some(4));
354        assert_eq!(inverse(16, 51), Some(16));
355        assert_eq!(inverse(19, 51), Some(43));
356        assert_eq!(inverse(22, 51), Some(7));
357        assert_eq!(inverse(25, 51), Some(49));
358        assert_eq!(inverse(28, 51), Some(31));
359        assert_eq!(inverse(1, 58), Some(1));
360        assert!(inverse(4, 58).is_none());
361        assert_eq!(inverse(7, 58), Some(25));
362        assert!(inverse(10, 58).is_none());
363        assert_eq!(inverse(13, 58), Some(9));
364        assert!(inverse(16, 58).is_none());
365        assert_eq!(inverse(19, 58), Some(55));
366        assert!(inverse(22, 58).is_none());
367        assert_eq!(inverse(25, 58), Some(7));
368        assert!(inverse(28, 58).is_none());
369        assert_eq!(inverse(1, 65), Some(1));
370        assert_eq!(inverse(4, 65), Some(49));
371        assert_eq!(inverse(7, 65), Some(28));
372        assert!(inverse(10, 65).is_none());
373        assert!(inverse(13, 65).is_none());
374        assert_eq!(inverse(16, 65), Some(61));
375        assert_eq!(inverse(19, 65), Some(24));
376        assert_eq!(inverse(22, 65), Some(3));
377        assert!(inverse(25, 65).is_none());
378        assert_eq!(inverse(28, 65), Some(7));
379        assert_eq!(inverse(1, 72), Some(1));
380        assert!(inverse(4, 72).is_none());
381        assert_eq!(inverse(7, 72), Some(31));
382        assert!(inverse(10, 72).is_none());
383        assert_eq!(inverse(13, 72), Some(61));
384        assert!(inverse(16, 72).is_none());
385        assert_eq!(inverse(19, 72), Some(19));
386        assert!(inverse(22, 72).is_none());
387        assert_eq!(inverse(25, 72), Some(49));
388        assert!(inverse(28, 72).is_none());
389        assert_eq!(inverse(1, 79), Some(1));
390        assert_eq!(inverse(4, 79), Some(20));
391        assert_eq!(inverse(7, 79), Some(34));
392        assert_eq!(inverse(10, 79), Some(8));
393        assert_eq!(inverse(13, 79), Some(73));
394        assert_eq!(inverse(16, 79), Some(5));
395        assert_eq!(inverse(19, 79), Some(25));
396        assert_eq!(inverse(22, 79), Some(18));
397        assert_eq!(inverse(25, 79), Some(19));
398        assert_eq!(inverse(28, 79), Some(48));
399        assert_eq!(inverse(1, 86), Some(1));
400        assert!(inverse(4, 86).is_none());
401        assert_eq!(inverse(7, 86), Some(37));
402        assert!(inverse(10, 86).is_none());
403        assert_eq!(inverse(13, 86), Some(53));
404        assert!(inverse(16, 86).is_none());
405        assert_eq!(inverse(19, 86), Some(77));
406        assert!(inverse(22, 86).is_none());
407        assert_eq!(inverse(25, 86), Some(31));
408        assert!(inverse(28, 86).is_none());
409        assert_eq!(inverse(1, 93), Some(1));
410        assert_eq!(inverse(4, 93), Some(70));
411        assert_eq!(inverse(7, 93), Some(40));
412        assert_eq!(inverse(10, 93), Some(28));
413        assert_eq!(inverse(13, 93), Some(43));
414        assert_eq!(inverse(16, 93), Some(64));
415        assert_eq!(inverse(19, 93), Some(49));
416        assert_eq!(inverse(22, 93), Some(55));
417        assert_eq!(inverse(25, 93), Some(67));
418        assert_eq!(inverse(28, 93), Some(10));
419        assert_eq!(inverse(1, 100), Some(1));
420        assert!(inverse(4, 100).is_none());
421        assert_eq!(inverse(7, 100), Some(43));
422        assert!(inverse(10, 100).is_none());
423        assert_eq!(inverse(13, 100), Some(77));
424        assert!(inverse(16, 100).is_none());
425        assert_eq!(inverse(19, 100), Some(79));
426        assert!(inverse(22, 100).is_none());
427        assert!(inverse(25, 100).is_none());
428        assert!(inverse(28, 100).is_none());
429        assert_eq!(inverse(1, 107), Some(1));
430        assert_eq!(inverse(4, 107), Some(27));
431        assert_eq!(inverse(7, 107), Some(46));
432        assert_eq!(inverse(10, 107), Some(75));
433        assert_eq!(inverse(13, 107), Some(33));
434        assert_eq!(inverse(16, 107), Some(87));
435        assert_eq!(inverse(19, 107), Some(62));
436        assert_eq!(inverse(22, 107), Some(73));
437        assert_eq!(inverse(25, 107), Some(30));
438        assert_eq!(inverse(28, 107), Some(65));
439        assert_eq!(inverse(1, 114), Some(1));
440        assert!(inverse(4, 114).is_none());
441        assert_eq!(inverse(7, 114), Some(49));
442        assert!(inverse(10, 114).is_none());
443        assert_eq!(inverse(13, 114), Some(79));
444        assert!(inverse(16, 114).is_none());
445        assert!(inverse(19, 114).is_none());
446        assert!(inverse(22, 114).is_none());
447        assert_eq!(inverse(25, 114), Some(73));
448        assert!(inverse(28, 114).is_none());
449        assert_eq!(inverse(1, 121), Some(1));
450        assert_eq!(inverse(4, 121), Some(91));
451        assert_eq!(inverse(7, 121), Some(52));
452        assert_eq!(inverse(10, 121), Some(109));
453        assert_eq!(inverse(13, 121), Some(28));
454        assert_eq!(inverse(16, 121), Some(53));
455        assert_eq!(inverse(19, 121), Some(51));
456        assert!(inverse(22, 121).is_none());
457        assert_eq!(inverse(25, 121), Some(92));
458        assert_eq!(inverse(28, 121), Some(13));
459        assert_eq!(inverse(1, 128), Some(1));
460        assert!(inverse(4, 128).is_none());
461        assert_eq!(inverse(7, 128), Some(55));
462        assert!(inverse(10, 128).is_none());
463        assert_eq!(inverse(13, 128), Some(69));
464        assert!(inverse(16, 128).is_none());
465        assert_eq!(inverse(19, 128), Some(27));
466        assert!(inverse(22, 128).is_none());
467        assert_eq!(inverse(25, 128), Some(41));
468        assert!(inverse(28, 128).is_none());
469        assert_eq!(inverse(1, 135), Some(1));
470        assert_eq!(inverse(4, 135), Some(34));
471        assert_eq!(inverse(7, 135), Some(58));
472        assert!(inverse(10, 135).is_none());
473        assert_eq!(inverse(13, 135), Some(52));
474        assert_eq!(inverse(16, 135), Some(76));
475        assert_eq!(inverse(19, 135), Some(64));
476        assert_eq!(inverse(22, 135), Some(43));
477        assert!(inverse(25, 135).is_none());
478        assert_eq!(inverse(28, 135), Some(82));
479        assert_eq!(inverse(1, 142), Some(1));
480        assert!(inverse(4, 142).is_none());
481        assert_eq!(inverse(7, 142), Some(61));
482        assert!(inverse(10, 142).is_none());
483        assert_eq!(inverse(13, 142), Some(11));
484        assert!(inverse(16, 142).is_none());
485        assert_eq!(inverse(19, 142), Some(15));
486        assert!(inverse(22, 142).is_none());
487        assert_eq!(inverse(25, 142), Some(125));
488        assert!(inverse(28, 142).is_none());
489        assert_eq!(inverse(1, 149), Some(1));
490        assert_eq!(inverse(4, 149), Some(112));
491        assert_eq!(inverse(7, 149), Some(64));
492        assert_eq!(inverse(10, 149), Some(15));
493        assert_eq!(inverse(13, 149), Some(23));
494        assert_eq!(inverse(16, 149), Some(28));
495        assert_eq!(inverse(19, 149), Some(102));
496        assert_eq!(inverse(22, 149), Some(61));
497        assert_eq!(inverse(25, 149), Some(6));
498        assert_eq!(inverse(28, 149), Some(16));
499        assert_eq!(inverse(1, 156), Some(1));
500        assert!(inverse(4, 156).is_none());
501        assert_eq!(inverse(7, 156), Some(67));
502        assert!(inverse(10, 156).is_none());
503        assert!(inverse(13, 156).is_none());
504        assert!(inverse(16, 156).is_none());
505        assert_eq!(inverse(19, 156), Some(115));
506        assert!(inverse(22, 156).is_none());
507        assert_eq!(inverse(25, 156), Some(25));
508        assert!(inverse(28, 156).is_none());
509        assert_eq!(inverse(1, 163), Some(1));
510        assert_eq!(inverse(4, 163), Some(41));
511        assert_eq!(inverse(7, 163), Some(70));
512        assert_eq!(inverse(10, 163), Some(49));
513        assert_eq!(inverse(13, 163), Some(138));
514        assert_eq!(inverse(16, 163), Some(51));
515        assert_eq!(inverse(19, 163), Some(103));
516        assert_eq!(inverse(22, 163), Some(126));
517        assert_eq!(inverse(25, 163), Some(150));
518        assert_eq!(inverse(28, 163), Some(99));
519        assert_eq!(inverse(1, 170), Some(1));
520        assert!(inverse(4, 170).is_none());
521        assert_eq!(inverse(7, 170), Some(73));
522        assert!(inverse(10, 170).is_none());
523        assert_eq!(inverse(13, 170), Some(157));
524        assert!(inverse(16, 170).is_none());
525        assert_eq!(inverse(19, 170), Some(9));
526        assert!(inverse(22, 170).is_none());
527        assert!(inverse(25, 170).is_none());
528        assert!(inverse(28, 170).is_none());
529        assert_eq!(inverse(1, 177), Some(1));
530        assert_eq!(inverse(4, 177), Some(133));
531        assert_eq!(inverse(7, 177), Some(76));
532        assert_eq!(inverse(10, 177), Some(124));
533        assert_eq!(inverse(13, 177), Some(109));
534        assert_eq!(inverse(16, 177), Some(166));
535        assert_eq!(inverse(19, 177), Some(28));
536        assert_eq!(inverse(22, 177), Some(169));
537        assert_eq!(inverse(25, 177), Some(85));
538        assert_eq!(inverse(28, 177), Some(19));
539        assert_eq!(inverse(1, 184), Some(1));
540        assert!(inverse(4, 184).is_none());
541        assert_eq!(inverse(7, 184), Some(79));
542        assert!(inverse(10, 184).is_none());
543        assert_eq!(inverse(13, 184), Some(85));
544        assert!(inverse(16, 184).is_none());
545        assert_eq!(inverse(19, 184), Some(155));
546        assert!(inverse(22, 184).is_none());
547        assert_eq!(inverse(25, 184), Some(81));
548        assert!(inverse(28, 184).is_none());
549        assert_eq!(inverse(1, 191), Some(1));
550        assert_eq!(inverse(4, 191), Some(48));
551        assert_eq!(inverse(7, 191), Some(82));
552        assert_eq!(inverse(10, 191), Some(172));
553        assert_eq!(inverse(13, 191), Some(147));
554        assert_eq!(inverse(16, 191), Some(12));
555        assert_eq!(inverse(19, 191), Some(181));
556        assert_eq!(inverse(22, 191), Some(165));
557        assert_eq!(inverse(25, 191), Some(107));
558        assert_eq!(inverse(28, 191), Some(116));
559        assert_eq!(inverse(1, 198), Some(1));
560        assert!(inverse(4, 198).is_none());
561        assert_eq!(inverse(7, 198), Some(85));
562        assert!(inverse(10, 198).is_none());
563        assert_eq!(inverse(13, 198), Some(61));
564        assert!(inverse(16, 198).is_none());
565        assert_eq!(inverse(19, 198), Some(73));
566        assert!(inverse(22, 198).is_none());
567        assert_eq!(inverse(25, 198), Some(103));
568        assert!(inverse(28, 198).is_none());
569        assert_eq!(inverse(1, 205), Some(1));
570        assert_eq!(inverse(4, 205), Some(154));
571        assert_eq!(inverse(7, 205), Some(88));
572        assert!(inverse(10, 205).is_none());
573        assert_eq!(inverse(13, 205), Some(142));
574        assert_eq!(inverse(16, 205), Some(141));
575        assert_eq!(inverse(19, 205), Some(54));
576        assert_eq!(inverse(22, 205), Some(28));
577        assert!(inverse(25, 205).is_none());
578        assert_eq!(inverse(28, 205), Some(22));
579        assert_eq!(inverse(1, 212), Some(1));
580        assert!(inverse(4, 212).is_none());
581        assert_eq!(inverse(7, 212), Some(91));
582        assert!(inverse(10, 212).is_none());
583        assert_eq!(inverse(13, 212), Some(49));
584        assert!(inverse(16, 212).is_none());
585        assert_eq!(inverse(19, 212), Some(67));
586        assert!(inverse(22, 212).is_none());
587        assert_eq!(inverse(25, 212), Some(17));
588        assert!(inverse(28, 212).is_none());
589        assert_eq!(inverse(1, 219), Some(1));
590        assert_eq!(inverse(4, 219), Some(55));
591        assert_eq!(inverse(7, 219), Some(94));
592        assert_eq!(inverse(10, 219), Some(22));
593        assert_eq!(inverse(13, 219), Some(118));
594        assert_eq!(inverse(16, 219), Some(178));
595        assert_eq!(inverse(19, 219), Some(196));
596        assert_eq!(inverse(22, 219), Some(10));
597        assert_eq!(inverse(25, 219), Some(184));
598        assert_eq!(inverse(28, 219), Some(133));
599        assert_eq!(inverse(1, 226), Some(1));
600        assert!(inverse(4, 226).is_none());
601        assert_eq!(inverse(7, 226), Some(97));
602        assert!(inverse(10, 226).is_none());
603        assert_eq!(inverse(13, 226), Some(87));
604        assert!(inverse(16, 226).is_none());
605        assert_eq!(inverse(19, 226), Some(119));
606        assert!(inverse(22, 226).is_none());
607        assert_eq!(inverse(25, 226), Some(217));
608        assert!(inverse(28, 226).is_none());
609        assert_eq!(inverse(1, 233), Some(1));
610        assert_eq!(inverse(4, 233), Some(175));
611        assert_eq!(inverse(7, 233), Some(100));
612        assert_eq!(inverse(10, 233), Some(70));
613        assert_eq!(inverse(13, 233), Some(18));
614        assert_eq!(inverse(16, 233), Some(102));
615        assert_eq!(inverse(19, 233), Some(184));
616        assert_eq!(inverse(22, 233), Some(53));
617        assert_eq!(inverse(25, 233), Some(28));
618        assert_eq!(inverse(28, 233), Some(25));
619        assert_eq!(inverse(1, 240), Some(1));
620        assert!(inverse(4, 240).is_none());
621        assert_eq!(inverse(7, 240), Some(103));
622        assert!(inverse(10, 240).is_none());
623        assert_eq!(inverse(13, 240), Some(37));
624        assert!(inverse(16, 240).is_none());
625        assert_eq!(inverse(19, 240), Some(139));
626        assert!(inverse(22, 240).is_none());
627        assert!(inverse(25, 240).is_none());
628        assert!(inverse(28, 240).is_none());
629        assert_eq!(inverse(1, 247), Some(1));
630        assert_eq!(inverse(4, 247), Some(62));
631        assert_eq!(inverse(7, 247), Some(106));
632        assert_eq!(inverse(10, 247), Some(173));
633        assert!(inverse(13, 247).is_none());
634        assert_eq!(inverse(16, 247), Some(139));
635        assert!(inverse(19, 247).is_none());
636        assert_eq!(inverse(22, 247), Some(146));
637        assert_eq!(inverse(25, 247), Some(168));
638        assert_eq!(inverse(28, 247), Some(150));
639        assert_eq!(inverse(1, 254), Some(1));
640        assert!(inverse(4, 254).is_none());
641        assert_eq!(inverse(7, 254), Some(109));
642        assert!(inverse(10, 254).is_none());
643        assert_eq!(inverse(13, 254), Some(215));
644        assert!(inverse(16, 254).is_none());
645        assert_eq!(inverse(19, 254), Some(107));
646        assert!(inverse(22, 254).is_none());
647        assert_eq!(inverse(25, 254), Some(61));
648        assert!(inverse(28, 254).is_none());
649        assert_eq!(inverse(1, 261), Some(1));
650        assert_eq!(inverse(4, 261), Some(196));
651        assert_eq!(inverse(7, 261), Some(112));
652        assert_eq!(inverse(10, 261), Some(235));
653        assert_eq!(inverse(13, 261), Some(241));
654        assert_eq!(inverse(16, 261), Some(49));
655        assert_eq!(inverse(19, 261), Some(55));
656        assert_eq!(inverse(22, 261), Some(178));
657        assert_eq!(inverse(25, 261), Some(94));
658        assert_eq!(inverse(28, 261), Some(28));
659        assert_eq!(inverse(1, 268), Some(1));
660        assert!(inverse(4, 268).is_none());
661        assert_eq!(inverse(7, 268), Some(115));
662        assert!(inverse(10, 268).is_none());
663        assert_eq!(inverse(13, 268), Some(165));
664        assert!(inverse(16, 268).is_none());
665        assert_eq!(inverse(19, 268), Some(127));
666        assert!(inverse(22, 268).is_none());
667        assert_eq!(inverse(25, 268), Some(193));
668        assert!(inverse(28, 268).is_none());
669        assert_eq!(inverse(1, 275), Some(1));
670        assert_eq!(inverse(4, 275), Some(69));
671        assert_eq!(inverse(7, 275), Some(118));
672        assert!(inverse(10, 275).is_none());
673        assert_eq!(inverse(13, 275), Some(127));
674        assert_eq!(inverse(16, 275), Some(86));
675        assert_eq!(inverse(19, 275), Some(29));
676        assert!(inverse(22, 275).is_none());
677        assert!(inverse(25, 275).is_none());
678        assert_eq!(inverse(28, 275), Some(167));
679        assert_eq!(inverse(1, 282), Some(1));
680        assert!(inverse(4, 282).is_none());
681        assert_eq!(inverse(7, 282), Some(121));
682        assert!(inverse(10, 282).is_none());
683        assert_eq!(inverse(13, 282), Some(217));
684        assert!(inverse(16, 282).is_none());
685        assert_eq!(inverse(19, 282), Some(193));
686        assert!(inverse(22, 282).is_none());
687        assert_eq!(inverse(25, 282), Some(79));
688        assert!(inverse(28, 282).is_none());
689        assert_eq!(inverse(1, 289), Some(1));
690        assert_eq!(inverse(4, 289), Some(217));
691        assert_eq!(inverse(7, 289), Some(124));
692        assert_eq!(inverse(10, 289), Some(29));
693        assert_eq!(inverse(13, 289), Some(89));
694        assert_eq!(inverse(16, 289), Some(271));
695        assert_eq!(inverse(19, 289), Some(213));
696        assert_eq!(inverse(22, 289), Some(92));
697        assert_eq!(inverse(25, 289), Some(185));
698        assert_eq!(inverse(28, 289), Some(31));
699        assert_eq!(inverse(1, 296), Some(1));
700        assert!(inverse(4, 296).is_none());
701        assert_eq!(inverse(7, 296), Some(127));
702        assert!(inverse(10, 296).is_none());
703        assert_eq!(inverse(13, 296), Some(205));
704        assert!(inverse(16, 296).is_none());
705        assert_eq!(inverse(19, 296), Some(187));
706        assert!(inverse(22, 296).is_none());
707        assert_eq!(inverse(25, 296), Some(225));
708        assert!(inverse(28, 296).is_none());
709        assert_eq!(inverse(1, 303), Some(1));
710        assert_eq!(inverse(4, 303), Some(76));
711        assert_eq!(inverse(7, 303), Some(130));
712        assert_eq!(inverse(10, 303), Some(91));
713        assert_eq!(inverse(13, 303), Some(70));
714        assert_eq!(inverse(16, 303), Some(19));
715        assert_eq!(inverse(19, 303), Some(16));
716        assert_eq!(inverse(22, 303), Some(124));
717        assert_eq!(inverse(25, 303), Some(97));
718        assert_eq!(inverse(28, 303), Some(184));
719        assert_eq!(inverse(1, 310), Some(1));
720        assert!(inverse(4, 310).is_none());
721        assert_eq!(inverse(7, 310), Some(133));
722        assert!(inverse(10, 310).is_none());
723        assert_eq!(inverse(13, 310), Some(167));
724        assert!(inverse(16, 310).is_none());
725        assert_eq!(inverse(19, 310), Some(49));
726        assert!(inverse(22, 310).is_none());
727        assert!(inverse(25, 310).is_none());
728        assert!(inverse(28, 310).is_none());
729        assert_eq!(inverse(1, 317), Some(1));
730        assert_eq!(inverse(4, 317), Some(238));
731        assert_eq!(inverse(7, 317), Some(136));
732        assert_eq!(inverse(10, 317), Some(222));
733        assert_eq!(inverse(13, 317), Some(122));
734        assert_eq!(inverse(16, 317), Some(218));
735        assert_eq!(inverse(19, 317), Some(267));
736        assert_eq!(inverse(22, 317), Some(245));
737        assert_eq!(inverse(25, 317), Some(279));
738        assert_eq!(inverse(28, 317), Some(34));
739        assert_eq!(inverse(1, 324), Some(1));
740        assert!(inverse(4, 324).is_none());
741        assert_eq!(inverse(7, 324), Some(139));
742        assert!(inverse(10, 324).is_none());
743        assert_eq!(inverse(13, 324), Some(25));
744        assert!(inverse(16, 324).is_none());
745        assert_eq!(inverse(19, 324), Some(307));
746        assert!(inverse(22, 324).is_none());
747        assert_eq!(inverse(25, 324), Some(13));
748        assert!(inverse(28, 324).is_none());
749        assert_eq!(inverse(1, 331), Some(1));
750        assert_eq!(inverse(4, 331), Some(83));
751        assert_eq!(inverse(7, 331), Some(142));
752        assert_eq!(inverse(10, 331), Some(298));
753        assert_eq!(inverse(13, 331), Some(51));
754        assert_eq!(inverse(16, 331), Some(269));
755        assert_eq!(inverse(19, 331), Some(122));
756        assert_eq!(inverse(22, 331), Some(316));
757        assert_eq!(inverse(25, 331), Some(53));
758        assert_eq!(inverse(28, 331), Some(201));
759        assert_eq!(inverse(1, 338), Some(1));
760        assert!(inverse(4, 338).is_none());
761        assert_eq!(inverse(7, 338), Some(145));
762        assert!(inverse(10, 338).is_none());
763        assert!(inverse(13, 338).is_none());
764        assert!(inverse(16, 338).is_none());
765        assert_eq!(inverse(19, 338), Some(89));
766        assert!(inverse(22, 338).is_none());
767        assert_eq!(inverse(25, 338), Some(311));
768        assert!(inverse(28, 338).is_none());
769        assert_eq!(inverse(1, 345), Some(1));
770        assert_eq!(inverse(4, 345), Some(259));
771        assert_eq!(inverse(7, 345), Some(148));
772        assert!(inverse(10, 345).is_none());
773        assert_eq!(inverse(13, 345), Some(292));
774        assert_eq!(inverse(16, 345), Some(151));
775        assert_eq!(inverse(19, 345), Some(109));
776        assert_eq!(inverse(22, 345), Some(298));
777        assert!(inverse(25, 345).is_none());
778        assert_eq!(inverse(28, 345), Some(37));
779        assert_eq!(inverse(1, 352), Some(1));
780        assert!(inverse(4, 352).is_none());
781        assert_eq!(inverse(7, 352), Some(151));
782        assert!(inverse(10, 352).is_none());
783        assert_eq!(inverse(13, 352), Some(325));
784        assert!(inverse(16, 352).is_none());
785        assert_eq!(inverse(19, 352), Some(315));
786        assert!(inverse(22, 352).is_none());
787        assert_eq!(inverse(25, 352), Some(169));
788        assert!(inverse(28, 352).is_none());
789        assert_eq!(inverse(1, 359), Some(1));
790        assert_eq!(inverse(4, 359), Some(90));
791        assert_eq!(inverse(7, 359), Some(154));
792        assert_eq!(inverse(10, 359), Some(36));
793        assert_eq!(inverse(13, 359), Some(221));
794        assert_eq!(inverse(16, 359), Some(202));
795        assert_eq!(inverse(19, 359), Some(189));
796        assert_eq!(inverse(22, 359), Some(49));
797        assert_eq!(inverse(25, 359), Some(158));
798        assert_eq!(inverse(28, 359), Some(218));
799        assert_eq!(inverse(1, 366), Some(1));
800        assert!(inverse(4, 366).is_none());
801        assert_eq!(inverse(7, 366), Some(157));
802        assert!(inverse(10, 366).is_none());
803        assert_eq!(inverse(13, 366), Some(169));
804        assert!(inverse(16, 366).is_none());
805        assert_eq!(inverse(19, 366), Some(289));
806        assert!(inverse(22, 366).is_none());
807        assert_eq!(inverse(25, 366), Some(205));
808        assert!(inverse(28, 366).is_none());
809        assert_eq!(inverse(1, 373), Some(1));
810        assert_eq!(inverse(4, 373), Some(280));
811        assert_eq!(inverse(7, 373), Some(160));
812        assert_eq!(inverse(10, 373), Some(112));
813        assert_eq!(inverse(13, 373), Some(287));
814        assert_eq!(inverse(16, 373), Some(70));
815        assert_eq!(inverse(19, 373), Some(216));
816        assert_eq!(inverse(22, 373), Some(17));
817        assert_eq!(inverse(25, 373), Some(194));
818        assert_eq!(inverse(28, 373), Some(40));
819        assert_eq!(inverse(1, 380), Some(1));
820        assert!(inverse(4, 380).is_none());
821        assert_eq!(inverse(7, 380), Some(163));
822        assert!(inverse(10, 380).is_none());
823        assert_eq!(inverse(13, 380), Some(117));
824        assert!(inverse(16, 380).is_none());
825        assert!(inverse(19, 380).is_none());
826        assert!(inverse(22, 380).is_none());
827        assert!(inverse(25, 380).is_none());
828        assert!(inverse(28, 380).is_none());
829        assert_eq!(inverse(1, 387), Some(1));
830        assert_eq!(inverse(4, 387), Some(97));
831        assert_eq!(inverse(7, 387), Some(166));
832        assert_eq!(inverse(10, 387), Some(271));
833        assert_eq!(inverse(13, 387), Some(268));
834        assert_eq!(inverse(16, 387), Some(121));
835        assert_eq!(inverse(19, 387), Some(163));
836        assert_eq!(inverse(22, 387), Some(88));
837        assert_eq!(inverse(25, 387), Some(31));
838        assert_eq!(inverse(28, 387), Some(235));
839        assert_eq!(inverse(1, 394), Some(1));
840        assert!(inverse(4, 394).is_none());
841        assert_eq!(inverse(7, 394), Some(169));
842        assert!(inverse(10, 394).is_none());
843        assert_eq!(inverse(13, 394), Some(91));
844        assert!(inverse(16, 394).is_none());
845        assert_eq!(inverse(19, 394), Some(83));
846        assert!(inverse(22, 394).is_none());
847        assert_eq!(inverse(25, 394), Some(331));
848        assert!(inverse(28, 394).is_none());
849        assert_eq!(inverse(1, 401), Some(1));
850        assert_eq!(inverse(4, 401), Some(301));
851        assert_eq!(inverse(7, 401), Some(172));
852        assert_eq!(inverse(10, 401), Some(361));
853        assert_eq!(inverse(13, 401), Some(216));
854        assert_eq!(inverse(16, 401), Some(376));
855        assert_eq!(inverse(19, 401), Some(190));
856        assert_eq!(inverse(22, 401), Some(237));
857        assert_eq!(inverse(25, 401), Some(385));
858        assert_eq!(inverse(28, 401), Some(43));
859        assert_eq!(inverse(1, 408), Some(1));
860        assert!(inverse(4, 408).is_none());
861        assert_eq!(inverse(7, 408), Some(175));
862        assert!(inverse(10, 408).is_none());
863        assert_eq!(inverse(13, 408), Some(157));
864        assert!(inverse(16, 408).is_none());
865        assert_eq!(inverse(19, 408), Some(43));
866        assert!(inverse(22, 408).is_none());
867        assert_eq!(inverse(25, 408), Some(49));
868        assert!(inverse(28, 408).is_none());
869        assert_eq!(inverse(1, 415), Some(1));
870        assert_eq!(inverse(4, 415), Some(104));
871        assert_eq!(inverse(7, 415), Some(178));
872        assert!(inverse(10, 415).is_none());
873        assert_eq!(inverse(13, 415), Some(32));
874        assert_eq!(inverse(16, 415), Some(26));
875        assert_eq!(inverse(19, 415), Some(284));
876        assert_eq!(inverse(22, 415), Some(283));
877        assert!(inverse(25, 415).is_none());
878        assert_eq!(inverse(28, 415), Some(252));
879        assert_eq!(inverse(1, 422), Some(1));
880        assert!(inverse(4, 422).is_none());
881        assert_eq!(inverse(7, 422), Some(181));
882        assert!(inverse(10, 422).is_none());
883        assert_eq!(inverse(13, 422), Some(65));
884        assert!(inverse(16, 422).is_none());
885        assert_eq!(inverse(19, 422), Some(311));
886        assert!(inverse(22, 422).is_none());
887        assert_eq!(inverse(25, 422), Some(287));
888        assert!(inverse(28, 422).is_none());
889        assert_eq!(inverse(1, 429), Some(1));
890        assert_eq!(inverse(4, 429), Some(322));
891        assert_eq!(inverse(7, 429), Some(184));
892        assert_eq!(inverse(10, 429), Some(43));
893        assert!(inverse(13, 429).is_none());
894        assert_eq!(inverse(16, 429), Some(295));
895        assert_eq!(inverse(19, 429), Some(271));
896        assert!(inverse(22, 429).is_none());
897        assert_eq!(inverse(25, 429), Some(103));
898        assert_eq!(inverse(28, 429), Some(46));
899        assert_eq!(inverse(1, 436), Some(1));
900        assert!(inverse(4, 436).is_none());
901        assert_eq!(inverse(7, 436), Some(187));
902        assert!(inverse(10, 436).is_none());
903        assert_eq!(inverse(13, 436), Some(369));
904        assert!(inverse(16, 436).is_none());
905        assert_eq!(inverse(19, 436), Some(23));
906        assert!(inverse(22, 436).is_none());
907        assert_eq!(inverse(25, 436), Some(157));
908        assert!(inverse(28, 436).is_none());
909        assert_eq!(inverse(1, 443), Some(1));
910        assert_eq!(inverse(4, 443), Some(111));
911        assert_eq!(inverse(7, 443), Some(190));
912        assert_eq!(inverse(10, 443), Some(133));
913        assert_eq!(inverse(13, 443), Some(409));
914        assert_eq!(inverse(16, 443), Some(360));
915        assert_eq!(inverse(19, 443), Some(70));
916        assert_eq!(inverse(22, 443), Some(141));
917        assert_eq!(inverse(25, 443), Some(319));
918        assert_eq!(inverse(28, 443), Some(269));
919        assert_eq!(inverse(1, 450), Some(1));
920        assert!(inverse(4, 450).is_none());
921        assert_eq!(inverse(7, 450), Some(193));
922        assert!(inverse(10, 450).is_none());
923        assert_eq!(inverse(13, 450), Some(277));
924        assert!(inverse(16, 450).is_none());
925        assert_eq!(inverse(19, 450), Some(379));
926        assert!(inverse(22, 450).is_none());
927        assert!(inverse(25, 450).is_none());
928        assert!(inverse(28, 450).is_none());
929        assert_eq!(inverse(1, 457), Some(1));
930        assert_eq!(inverse(4, 457), Some(343));
931        assert_eq!(inverse(7, 457), Some(196));
932        assert_eq!(inverse(10, 457), Some(320));
933        assert_eq!(inverse(13, 457), Some(211));
934        assert_eq!(inverse(16, 457), Some(200));
935        assert_eq!(inverse(19, 457), Some(433));
936        assert_eq!(inverse(22, 457), Some(187));
937        assert_eq!(inverse(25, 457), Some(128));
938        assert_eq!(inverse(28, 457), Some(49));
939        assert_eq!(inverse(1, 464), Some(1));
940        assert!(inverse(4, 464).is_none());
941        assert_eq!(inverse(7, 464), Some(199));
942        assert!(inverse(10, 464).is_none());
943        assert_eq!(inverse(13, 464), Some(357));
944        assert!(inverse(16, 464).is_none());
945        assert_eq!(inverse(19, 464), Some(171));
946        assert!(inverse(22, 464).is_none());
947        assert_eq!(inverse(25, 464), Some(297));
948        assert!(inverse(28, 464).is_none());
949        assert_eq!(inverse(1, 471), Some(1));
950        assert_eq!(inverse(4, 471), Some(118));
951        assert_eq!(inverse(7, 471), Some(202));
952        assert_eq!(inverse(10, 471), Some(424));
953        assert_eq!(inverse(13, 471), Some(145));
954        assert_eq!(inverse(16, 471), Some(265));
955        assert_eq!(inverse(19, 471), Some(124));
956        assert_eq!(inverse(22, 471), Some(364));
957        assert_eq!(inverse(25, 471), Some(358));
958        assert_eq!(inverse(28, 471), Some(286));
959        assert_eq!(inverse(1, 478), Some(1));
960        assert!(inverse(4, 478).is_none());
961        assert_eq!(inverse(7, 478), Some(205));
962        assert!(inverse(10, 478).is_none());
963        assert_eq!(inverse(13, 478), Some(331));
964        assert!(inverse(16, 478).is_none());
965        assert_eq!(inverse(19, 478), Some(151));
966        assert!(inverse(22, 478).is_none());
967        assert_eq!(inverse(25, 478), Some(153));
968        assert!(inverse(28, 478).is_none());
969        assert_eq!(inverse(1, 485), Some(1));
970        assert_eq!(inverse(4, 485), Some(364));
971        assert_eq!(inverse(7, 485), Some(208));
972        assert!(inverse(10, 485).is_none());
973        assert_eq!(inverse(13, 485), Some(112));
974        assert_eq!(inverse(16, 485), Some(91));
975        assert_eq!(inverse(19, 485), Some(434));
976        assert_eq!(inverse(22, 485), Some(463));
977        assert!(inverse(25, 485).is_none());
978        assert_eq!(inverse(28, 485), Some(52));
979        assert_eq!(inverse(1, 492), Some(1));
980        assert!(inverse(4, 492).is_none());
981        assert_eq!(inverse(7, 492), Some(211));
982        assert!(inverse(10, 492).is_none());
983        assert_eq!(inverse(13, 492), Some(265));
984        assert!(inverse(16, 492).is_none());
985        assert_eq!(inverse(19, 492), Some(259));
986        assert!(inverse(22, 492).is_none());
987        assert_eq!(inverse(25, 492), Some(433));
988        assert!(inverse(28, 492).is_none());
989        assert_eq!(inverse(1, 499), Some(1));
990        assert_eq!(inverse(4, 499), Some(125));
991        assert_eq!(inverse(7, 499), Some(214));
992        assert_eq!(inverse(10, 499), Some(50));
993        assert_eq!(inverse(13, 499), Some(192));
994        assert_eq!(inverse(16, 499), Some(156));
995        assert_eq!(inverse(19, 499), Some(394));
996        assert_eq!(inverse(22, 499), Some(431));
997        assert_eq!(inverse(25, 499), Some(20));
998        assert_eq!(inverse(28, 499), Some(303));
999        assert_eq!(inverse(1, 506), Some(1));
1000        assert!(inverse(4, 506).is_none());
1001        assert_eq!(inverse(7, 506), Some(217));
1002        assert!(inverse(10, 506).is_none());
1003        assert_eq!(inverse(13, 506), Some(39));
1004        assert!(inverse(16, 506).is_none());
1005        assert_eq!(inverse(19, 506), Some(293));
1006        assert!(inverse(22, 506).is_none());
1007        assert_eq!(inverse(25, 506), Some(81));
1008        assert!(inverse(28, 506).is_none());
1009        assert_eq!(inverse(1, 513), Some(1));
1010        assert_eq!(inverse(4, 513), Some(385));
1011        assert_eq!(inverse(7, 513), Some(220));
1012        assert_eq!(inverse(10, 513), Some(154));
1013        assert_eq!(inverse(13, 513), Some(79));
1014        assert_eq!(inverse(16, 513), Some(481));
1015        assert!(inverse(19, 513).is_none());
1016        assert_eq!(inverse(22, 513), Some(70));
1017        assert_eq!(inverse(25, 513), Some(472));
1018        assert_eq!(inverse(28, 513), Some(55));
1019        assert_eq!(inverse(1, 520), Some(1));
1020        assert!(inverse(4, 520).is_none());
1021        assert_eq!(inverse(7, 520), Some(223));
1022        assert!(inverse(10, 520).is_none());
1023        assert!(inverse(13, 520).is_none());
1024        assert!(inverse(16, 520).is_none());
1025        assert_eq!(inverse(19, 520), Some(219));
1026        assert!(inverse(22, 520).is_none());
1027        assert!(inverse(25, 520).is_none());
1028        assert!(inverse(28, 520).is_none());
1029        assert_eq!(inverse(1, 527), Some(1));
1030        assert_eq!(inverse(4, 527), Some(132));
1031        assert_eq!(inverse(7, 527), Some(226));
1032        assert_eq!(inverse(10, 527), Some(369));
1033        assert_eq!(inverse(13, 527), Some(446));
1034        assert_eq!(inverse(16, 527), Some(33));
1035        assert_eq!(inverse(19, 527), Some(111));
1036        assert_eq!(inverse(22, 527), Some(24));
1037        assert_eq!(inverse(25, 527), Some(253));
1038        assert_eq!(inverse(28, 527), Some(320));
1039        assert_eq!(inverse(1, 534), Some(1));
1040        assert!(inverse(4, 534).is_none());
1041        assert_eq!(inverse(7, 534), Some(229));
1042        assert!(inverse(10, 534).is_none());
1043        assert_eq!(inverse(13, 534), Some(493));
1044        assert!(inverse(16, 534).is_none());
1045        assert_eq!(inverse(19, 534), Some(253));
1046        assert!(inverse(22, 534).is_none());
1047        assert_eq!(inverse(25, 534), Some(235));
1048        assert!(inverse(28, 534).is_none());
1049        assert_eq!(inverse(1, 541), Some(1));
1050        assert_eq!(inverse(4, 541), Some(406));
1051        assert_eq!(inverse(7, 541), Some(232));
1052        assert_eq!(inverse(10, 541), Some(487));
1053        assert_eq!(inverse(13, 541), Some(333));
1054        assert_eq!(inverse(16, 541), Some(372));
1055        assert_eq!(inverse(19, 541), Some(57));
1056        assert_eq!(inverse(22, 541), Some(123));
1057        assert_eq!(inverse(25, 541), Some(303));
1058        assert_eq!(inverse(28, 541), Some(58));
1059        assert_eq!(inverse(1, 548), Some(1));
1060        assert!(inverse(4, 548).is_none());
1061        assert_eq!(inverse(7, 548), Some(235));
1062        assert!(inverse(10, 548).is_none());
1063        assert_eq!(inverse(13, 548), Some(253));
1064        assert!(inverse(16, 548).is_none());
1065        assert_eq!(inverse(19, 548), Some(375));
1066        assert!(inverse(22, 548).is_none());
1067        assert_eq!(inverse(25, 548), Some(285));
1068        assert!(inverse(28, 548).is_none());
1069        assert_eq!(inverse(1, 555), Some(1));
1070        assert_eq!(inverse(4, 555), Some(139));
1071        assert_eq!(inverse(7, 555), Some(238));
1072        assert!(inverse(10, 555).is_none());
1073        assert_eq!(inverse(13, 555), Some(427));
1074        assert_eq!(inverse(16, 555), Some(451));
1075        assert_eq!(inverse(19, 555), Some(409));
1076        assert_eq!(inverse(22, 555), Some(328));
1077        assert!(inverse(25, 555).is_none());
1078        assert_eq!(inverse(28, 555), Some(337));
1079        assert_eq!(inverse(1, 562), Some(1));
1080        assert!(inverse(4, 562).is_none());
1081        assert_eq!(inverse(7, 562), Some(241));
1082        assert!(inverse(10, 562).is_none());
1083        assert_eq!(inverse(13, 562), Some(173));
1084        assert!(inverse(16, 562).is_none());
1085        assert_eq!(inverse(19, 562), Some(355));
1086        assert!(inverse(22, 562).is_none());
1087        assert_eq!(inverse(25, 562), Some(45));
1088        assert!(inverse(28, 562).is_none());
1089        assert_eq!(inverse(1, 569), Some(1));
1090        assert_eq!(inverse(4, 569), Some(427));
1091        assert_eq!(inverse(7, 569), Some(244));
1092        assert_eq!(inverse(10, 569), Some(57));
1093        assert_eq!(inverse(13, 569), Some(394));
1094        assert_eq!(inverse(16, 569), Some(249));
1095        assert_eq!(inverse(19, 569), Some(30));
1096        assert_eq!(inverse(22, 569), Some(388));
1097        assert_eq!(inverse(25, 569), Some(478));
1098        assert_eq!(inverse(28, 569), Some(61));
1099        assert_eq!(inverse(1, 576), Some(1));
1100        assert!(inverse(4, 576).is_none());
1101        assert_eq!(inverse(7, 576), Some(247));
1102        assert!(inverse(10, 576).is_none());
1103        assert_eq!(inverse(13, 576), Some(133));
1104        assert!(inverse(16, 576).is_none());
1105        assert_eq!(inverse(19, 576), Some(91));
1106        assert!(inverse(22, 576).is_none());
1107        assert_eq!(inverse(25, 576), Some(553));
1108        assert!(inverse(28, 576).is_none());
1109        assert_eq!(inverse(1, 583), Some(1));
1110        assert_eq!(inverse(4, 583), Some(146));
1111        assert_eq!(inverse(7, 583), Some(250));
1112        assert_eq!(inverse(10, 583), Some(175));
1113        assert_eq!(inverse(13, 583), Some(314));
1114        assert_eq!(inverse(16, 583), Some(328));
1115        assert_eq!(inverse(19, 583), Some(491));
1116        assert!(inverse(22, 583).is_none());
1117        assert_eq!(inverse(25, 583), Some(70));
1118        assert_eq!(inverse(28, 583), Some(354));
1119        assert_eq!(inverse(1, 590), Some(1));
1120        assert!(inverse(4, 590).is_none());
1121        assert_eq!(inverse(7, 590), Some(253));
1122        assert!(inverse(10, 590).is_none());
1123        assert_eq!(inverse(13, 590), Some(227));
1124        assert!(inverse(16, 590).is_none());
1125        assert_eq!(inverse(19, 590), Some(559));
1126        assert!(inverse(22, 590).is_none());
1127        assert!(inverse(25, 590).is_none());
1128        assert!(inverse(28, 590).is_none());
1129        assert_eq!(inverse(1, 597), Some(1));
1130        assert_eq!(inverse(4, 597), Some(448));
1131        assert_eq!(inverse(7, 597), Some(256));
1132        assert_eq!(inverse(10, 597), Some(418));
1133        assert_eq!(inverse(13, 597), Some(46));
1134        assert_eq!(inverse(16, 597), Some(112));
1135        assert_eq!(inverse(19, 597), Some(220));
1136        assert_eq!(inverse(22, 597), Some(190));
1137        assert_eq!(inverse(25, 597), Some(406));
1138        assert_eq!(inverse(28, 597), Some(64));
1139        assert_eq!(inverse(1, 604), Some(1));
1140        assert!(inverse(4, 604).is_none());
1141        assert_eq!(inverse(7, 604), Some(259));
1142        assert!(inverse(10, 604).is_none());
1143        assert_eq!(inverse(13, 604), Some(93));
1144        assert!(inverse(16, 604).is_none());
1145        assert_eq!(inverse(19, 604), Some(159));
1146        assert!(inverse(22, 604).is_none());
1147        assert_eq!(inverse(25, 604), Some(145));
1148        assert!(inverse(28, 604).is_none());
1149        assert_eq!(inverse(1, 611), Some(1));
1150        assert_eq!(inverse(4, 611), Some(153));
1151        assert_eq!(inverse(7, 611), Some(262));
1152        assert_eq!(inverse(10, 611), Some(550));
1153        assert!(inverse(13, 611).is_none());
1154        assert_eq!(inverse(16, 611), Some(191));
1155        assert_eq!(inverse(19, 611), Some(193));
1156        assert_eq!(inverse(22, 611), Some(250));
1157        assert_eq!(inverse(25, 611), Some(220));
1158        assert_eq!(inverse(28, 611), Some(371));
1159        assert_eq!(inverse(1, 618), Some(1));
1160        assert!(inverse(4, 618).is_none());
1161        assert_eq!(inverse(7, 618), Some(265));
1162        assert!(inverse(10, 618).is_none());
1163        assert_eq!(inverse(13, 618), Some(523));
1164        assert!(inverse(16, 618).is_none());
1165        assert_eq!(inverse(19, 618), Some(553));
1166        assert!(inverse(22, 618).is_none());
1167        assert_eq!(inverse(25, 618), Some(445));
1168        assert!(inverse(28, 618).is_none());
1169        assert_eq!(inverse(1, 625), Some(1));
1170        assert_eq!(inverse(4, 625), Some(469));
1171        assert_eq!(inverse(7, 625), Some(268));
1172        assert!(inverse(10, 625).is_none());
1173        assert_eq!(inverse(13, 625), Some(577));
1174        assert_eq!(inverse(16, 625), Some(586));
1175        assert_eq!(inverse(19, 625), Some(329));
1176        assert_eq!(inverse(22, 625), Some(483));
1177        assert!(inverse(25, 625).is_none());
1178        assert_eq!(inverse(28, 625), Some(67));
1179        assert_eq!(inverse(1, 632), Some(1));
1180        assert!(inverse(4, 632).is_none());
1181        assert_eq!(inverse(7, 632), Some(271));
1182        assert!(inverse(10, 632).is_none());
1183        assert_eq!(inverse(13, 632), Some(389));
1184        assert!(inverse(16, 632).is_none());
1185        assert_eq!(inverse(19, 632), Some(499));
1186        assert!(inverse(22, 632).is_none());
1187        assert_eq!(inverse(25, 632), Some(177));
1188        assert!(inverse(28, 632).is_none());
1189        assert_eq!(inverse(1, 639), Some(1));
1190        assert_eq!(inverse(4, 639), Some(160));
1191        assert_eq!(inverse(7, 639), Some(274));
1192        assert_eq!(inverse(10, 639), Some(64));
1193        assert_eq!(inverse(13, 639), Some(295));
1194        assert_eq!(inverse(16, 639), Some(40));
1195        assert_eq!(inverse(19, 639), Some(370));
1196        assert_eq!(inverse(22, 639), Some(610));
1197        assert_eq!(inverse(25, 639), Some(409));
1198        assert_eq!(inverse(28, 639), Some(388));
1199        assert_eq!(inverse(1, 646), Some(1));
1200        assert!(inverse(4, 646).is_none());
1201        assert_eq!(inverse(7, 646), Some(277));
1202        assert!(inverse(10, 646).is_none());
1203        assert_eq!(inverse(13, 646), Some(497));
1204        assert!(inverse(16, 646).is_none());
1205        assert!(inverse(19, 646).is_none());
1206        assert!(inverse(22, 646).is_none());
1207        assert_eq!(inverse(25, 646), Some(491));
1208        assert!(inverse(28, 646).is_none());
1209        assert_eq!(inverse(1, 653), Some(1));
1210        assert_eq!(inverse(4, 653), Some(490));
1211        assert_eq!(inverse(7, 653), Some(280));
1212        assert_eq!(inverse(10, 653), Some(196));
1213        assert_eq!(inverse(13, 653), Some(201));
1214        assert_eq!(inverse(16, 653), Some(449));
1215        assert_eq!(inverse(19, 653), Some(275));
1216        assert_eq!(inverse(22, 653), Some(564));
1217        assert_eq!(inverse(25, 653), Some(209));
1218        assert_eq!(inverse(28, 653), Some(70));
1219        assert_eq!(inverse(1, 660), Some(1));
1220        assert!(inverse(4, 660).is_none());
1221        assert_eq!(inverse(7, 660), Some(283));
1222        assert!(inverse(10, 660).is_none());
1223        assert_eq!(inverse(13, 660), Some(457));
1224        assert!(inverse(16, 660).is_none());
1225        assert_eq!(inverse(19, 660), Some(139));
1226        assert!(inverse(22, 660).is_none());
1227        assert!(inverse(25, 660).is_none());
1228        assert!(inverse(28, 660).is_none());
1229        assert_eq!(inverse(1, 667), Some(1));
1230        assert_eq!(inverse(4, 667), Some(167));
1231        assert_eq!(inverse(7, 667), Some(286));
1232        assert_eq!(inverse(10, 667), Some(467));
1233        assert_eq!(inverse(13, 667), Some(154));
1234        assert_eq!(inverse(16, 667), Some(542));
1235        assert_eq!(inverse(19, 667), Some(316));
1236        assert_eq!(inverse(22, 667), Some(91));
1237        assert_eq!(inverse(25, 667), Some(587));
1238        assert_eq!(inverse(28, 667), Some(405));
1239        assert_eq!(inverse(1, 674), Some(1));
1240        assert!(inverse(4, 674).is_none());
1241        assert_eq!(inverse(7, 674), Some(289));
1242        assert!(inverse(10, 674).is_none());
1243        assert_eq!(inverse(13, 674), Some(363));
1244        assert!(inverse(16, 674).is_none());
1245        assert_eq!(inverse(19, 674), Some(71));
1246        assert!(inverse(22, 674).is_none());
1247        assert_eq!(inverse(25, 674), Some(27));
1248        assert!(inverse(28, 674).is_none());
1249        assert_eq!(inverse(1, 681), Some(1));
1250        assert_eq!(inverse(4, 681), Some(511));
1251        assert_eq!(inverse(7, 681), Some(292));
1252        assert_eq!(inverse(10, 681), Some(613));
1253        assert_eq!(inverse(13, 681), Some(262));
1254        assert_eq!(inverse(16, 681), Some(298));
1255        assert_eq!(inverse(19, 681), Some(466));
1256        assert_eq!(inverse(22, 681), Some(31));
1257        assert_eq!(inverse(25, 681), Some(109));
1258        assert_eq!(inverse(28, 681), Some(73));
1259        assert_eq!(inverse(1, 688), Some(1));
1260        assert!(inverse(4, 688).is_none());
1261        assert_eq!(inverse(7, 688), Some(295));
1262        assert!(inverse(10, 688).is_none());
1263        assert_eq!(inverse(13, 688), Some(53));
1264        assert!(inverse(16, 688).is_none());
1265        assert_eq!(inverse(19, 688), Some(507));
1266        assert!(inverse(22, 688).is_none());
1267        assert_eq!(inverse(25, 688), Some(633));
1268        assert!(inverse(28, 688).is_none());
1269        assert_eq!(inverse(1, 695), Some(1));
1270        assert_eq!(inverse(4, 695), Some(174));
1271        assert_eq!(inverse(7, 695), Some(298));
1272        assert!(inverse(10, 695).is_none());
1273        assert_eq!(inverse(13, 695), Some(107));
1274        assert_eq!(inverse(16, 695), Some(391));
1275        assert_eq!(inverse(19, 695), Some(439));
1276        assert_eq!(inverse(22, 695), Some(158));
1277        assert!(inverse(25, 695).is_none());
1278        assert_eq!(inverse(28, 695), Some(422));
1279        assert_eq!(inverse(1, 702), Some(1));
1280        assert!(inverse(4, 702).is_none());
1281        assert_eq!(inverse(7, 702), Some(301));
1282        assert!(inverse(10, 702).is_none());
1283        assert!(inverse(13, 702).is_none());
1284        assert!(inverse(16, 702).is_none());
1285        assert_eq!(inverse(19, 702), Some(37));
1286        assert!(inverse(22, 702).is_none());
1287        assert_eq!(inverse(25, 702), Some(337));
1288        assert!(inverse(28, 702).is_none());
1289        assert_eq!(inverse(1, 709), Some(1));
1290        assert_eq!(inverse(4, 709), Some(532));
1291        assert_eq!(inverse(7, 709), Some(304));
1292        assert_eq!(inverse(10, 709), Some(71));
1293        assert_eq!(inverse(13, 709), Some(600));
1294        assert_eq!(inverse(16, 709), Some(133));
1295        assert_eq!(inverse(19, 709), Some(112));
1296        assert_eq!(inverse(22, 709), Some(419));
1297        assert_eq!(inverse(25, 709), Some(312));
1298        assert_eq!(inverse(28, 709), Some(76));
1299        assert_eq!(inverse(1, 716), Some(1));
1300        assert!(inverse(4, 716).is_none());
1301        assert_eq!(inverse(7, 716), Some(307));
1302        assert!(inverse(10, 716).is_none());
1303        assert_eq!(inverse(13, 716), Some(661));
1304        assert!(inverse(16, 716).is_none());
1305        assert_eq!(inverse(19, 716), Some(603));
1306        assert!(inverse(22, 716).is_none());
1307        assert_eq!(inverse(25, 716), Some(401));
1308        assert!(inverse(28, 716).is_none());
1309        assert_eq!(inverse(1, 723), Some(1));
1310        assert_eq!(inverse(4, 723), Some(181));
1311        assert_eq!(inverse(7, 723), Some(310));
1312        assert_eq!(inverse(10, 723), Some(217));
1313        assert_eq!(inverse(13, 723), Some(445));
1314        assert_eq!(inverse(16, 723), Some(226));
1315        assert_eq!(inverse(19, 723), Some(685));
1316        assert_eq!(inverse(22, 723), Some(493));
1317        assert_eq!(inverse(25, 723), Some(376));
1318        assert_eq!(inverse(28, 723), Some(439));
1319        assert_eq!(inverse(1, 730), Some(1));
1320        assert!(inverse(4, 730).is_none());
1321        assert_eq!(inverse(7, 730), Some(313));
1322        assert!(inverse(10, 730).is_none());
1323        assert_eq!(inverse(13, 730), Some(337));
1324        assert!(inverse(16, 730).is_none());
1325        assert_eq!(inverse(19, 730), Some(269));
1326        assert!(inverse(22, 730).is_none());
1327        assert!(inverse(25, 730).is_none());
1328        assert!(inverse(28, 730).is_none());
1329        assert_eq!(inverse(1, 737), Some(1));
1330        assert_eq!(inverse(4, 737), Some(553));
1331        assert_eq!(inverse(7, 737), Some(316));
1332        assert_eq!(inverse(10, 737), Some(516));
1333        assert_eq!(inverse(13, 737), Some(567));
1334        assert_eq!(inverse(16, 737), Some(691));
1335        assert_eq!(inverse(19, 737), Some(194));
1336        assert!(inverse(22, 737).is_none());
1337        assert_eq!(inverse(25, 737), Some(59));
1338        assert_eq!(inverse(28, 737), Some(79));
1339        assert_eq!(inverse(1, 744), Some(1));
1340        assert!(inverse(4, 744).is_none());
1341        assert_eq!(inverse(7, 744), Some(319));
1342        assert!(inverse(10, 744).is_none());
1343        assert_eq!(inverse(13, 744), Some(229));
1344        assert!(inverse(16, 744).is_none());
1345        assert_eq!(inverse(19, 744), Some(235));
1346        assert!(inverse(22, 744).is_none());
1347        assert_eq!(inverse(25, 744), Some(625));
1348        assert!(inverse(28, 744).is_none());
1349        assert_eq!(inverse(1, 751), Some(1));
1350        assert_eq!(inverse(4, 751), Some(188));
1351        assert_eq!(inverse(7, 751), Some(322));
1352        assert_eq!(inverse(10, 751), Some(676));
1353        assert_eq!(inverse(13, 751), Some(520));
1354        assert_eq!(inverse(16, 751), Some(47));
1355        assert_eq!(inverse(19, 751), Some(672));
1356        assert_eq!(inverse(22, 751), Some(239));
1357        assert_eq!(inverse(25, 751), Some(721));
1358        assert_eq!(inverse(28, 751), Some(456));
1359        assert_eq!(inverse(1, 758), Some(1));
1360        assert!(inverse(4, 758).is_none());
1361        assert_eq!(inverse(7, 758), Some(325));
1362        assert!(inverse(10, 758).is_none());
1363        assert_eq!(inverse(13, 758), Some(175));
1364        assert!(inverse(16, 758).is_none());
1365        assert_eq!(inverse(19, 758), Some(399));
1366        assert!(inverse(22, 758).is_none());
1367        assert_eq!(inverse(25, 758), Some(91));
1368        assert!(inverse(28, 758).is_none());
1369        assert_eq!(inverse(1, 765), Some(1));
1370        assert_eq!(inverse(4, 765), Some(574));
1371        assert_eq!(inverse(7, 765), Some(328));
1372        assert!(inverse(10, 765).is_none());
1373        assert_eq!(inverse(13, 765), Some(412));
1374        assert_eq!(inverse(16, 765), Some(526));
1375        assert_eq!(inverse(19, 765), Some(604));
1376        assert_eq!(inverse(22, 765), Some(313));
1377        assert!(inverse(25, 765).is_none());
1378        assert_eq!(inverse(28, 765), Some(82));
1379        assert_eq!(inverse(1, 772), Some(1));
1380        assert!(inverse(4, 772).is_none());
1381        assert_eq!(inverse(7, 772), Some(331));
1382        assert!(inverse(10, 772).is_none());
1383        assert_eq!(inverse(13, 772), Some(297));
1384        assert!(inverse(16, 772).is_none());
1385        assert_eq!(inverse(19, 772), Some(447));
1386        assert!(inverse(22, 772).is_none());
1387        assert_eq!(inverse(25, 772), Some(525));
1388        assert!(inverse(28, 772).is_none());
1389        assert_eq!(inverse(1, 779), Some(1));
1390        assert_eq!(inverse(4, 779), Some(195));
1391        assert_eq!(inverse(7, 779), Some(334));
1392        assert_eq!(inverse(10, 779), Some(78));
1393        assert_eq!(inverse(13, 779), Some(60));
1394        assert_eq!(inverse(16, 779), Some(633));
1395        assert!(inverse(19, 779).is_none());
1396        assert_eq!(inverse(22, 779), Some(602));
1397        assert_eq!(inverse(25, 779), Some(187));
1398        assert_eq!(inverse(28, 779), Some(473));
1399        assert_eq!(inverse(1, 786), Some(1));
1400        assert!(inverse(4, 786).is_none());
1401        assert_eq!(inverse(7, 786), Some(337));
1402        assert!(inverse(10, 786).is_none());
1403        assert_eq!(inverse(13, 786), Some(121));
1404        assert!(inverse(16, 786).is_none());
1405        assert_eq!(inverse(19, 786), Some(331));
1406        assert!(inverse(22, 786).is_none());
1407        assert_eq!(inverse(25, 786), Some(283));
1408        assert!(inverse(28, 786).is_none());
1409        assert_eq!(inverse(1, 793), Some(1));
1410        assert_eq!(inverse(4, 793), Some(595));
1411        assert_eq!(inverse(7, 793), Some(340));
1412        assert_eq!(inverse(10, 793), Some(238));
1413        assert!(inverse(13, 793).is_none());
1414        assert_eq!(inverse(16, 793), Some(347));
1415        assert_eq!(inverse(19, 793), Some(167));
1416        assert_eq!(inverse(22, 793), Some(757));
1417        assert_eq!(inverse(25, 793), Some(571));
1418        assert_eq!(inverse(28, 793), Some(85));
1419        assert_eq!(inverse(1, 800), Some(1));
1420        assert!(inverse(4, 800).is_none());
1421        assert_eq!(inverse(7, 800), Some(343));
1422        assert!(inverse(10, 800).is_none());
1423        assert_eq!(inverse(13, 800), Some(677));
1424        assert!(inverse(16, 800).is_none());
1425        assert_eq!(inverse(19, 800), Some(379));
1426        assert!(inverse(22, 800).is_none());
1427        assert!(inverse(25, 800).is_none());
1428        assert!(inverse(28, 800).is_none());
1429        assert_eq!(inverse(1, 807), Some(1));
1430        assert_eq!(inverse(4, 807), Some(202));
1431        assert_eq!(inverse(7, 807), Some(346));
1432        assert_eq!(inverse(10, 807), Some(565));
1433        assert_eq!(inverse(13, 807), Some(745));
1434        assert_eq!(inverse(16, 807), Some(454));
1435        assert_eq!(inverse(19, 807), Some(85));
1436        assert_eq!(inverse(22, 807), Some(697));
1437        assert_eq!(inverse(25, 807), Some(226));
1438        assert_eq!(inverse(28, 807), Some(490));
1439        assert_eq!(inverse(1, 814), Some(1));
1440        assert!(inverse(4, 814).is_none());
1441        assert_eq!(inverse(7, 814), Some(349));
1442        assert!(inverse(10, 814).is_none());
1443        assert_eq!(inverse(13, 814), Some(501));
1444        assert!(inverse(16, 814).is_none());
1445        assert_eq!(inverse(19, 814), Some(557));
1446        assert!(inverse(22, 814).is_none());
1447        assert_eq!(inverse(25, 814), Some(521));
1448        assert!(inverse(28, 814).is_none());
1449        assert_eq!(inverse(1, 821), Some(1));
1450        assert_eq!(inverse(4, 821), Some(616));
1451        assert_eq!(inverse(7, 821), Some(352));
1452        assert_eq!(inverse(10, 821), Some(739));
1453        assert_eq!(inverse(13, 821), Some(379));
1454        assert_eq!(inverse(16, 821), Some(154));
1455        assert_eq!(inverse(19, 821), Some(605));
1456        assert_eq!(inverse(22, 821), Some(112));
1457        assert_eq!(inverse(25, 821), Some(624));
1458        assert_eq!(inverse(28, 821), Some(88));
1459        assert_eq!(inverse(1, 828), Some(1));
1460        assert!(inverse(4, 828).is_none());
1461        assert_eq!(inverse(7, 828), Some(355));
1462        assert!(inverse(10, 828).is_none());
1463        assert_eq!(inverse(13, 828), Some(637));
1464        assert!(inverse(16, 828).is_none());
1465        assert_eq!(inverse(19, 828), Some(523));
1466        assert!(inverse(22, 828).is_none());
1467        assert_eq!(inverse(25, 828), Some(265));
1468        assert!(inverse(28, 828).is_none());
1469        assert_eq!(inverse(1, 835), Some(1));
1470        assert_eq!(inverse(4, 835), Some(209));
1471        assert_eq!(inverse(7, 835), Some(358));
1472        assert!(inverse(10, 835).is_none());
1473        assert_eq!(inverse(13, 835), Some(257));
1474        assert_eq!(inverse(16, 835), Some(261));
1475        assert_eq!(inverse(19, 835), Some(44));
1476        assert_eq!(inverse(22, 835), Some(38));
1477        assert!(inverse(25, 835).is_none());
1478        assert_eq!(inverse(28, 835), Some(507));
1479        assert_eq!(inverse(1, 842), Some(1));
1480        assert!(inverse(4, 842).is_none());
1481        assert_eq!(inverse(7, 842), Some(361));
1482        assert!(inverse(10, 842).is_none());
1483        assert_eq!(inverse(13, 842), Some(583));
1484        assert!(inverse(16, 842).is_none());
1485        assert_eq!(inverse(19, 842), Some(133));
1486        assert!(inverse(22, 842).is_none());
1487        assert_eq!(inverse(25, 842), Some(741));
1488        assert!(inverse(28, 842).is_none());
1489        assert_eq!(inverse(1, 849), Some(1));
1490        assert_eq!(inverse(4, 849), Some(637));
1491        assert_eq!(inverse(7, 849), Some(364));
1492        assert_eq!(inverse(10, 849), Some(85));
1493        assert_eq!(inverse(13, 849), Some(196));
1494        assert_eq!(inverse(16, 849), Some(796));
1495        assert_eq!(inverse(19, 849), Some(715));
1496        assert_eq!(inverse(22, 849), Some(193));
1497        assert_eq!(inverse(25, 849), Some(34));
1498        assert_eq!(inverse(28, 849), Some(91));
1499        assert_eq!(inverse(1, 856), Some(1));
1500        assert!(inverse(4, 856).is_none());
1501        assert_eq!(inverse(7, 856), Some(367));
1502        assert!(inverse(10, 856).is_none());
1503        assert_eq!(inverse(13, 856), Some(461));
1504        assert!(inverse(16, 856).is_none());
1505        assert_eq!(inverse(19, 856), Some(811));
1506        assert!(inverse(22, 856).is_none());
1507        assert_eq!(inverse(25, 856), Some(137));
1508        assert!(inverse(28, 856).is_none());
1509        assert_eq!(inverse(1, 863), Some(1));
1510        assert_eq!(inverse(4, 863), Some(216));
1511        assert_eq!(inverse(7, 863), Some(370));
1512        assert_eq!(inverse(10, 863), Some(259));
1513        assert_eq!(inverse(13, 863), Some(332));
1514        assert_eq!(inverse(16, 863), Some(54));
1515        assert_eq!(inverse(19, 863), Some(318));
1516        assert_eq!(inverse(22, 863), Some(510));
1517        assert_eq!(inverse(25, 863), Some(794));
1518        assert_eq!(inverse(28, 863), Some(524));
1519        assert_eq!(inverse(1, 870), Some(1));
1520        assert!(inverse(4, 870).is_none());
1521        assert_eq!(inverse(7, 870), Some(373));
1522        assert!(inverse(10, 870).is_none());
1523        assert_eq!(inverse(13, 870), Some(67));
1524        assert!(inverse(16, 870).is_none());
1525        assert_eq!(inverse(19, 870), Some(229));
1526        assert!(inverse(22, 870).is_none());
1527        assert!(inverse(25, 870).is_none());
1528        assert!(inverse(28, 870).is_none());
1529        assert_eq!(inverse(1, 877), Some(1));
1530        assert_eq!(inverse(4, 877), Some(658));
1531        assert_eq!(inverse(7, 877), Some(376));
1532        assert_eq!(inverse(10, 877), Some(614));
1533        assert_eq!(inverse(13, 877), Some(135));
1534        assert_eq!(inverse(16, 877), Some(603));
1535        assert_eq!(inverse(19, 877), Some(277));
1536        assert_eq!(inverse(22, 877), Some(598));
1537        assert_eq!(inverse(25, 877), Some(421));
1538        assert_eq!(inverse(28, 877), Some(94));
1539        assert_eq!(inverse(1, 884), Some(1));
1540        assert!(inverse(4, 884).is_none());
1541        assert_eq!(inverse(7, 884), Some(379));
1542        assert!(inverse(10, 884).is_none());
1543        assert!(inverse(13, 884).is_none());
1544        assert!(inverse(16, 884).is_none());
1545        assert_eq!(inverse(19, 884), Some(791));
1546        assert!(inverse(22, 884).is_none());
1547        assert_eq!(inverse(25, 884), Some(389));
1548        assert!(inverse(28, 884).is_none());
1549        assert_eq!(inverse(1, 891), Some(1));
1550        assert_eq!(inverse(4, 891), Some(223));
1551        assert_eq!(inverse(7, 891), Some(382));
1552        assert_eq!(inverse(10, 891), Some(802));
1553        assert_eq!(inverse(13, 891), Some(754));
1554        assert_eq!(inverse(16, 891), Some(724));
1555        assert_eq!(inverse(19, 891), Some(469));
1556        assert!(inverse(22, 891).is_none());
1557        assert_eq!(inverse(25, 891), Some(499));
1558        assert_eq!(inverse(28, 891), Some(541));
1559        assert_eq!(inverse(1, 898), Some(1));
1560        assert!(inverse(4, 898).is_none());
1561        assert_eq!(inverse(7, 898), Some(385));
1562        assert!(inverse(10, 898).is_none());
1563        assert_eq!(inverse(13, 898), Some(829));
1564        assert!(inverse(16, 898).is_none());
1565        assert_eq!(inverse(19, 898), Some(709));
1566        assert!(inverse(22, 898).is_none());
1567        assert_eq!(inverse(25, 898), Some(467));
1568        assert!(inverse(28, 898).is_none());
1569        assert_eq!(inverse(1, 905), Some(1));
1570        assert_eq!(inverse(4, 905), Some(679));
1571        assert_eq!(inverse(7, 905), Some(388));
1572        assert!(inverse(10, 905).is_none());
1573        assert_eq!(inverse(13, 905), Some(557));
1574        assert_eq!(inverse(16, 905), Some(396));
1575        assert_eq!(inverse(19, 905), Some(524));
1576        assert_eq!(inverse(22, 905), Some(288));
1577        assert!(inverse(25, 905).is_none());
1578        assert_eq!(inverse(28, 905), Some(97));
1579        assert_eq!(inverse(1, 912), Some(1));
1580        assert!(inverse(4, 912).is_none());
1581        assert_eq!(inverse(7, 912), Some(391));
1582        assert!(inverse(10, 912).is_none());
1583        assert_eq!(inverse(13, 912), Some(421));
1584        assert!(inverse(16, 912).is_none());
1585        assert!(inverse(19, 912).is_none());
1586        assert!(inverse(22, 912).is_none());
1587        assert_eq!(inverse(25, 912), Some(73));
1588        assert!(inverse(28, 912).is_none());
1589        assert_eq!(inverse(1, 919), Some(1));
1590        assert_eq!(inverse(4, 919), Some(230));
1591        assert_eq!(inverse(7, 919), Some(394));
1592        assert_eq!(inverse(10, 919), Some(92));
1593        assert_eq!(inverse(13, 919), Some(707));
1594        assert_eq!(inverse(16, 919), Some(517));
1595        assert_eq!(inverse(19, 919), Some(387));
1596        assert_eq!(inverse(22, 919), Some(376));
1597        assert_eq!(inverse(25, 919), Some(772));
1598        assert_eq!(inverse(28, 919), Some(558));
1599        assert_eq!(inverse(1, 926), Some(1));
1600        assert!(inverse(4, 926).is_none());
1601        assert_eq!(inverse(7, 926), Some(397));
1602        assert!(inverse(10, 926).is_none());
1603        assert_eq!(inverse(13, 926), Some(285));
1604        assert!(inverse(16, 926).is_none());
1605        assert_eq!(inverse(19, 926), Some(195));
1606        assert!(inverse(22, 926).is_none());
1607        assert_eq!(inverse(25, 926), Some(889));
1608        assert!(inverse(28, 926).is_none());
1609        assert_eq!(inverse(1, 933), Some(1));
1610        assert_eq!(inverse(4, 933), Some(700));
1611        assert_eq!(inverse(7, 933), Some(400));
1612        assert_eq!(inverse(10, 933), Some(280));
1613        assert_eq!(inverse(13, 933), Some(646));
1614        assert_eq!(inverse(16, 933), Some(175));
1615        assert_eq!(inverse(19, 933), Some(442));
1616        assert_eq!(inverse(22, 933), Some(721));
1617        assert_eq!(inverse(25, 933), Some(112));
1618        assert_eq!(inverse(28, 933), Some(100));
1619        assert_eq!(inverse(1, 940), Some(1));
1620        assert!(inverse(4, 940).is_none());
1621        assert_eq!(inverse(7, 940), Some(403));
1622        assert!(inverse(10, 940).is_none());
1623        assert_eq!(inverse(13, 940), Some(217));
1624        assert!(inverse(16, 940).is_none());
1625        assert_eq!(inverse(19, 940), Some(99));
1626        assert!(inverse(22, 940).is_none());
1627        assert!(inverse(25, 940).is_none());
1628        assert!(inverse(28, 940).is_none());
1629        assert_eq!(inverse(1, 947), Some(1));
1630        assert_eq!(inverse(4, 947), Some(237));
1631        assert_eq!(inverse(7, 947), Some(406));
1632        assert_eq!(inverse(10, 947), Some(663));
1633        assert_eq!(inverse(13, 947), Some(510));
1634        assert_eq!(inverse(16, 947), Some(296));
1635        assert_eq!(inverse(19, 947), Some(648));
1636        assert_eq!(inverse(22, 947), Some(904));
1637        assert_eq!(inverse(25, 947), Some(644));
1638        assert_eq!(inverse(28, 947), Some(575));
1639        assert_eq!(inverse(1, 954), Some(1));
1640        assert!(inverse(4, 954).is_none());
1641        assert_eq!(inverse(7, 954), Some(409));
1642        assert!(inverse(10, 954).is_none());
1643        assert_eq!(inverse(13, 954), Some(367));
1644        assert!(inverse(16, 954).is_none());
1645        assert_eq!(inverse(19, 954), Some(703));
1646        assert!(inverse(22, 954).is_none());
1647        assert_eq!(inverse(25, 954), Some(229));
1648        assert!(inverse(28, 954).is_none());
1649        assert_eq!(inverse(1, 961), Some(1));
1650        assert_eq!(inverse(4, 961), Some(721));
1651        assert_eq!(inverse(7, 961), Some(412));
1652        assert_eq!(inverse(10, 961), Some(865));
1653        assert_eq!(inverse(13, 961), Some(74));
1654        assert_eq!(inverse(16, 961), Some(901));
1655        assert_eq!(inverse(19, 961), Some(607));
1656        assert_eq!(inverse(22, 961), Some(830));
1657        assert_eq!(inverse(25, 961), Some(346));
1658        assert_eq!(inverse(28, 961), Some(103));
1659        assert_eq!(inverse(1, 968), Some(1));
1660        assert!(inverse(4, 968).is_none());
1661        assert_eq!(inverse(7, 968), Some(415));
1662        assert!(inverse(10, 968).is_none());
1663        assert_eq!(inverse(13, 968), Some(149));
1664        assert!(inverse(16, 968).is_none());
1665        assert_eq!(inverse(19, 968), Some(51));
1666        assert!(inverse(22, 968).is_none());
1667        assert_eq!(inverse(25, 968), Some(697));
1668        assert!(inverse(28, 968).is_none());
1669        assert_eq!(inverse(1, 975), Some(1));
1670        assert_eq!(inverse(4, 975), Some(244));
1671        assert_eq!(inverse(7, 975), Some(418));
1672        assert!(inverse(10, 975).is_none());
1673        assert!(inverse(13, 975).is_none());
1674        assert_eq!(inverse(16, 975), Some(61));
1675        assert_eq!(inverse(19, 975), Some(154));
1676        assert_eq!(inverse(22, 975), Some(133));
1677        assert!(inverse(25, 975).is_none());
1678        assert_eq!(inverse(28, 975), Some(592));
1679        assert_eq!(inverse(1, 982), Some(1));
1680        assert!(inverse(4, 982).is_none());
1681        assert_eq!(inverse(7, 982), Some(421));
1682        assert!(inverse(10, 982).is_none());
1683        assert_eq!(inverse(13, 982), Some(831));
1684        assert!(inverse(16, 982).is_none());
1685        assert_eq!(inverse(19, 982), Some(827));
1686        assert!(inverse(22, 982).is_none());
1687        assert_eq!(inverse(25, 982), Some(275));
1688        assert!(inverse(28, 982).is_none());
1689        assert_eq!(inverse(1, 989), Some(1));
1690        assert_eq!(inverse(4, 989), Some(742));
1691        assert_eq!(inverse(7, 989), Some(424));
1692        assert_eq!(inverse(10, 989), Some(99));
1693        assert_eq!(inverse(13, 989), Some(913));
1694        assert_eq!(inverse(16, 989), Some(680));
1695        assert_eq!(inverse(19, 989), Some(937));
1696        assert_eq!(inverse(22, 989), Some(45));
1697        assert_eq!(inverse(25, 989), Some(633));
1698        assert_eq!(inverse(28, 989), Some(106));
1699        assert_eq!(inverse(1, 996), Some(1));
1700        assert!(inverse(4, 996).is_none());
1701        assert_eq!(inverse(7, 996), Some(427));
1702        assert!(inverse(10, 996).is_none());
1703        assert_eq!(inverse(13, 996), Some(613));
1704        assert!(inverse(16, 996).is_none());
1705        assert_eq!(inverse(19, 996), Some(367));
1706        assert!(inverse(22, 996).is_none());
1707        assert_eq!(inverse(25, 996), Some(757));
1708        assert!(inverse(28, 996).is_none());
1709    }
1710}
fhe_util/lib.rs

fhe_util/
lib.rs
