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
|
package rsa;
import org.junit.Test;
public class Montgomery {
static final int TEST_CONSTANT_PRIME_15_1 = 65537;
static final int TEST_CONSTANT_PRIME_31_1 = 2147483647; // eighth Mersenne prime
int mont_prod(int A, int B, int M) {
int s = 0;
for(int i = 0; i < 32; i++) {
int b = (B >>> i) & 1;
int q = (s - b * A) & 1;
s = (s + q*M + b*A) >>> 1;
}
return s;
}
int m_residue(int A, int M) {
long x = A & 0xFFFFFFFFFL;
long m = M & 0xFFFFFFFFFL;
x <<= 32;
x %= m;
return (int) x;
}
boolean test_montgomery_a_b_m(int A, int B, int M) {
//int prodMod = (A * B) % M;
int prodMod = A % M;
prodMod *= B % M;
prodMod %= M;
int Ar = m_residue(A, M);
int Br = m_residue(B, M);
int monProdMod = mont_prod(Ar, Br, M);
int monProdMod_ = mont_prod(1, monProdMod, M);
boolean success = prodMod == monProdMod_;
System.out.printf("%c A=%3x B=%3x M=%3x A*B=%3x Ar=%3x Br=%3x Ar*Br=%3x A*B=%3x\n",
success ? '*' : ' ', A, B, M, prodMod, Ar, Br,
monProdMod, monProdMod_);
return success;
}
@Test
public void test_montgomery() {
test_montgomery_a_b_m(11, 17, 19);
test_montgomery_a_b_m(11, 19, 17);
test_montgomery_a_b_m(17, 11, 19);
test_montgomery_a_b_m(17, 19, 11);
test_montgomery_a_b_m(19, 11, 17);
test_montgomery_a_b_m(19, 17, 11);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_15_1, 17, 19);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_15_1, 19, 17);
test_montgomery_a_b_m(17, TEST_CONSTANT_PRIME_15_1, 19);
test_montgomery_a_b_m(17, 19, TEST_CONSTANT_PRIME_15_1);
test_montgomery_a_b_m(19, TEST_CONSTANT_PRIME_15_1, 17);
test_montgomery_a_b_m(19, 17, TEST_CONSTANT_PRIME_15_1);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_15_1, 17,
TEST_CONSTANT_PRIME_31_1);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_15_1, TEST_CONSTANT_PRIME_31_1,
17);
test_montgomery_a_b_m(17, TEST_CONSTANT_PRIME_15_1,
TEST_CONSTANT_PRIME_31_1);
test_montgomery_a_b_m(17, TEST_CONSTANT_PRIME_31_1,
TEST_CONSTANT_PRIME_15_1);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_31_1, TEST_CONSTANT_PRIME_15_1,
17);
test_montgomery_a_b_m(TEST_CONSTANT_PRIME_31_1, 17,
TEST_CONSTANT_PRIME_15_1);
}
}
|
