The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/expt.txt
security/nss/lib/freebl/mpi/doc/expt.txt
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:5218e6d1d464 |
|---|---|
| 1 Exponentiation | |
| 2 | |
| 3 For exponentiation, the MPI library uses a simple and fairly standard | |
| 4 square-and-multiply method. The algorithm is this: | |
| 5 | |
| 6 Input: a, b | |
| 7 Output: a ** b | |
| 8 | |
| 9 s = 1 | |
| 10 | |
| 11 while(b != 0) | |
| 12 if(b is odd) | |
| 13 s = s * a | |
| 14 endif | |
| 15 | |
| 16 b = b / 2 | |
| 17 | |
| 18 x = x * x | |
| 19 endwhile | |
| 20 | |
| 21 return s | |
| 22 | |
| 23 The modular exponentiation is done the same way, except replacing: | |
| 24 | |
| 25 s = s * a | |
| 26 | |
| 27 with | |
| 28 s = (s * a) mod m | |
| 29 | |
| 30 and replacing | |
| 31 | |
| 32 x = x * x | |
| 33 | |
| 34 with | |
| 35 | |
| 36 x = (x * x) mod m | |
| 37 | |
| 38 Here is a sample exponentiation using the MPI library, as compared to | |
| 39 the same problem solved by the Unix 'bc' program on my system: | |
| 40 | |
| 41 Computation of 2,381,283 ** 235 | |
| 42 | |
| 43 'bc' says: | |
| 44 | |
| 45 4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\ | |
| 46 4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\ | |
| 47 6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\ | |
| 48 4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\ | |
| 49 6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\ | |
| 50 FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\ | |
| 51 CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\ | |
| 52 5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\ | |
| 53 CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\ | |
| 54 49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\ | |
| 55 5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\ | |
| 56 A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\ | |
| 57 D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\ | |
| 58 92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\ | |
| 59 A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\ | |
| 60 AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\ | |
| 61 E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\ | |
| 62 1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\ | |
| 63 CFFF2E1AC93F3CA264A1B | |
| 64 | |
| 65 MPI says: | |
| 66 | |
| 67 4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\ | |
| 68 4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\ | |
| 69 6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\ | |
| 70 4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\ | |
| 71 6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\ | |
| 72 FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\ | |
| 73 CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\ | |
| 74 5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\ | |
| 75 CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\ | |
| 76 49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\ | |
| 77 5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\ | |
| 78 A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\ | |
| 79 D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\ | |
| 80 92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\ | |
| 81 A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\ | |
| 82 AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\ | |
| 83 E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\ | |
| 84 1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\ | |
| 85 CFFF2E1AC93F3CA264A1B | |
| 86 | |
| 87 Diff says: | |
| 88 % diff bc.txt mp.txt | |
| 89 % | |
| 90 | |
| 91 ------------------------------------------------------------------ | |
| 92 This Source Code Form is subject to the terms of the Mozilla Public | |
| 93 # License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 94 # file, You can obtain one at http://mozilla.org/MPL/2.0/. |
