1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/expt.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,94 @@
1.4 +Exponentiation
1.5 +
1.6 +For exponentiation, the MPI library uses a simple and fairly standard
1.7 +square-and-multiply method. The algorithm is this:
1.8 +
1.9 +Input: a, b
1.10 +Output: a ** b
1.11 +
1.12 + s = 1
1.13 +
1.14 + while(b != 0)
1.15 + if(b is odd)
1.16 + s = s * a
1.17 + endif
1.18 +
1.19 + b = b / 2
1.20 +
1.21 + x = x * x
1.22 + endwhile
1.23 +
1.24 + return s
1.25 +
1.26 +The modular exponentiation is done the same way, except replacing:
1.27 +
1.28 + s = s * a
1.29 +
1.30 +with
1.31 + s = (s * a) mod m
1.32 +
1.33 +and replacing
1.34 +
1.35 + x = x * x
1.36 +
1.37 +with
1.38 +
1.39 + x = (x * x) mod m
1.40 +
1.41 +Here is a sample exponentiation using the MPI library, as compared to
1.42 +the same problem solved by the Unix 'bc' program on my system:
1.43 +
1.44 +Computation of 2,381,283 ** 235
1.45 +
1.46 +'bc' says:
1.47 +
1.48 +4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\
1.49 +4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\
1.50 +6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\
1.51 +4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\
1.52 +6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\
1.53 +FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\
1.54 +CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\
1.55 +5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\
1.56 +CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\
1.57 +49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\
1.58 +5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\
1.59 +A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\
1.60 +D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\
1.61 +92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\
1.62 +A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\
1.63 +AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\
1.64 +E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\
1.65 +1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\
1.66 +CFFF2E1AC93F3CA264A1B
1.67 +
1.68 +MPI says:
1.69 +
1.70 +4385CA4A804D199FBEAD95FAD0796FAD0D0B51FC9C16743C45568C789666985DB719\
1.71 +4D90E393522F74C9601262C0514145A49F3B53D00983F95FDFCEA3D0043ECEF6227E\
1.72 +6FB59C924C3EE74447B359B5BF12A555D46CB819809EF423F004B55C587D6F0E8A55\
1.73 +4988036A42ACEF9F71459F97CEF6E574BD7373657111648626B1FF8EE15F663B2C0E\
1.74 +6BBE5082D4CDE8E14F263635AE8F35DB2C280819517BE388B5573B84C5A19C871685\
1.75 +FD408A6471F9D6AFAF5129A7548EAE926B40874B340285F44765BF5468CE20A13267\
1.76 +CD88CE6BC786ACED36EC7EA50F67FF27622575319068A332C3C0CB23E26FB55E26F4\
1.77 +5F732753A52B8E2FB4D4F42D894242613CA912A25486C3DEC9C66E5DB6182F6C1761\
1.78 +CF8CD0D255BE64B93836B27D452AE38F950EB98B517D4CF50D48F0165EF0CCCE1F5C\
1.79 +49BF18219FDBA0EEDD1A7E8B187B70C2BAED5EC5C6821EF27FAFB1CFF70111C52235\
1.80 +5E948B93A015AA1AE152B110BB5658CB14D3E45A48BFE7F082C1182672A455A695CD\
1.81 +A1855E8781E625F25B41B516E77F589FA420C3B058861EA138CF7A2C58DB3C7504FD\
1.82 +D29554D78237834CC5AE710D403CC4F6973D5012B7E117A8976B14A0B5AFA889BD47\
1.83 +92C461F0F96116F00A97AE9E83DC5203680CAF9A18A062566C145650AB86BE4F907F\
1.84 +A9F7AB4A700B29E1E5BACCD6DCBFA513E10832815F710807EED2E279081FEC61D619\
1.85 +AB270BEB3D3A1787B35A9DD41A8766CF21F3B5C693B3BAB1C2FA14A4ED202BC35743\
1.86 +E5CBE2391624D4F8C9BFBBC78D69764E7C6C5B11BF005677BFAD17D9278FFC1F158F\
1.87 +1B3683FF7960FA0608103792C4163DC0AF3E06287BB8624F8FE3A0FFBDF82ACECA2F\
1.88 +CFFF2E1AC93F3CA264A1B
1.89 +
1.90 +Diff says:
1.91 +% diff bc.txt mp.txt
1.92 +%
1.93 +
1.94 +------------------------------------------------------------------
1.95 + This Source Code Form is subject to the terms of the Mozilla Public
1.96 + # License, v. 2.0. If a copy of the MPL was not distributed with this
1.97 + # file, You can obtain one at http://mozilla.org/MPL/2.0/.
