Montgomery reduction: Difference between revisions
m
→{{header|Go}}: removed timing
m (→{{header|Tcl}}: mark as in progress) |
m (→{{header|Go}}: removed timing) |
||
Line 110:
"fmt"
"math/big"
"math/rand"
"time"
)
// mont holds numbers useful for working in Mongomery representation.
type mont struct {
n uint // m.BitLen()
m *big.Int // modulus, must be odd
r2 *big.Int // (1<<2n) mod m
}
// constructor
func newMont(m *big.Int) *mont {
Line 145:
}
return a
}
// example use:
func main() {
Line 194:
// and demonstrate a use:
return new(big.Int).Exp(x1, x2, m)▼
prod := mr.reduce(mr.r2) // 1
▲ // this is the modular exponentiation algorithm, except we call
▲ // mont.reduce instead of using a mod function.
for
▲ exp := new(big.Int).Set(x2) // not reduced
▲ prod = mr.reduce(prod.Mul(prod, base))
▲ base = mr.reduce(base.Mul(base, base))
}
base = mr.reduce(base.Mul(base, base))
// show library-based equivalent computation as a check
fmt.Println(
▲ fmt.Println("x1 ^ x2 mod m:", f())
▲ fmt.Println(time.Now().Sub(t0))
}</lang>
{{out}}
<pre>
b: 2
n: 100
r: 1267650600228229401496703205376
m: 750791094644726559640638407699
t1: 323165824550862327179367294465482435542970161392400401329100
t2: 308607334419945011411837686695175944083084270671482464168730
r1: 440160025148131680164261562101
r2: 435362628198191204145287283255
Original x1:
Recovererd from r1:
Original x2:
Recovererd from r2:
Montgomery computation of x1 ^ x2 mod m:
151232511393500655853002423778
Library based computation of x1 ^ x2 mod m:
151232511393500655853002423778
</pre>
| |||