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