Montgomery reduction: Difference between revisions
Content added Content deleted
m (→{{header|Tcl}}: mark as in progress) |
m (→{{header|Go}}: removed timing) |
||
Line 110: | Line 110: | ||
"fmt" |
"fmt" |
||
"math/big" |
"math/big" |
||
"math/rand" |
"math/rand" |
||
"time" |
"time" |
||
) |
) |
||
// mont holds numbers useful for working in Mongomery representation. |
// mont holds numbers useful for working in Mongomery representation. |
||
type mont struct { |
type mont struct { |
||
n uint // m.BitLen() |
n uint // m.BitLen() |
||
m *big.Int // modulus, must be odd |
m *big.Int // modulus, must be odd |
||
r2 *big.Int // (1<<2n) mod m |
r2 *big.Int // (1<<2n) mod m |
||
} |
} |
||
// constructor |
// constructor |
||
func newMont(m *big.Int) *mont { |
func newMont(m *big.Int) *mont { |
||
Line 145: | Line 145: | ||
} |
} |
||
return a |
return a |
||
} |
} |
||
// example use: |
// example use: |
||
func main() { |
func main() { |
||
Line 194: | Line 194: | ||
// and demonstrate a use: |
// and demonstrate a use: |
||
⚫ | |||
show("\nLibrary:", func() *big.Int { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
}) |
|||
prod := mr.reduce(mr.r2) // 1 |
|||
show("\nMontgomery:", func() *big.Int { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
for exp.BitLen() > 0 { |
|||
if exp.Bit(0) == 1 { |
|||
⚫ | |||
⚫ | |||
for exp.BitLen() > 0 { |
|||
if exp.Bit(0) == 1 { |
|||
⚫ | |||
} |
|||
exp.Rsh(exp, 1) |
|||
⚫ | |||
} |
} |
||
exp.Rsh(exp, 1) |
|||
base = mr.reduce(base.Mul(base, base)) |
|||
}) |
|||
} |
|||
⚫ | |||
// show library-based equivalent computation as a check |
|||
func show(heading string, f func() *big.Int) { |
|||
fmt.Println( |
fmt.Println("\nLibrary-based computation of x1 ^ x2 mod m:") |
||
⚫ | |||
t0 := time.Now() |
|||
⚫ | |||
⚫ | |||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
b: 2 |
b: 2 |
||
n: 100 |
n: 100 |
||
r: 1267650600228229401496703205376 |
r: 1267650600228229401496703205376 |
||
m: 750791094644726559640638407699 |
|||
m: 1191151171693032142151966564621 |
|||
t1: 323165824550862327179367294465482435542970161392400401329100 |
|||
t1: 138602318824179275477121611740471794618999274340657947731554 |
|||
t2: 308607334419945011411837686695175944083084270671482464168730 |
|||
t2: 397645077922552596057001924720561733079744309909810064024787 |
|||
r1: 440160025148131680164261562101 |
|||
r1: 1073769066977456952449715239458 |
|||
r2: 435362628198191204145287283255 |
|||
r2: 460620928979319347925360938242 |
|||
Original x1: |
Original x1: 540019781128412936473322405310 |
||
Recovererd from r1: |
Recovererd from r1: 540019781128412936473322405310 |
||
Original x2: |
Original x2: 515692107665463680305819378593 |
||
Recovererd from r2: |
Recovererd from r2: 515692107665463680305819378593 |
||
Montgomery computation of x1 ^ x2 mod m: |
|||
Library: |
|||
151232511393500655853002423778 |
|||
x1 ^ x2 mod m: 599840174322403511400105423249 |
|||
231us |
|||
Library based computation of x1 ^ x2 mod m: |
|||
Montgomery: |
|||
151232511393500655853002423778 |
|||
x1 ^ x2 mod m: 599840174322403511400105423249 |
|||
2.316ms |
|||
</pre> |
</pre> |
||