1 (* Copyright (C
) 1999-2006 Henry Cejtin
, Matthew Fluet
, Suresh
2 * Jagannathan
, and Stephen Weeks
.
4 * MLton is released under a BSD
-style license
.
5 * See the file MLton
-LICENSE for details
.
11 {layout
: 'a
-> Layout
.t
,
17 type ('a
, 'b
) simultaneous
=
18 {layout
: 'a
-> Layout
.t
,
27 val power
: ('a
, Pervasive
.Int.int) Types
.power
28 val powerInf
: ('a
, Pervasive
.IntInf
.int) Types
.power
29 val simultaneous
: ('a
, Pervasive
.Int.int) Types
.simultaneous
30 val simultaneousInf
: ('a
, Pervasive
.IntInf
.int) Types
.simultaneous
36 structure Int = Pervasive
.Int
37 structure Array
= Pervasive
.Array
39 fun for(a
: Int.int, b
: Int.int, f
: Int.int -> unit
) =
40 let fun loop i
= if i
>= b
then () else (f i
; loop(i
+ 1))
44 type 'a exponent
= {isZero
: 'a
-> bool,
45 divMod
: 'a
* 'a
-> 'a
* 'a
,
48 type 'a base
= {one
: 'a
,
50 layout
: 'a
-> Layout
.t
}
53 ({isZero
, divMod
, two
}: 'a exponent
)
54 ({one
, times
, layout
= _
}: 'b base
) =
57 (* Repeated squaring
. *)
58 fun power(b
: 'b
, n
: 'a
): 'b
=
60 (* The loop has been carefully unrolled once to avoid overflow when
61 * 'a is a fixed size integer
.
64 (* c
* b^
2n
= b0^n0
*)
65 if isZero n
then c
else next(c
, b
* b
, n
)
68 let val (d
, m
) = divMod(n
, two
)
69 in loop(if isZero m
then c
else c
* b
, b
, d
)
75 (* Based on page
618 of Handbook
of Applied Cryptography
. *)
76 fun simultaneous(ges
: ('b
* 'a
) list
): 'b
=
78 fun twoPowerWord i
: Word.t
= Word.<<(0w1
, Word.fromInt i
)
79 val twoPower
= Word.toInt
o twoPowerWord
82 val n
= List.length ges
83 val tableSize
= twoPower n
84 val table
= Array
.array(tableSize
, one
)
87 (ges
, fn (i
, (g
, _
)) =>
88 let val min
= twoPower i
89 in for(min
, twoPower(i
+ 1), fn i
=>
90 Array
.update(table
, i
,
91 g
* Array
.sub(table
, i
- min
)))
93 fun loop(ews
: ('a
* Word.t
) list
, Gs
: 'b list
): 'b list
=
100 (ews
, ([], 0w0
: Word.t
),
101 fn ((e
, w
'), (ews
, w
)) =>
103 val (e
, m
) = divMod(e
, two
)
105 if isZero e
then ews
else (e
, w
') :: ews
107 if isZero m
then w
else Word.orb(w
', w
)
110 in loop(ews
, Array
.sub(table
, Word.toInt w
) :: Gs
)
112 val ews
= List.mapi (ges
, fn (i
, (_
, e
)) =>
114 val Gs
= loop (ews
, [])
115 in List.fold (Gs
, one
, fn (G
, A
) => A
* A
* G
)
125 | x
:: l
=> loop(l
, n
- 1, x
:: ac
))
126 in loop(l
, window
, [])
128 fun loop(ges
: ('b
* 'a
) list
, ac
: 'b
): 'b
=
131 |
[(g
, e
)] => ac
* power(g
, e
)
132 | _
=> let val (ges
, rest
) = split ges
133 in loop(rest
, ac
* doit ges
)
137 in {power
= power
, simultaneous
= simultaneous
}
140 val intExp
: Int.int exponent
=
141 {isZero
= fn n
=> n
= 0,
142 divMod
= fn (a
, b
) => (a
div b
, a
mod b
),
145 fun power z
= #
power(make intExp z
)
146 fun simultaneous z
= #
simultaneous(make intExp z
)
149 let open Pervasive
.IntInf
151 in {isZero
= fn n
=> n
= zero
,
156 fun powerInf z
= #
power(make intInfExp z
)
157 fun simultaneousInf z
= #
simultaneous(make intInfExp z
)