Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(277)

Side by Side Diff: src/pkg/math/big/nat.go

Issue 6716048: code review 6716048: math/big: add 4-bit, fixed window exponentiation. (Closed)
Patch Set: diff -r 32c1ce44286f https://go.googlecode.com/hg/ Created 11 years, 5 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2009 The Go Authors. All rights reserved. 1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style 2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file. 3 // license that can be found in the LICENSE file.
4 4
5 // Package big implements multi-precision arithmetic (big numbers). 5 // Package big implements multi-precision arithmetic (big numbers).
6 // The following numeric types are supported: 6 // The following numeric types are supported:
7 // 7 //
8 // - Int signed integers 8 // - Int signed integers
9 // - Rat rational numbers 9 // - Rat rational numbers
10 // 10 //
(...skipping 1230 matching lines...) Expand 10 before | Expand all | Expand 10 after
1241 return z 1241 return z
1242 } 1242 }
1243 // y > 0 1243 // y > 0
1244 1244
1245 if len(m) != 0 { 1245 if len(m) != 0 {
1246 // We likely end up being as long as the modulus. 1246 // We likely end up being as long as the modulus.
1247 z = z.make(len(m)) 1247 z = z.make(len(m))
1248 } 1248 }
1249 z = z.set(x) 1249 z = z.set(x)
1250 1250
1251 // If the base is non-trivial and the exponent is large, we use
1252 // 4-bit, windowed exponentiation. This involves precomputing 14 values
1253 // (x^2...x^15) but then reduces the number of multiply-reduces by a
1254 // third. Even for a 32-bit exponent, this reduces the number of
1255 // operations.
1256 if len(x) > 1 && len(y) > 1 && len(m) > 0 {
1257 return z.expNNWindowed(x, y, m)
1258 }
1259
1251 v := y[len(y)-1] // v > 0 because y is normalized and y > 0 1260 v := y[len(y)-1] // v > 0 because y is normalized and y > 0
1252 shift := leadingZeros(v) + 1 1261 shift := leadingZeros(v) + 1
1253 v <<= shift 1262 v <<= shift
1254 var q nat 1263 var q nat
1255 1264
1256 const mask = 1 << (_W - 1) 1265 const mask = 1 << (_W - 1)
1257 1266
1258 // We walk through the bits of the exponent one by one. Each time we 1267 // We walk through the bits of the exponent one by one. Each time we
1259 // see a bit, we square, thus doubling the power. If the bit is a one, 1268 // see a bit, we square, thus doubling the power. If the bit is a one,
1260 // we also multiply by x, thus adding one to the power. 1269 // we also multiply by x, thus adding one to the power.
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after
1297 zz, r, q, z = q, z, zz, r 1306 zz, r, q, z = q, z, zz, r
1298 } 1307 }
1299 1308
1300 v <<= 1 1309 v <<= 1
1301 } 1310 }
1302 } 1311 }
1303 1312
1304 return z.norm() 1313 return z.norm()
1305 } 1314 }
1306 1315
1316 // expNNWindowed calculates x**y mod m using a fixed, 4-bit window.
1317 func (z nat) expNNWindowed(x, y, m nat) nat {
1318 // zz and r are used to avoid allocating in mul and div as otherwise
1319 // the arguments would alias.
1320 var zz, r nat
1321
1322 const n = 4
1323 // powers[i] contains x^i.
1324 var powers [1 << n]nat
1325 powers[0] = natOne
1326 powers[1] = x
1327 for i := 2; i < 1<<n; i += 2 {
1328 p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
1329 *p = p.mul(*p2, *p2)
1330 zz, r = zz.div(r, *p, m)
1331 *p, r = r, *p
1332 *p1 = p1.mul(*p, x)
1333 zz, r = zz.div(r, *p1, m)
1334 *p1, r = r, *p1
1335 }
1336
1337 z = z.setWord(1)
1338
1339 for i := len(y) - 1; i >= 0; i-- {
1340 yi := y[i]
1341 for j := 0; j < _W; j += n {
1342 if i != len(y)-1 || j != 0 {
1343 // Unrolled loop for significant performance
1344 // gain. Use go test -bench=".*" in crypto/rsa
1345 // to check performance before making changes.
1346 zz = zz.mul(z, z)
1347 zz, z = z, zz
1348 zz, r = zz.div(r, z, m)
1349 z, r = r, z
1350
1351 zz = zz.mul(z, z)
1352 zz, z = z, zz
1353 zz, r = zz.div(r, z, m)
1354 z, r = r, z
1355
1356 zz = zz.mul(z, z)
1357 zz, z = z, zz
1358 zz, r = zz.div(r, z, m)
1359 z, r = r, z
1360
1361 zz = zz.mul(z, z)
1362 zz, z = z, zz
1363 zz, r = zz.div(r, z, m)
1364 z, r = r, z
1365 }
1366
1367 zz = zz.mul(z, powers[yi>>(_W-n)])
1368 zz, z = z, zz
1369 zz, r = zz.div(r, z, m)
1370 z, r = r, z
1371
1372 yi <<= n
1373 }
1374 }
1375
1376 return z.norm()
1377 }
1378
1307 // probablyPrime performs reps Miller-Rabin tests to check whether n is prime. 1379 // probablyPrime performs reps Miller-Rabin tests to check whether n is prime.
1308 // If it returns true, n is prime with probability 1 - 1/4^reps. 1380 // If it returns true, n is prime with probability 1 - 1/4^reps.
1309 // If it returns false, n is not prime. 1381 // If it returns false, n is not prime.
1310 func (n nat) probablyPrime(reps int) bool { 1382 func (n nat) probablyPrime(reps int) bool {
1311 if len(n) == 0 { 1383 if len(n) == 0 {
1312 return false 1384 return false
1313 } 1385 }
1314 1386
1315 if len(n) == 1 { 1387 if len(n) == 1 {
1316 if n[0] < 2 { 1388 if n[0] < 2 {
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after
1424 s = 0 1496 s = 0
1425 d = 0 1497 d = 0
1426 } 1498 }
1427 } 1499 }
1428 if k < len(z) { 1500 if k < len(z) {
1429 z[k] = d 1501 z[k] = d
1430 } 1502 }
1431 1503
1432 return z.norm() 1504 return z.norm()
1433 } 1505 }
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b