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
|
package com.hurlant.math
{
use namespace bi_internal;
internal class BarrettReduction implements IReduction
{
private var m:BigInteger;
private var r2:BigInteger;
private var q3:BigInteger;
private var mu:BigInteger;
public function BarrettReduction(m:BigInteger) {
// setup Barrett
r2 = new BigInteger;
q3 = new BigInteger;
BigInteger.ONE.dlShiftTo(2*m.t, r2);
mu = r2.divide(m);
this.m = m;
}
public function revert(x:BigInteger):BigInteger
{
return x;
}
/**
*
* @param x
* @param y
* @param r = x*y mod m; x != r
*
*/
public function mulTo(x:BigInteger, y:BigInteger, r:BigInteger):void
{
x.multiplyTo(y, r);
reduce(r);
}
/**
*
* @param x
* @param r = x^2 mod m; x != r
*
*/
public function sqrTo(x:BigInteger, r:BigInteger):void
{
x.squareTo(r);
reduce(r);
}
public function convert(x:BigInteger):BigInteger
{
if (x.s<0 || x.t>2*m.t) {
return x.mod(m);
} else if (x.compareTo(m)<0) {
return x;
} else {
var r:BigInteger = new BigInteger;
x.copyTo(r);
reduce(r);
return r;
}
}
/**
*
* @param x = x mod m (HAC 14.42)
*
*/
public function reduce(lx:BigInteger):void
{
var x:BigInteger = lx as BigInteger;
x.drShiftTo(m.t-1,r2);
if (x.t>m.t+1) {
x.t = m.t+1;
x.clamp();
}
mu.multiplyUpperTo(r2, m.t+1, q3);
m.multiplyLowerTo(q3, m.t+1, r2);
while (x.compareTo(r2)<0) {
x.dAddOffset(1, m.t+1);
}
x.subTo(r2,x);
while (x.compareTo(m)>=0) {
x.subTo(m,x);
}
}
}
}
|
