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
82
83
84
85
86
87
88
89
90
91
92
93
|
/*
* Copyright (c) 2020, Ali Mohammad Pur <mpfard@serenityos.org>
* Copyright (c) 2020-2021, Dex♪ <dexes.ttp@gmail.com>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#include "UnsignedBigIntegerAlgorithms.h"
namespace Crypto {
void UnsignedBigIntegerAlgorithms::modular_inverse_without_allocation(
UnsignedBigInteger const& a,
UnsignedBigInteger const& b,
UnsignedBigInteger& temp_1,
UnsignedBigInteger& temp_2,
UnsignedBigInteger& temp_3,
UnsignedBigInteger& temp_4,
UnsignedBigInteger& temp_minus,
UnsignedBigInteger& temp_quotient,
UnsignedBigInteger& temp_d,
UnsignedBigInteger& temp_u,
UnsignedBigInteger& temp_v,
UnsignedBigInteger& temp_x,
UnsignedBigInteger& result)
{
UnsignedBigInteger one { 1 };
temp_u.set_to(a);
if (a.words()[0] % 2 == 0) {
// u += b
add_into_accumulator_without_allocation(temp_u, b);
}
temp_v.set_to(b);
temp_x.set_to(0);
// d = b - 1
subtract_without_allocation(b, one, temp_d);
while (!(temp_v == 1)) {
while (temp_v < temp_u) {
// u -= v
subtract_without_allocation(temp_u, temp_v, temp_minus);
temp_u.set_to(temp_minus);
// d += x
add_into_accumulator_without_allocation(temp_d, temp_x);
while (temp_u.words()[0] % 2 == 0) {
if (temp_d.words()[0] % 2 == 1) {
// d += b
add_into_accumulator_without_allocation(temp_d, b);
}
// u /= 2
divide_u16_without_allocation(temp_u, 2, temp_quotient, temp_1);
temp_u.set_to(temp_quotient);
// d /= 2
divide_u16_without_allocation(temp_d, 2, temp_quotient, temp_1);
temp_d.set_to(temp_quotient);
}
}
// v -= u
subtract_without_allocation(temp_v, temp_u, temp_minus);
temp_v.set_to(temp_minus);
// x += d
add_into_accumulator_without_allocation(temp_x, temp_d);
while (temp_v.words()[0] % 2 == 0) {
if (temp_x.words()[0] % 2 == 1) {
// x += b
add_into_accumulator_without_allocation(temp_x, b);
}
// v /= 2
divide_u16_without_allocation(temp_v, 2, temp_quotient, temp_1);
temp_v.set_to(temp_quotient);
// x /= 2
divide_u16_without_allocation(temp_x, 2, temp_quotient, temp_1);
temp_x.set_to(temp_quotient);
}
}
// return x % b
divide_without_allocation(temp_x, b, temp_1, temp_2, temp_3, temp_4, temp_quotient, result);
}
}
|
