tapyrus 0.5.0

General purpose library for using and interoperating with Tapyrus.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// Copyright (c) 2020 Chaintope Inc.
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

//! Utility for prime number
//!
//!

use rug::Integer;
use rug::integer::Order;

/// Prime number for secp256k1 field element.
pub const P: [u8; 32] = [
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2f
];

/// Calculate jacobi symbol
pub fn jacobi(a: &[u8]) -> i8 {
    let a = Integer::from_digits(a, Order::MsfBe);
    let p = Integer::from_digits(&P[..], Order::MsfBe);
    jacobi_inner(&a, &p)
}

fn jacobi_inner(a: &Integer, n: &Integer) -> i8 {
    assert!(*n >= 3);
    let a = Integer::from(a % n);
    if a == 0 {
        return 0;
    }
    if a == 1 {
        return 1;
    }

    let mut a1: Integer = a.clone();
    let mut e = 0;
    while a1.is_even() {
        a1 = a1.div_exact_u(2);
        e += 1;
    }
    let mut s: i8 = if e & 1 == 0
        || n.mod_u(8) == 1
        || n.mod_u(8) == 7
    {
        1
    } else if n.mod_u(8) == 3
        || n.mod_u(8) == 5
    {
        -1
    } else {
        0
    };
    if n.mod_u(4) == 3 && a1.mod_u(4) == 3
    {
        s = -s
    }

    if a1 == 1 {
        s
    } else {
        s * jacobi_inner(&(n % a1.clone()), &a1.clone())
    }
}

#[cfg(test)]
mod tests {
    use crate::util::prime::{jacobi, jacobi_inner};
    use rug::Integer;

    #[test]
    fn test_jacobi() {
        assert_eq!(1, jacobi_inner(&Integer::from(1), &Integer::from(3)));
        assert_eq!(-1, jacobi_inner(&Integer::from(2), &Integer::from(3)));
        assert_eq!(0, jacobi_inner(&Integer::from(3), &Integer::from(3)));

        let a = hex::decode("388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672").unwrap();
        assert_eq!(-1, jacobi(&a[..]));
    }
}