Ton

1
/*
2
    This file is part of TON Blockchain Library.
3

4
    TON Blockchain Library is free software: you can redistribute it and/or modify
5
    it under the terms of the GNU Lesser General Public License as published by
6
    the Free Software Foundation, either version 2 of the License, or
7
    (at your option) any later version.
8

9
    TON Blockchain Library is distributed in the hope that it will be useful,
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
    GNU Lesser General Public License for more details.
13

14
    You should have received a copy of the GNU Lesser General Public License
15
    along with TON Blockchain Library.  If not, see <http://www.gnu.org/licenses/>.
16

17
    Copyright 2017-2020 Telegram Systems LLP
18
*/
19
#include "residue.h"
20

21
// --- impl
22
#include <assert.h>
23

24
namespace arith {
25
class Residue;
26
class ResidueRing;
27

28
void ResidueRing::init() {
29
  Zero = new Residue(0, td::Ref<ResidueRing>(this));
30
  One = new Residue(1, td::Ref<ResidueRing>(this));
31
}
32

33
ResidueRing::~ResidueRing() {
34
  delete Zero;
35
  delete One;
36
  delete Img_i;
37
  Zero = One = Img_i = 0;
38
}
39

40
const Residue operator+(const Residue& x, const Residue& y) {
41
  x.same_ring(y);
42
  Residue z(x.ring_ref());
43
  bn_assert(BN_mod_add(z.val.bn_ptr(), x.val.bn_ptr(), y.val.bn_ptr(), x.modulus().bn_ptr(), get_ctx()));
44
  return z;
45
}
46

47
const Residue operator-(const Residue& x, const Residue& y) {
48
  x.same_ring(y);
49
  Residue z(x.ring_ref());
50
  bn_assert(BN_mod_sub(z.val.bn_ptr(), x.val.bn_ptr(), y.val.bn_ptr(), x.modulus().bn_ptr(), get_ctx()));
51
  return z;
52
}
53

54
const Residue operator*(const Residue& x, const Residue& y) {
55
  x.same_ring(y);
56
  Residue z(x.ring_ref());
57
  bn_assert(BN_mod_mul(z.val.bn_ptr(), x.val.bn_ptr(), y.val.bn_ptr(), x.modulus().bn_ptr(), get_ctx()));
58
  return z;
59
}
60

61
const Residue operator-(const Residue& x) {
62
  Residue z(x);
63
  z.val.negate();
64
  return z.reduce();
65
}
66

67
Residue& Residue::operator+=(const Residue& y) {
68
  same_ring(y);
69
  bn_assert(BN_mod_add(val.bn_ptr(), val.bn_ptr(), y.val.bn_ptr(), modulus().bn_ptr(), get_ctx()));
70
  return *this;
71
}
72

73
Residue& Residue::operator-=(const Residue& y) {
74
  same_ring(y);
75
  bn_assert(BN_mod_sub(val.bn_ptr(), val.bn_ptr(), y.val.bn_ptr(), modulus().bn_ptr(), get_ctx()));
76
  return *this;
77
}
78

79
Residue& Residue::operator*=(const Residue& y) {
80
  same_ring(y);
81
  bn_assert(BN_mod_mul(val.bn_ptr(), val.bn_ptr(), y.val.bn_ptr(), modulus().bn_ptr(), get_ctx()));
82
  return *this;
83
}
84

85
bool operator==(const Residue& x, const Residue& y) {
86
  x.same_ring(y);
87
  return x.extract() == y.extract();
88
}
89

90
bool operator!=(const Residue& x, const Residue& y) {
91
  x.same_ring(y);
92
  return x.extract() != y.extract();
93
}
94

95
Residue sqr(const Residue& x) {
96
  Residue z(x.ring_ref());
97
  bn_assert(BN_mod_sqr(z.val.bn_ptr(), x.val.bn_ptr(), x.modulus().bn_ptr(), get_ctx()));
98
  return z;
99
}
100

101
Residue power(const Residue& x, const Bignum& y) {
102
  Residue z(x.ring_ref());
103
  bn_assert(BN_mod_exp(z.val.bn_ptr(), x.val.bn_ptr(), y.bn_ptr(), x.modulus().bn_ptr(), get_ctx()));
104
  return z;
105
}
106

107
Residue inverse(const Residue& x) {
108
  assert(x.ring_ref()->is_prime());
109
  return power(x, x.ring_ref()->get_modulus() - 2);
110
}
111

112
const Residue& ResidueRing::img_i() const {
113
  if (!Img_i) {
114
    assert(is_prime());
115
    assert(modulus % 4 == 1);
116
    int g = 2;
117
    Bignum n = (modulus - 1) / 4;
118
    while (true) {
119
      Residue t = power(frac(g), n);
120
      if (t != one() && t != frac(-1)) {
121
        Img_i = new Residue(t);
122
        break;
123
      }
124
      g++;
125
    }
126
  }
127
  return *Img_i;
128
}
129

130
Residue sqrt(const Residue& x) {
131
  assert(x.ring_of().is_prime());
132
  const ResidueRing& R = x.ring_of();
133
  const Bignum& p = R.get_modulus();
134
  if (x.is_zero() || !p.odd()) {
135
    return x;
136
  }
137
  if (p[1]) {  // p=3 (mod 4)
138
    return power(x, (p + 1) >> 2);
139
  } else if (p[2]) {
140
    // p=5 (mod 8)
141
    Residue t = power(x, (p + 3) >> 3);
142
    return (sqr(t) == x) ? t : R.img_i() * t;
143
  } else {
144
    assert(p[2]);
145
    return R.zero();
146
  }
147
}
148

149
Residue ResidueRing::frac(long num, long denom) const {
150
  assert(denom);
151
  if (denom < 0) {
152
    num = -num;
153
    denom = -denom;
154
  }
155
  if (!(num % denom)) {
156
    return Residue(num / denom, self_ref());
157
  } else {
158
    return Residue(num, self_ref()) * inverse(Residue(denom, self_ref()));
159
  }
160
}
161

162
std::string Residue::to_str() const {
163
  return "Mod(" + val.to_str() + "," + modulus().to_str() + ")";
164
}
165

166
std::ostream& operator<<(std::ostream& os, const Residue& x) {
167
  return os << x.to_str();
168
}
169

170
std::istream& operator>>(std::istream& is, Residue& x) {
171
  std::string word;
172
  is >> word;
173
  x = dec_string(word);
174
  return is;
175
}
176
}  // namespace arith
177