scale-core 0.1.2

low level datastructures and functionality for compiling for SCALE via wasm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// Copyright (c) 2021, COSIC-KU Leuven, Kasteelpark Arenberg 10, bus 2452, B-3001 Leuven-Heverlee, Belgium.
// Copyright (c) 2021, Cosmian Tech SAS, 53-55 rue La Boétie, Paris, France.

use crate::testing_emulated::P;
use crate::ClearModp;
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::ToPrimitive;

fn two_over(n: &BigInt) -> i8 {
    let nn: u32 = (n % BigInt::from(8)).to_u32().unwrap();
    if nn == 1 || nn == 7 {
        1
    } else {
        -1
    }
}

fn reciprocity(num: &BigInt, den: &BigInt) -> i8 {
    let nn: u32 = (num % BigInt::from(4)).to_u32().unwrap();
    let dd: u32 = (den % BigInt::from(4)).to_u32().unwrap();
    if nn == 3 && dd == 3 {
        -1
    } else {
        1
    }
}

fn is_even(num: &BigInt) -> bool {
    let nn: u32 = (num % BigInt::from(2)).to_u32().unwrap();
    nn == 0
}

pub fn jacobi(a: &BigInt, n: &BigInt) -> i8 {
    let mut acc = 1;
    let mut num = a % n;
    let mut den = n.clone();
    loop {
        num = num % &den;
        if num == BigInt::from(0) {
            return 0;
        }

        while is_even(&num) {
            acc *= two_over(&den);
            num /= 2;
        }

        if num == BigInt::from(1) {
            return acc;
        }

        if num.gcd(&den) > BigInt::from(1) {
            return 0;
        }

        acc *= reciprocity(&num, &den);
        let tmp = num;
        num = den;
        den = tmp;
    }
}

#[no_mangle]
extern "C" fn __legendrec(value: ClearModp) -> ClearModp {
    let a: BigInt = value.into();
    let ans = jacobi(&a, &*P);
    BigInt::from(ans).into()
}