OLD | NEW |
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 Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |