The unified diff between revisions [ee2b2c17..] and [b676473c..] is displayed below. It can also be downloaded as a raw diff.
#
#
# delete ""
#
# delete "LICENSE"
#
# delete "bn_error.c"
#
# delete "bn_fast_mp_invmod.c"
#
# delete "bn_fast_mp_montgomery_reduce.c"
#
# delete "bn_fast_s_mp_mul_digs.c"
#
# delete "bn_fast_s_mp_mul_high_digs.c"
#
# delete "bn_fast_s_mp_sqr.c"
#
# delete "bn_mp_2expt.c"
#
# delete "bn_mp_abs.c"
#
# delete "bn_mp_add.c"
#
# delete "bn_mp_add_d.c"
#
# delete "bn_mp_addmod.c"
#
# delete "bn_mp_and.c"
#
# delete "bn_mp_clamp.c"
#
# delete "bn_mp_clear.c"
#
# delete "bn_mp_clear_multi.c"
#
# delete "bn_mp_cmp.c"
#
# delete "bn_mp_cmp_d.c"
#
# delete "bn_mp_cmp_mag.c"
#
# delete "bn_mp_cnt_lsb.c"
#
# delete "bn_mp_copy.c"
#
# delete "bn_mp_count_bits.c"
#
# delete "bn_mp_div.c"
#
# delete "bn_mp_div_2.c"
#
# delete "bn_mp_div_2d.c"
#
# delete "bn_mp_div_3.c"
#
# delete "bn_mp_div_d.c"
#
# delete "bn_mp_dr_is_modulus.c"
#
# delete "bn_mp_dr_reduce.c"
#
# delete "bn_mp_dr_setup.c"
#
# delete "bn_mp_exch.c"
#
# delete "bn_mp_expt_d.c"
#
# delete "bn_mp_exptmod.c"
#
# delete "bn_mp_exptmod_fast.c"
#
# delete "bn_mp_exteuclid.c"
#
# delete "bn_mp_fread.c"
#
# delete "bn_mp_fwrite.c"
#
# delete "bn_mp_gcd.c"
#
# delete "bn_mp_get_int.c"
#
# delete "bn_mp_grow.c"
#
# delete "bn_mp_init.c"
#
# delete "bn_mp_init_copy.c"
#
# delete "bn_mp_init_multi.c"
#
# delete "bn_mp_init_set.c"
#
# delete "bn_mp_init_set_int.c"
#
# delete "bn_mp_init_size.c"
#
# delete "bn_mp_invmod.c"
#
# delete "bn_mp_is_square.c"
#
# delete "bn_mp_jacobi.c"
#
# delete "bn_mp_karatsuba_mul.c"
#
# delete "bn_mp_karatsuba_sqr.c"
#
# delete "bn_mp_lcm.c"
#
# delete "bn_mp_lshd.c"
#
# delete "bn_mp_mod.c"
#
# delete "bn_mp_mod_2d.c"
#
# delete "bn_mp_mod_d.c"
#
# delete "bn_mp_montgomery_calc_normalization.c"
#
# delete "bn_mp_montgomery_reduce.c"
#
# delete "bn_mp_montgomery_setup.c"
#
# delete "bn_mp_mul.c"
#
# delete "bn_mp_mul_2.c"
#
# delete "bn_mp_mul_2d.c"
#
# delete "bn_mp_mul_d.c"
#
# delete "bn_mp_mulmod.c"
#
# delete "bn_mp_n_root.c"
#
# delete "bn_mp_neg.c"
#
# delete "bn_mp_or.c"
#
# delete "bn_mp_prime_fermat.c"
#
# delete "bn_mp_prime_is_divisible.c"
#
# delete "bn_mp_prime_is_prime.c"
#
# delete "bn_mp_prime_miller_rabin.c"
#
# delete "bn_mp_prime_next_prime.c"
#
# delete "bn_mp_prime_random_ex.c"
#
# delete "bn_mp_radix_size.c"
#
# delete "bn_mp_radix_smap.c"
#
# delete "bn_mp_rand.c"
#
# delete "bn_mp_read_radix.c"
#
# delete "bn_mp_read_signed_bin.c"
#
# delete "bn_mp_read_unsigned_bin.c"
#
# delete "bn_mp_reduce.c"
#
# delete "bn_mp_reduce_2k.c"
#
# delete "bn_mp_reduce_2k_setup.c"
#
# delete "bn_mp_reduce_is_2k.c"
#
# delete "bn_mp_reduce_setup.c"
#
# delete "bn_mp_rshd.c"
#
# delete "bn_mp_set.c"
#
# delete "bn_mp_set_int.c"
#
# delete "bn_mp_shrink.c"
#
# delete "bn_mp_signed_bin_size.c"
#
# delete "bn_mp_sqr.c"
#
# delete "bn_mp_sqrmod.c"
#
# delete "bn_mp_sqrt.c"
#
# delete "bn_mp_sub.c"
#
# delete "bn_mp_sub_d.c"
#
# delete "bn_mp_submod.c"
#
# delete "bn_mp_to_signed_bin.c"
#
# delete "bn_mp_to_unsigned_bin.c"
#
# delete "bn_mp_toom_mul.c"
#
# delete "bn_mp_toom_sqr.c"
#
# delete "bn_mp_toradix.c"
#
# delete "bn_mp_toradix_n.c"
#
# delete "bn_mp_unsigned_bin_size.c"
#
# delete "bn_mp_xor.c"
#
# delete "bn_mp_zero.c"
#
# delete "bn_prime_tab.c"
#
# delete "bn_reverse.c"
#
# delete "bn_s_mp_add.c"
#
# delete "bn_s_mp_exptmod.c"
#
# delete "bn_s_mp_mul_digs.c"
#
# delete "bn_s_mp_mul_high_digs.c"
#
# delete "bn_s_mp_sqr.c"
#
# delete "bn_s_mp_sub.c"
#
# delete "bncore.c"
#
# delete "booker.pl"
#
# delete "changes.txt"
#
# delete "demo"
#
# delete "demo/demo.c"
#
# delete "etc"
#
# delete "etc/2kprime.1"
#
# delete "etc/2kprime.c"
#
# delete "etc/drprime.c"
#
# delete "etc/drprimes.28"
#
# delete "etc/drprimes.txt"
#
# delete "etc/makefile"
#
# delete "etc/makefile.msvc"
#
# delete "etc/mersenne.c"
#
# delete "etc/mont.c"
#
# delete "etc/pprime.c"
#
# delete "etc/prime.1024"
#
# delete "etc/prime.512"
#
# delete "etc/timer.asm"
#
# delete "etc/tune.c"
#
# delete "gen.pl"
#
# delete "logs"
#
# delete "logs/README"
#
# delete "logs/add.log"
#
# delete "logs/addsub.png"
#
# delete "logs/expt.log"
#
# delete "logs/expt.png"
#
# delete "logs/expt_2k.log"
#
# delete "logs/expt_dr.log"
#
# delete "logs/graphs.dem"
#
# delete "logs/index.html"
#
# delete "logs/invmod.log"
#
# delete "logs/invmod.png"
#
# delete "logs/mult.log"
#
# delete "logs/mult.png"
#
# delete "logs/mult_kara.log"
#
# delete "logs/sqr.log"
#
# delete "logs/sqr_kara.log"
#
# delete "logs/sub.log"
#
# delete "makefile.bcc"
#
# delete "makefile.cygwin_dll"
#
# delete "makefile.msvc"
#
# delete "mtest"
#
# delete "mtest/logtab.h"
#
# delete "mtest/mpi-config.h"
#
# delete "mtest/mpi-types.h"
#
# delete "mtest/mpi.c"
#
# delete "mtest/mpi.h"
#
# delete "mtest/mtest.c"
#
# delete "pics"
#
# delete "pics/design_process.sxd"
#
# delete "pics/design_process.tif"
#
# delete "pics/expt_state.sxd"
#
# delete "pics/expt_state.tif"
#
# delete "pics/makefile"
#
# delete "pics/primality.tif"
#
# delete "pics/radix.sxd"
#
# delete "pics/sliding_window.sxd"
#
# delete "pre_gen"
#
# delete "pre_gen/mpi.c"
#
# delete "tommath.h"
#
# rename "Makefile.in"
# to "Makefile.in"
#
# rename "bn_prime_sizes_tab.c"
# to "bn_prime_sizes_tab.c"
#
# rename "demo/test.c"
# to "demo/test.c"
#
# rename "etc/tuning"
# to "etc/tuning"
#
# rename "logs/k7"
# to "logs/k7"
#
# rename "logs/p4"
# to "logs/p4"
#
# add_dir ""
#
# add_dir "demo"
#
# add_dir "etc"
#
# add_dir "logs"
#
# add_dir "mtest"
#
# add_dir "pics"
#
# add_dir "pre_gen"
#
# add_file "LICENSE"
# content [eec30656837132b5037dc0b5d021a6242888e0c0]
#
# add_file "bn.ilg"
# content [c43c9b999b935cc07f1e830cae687ab5da0f4347]
#
# add_file "bn.ind"
# content [eb15c6226d253088d1c63b4d47035e0c2a829fe2]
#
# add_file "bn.pdf"
# content [7f4a5f11d6752ff679a3d3f7fc153687d6d6abba]
#
# add_file "bn.tex"
# content [36834c9317131d36ca59ec5bcbdd2cfa7109fd4d]
#
# add_file "bn_error.c"
# content [a3f1d67e5952a5288a5e3b25ae1af448d0c55323]
#
# add_file "bn_fast_mp_invmod.c"
# content [08f10544b85d8060d7f7afe57fed583c889e3c9c]
#
# add_file "bn_fast_mp_montgomery_reduce.c"
# content [325a7d4683d34160114e1c5c4bdee24f78d53e34]
#
# add_file "bn_fast_s_mp_mul_digs.c"
# content [0672a145d0569d227d950c2555234afe2ab394d6]
#
# add_file "bn_fast_s_mp_mul_high_digs.c"
# content [0d7785aa91e231bdc765d67ff4074ecc29d556a2]
#
# add_file "bn_fast_s_mp_sqr.c"
# content [5765234e01ae11780dcaade97742404013b1da42]
#
# add_file "bn_mp_2expt.c"
# content [c0a974c10b34a7d5fa7e677ae3d1293a4e290138]
#
# add_file "bn_mp_abs.c"
# content [5ee072348880edcf0c2830885697a4233734580d]
#
# add_file "bn_mp_add.c"
# content [0cc7225dceeea5eb317eb215e4417ee0f23dd4ae]
#
# add_file "bn_mp_add_d.c"
# content [d6830e293314b416b519fede793966d4ecbfde57]
#
# add_file "bn_mp_addmod.c"
# content [b15c4348f1d5f51ccb10b50d1206032b4e0e0c4c]
#
# add_file "bn_mp_and.c"
# content [74d28d927a0271c274f0ff8195651d793c2307a1]
#
# add_file "bn_mp_clamp.c"
# content [7c26a55902cadb40f234df0f174b750102b05122]
#
# add_file "bn_mp_clear.c"
# content [246c4a2b16e20f7d0a43f1fc990c3a7f1ead9bfb]
#
# add_file "bn_mp_clear_multi.c"
# content [30f79c92867e21713828f674e9f125602d1edbfb]
#
# add_file "bn_mp_cmp.c"
# content [f48e439ef12bf49c92d8269958c09d2fb7e390ec]
#
# add_file "bn_mp_cmp_d.c"
# content [a3e0a785b17ac01577ef58cebd7df89baa4a0dc9]
#
# add_file "bn_mp_cmp_mag.c"
# content [a0698d9635cf3832841c8cc50639af3caa3d02c4]
#
# add_file "bn_mp_cnt_lsb.c"
# content [3d6446de20143460fada1208b56c20fdcb5a0f89]
#
# add_file "bn_mp_copy.c"
# content [a548ebca4bf8db0dca759222dfa976b97d551c89]
#
# add_file "bn_mp_count_bits.c"
# content [40adf953ce3210d33f9723e6f724e4700a807718]
#
# add_file "bn_mp_div.c"
# content [d993f550cc6ff9caa00c918bbfba773949fc65ca]
#
# add_file "bn_mp_div_2.c"
# content [e57a17c6b78085f9e5eef4df072218919a1888b6]
#
# add_file "bn_mp_div_2d.c"
# content [58636c779564cc44fdd8ccf9b75f01f047fb45e8]
#
# add_file "bn_mp_div_3.c"
# content [1d32a597de97e1ae46dc5b399c9dc9f6a2068475]
#
# add_file "bn_mp_div_d.c"
# content [d7f4600af77c0ec3d063e71f1ea76bb6da0f882f]
#
# add_file "bn_mp_dr_is_modulus.c"
# content [66009ac52e299147a27b8562fcaeef9ff806b8f0]
#
# add_file "bn_mp_dr_reduce.c"
# content [1736b0957a7bbeabb32ba902730f8dd031ab8a97]
#
# add_file "bn_mp_dr_setup.c"
# content [bd378fd2525c0d744ffeccebc38703c189f4a140]
#
# add_file "bn_mp_exch.c"
# content [acfc6896a26538be3832eba6ff1d4d17a0b2fae2]
#
# add_file "bn_mp_expt_d.c"
# content [b7adb8028ffe97d74f17a2c3e4ee85aa222ffe0f]
#
# add_file "bn_mp_exptmod.c"
# content [9a6256e60d747e910cc0f089a7cc51f3fae51f39]
#
# add_file "bn_mp_exptmod_fast.c"
# content [ec6cb8ea6c2dde8b87493bd481a51c9f8f946ede]
#
# add_file "bn_mp_exteuclid.c"
# content [3c13b9da30303b4bb43aa8a362d695f214c67a94]
#
# add_file "bn_mp_fread.c"
# content [4e80ea1d33795bf3aac96f439e182f56c46992d7]
#
# add_file "bn_mp_fwrite.c"
# content [3923546490c8d8ea313e3a75ed030bb5f637a14b]
#
# add_file "bn_mp_gcd.c"
# content [75332794a8c6790c417d7cdcc51c92be8d5bdc91]
#
# add_file "bn_mp_get_int.c"
# content [c161ac67fec2fda9279c294f69845fd44cabfa6d]
#
# add_file "bn_mp_grow.c"
# content [5d24eb35c5e6eeb36e58dc477f570f308e31b86c]
#
# add_file "bn_mp_init.c"
# content [dc9416c8eef1a2aec31f655efbf69f30366707ec]
#
# add_file "bn_mp_init_copy.c"
# content [85088498a8625eb86dd85679e1f39c7757561fa2]
#
# add_file "bn_mp_init_multi.c"
# content [b1635102a3be4451303a739b6f164f73d10ca561]
#
# add_file "bn_mp_init_set.c"
# content [53918f753d6f18c1e0fc608b8b67ada7fc25af3b]
#
# add_file "bn_mp_init_set_int.c"
# content [1772b10c31bf67011748664d7ed6541d9cad0ac6]
#
# add_file "bn_mp_init_size.c"
# content [f343728fd0b919c0551ee4fb955c7b7348084917]
#
# add_file "bn_mp_invmod.c"
# content [05e43c05923465c284cccf8707ee1a59ed911233]
#
# add_file "bn_mp_invmod_slow.c"
# content [c0acf30269eaf91f32b682b1b2d4150ee566f1a5]
#
# add_file "bn_mp_is_square.c"
# content [e905ec883178a2185809f2c902bac355e5816bad]
#
# add_file "bn_mp_jacobi.c"
# content [5f0894cc606a9979ce7008fc29d56c24cf53e9d6]
#
# add_file "bn_mp_karatsuba_mul.c"
# content [7bed1bacfcdcc8d1c5962ad4bcc6ef3c1f55bea9]
#
# add_file "bn_mp_karatsuba_sqr.c"
# content [32ce87d5ec2f68aea40bea22927f5a3f632c47b5]
#
# add_file "bn_mp_lcm.c"
# content [525b0299d60ea98ecbe42622d6f44d6e64ea32a7]
#
# add_file "bn_mp_lshd.c"
# content [0c04c3e6d8491249a27227826faeae84c966a94f]
#
# add_file "bn_mp_mod.c"
# content [c8090d320496ca60b99764b9335ba865c36cbfed]
#
# add_file "bn_mp_mod_2d.c"
# content [6860d01c3277c6edd0a7ca03dd22248983306b8e]
#
# add_file "bn_mp_mod_d.c"
# content [57cd7a01f1616d22ebced526e91159b1d242e0f9]
#
# add_file "bn_mp_montgomery_calc_normalization.c"
# content [fa4dcf6f68dfbab19a37ab68781ef3763b2e904d]
#
# add_file "bn_mp_montgomery_reduce.c"
# content [0b42eac9d7346004d688cbe3063e947ea1893f3f]
#
# add_file "bn_mp_montgomery_setup.c"
# content [0ddf17c06f6f5dc9fd7311284277b7a87a3cfc27]
#
# add_file "bn_mp_mul.c"
# content [cb9292558d6b699232dfe1d24d6b134b265aec30]
#
# add_file "bn_mp_mul_2.c"
# content [e7df32645d7a80e3badc2c696caf09d438932742]
#
# add_file "bn_mp_mul_2d.c"
# content [2d59d8ba0c487c42e75e24cd6808147fee6041ff]
#
# add_file "bn_mp_mul_d.c"
# content [fe7fe17b0dc44d3f3c6ab78998691e412280255e]
#
# add_file "bn_mp_mulmod.c"
# content [958738a570b35415e919d6c6e55adbce7ff59f55]
#
# add_file "bn_mp_n_root.c"
# content [339cf93663939605c6304419a020f33d4184b3dd]
#
# add_file "bn_mp_neg.c"
# content [afc6d203cc58d956e118f218c440bca91f94adce]
#
# add_file "bn_mp_or.c"
# content [01c1a84d9dcba644c61f69a3c00164f5f3346599]
#
# add_file "bn_mp_prime_fermat.c"
# content [7a08d1ab74369ae14b39a95258a6b955e0d7be22]
#
# add_file "bn_mp_prime_is_divisible.c"
# content [7536731238b627bc2d90c623d38fd2952bf0dba8]
#
# add_file "bn_mp_prime_is_prime.c"
# content [2c13d4e47af42472ed769696f340f3272cfae3c6]
#
# add_file "bn_mp_prime_miller_rabin.c"
# content [aef8e16b5107c8424ed96e143d41ac1f0c419a09]
#
# add_file "bn_mp_prime_next_prime.c"
# content [23111d40777e3c227c814ceb8726f187328b1db9]
#
# add_file "bn_mp_prime_rabin_miller_trials.c"
# content [93963170cbd3a50b33dc5f1dd76ccdfd935c239c]
#
# add_file "bn_mp_prime_random_ex.c"
# content [31f8a27d870e541417b0ca1a911480e1e060169f]
#
# add_file "bn_mp_radix_size.c"
# content [891ae52347addbb788c35c3c11e4912c6f6d7c35]
#
# add_file "bn_mp_radix_smap.c"
# content [9b2641767d4071696aa72126a339bd5450163b9e]
#
# add_file "bn_mp_rand.c"
# content [139744910e08eeab5d37af0510cea07399d318ac]
#
# add_file "bn_mp_read_radix.c"
# content [a29dabc5cc4dfe65e231782ea78675ca067302b7]
#
# add_file "bn_mp_read_signed_bin.c"
# content [5e3b2483fb9e04ac544331b7a46df0263e3a6cd0]
#
# add_file "bn_mp_read_unsigned_bin.c"
# content [15a5dc9e2dd8a6fe5a7b53c52c4ecb4babbdd1d5]
#
# add_file "bn_mp_reduce.c"
# content [6e809ceeb191e65004ef4d040f5f8b14a2253074]
#
# add_file "bn_mp_reduce_2k.c"
# content [9aa2bd43d0e23a59c71b2ee1461823cad97cbc1b]
#
# add_file "bn_mp_reduce_2k_setup.c"
# content [6989724dbee168ff723d4732c1f5bf29fb05dd33]
#
# add_file "bn_mp_reduce_is_2k.c"
# content [daa704193df12dfc34059c8a7eb5223470b9464f]
#
# add_file "bn_mp_reduce_setup.c"
# content [c0d6b73b259cda2c962f44710c16a7942f6adbfc]
#
# add_file "bn_mp_rshd.c"
# content [f3d16d9373f3707a2024da60481cfcb91484a34d]
#
# add_file "bn_mp_set.c"
# content [a9535a1aa1f54c47f3bb503c74d03b7202f682a0]
#
# add_file "bn_mp_set_int.c"
# content [f969f32a9ce516009747993ccd66e03e17aff3f2]
#
# add_file "bn_mp_shrink.c"
# content [1349448a8f2a625e7817074996951d5a2d1ec158]
#
# add_file "bn_mp_signed_bin_size.c"
# content [9ad18efcb95355ea048e428c9a1808cf3e44de82]
#
# add_file "bn_mp_sqr.c"
# content [093d797ab504fa4cfb271b47a8c10075b2441b9f]
#
# add_file "bn_mp_sqrmod.c"
# content [2d316f2f768b25e981f2e62c0bb245cb4dfc8ec8]
#
# add_file "bn_mp_sqrt.c"
# content [9d312eb9205cadcc089d54d19d712238dbf6d03c]
#
# add_file "bn_mp_sub.c"
# content [c5092e05763947b6dc2e9fa0858dc3750bac02fe]
#
# add_file "bn_mp_sub_d.c"
# content [e80435db75b1dc7f60a2b3f6d27204113017d849]
#
# add_file "bn_mp_submod.c"
# content [72847e4cc7457fd16feda88a9a22461c9cc6467a]
#
# add_file "bn_mp_to_signed_bin.c"
# content [7c004817480da3880393125065bb1c86994e49aa]
#
# add_file "bn_mp_to_unsigned_bin.c"
# content [b63653084377cf62c63b7ad3f5fbe8b3bc1daa7e]
#
# add_file "bn_mp_toom_mul.c"
# content [ef10988525e274d5e954a11fc04edb96bc4590a3]
#
# add_file "bn_mp_toom_sqr.c"
# content [496802f1dbcf4a358fb38b7458609f209b5435cd]
#
# add_file "bn_mp_toradix.c"
# content [78a3ed650fec464f1229d14ea550b3703d3ef8d1]
#
# add_file "bn_mp_toradix_n.c"
# content [1a2704322409b2e9f54e9f7e41ef69be2ae5e4c9]
#
# add_file "bn_mp_unsigned_bin_size.c"
# content [30a163d04f2e09c8df11ab2f8e9f781adb500ec4]
#
# add_file "bn_mp_xor.c"
# content [fe21cdda0a62908ce461de7a806cfdd743c4db1b]
#
# add_file "bn_mp_zero.c"
# content [130f819e9e81d1206739e40b52df5b86a82d584c]
#
# add_file "bn_prime_tab.c"
# content [55558f0b3a503f1604933fb2d05e900af8ea9c40]
#
# add_file "bn_reverse.c"
# content [dd999dcbec79713c226d741f97af41ec6ed7e58f]
#
# add_file "bn_s_mp_add.c"
# content [e16a196df2c5a2a1ba9c51d184105791f7151e6c]
#
# add_file "bn_s_mp_exptmod.c"
# content [9af99058a9d79e6032e4c8302c568dc89b9a8d4d]
#
# add_file "bn_s_mp_mul_digs.c"
# content [132dd48c3ff5effbb5ea45cdcd744ee77d7253da]
#
# add_file "bn_s_mp_mul_high_digs.c"
# content [7fedd32cbf39b73ee19e2c4f84708d46e6698375]
#
# add_file "bn_s_mp_sqr.c"
# content [73569fd80f5b6535e45cd018a71661f52e4eb9b1]
#
# add_file "bn_s_mp_sub.c"
# content [46e30a7f53648000600b31472e9f6f8463145196]
#
# add_file "bncore.c"
# content [9168a11431458dface0fe16fb1cb4e5c483ff314]
#
# add_file "booker.pl"
# content [f5935051a27a7a963ac1730d44d2de8f682e12e6]
#
# add_file "callgraph.txt"
# content [1c575d5b40fd8adc98fcbae3be9b0b992d9fd7ac]
#
# add_file "changes.txt"
# content [07d05c9531404b01bcd359e42821c4d039e3f851]
#
# add_file "demo/demo.c"
# content [58eeef30dee744087fb774f617ff7033b18d77e0]
#
# add_file "demo/timing.c"
# content [98827dad0973588bcd4b325718442b1ab0efb719]
#
# add_file "dep.pl"
# content [b154a4d839947d3a5b4218fb3b76284469091256]
#
# add_file "etc/2kprime.1"
# content [bca066352f0a727770c9e1ba95b74b0fd1e49065]
#
# add_file "etc/2kprime.c"
# content [8916b4a19cfcec43ec1788ca54b59d213e0bbe30]
#
# add_file "etc/drprime.c"
# content [721a3e4d253bbe004dd67da6e9cd28dba2e5fe8b]
#
# add_file "etc/drprimes.28"
# content [d3a9cb7e891a1c26d8e9b2b7e3f73e36e0b7941b]
#
# add_file "etc/drprimes.txt"
# content [a1729704304c95123744b923bf4aad877575b27f]
#
# add_file "etc/makefile"
# content [a7f87a81798ae6cf8320687175dcdeabd862a4eb]
#
# add_file "etc/makefile.icc"
# content [bd3824382f4b2ca2df34f552e13393a2f27739c7]
#
# add_file "etc/makefile.msvc"
# content [fe51f9ad1c7cb9f2d23bca7a140d46fe480ebf3c]
#
# add_file "etc/mersenne.c"
# content [4324b77f9ff20f45dba21ada611c786665030b3d]
#
# add_file "etc/mont.c"
# content [3618f1f988eddb11db6f83d114a13e74c1078ba4]
#
# add_file "etc/pprime.c"
# content [216818739f847e9b2e1dbb302d206d6c8cffccec]
#
# add_file "etc/prime.1024"
# content [0867a29f21856790289596532af7e528b64955a2]
#
# add_file "etc/prime.512"
# content [dc46a62c261fd1753420f62066840a14c856e57e]
#
# add_file "etc/timer.asm"
# content [c38980bb26532b829d6678ae2ebbecb24ebb9537]
#
# add_file "etc/tune.c"
# content [935b41e6df657dd2ceede4e1311e6848a432893a]
#
# add_file "gen.pl"
# content [67c4b0ca0cfd7c389b6a1ec96950b5892113d140]
#
# add_file "logs/README"
# content [a35d80785b6881f18a35bf069cbcd820b71e41e7]
#
# add_file "logs/add.log"
# content [a1a423131bd0068100058228aad36c31c53ab2c7]
#
# add_file "logs/addsub.png"
# content [7620d52ec0019c9a804f3943695c215688bec398]
#
# add_file "logs/expt.log"
# content [da39a3ee5e6b4b0d3255bfef95601890afd80709]
#
# add_file "logs/expt.png"
# content [4d2052c39da2fa14754ece810bf2bba2fbc380e1]
#
# add_file "logs/expt_2k.log"
# content [da39a3ee5e6b4b0d3255bfef95601890afd80709]
#
# add_file "logs/expt_dr.log"
# content [da39a3ee5e6b4b0d3255bfef95601890afd80709]
#
# add_file "logs/graphs.dem"
# content [467f6c3dccef1ea64d84f2bac5f31e23ff334867]
#
# add_file "logs/index.html"
# content [9dfaca0a0c5f26c88275c7e29a9b8fb7276954ea]
#
# add_file "logs/invmod.log"
# content [da39a3ee5e6b4b0d3255bfef95601890afd80709]
#
# add_file "logs/invmod.png"
# content [22a1361aa5b92372056e900c698a49118e1a941c]
#
# add_file "logs/mult.log"
# content [b9d3dd04155318a5a87ee0b8d76c9174ccddad17]
#
# add_file "logs/mult.png"
# content [1329681fa28d186842464da64820f97d1ce5f2a4]
#
# add_file "logs/mult_kara.log"
# content [55b8d281c45ca7689e48d924801bea8ee1cf371e]
#
# add_file "logs/sqr.log"
# content [27daa1a1360faa0c921fb069471a14f6a64e256a]
#
# add_file "logs/sqr.old"
# content [1d1b958f6486d980f788258dc3c2f1078589f70b]
#
# add_file "logs/sqr_kara.log"
# content [a5458d81446e82a302429ae75e0135576c82c346]
#
# add_file "logs/sub.log"
# content [730a1558fa8a5f8370ed0e296ad0fc2a6d1ae264]
#
# add_file "makefile"
# content [b959d8ba1f022caeb787e2f9a397e23049c43af9]
#
# add_file "makefile.bcc"
# content [6ff4455fd30f15d67594b85c18ed6fbdfa2326d5]
#
# add_file "makefile.cygwin_dll"
# content [2ac775af392c3690497d9fae518083585045fc97]
#
# add_file "makefile.icc"
# content [4155389d03c96022b3469acdca2ab3452475a0d3]
#
# add_file "makefile.msvc"
# content [d2c181e3340ba3cc1adb26c65c7e18b9e0d39ff1]
#
# add_file "makefile.shared"
# content [c948f0e25a808a63df3e661392ae815aa1515734]
#
# add_file "mtest/logtab.h"
# content [129e0480989c9d1e36f287c5a1eb97cea42b2b52]
#
# add_file "mtest/mpi-config.h"
# content [c4f05a0ca82cde231f973614d08bde9ee0a707ae]
#
# add_file "mtest/mpi-types.h"
# content [f93df694e834dc18f7fd0103c87c0cc316366d04]
#
# add_file "mtest/mpi.c"
# content [8c0d35e1c5f6cbfe99f6147b85dcb7f40b8603b7]
#
# add_file "mtest/mpi.h"
# content [4256d0c148b57666041afe30c664ba571b62852c]
#
# add_file "mtest/mtest.c"
# content [c149902fa871e967295b7b33b01914088ee054ab]
#
# add_file "pics/design_process.sxd"
# content [64579069e408f7e6ceda7951bde0ef1ef42960ca]
#
# add_file "pics/design_process.tif"
# content [cbf992df42aafb6db320258d9117a96eba41a57a]
#
# add_file "pics/expt_state.sxd"
# content [643b0367363109d2974f5ea5041234b4ffae3db6]
#
# add_file "pics/expt_state.tif"
# content [8a83f4dec23a49c70d159facffb5dfcc46204618]
#
# add_file "pics/makefile"
# content [42eb423e60521ddf59e8243e0b9d27bdafed4ffa]
#
# add_file "pics/primality.tif"
# content [4f9013fe6ec0a684cfd28bcb534bd860d96207b4]
#
# add_file "pics/radix.sxd"
# content [0a7851b1c898430cccffe6f4206e9a481b2e419e]
#
# add_file "pics/sliding_window.sxd"
# content [ce2b2b35e0e686c6aa75436ab7f1306ac2e15b93]
#
# add_file "pics/sliding_window.tif"
# content [9f70a7fa43bfac245f8cc2cedc83ea478944a809]
#
# add_file "poster.out"
# content [da39a3ee5e6b4b0d3255bfef95601890afd80709]
#
# add_file "poster.pdf"
# content [57892edde6aa6ec6faa875a27df39e3bd054fcf6]
#
# add_file "poster.tex"
# content [1fe3768a9d3d68873cd1b468f34e6b0474ac29dc]
#
# add_file "pre_gen/mpi.c"
# content [b8de79c7fe9009ecf50a8a1d5267e9ce888c6b50]
#
# add_file "pretty.build"
# content [ef98abab69cf137623e74611cfa9cb71901be3ce]
#
# add_file "tommath.h"
# content [d7e663fdcde877eb8c7d2656af2ffe5129a42d37]
#
# add_file "tommath.out"
# content [8b1ec2f5e8f380908d72001636ea44581d64bf76]
#
# add_file "tommath.pdf"
# content [0e06f40b55ed705fe3a0e1e21812f9527e4f8237]
#
# add_file "tommath.src"
# content [665b9cf81a130c911f7c8baee277aa7a565d652e]
#
# add_file "tommath.tex"
# content [af59d0cd6ddc7dfed2554343a319f578eccdbd11]
#
# add_file "tommath_class.h"
# content [d2d0596bd40615d49d7d9bdf8036e01e3d2e21a4]
#
# add_file "tommath_superclass.h"
# content [47527ad5ee97a9524e14b307da9796293b1f586f]
#
============================================================
--- LICENSE eec30656837132b5037dc0b5d021a6242888e0c0
+++ LICENSE eec30656837132b5037dc0b5d021a6242888e0c0
@@ -0,0 +1,4 @@
+LibTomMath is hereby released into the Public Domain.
+
+-- Tom St Denis
+
============================================================
--- bn.ilg c43c9b999b935cc07f1e830cae687ab5da0f4347
+++ bn.ilg c43c9b999b935cc07f1e830cae687ab5da0f4347
@@ -0,0 +1,6 @@
+This is makeindex, version 2.14 [02-Oct-2002] (kpathsea + Thai support).
+Scanning input file bn.idx....done (79 entries accepted, 0 rejected).
+Sorting entries....done (511 comparisons).
+Generating output file bn.ind....done (82 lines written, 0 warnings).
+Output written in bn.ind.
+Transcript written in bn.ilg.
============================================================
--- bn.ind eb15c6226d253088d1c63b4d47035e0c2a829fe2
+++ bn.ind eb15c6226d253088d1c63b4d47035e0c2a829fe2
@@ -0,0 +1,82 @@
+\begin{theindex}
+
+ \item mp\_add, \hyperpage{29}
+ \item mp\_add\_d, \hyperpage{52}
+ \item mp\_and, \hyperpage{29}
+ \item mp\_clear, \hyperpage{11}
+ \item mp\_clear\_multi, \hyperpage{12}
+ \item mp\_cmp, \hyperpage{24}
+ \item mp\_cmp\_d, \hyperpage{25}
+ \item mp\_cmp\_mag, \hyperpage{23}
+ \item mp\_div, \hyperpage{30}
+ \item mp\_div\_2, \hyperpage{26}
+ \item mp\_div\_2d, \hyperpage{28}
+ \item mp\_div\_d, \hyperpage{52}
+ \item mp\_dr\_reduce, \hyperpage{40}
+ \item mp\_dr\_setup, \hyperpage{40}
+ \item MP\_EQ, \hyperpage{22}
+ \item mp\_error\_to\_string, \hyperpage{10}
+ \item mp\_expt\_d, \hyperpage{43}
+ \item mp\_exptmod, \hyperpage{43}
+ \item mp\_exteuclid, \hyperpage{51}
+ \item mp\_gcd, \hyperpage{51}
+ \item mp\_get\_int, \hyperpage{20}
+ \item mp\_grow, \hyperpage{16}
+ \item MP\_GT, \hyperpage{22}
+ \item mp\_init, \hyperpage{11}
+ \item mp\_init\_copy, \hyperpage{13}
+ \item mp\_init\_multi, \hyperpage{12}
+ \item mp\_init\_set, \hyperpage{21}
+ \item mp\_init\_set\_int, \hyperpage{21}
+ \item mp\_init\_size, \hyperpage{14}
+ \item mp\_int, \hyperpage{10}
+ \item mp\_invmod, \hyperpage{52}
+ \item mp\_jacobi, \hyperpage{52}
+ \item mp\_lcm, \hyperpage{51}
+ \item mp\_lshd, \hyperpage{28}
+ \item MP\_LT, \hyperpage{22}
+ \item MP\_MEM, \hyperpage{9}
+ \item mp\_mod, \hyperpage{35}
+ \item mp\_mod\_d, \hyperpage{52}
+ \item mp\_montgomery\_calc\_normalization, \hyperpage{38}
+ \item mp\_montgomery\_reduce, \hyperpage{37}
+ \item mp\_montgomery\_setup, \hyperpage{37}
+ \item mp\_mul, \hyperpage{31}
+ \item mp\_mul\_2, \hyperpage{26}
+ \item mp\_mul\_2d, \hyperpage{28}
+ \item mp\_mul\_d, \hyperpage{52}
+ \item mp\_n\_root, \hyperpage{44}
+ \item mp\_neg, \hyperpage{29}
+ \item MP\_NO, \hyperpage{9}
+ \item MP\_OKAY, \hyperpage{9}
+ \item mp\_or, \hyperpage{29}
+ \item mp\_prime\_fermat, \hyperpage{45}
+ \item mp\_prime\_is\_divisible, \hyperpage{45}
+ \item mp\_prime\_is\_prime, \hyperpage{46}
+ \item mp\_prime\_miller\_rabin, \hyperpage{45}
+ \item mp\_prime\_next\_prime, \hyperpage{46}
+ \item mp\_prime\_rabin\_miller\_trials, \hyperpage{46}
+ \item mp\_prime\_random, \hyperpage{47}
+ \item mp\_prime\_random\_ex, \hyperpage{47}
+ \item mp\_radix\_size, \hyperpage{49}
+ \item mp\_read\_radix, \hyperpage{49}
+ \item mp\_read\_unsigned\_bin, \hyperpage{50}
+ \item mp\_reduce, \hyperpage{36}
+ \item mp\_reduce\_2k, \hyperpage{41}
+ \item mp\_reduce\_2k\_setup, \hyperpage{41}
+ \item mp\_reduce\_setup, \hyperpage{36}
+ \item mp\_rshd, \hyperpage{28}
+ \item mp\_set, \hyperpage{19}
+ \item mp\_set\_int, \hyperpage{20}
+ \item mp\_shrink, \hyperpage{15}
+ \item mp\_sqr, \hyperpage{33}
+ \item mp\_sub, \hyperpage{29}
+ \item mp\_sub\_d, \hyperpage{52}
+ \item mp\_to\_unsigned\_bin, \hyperpage{50}
+ \item mp\_toradix, \hyperpage{49}
+ \item mp\_unsigned\_bin\_size, \hyperpage{50}
+ \item MP\_VAL, \hyperpage{9}
+ \item mp\_xor, \hyperpage{29}
+ \item MP\_YES, \hyperpage{9}
+
+\end{theindex}
============================================================
# bn.pdf is binary
============================================================
--- bn.tex 36834c9317131d36ca59ec5bcbdd2cfa7109fd4d
+++ bn.tex 36834c9317131d36ca59ec5bcbdd2cfa7109fd4d
@@ -0,0 +1,1830 @@
+\documentclass[b5paper]{book}
+\usepackage{hyperref}
+\usepackage{makeidx}
+\usepackage{amssymb}
+\usepackage{color}
+\usepackage{alltt}
+\usepackage{graphicx}
+\usepackage{layout}
+\def\union{\cup}
+\def\intersect{\cap}
+\def\getsrandom{\stackrel{\rm R}{\gets}}
+\def\cross{\times}
+\def\cat{\hspace{0.5em} \| \hspace{0.5em}}
+\def\catn{$\|$}
+\def\divides{\hspace{0.3em} | \hspace{0.3em}}
+\def\nequiv{\not\equiv}
+\def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
+\def\lcm{{\rm lcm}}
+\def\gcd{{\rm gcd}}
+\def\log{{\rm log}}
+\def\ord{{\rm ord}}
+\def\abs{{\mathit abs}}
+\def\rep{{\mathit rep}}
+\def\mod{{\mathit\ mod\ }}
+\renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
+\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
+\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
+\def\Or{{\rm\ or\ }}
+\def\And{{\rm\ and\ }}
+\def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
+\def\implies{\Rightarrow}
+\def\undefined{{\rm ``undefined"}}
+\def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
+\let\oldphi\phi
+\def\phi{\varphi}
+\def\Pr{{\rm Pr}}
+\newcommand{\str}[1]{{\mathbf{#1}}}
+\def\F{{\mathbb F}}
+\def\N{{\mathbb N}}
+\def\Z{{\mathbb Z}}
+\def\R{{\mathbb R}}
+\def\C{{\mathbb C}}
+\def\Q{{\mathbb Q}}
+\definecolor{DGray}{gray}{0.5}
+\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
+\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
+\def\gap{\vspace{0.5ex}}
+\makeindex
+\begin{document}
+\frontmatter
+\pagestyle{empty}
+\title{LibTomMath User Manual \\ v0.32}
+\author{Tom St Denis \\ tomstdenis@iahu.ca}
+\maketitle
+This text, the library and the accompanying textbook are all hereby placed in the public domain. This book has been
+formatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package.
+
+\vspace{10cm}
+
+\begin{flushright}Open Source. Open Academia. Open Minds.
+
+\mbox{ }
+
+Tom St Denis,
+
+Ontario, Canada
+\end{flushright}
+
+\tableofcontents
+\listoffigures
+\mainmatter
+\pagestyle{headings}
+\chapter{Introduction}
+\section{What is LibTomMath?}
+LibTomMath is a library of source code which provides a series of efficient and carefully written functions for manipulating
+large integer numbers. It was written in portable ISO C source code so that it will build on any platform with a conforming
+C compiler.
+
+In a nutshell the library was written from scratch with verbose comments to help instruct computer science students how
+to implement ``bignum'' math. However, the resulting code has proven to be very useful. It has been used by numerous
+universities, commercial and open source software developers. It has been used on a variety of platforms ranging from
+Linux and Windows based x86 to ARM based Gameboys and PPC based MacOS machines.
+
+\section{License}
+As of the v0.25 the library source code has been placed in the public domain with every new release. As of the v0.28
+release the textbook ``Implementing Multiple Precision Arithmetic'' has been placed in the public domain with every new
+release as well. This textbook is meant to compliment the project by providing a more solid walkthrough of the development
+algorithms used in the library.
+
+Since both\footnote{Note that the MPI files under mtest/ are copyrighted by Michael Fromberger. They are not required to use LibTomMath.} are in the
+public domain everyone is entitled to do with them as they see fit.
+
+\section{Building LibTomMath}
+
+LibTomMath is meant to be very ``GCC friendly'' as it comes with a makefile well suited for GCC. However, the library will
+also build in MSVC, Borland C out of the box. For any other ISO C compiler a makefile will have to be made by the end
+developer.
+
+\subsection{Static Libraries}
+To build as a static library for GCC issue the following
+\begin{alltt}
+make
+\end{alltt}
+
+command. This will build the library and archive the object files in ``libtommath.a''. Now you link against
+that and include ``tommath.h'' within your programs. Alternatively to build with MSVC issue the following
+\begin{alltt}
+nmake -f makefile.msvc
+\end{alltt}
+
+This will build the library and archive the object files in ``tommath.lib''. This has been tested with MSVC
+version 6.00 with service pack 5.
+
+\subsection{Shared Libraries}
+To build as a shared library for GCC issue the following
+\begin{alltt}
+make -f makefile.shared
+\end{alltt}
+This requires the ``libtool'' package (common on most Linux/BSD systems). It will build LibTomMath as both shared
+and static then install (by default) into /usr/lib as well as install the header files in /usr/include. The shared
+library (resource) will be called ``libtommath.la'' while the static library called ``libtommath.a''. Generally
+you use libtool to link your application against the shared object.
+
+There is limited support for making a ``DLL'' in windows via the ``makefile.cygwin\_dll'' makefile. It requires
+Cygwin to work with since it requires the auto-export/import functionality. The resulting DLL and import library
+``libtommath.dll.a'' can be used to link LibTomMath dynamically to any Windows program using Cygwin.
+
+\subsection{Testing}
+To build the library and the test harness type
+
+\begin{alltt}
+make test
+\end{alltt}
+
+This will build the library, ``test'' and ``mtest/mtest''. The ``test'' program will accept test vectors and verify the
+results. ``mtest/mtest'' will generate test vectors using the MPI library by Michael Fromberger\footnote{A copy of MPI
+is included in the package}. Simply pipe mtest into test using
+
+\begin{alltt}
+mtest/mtest | test
+\end{alltt}
+
+If you do not have a ``/dev/urandom'' style RNG source you will have to write your own PRNG and simply pipe that into
+mtest. For example, if your PRNG program is called ``myprng'' simply invoke
+
+\begin{alltt}
+myprng | mtest/mtest | test
+\end{alltt}
+
+This will output a row of numbers that are increasing. Each column is a different test (such as addition, multiplication, etc)
+that is being performed. The numbers represent how many times the test was invoked. If an error is detected the program
+will exit with a dump of the relevent numbers it was working with.
+
+\section{Build Configuration}
+LibTomMath can configured at build time in three phases we shall call ``depends'', ``tweaks'' and ``trims''.
+Each phase changes how the library is built and they are applied one after another respectively.
+
+To make the system more powerful you can tweak the build process. Classes are defined in the file
+``tommath\_superclass.h''. By default, the symbol ``LTM\_ALL'' shall be defined which simply
+instructs the system to build all of the functions. This is how LibTomMath used to be packaged. This will give you
+access to every function LibTomMath offers.
+
+However, there are cases where such a build is not optional. For instance, you want to perform RSA operations. You
+don't need the vast majority of the library to perform these operations. Aside from LTM\_ALL there is
+another pre--defined class ``SC\_RSA\_1'' which works in conjunction with the RSA from LibTomCrypt. Additional
+classes can be defined base on the need of the user.
+
+\subsection{Build Depends}
+In the file tommath\_class.h you will see a large list of C ``defines'' followed by a series of ``ifdefs''
+which further define symbols. All of the symbols (technically they're macros $\ldots$) represent a given C source
+file. For instance, BN\_MP\_ADD\_C represents the file ``bn\_mp\_add.c''. When a define has been enabled the
+function in the respective file will be compiled and linked into the library. Accordingly when the define
+is absent the file will not be compiled and not contribute any size to the library.
+
+You will also note that the header tommath\_class.h is actually recursively included (it includes itself twice).
+This is to help resolve as many dependencies as possible. In the last pass the symbol LTM\_LAST will be defined.
+This is useful for ``trims''.
+
+\subsection{Build Tweaks}
+A tweak is an algorithm ``alternative''. For example, to provide tradeoffs (usually between size and space).
+They can be enabled at any pass of the configuration phase.
+
+\begin{small}
+\begin{center}
+\begin{tabular}{|l|l|}
+\hline \textbf{Define} & \textbf{Purpose} \\
+\hline BN\_MP\_DIV\_SMALL & Enables a slower, smaller and equally \\
+ & functional mp\_div() function \\
+\hline
+\end{tabular}
+\end{center}
+\end{small}
+
+\subsection{Build Trims}
+A trim is a manner of removing functionality from a function that is not required. For instance, to perform
+RSA cryptography you only require exponentiation with odd moduli so even moduli support can be safely removed.
+Build trims are meant to be defined on the last pass of the configuration which means they are to be defined
+only if LTM\_LAST has been defined.
+
+\subsubsection{Moduli Related}
+\begin{small}
+\begin{center}
+\begin{tabular}{|l|l|}
+\hline \textbf{Restriction} & \textbf{Undefine} \\
+\hline Exponentiation with odd moduli only & BN\_S\_MP\_EXPTMOD\_C \\
+ & BN\_MP\_REDUCE\_C \\
+ & BN\_MP\_REDUCE\_SETUP\_C \\
+ & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\
+ & BN\_FAST\_S\_MP\_MUL\_HIGH\_DIGS\_C \\
+\hline Exponentiation with random odd moduli & (The above plus the following) \\
+ & BN\_MP\_REDUCE\_2K\_C \\
+ & BN\_MP\_REDUCE\_2K\_SETUP\_C \\
+ & BN\_MP\_REDUCE\_IS\_2K\_C \\
+ & BN\_MP\_DR\_IS\_MODULUS\_C \\
+ & BN\_MP\_DR\_REDUCE\_C \\
+ & BN\_MP\_DR\_SETUP\_C \\
+\hline Modular inverse odd moduli only & BN\_MP\_INVMOD\_SLOW\_C \\
+\hline Modular inverse (both, smaller/slower) & BN\_FAST\_MP\_INVMOD\_C \\
+\hline
+\end{tabular}
+\end{center}
+\end{small}
+
+\subsubsection{Operand Size Related}
+\begin{small}
+\begin{center}
+\begin{tabular}{|l|l|}
+\hline \textbf{Restriction} & \textbf{Undefine} \\
+\hline Moduli $\le 2560$ bits & BN\_MP\_MONTGOMERY\_REDUCE\_C \\
+ & BN\_S\_MP\_MUL\_DIGS\_C \\
+ & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\
+ & BN\_S\_MP\_SQR\_C \\
+\hline Polynomial Schmolynomial & BN\_MP\_KARATSUBA\_MUL\_C \\
+ & BN\_MP\_KARATSUBA\_SQR\_C \\
+ & BN\_MP\_TOOM\_MUL\_C \\
+ & BN\_MP\_TOOM\_SQR\_C \\
+
+\hline
+\end{tabular}
+\end{center}
+\end{small}
+
+
+\section{Purpose of LibTomMath}
+Unlike GNU MP (GMP) Library, LIP, OpenSSL or various other commercial kits (Miracl), LibTomMath was not written with
+bleeding edge performance in mind. First and foremost LibTomMath was written to be entirely open. Not only is the
+source code public domain (unlike various other GPL/etc licensed code), not only is the code freely downloadable but the
+source code is also accessible for computer science students attempting to learn ``BigNum'' or multiple precision
+arithmetic techniques.
+
+LibTomMath was written to be an instructive collection of source code. This is why there are many comments, only one
+function per source file and often I use a ``middle-road'' approach where I don't cut corners for an extra 2\% speed
+increase.
+
+Source code alone cannot really teach how the algorithms work which is why I also wrote a textbook that accompanies
+the library (beat that!).
+
+So you may be thinking ``should I use LibTomMath?'' and the answer is a definite maybe. Let me tabulate what I think
+are the pros and cons of LibTomMath by comparing it to the math routines from GnuPG\footnote{GnuPG v1.2.3 versus LibTomMath v0.28}.
+
+\newpage\begin{figure}[here]
+\begin{small}
+\begin{center}
+\begin{tabular}{|l|c|c|l|}
+\hline \textbf{Criteria} & \textbf{Pro} & \textbf{Con} & \textbf{Notes} \\
+\hline Few lines of code per file & X & & GnuPG $ = 300.9$, LibTomMath $ = 76.04$ \\
+\hline Commented function prototypes & X && GnuPG function names are cryptic. \\
+\hline Speed && X & LibTomMath is slower. \\
+\hline Totally free & X & & GPL has unfavourable restrictions.\\
+\hline Large function base & X & & GnuPG is barebones. \\
+\hline Four modular reduction algorithms & X & & Faster modular exponentiation. \\
+\hline Portable & X & & GnuPG requires configuration to build. \\
+\hline
+\end{tabular}
+\end{center}
+\end{small}
+\caption{LibTomMath Valuation}
+\end{figure}
+
+It may seem odd to compare LibTomMath to GnuPG since the math in GnuPG is only a small portion of the entire application.
+However, LibTomMath was written with cryptography in mind. It provides essentially all of the functions a cryptosystem
+would require when working with large integers.
+
+So it may feel tempting to just rip the math code out of GnuPG (or GnuMP where it was taken from originally) in your
+own application but I think there are reasons not to. While LibTomMath is slower than libraries such as GnuMP it is
+not normally significantly slower. On x86 machines the difference is normally a factor of two when performing modular
+exponentiations.
+
+Essentially the only time you wouldn't use LibTomMath is when blazing speed is the primary concern.
+
+\chapter{Getting Started with LibTomMath}
+\section{Building Programs}
+In order to use LibTomMath you must include ``tommath.h'' and link against the appropriate library file (typically
+libtommath.a). There is no library initialization required and the entire library is thread safe.
+
+\section{Return Codes}
+There are three possible return codes a function may return.
+
+\index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM}
+\begin{figure}[here!]
+\begin{center}
+\begin{small}
+\begin{tabular}{|l|l|}
+\hline \textbf{Code} & \textbf{Meaning} \\
+\hline MP\_OKAY & The function succeeded. \\
+\hline MP\_VAL & The function input was invalid. \\
+\hline MP\_MEM & Heap memory exhausted. \\
+\hline &\\
+\hline MP\_YES & Response is yes. \\
+\hline MP\_NO & Response is no. \\
+\hline
+\end{tabular}
+\end{small}
+\end{center}
+\caption{Return Codes}
+\end{figure}
+
+The last two codes listed are not actually ``return'ed'' by a function. They are placed in an integer (the caller must
+provide the address of an integer it can store to) which the caller can access. To convert one of the three return codes
+to a string use the following function.
+
+\index{mp\_error\_to\_string}
+\begin{alltt}
+char *mp_error_to_string(int code);
+\end{alltt}
+
+This will return a pointer to a string which describes the given error code. It will not work for the return codes
+MP\_YES and MP\_NO.
+
+\section{Data Types}
+The basic ``multiple precision integer'' type is known as the ``mp\_int'' within LibTomMath. This data type is used to
+organize all of the data required to manipulate the integer it represents. Within LibTomMath it has been prototyped
+as the following.
+
+\index{mp\_int}
+\begin{alltt}
+typedef struct \{
+ int used, alloc, sign;
+ mp_digit *dp;
+\} mp_int;
+\end{alltt}
+
+Where ``mp\_digit'' is a data type that represents individual digits of the integer. By default, an mp\_digit is the
+ISO C ``unsigned long'' data type and each digit is $28-$bits long. The mp\_digit type can be configured to suit other
+platforms by defining the appropriate macros.
+
+All LTM functions that use the mp\_int type will expect a pointer to mp\_int structure. You must allocate memory to
+hold the structure itself by yourself (whether off stack or heap it doesn't matter). The very first thing that must be
+done to use an mp\_int is that it must be initialized.
+
+\section{Function Organization}
+
+The arithmetic functions of the library are all organized to have the same style prototype. That is source operands
+are passed on the left and the destination is on the right. For instance,
+
+\begin{alltt}
+mp_add(&a, &b, &c); /* c = a + b */
+mp_mul(&a, &a, &c); /* c = a * a */
+mp_div(&a, &b, &c, &d); /* c = [a/b], d = a mod b */
+\end{alltt}
+
+Another feature of the way the functions have been implemented is that source operands can be destination operands as well.
+For instance,
+
+\begin{alltt}
+mp_add(&a, &b, &b); /* b = a + b */
+mp_div(&a, &b, &a, &c); /* a = [a/b], c = a mod b */
+\end{alltt}
+
+This allows operands to be re-used which can make programming simpler.
+
+\section{Initialization}
+\subsection{Single Initialization}
+A single mp\_int can be initialized with the ``mp\_init'' function.
+
+\index{mp\_init}
+\begin{alltt}
+int mp_init (mp_int * a);
+\end{alltt}
+
+This function expects a pointer to an mp\_int structure and will initialize the members of the structure so the mp\_int
+represents the default integer which is zero. If the functions returns MP\_OKAY then the mp\_int is ready to be used
+by the other LibTomMath functions.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the number */
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\subsection{Single Free}
+When you are finished with an mp\_int it is ideal to return the heap it used back to the system. The following function
+provides this functionality.
+
+\index{mp\_clear}
+\begin{alltt}
+void mp_clear (mp_int * a);
+\end{alltt}
+
+The function expects a pointer to a previously initialized mp\_int structure and frees the heap it uses. It sets the
+pointer\footnote{The ``dp'' member.} within the mp\_int to \textbf{NULL} which is used to prevent double free situations.
+Is is legal to call mp\_clear() twice on the same mp\_int in a row.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the number */
+
+ /* We're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\subsection{Multiple Initializations}
+Certain algorithms require more than one large integer. In these instances it is ideal to initialize all of the mp\_int
+variables in an ``all or nothing'' fashion. That is, they are either all initialized successfully or they are all
+not initialized.
+
+The mp\_init\_multi() function provides this functionality.
+
+\index{mp\_init\_multi} \index{mp\_clear\_multi}
+\begin{alltt}
+int mp_init_multi(mp_int *mp, ...);
+\end{alltt}
+
+It accepts a \textbf{NULL} terminated list of pointers to mp\_int structures. It will attempt to initialize them all
+at once. If the function returns MP\_OKAY then all of the mp\_int variables are ready to use, otherwise none of them
+are available for use. A complementary mp\_clear\_multi() function allows multiple mp\_int variables to be free'd
+from the heap at the same time.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int num1, num2, num3;
+ int result;
+
+ if ((result = mp_init_multi(&num1,
+ &num2,
+ &num3, NULL)) != MP\_OKAY) \{
+ printf("Error initializing the numbers. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the numbers */
+
+ /* We're done with them. */
+ mp_clear_multi(&num1, &num2, &num3, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\subsection{Other Initializers}
+To initialized and make a copy of an mp\_int the mp\_init\_copy() function has been provided.
+
+\index{mp\_init\_copy}
+\begin{alltt}
+int mp_init_copy (mp_int * a, mp_int * b);
+\end{alltt}
+
+This function will initialize $a$ and make it a copy of $b$ if all goes well.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int num1, num2;
+ int result;
+
+ /* initialize and do work on num1 ... */
+
+ /* We want a copy of num1 in num2 now */
+ if ((result = mp_init_copy(&num2, &num1)) != MP_OKAY) \{
+ printf("Error initializing the copy. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now num2 is ready and contains a copy of num1 */
+
+ /* We're done with them. */
+ mp_clear_multi(&num1, &num2, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+Another less common initializer is mp\_init\_size() which allows the user to initialize an mp\_int with a given
+default number of digits. By default, all initializers allocate \textbf{MP\_PREC} digits. This function lets
+you override this behaviour.
+
+\index{mp\_init\_size}
+\begin{alltt}
+int mp_init_size (mp_int * a, int size);
+\end{alltt}
+
+The $size$ parameter must be greater than zero. If the function succeeds the mp\_int $a$ will be initialized
+to have $size$ digits (which are all initially zero).
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ /* we need a 60-digit number */
+ if ((result = mp_init_size(&number, 60)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the number */
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\section{Maintenance Functions}
+
+\subsection{Reducing Memory Usage}
+When an mp\_int is in a state where it won't be changed again\footnote{A Diffie-Hellman modulus for instance.} excess
+digits can be removed to return memory to the heap with the mp\_shrink() function.
+
+\index{mp\_shrink}
+\begin{alltt}
+int mp_shrink (mp_int * a);
+\end{alltt}
+
+This will remove excess digits of the mp\_int $a$. If the operation fails the mp\_int should be intact without the
+excess digits being removed. Note that you can use a shrunk mp\_int in further computations, however, such operations
+will require heap operations which can be slow. It is not ideal to shrink mp\_int variables that you will further
+modify in the system (unless you are seriously low on memory).
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the number [e.g. pre-computation] */
+
+ /* We're done with it for now. */
+ if ((result = mp_shrink(&number)) != MP_OKAY) \{
+ printf("Error shrinking the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use it .... */
+
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\subsection{Adding additional digits}
+
+Within the mp\_int structure are two parameters which control the limitations of the array of digits that represent
+the integer the mp\_int is meant to equal. The \textit{used} parameter dictates how many digits are significant, that is,
+contribute to the value of the mp\_int. The \textit{alloc} parameter dictates how many digits are currently available in
+the array. If you need to perform an operation that requires more digits you will have to mp\_grow() the mp\_int to
+your desired size.
+
+\index{mp\_grow}
+\begin{alltt}
+int mp_grow (mp_int * a, int size);
+\end{alltt}
+
+This will grow the array of digits of $a$ to $size$. If the \textit{alloc} parameter is already bigger than
+$size$ the function will not do anything.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* use the number */
+
+ /* We need to add 20 digits to the number */
+ if ((result = mp_grow(&number, number.alloc + 20)) != MP_OKAY) \{
+ printf("Error growing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+
+ /* use the number */
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\chapter{Basic Operations}
+\section{Small Constants}
+Setting mp\_ints to small constants is a relatively common operation. To accomodate these instances there are two
+small constant assignment functions. The first function is used to set a single digit constant while the second sets
+an ISO C style ``unsigned long'' constant. The reason for both functions is efficiency. Setting a single digit is quick but the
+domain of a digit can change (it's always at least $0 \ldots 127$).
+
+\subsection{Single Digit}
+
+Setting a single digit can be accomplished with the following function.
+
+\index{mp\_set}
+\begin{alltt}
+void mp_set (mp_int * a, mp_digit b);
+\end{alltt}
+
+This will zero the contents of $a$ and make it represent an integer equal to the value of $b$. Note that this
+function has a return type of \textbf{void}. It cannot cause an error so it is safe to assume the function
+succeeded.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number to 5 */
+ mp_set(&number, 5);
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+\subsection{Long Constants}
+
+To set a constant that is the size of an ISO C ``unsigned long'' and larger than a single digit the following function
+can be used.
+
+\index{mp\_set\_int}
+\begin{alltt}
+int mp_set_int (mp_int * a, unsigned long b);
+\end{alltt}
+
+This will assign the value of the 32-bit variable $b$ to the mp\_int $a$. Unlike mp\_set() this function will always
+accept a 32-bit input regardless of the size of a single digit. However, since the value may span several digits
+this function can fail if it runs out of heap memory.
+
+To get the ``unsigned long'' copy of an mp\_int the following function can be used.
+
+\index{mp\_get\_int}
+\begin{alltt}
+unsigned long mp_get_int (mp_int * a);
+\end{alltt}
+
+This will return the 32 least significant bits of the mp\_int $a$.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number to 654321 (note this is bigger than 127) */
+ if ((result = mp_set_int(&number, 654321)) != MP_OKAY) \{
+ printf("Error setting the value of the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ printf("number == \%lu", mp_get_int(&number));
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+This should output the following if the program succeeds.
+
+\begin{alltt}
+number == 654321
+\end{alltt}
+
+\subsection{Initialize and Setting Constants}
+To both initialize and set small constants the following two functions are available.
+\index{mp\_init\_set} \index{mp\_init\_set\_int}
+\begin{alltt}
+int mp_init_set (mp_int * a, mp_digit b);
+int mp_init_set_int (mp_int * a, unsigned long b);
+\end{alltt}
+
+Both functions work like the previous counterparts except they first mp\_init $a$ before setting the values.
+
+\begin{alltt}
+int main(void)
+\{
+ mp_int number1, number2;
+ int result;
+
+ /* initialize and set a single digit */
+ if ((result = mp_init_set(&number1, 100)) != MP_OKAY) \{
+ printf("Error setting number1: \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* initialize and set a long */
+ if ((result = mp_init_set_int(&number2, 1023)) != MP_OKAY) \{
+ printf("Error setting number2: \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* display */
+ printf("Number1, Number2 == \%lu, \%lu",
+ mp_get_int(&number1), mp_get_int(&number2));
+
+ /* clear */
+ mp_clear_multi(&number1, &number2, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt}
+
+If this program succeeds it shall output.
+\begin{alltt}
+Number1, Number2 == 100, 1023
+\end{alltt}
+
+\section{Comparisons}
+
+Comparisons in LibTomMath are always performed in a ``left to right'' fashion. There are three possible return codes
+for any comparison.
+
+\index{MP\_GT} \index{MP\_EQ} \index{MP\_LT}
+\begin{figure}[here]
+\begin{center}
+\begin{tabular}{|c|c|}
+\hline \textbf{Result Code} & \textbf{Meaning} \\
+\hline MP\_GT & $a > b$ \\
+\hline MP\_EQ & $a = b$ \\
+\hline MP\_LT & $a < b$ \\
+\hline
+\end{tabular}
+\end{center}
+\caption{Comparison Codes for $a, b$}
+\label{fig:CMP}
+\end{figure}
+
+In figure \ref{fig:CMP} two integers $a$ and $b$ are being compared. In this case $a$ is said to be ``to the left'' of
+$b$.
+
+\subsection{Unsigned comparison}
+
+An unsigned comparison considers only the digits themselves and not the associated \textit{sign} flag of the
+mp\_int structures. This is analogous to an absolute comparison. The function mp\_cmp\_mag() will compare two
+mp\_int variables based on their digits only.
+
+\index{mp\_cmp\_mag}
+\begin{alltt}
+int mp_cmp(mp_int * a, mp_int * b);
+\end{alltt}
+This will compare $a$ to $b$ placing $a$ to the left of $b$. This function cannot fail and will return one of the
+three compare codes listed in figure \ref{fig:CMP}.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number1, number2;
+ int result;
+
+ if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{
+ printf("Error initializing the numbers. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number1 to 5 */
+ mp_set(&number1, 5);
+
+ /* set the number2 to -6 */
+ mp_set(&number2, 6);
+ if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{
+ printf("Error negating number2. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ switch(mp_cmp_mag(&number1, &number2)) \{
+ case MP_GT: printf("|number1| > |number2|"); break;
+ case MP_EQ: printf("|number1| = |number2|"); break;
+ case MP_LT: printf("|number1| < |number2|"); break;
+ \}
+
+ /* we're done with it. */
+ mp_clear_multi(&number1, &number2, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes
+successfully it should print the following.
+
+\begin{alltt}
+|number1| < |number2|
+\end{alltt}
+
+This is because $\vert -6 \vert = 6$ and obviously $5 < 6$.
+
+\subsection{Signed comparison}
+
+To compare two mp\_int variables based on their signed value the mp\_cmp() function is provided.
+
+\index{mp\_cmp}
+\begin{alltt}
+int mp_cmp(mp_int * a, mp_int * b);
+\end{alltt}
+
+This will compare $a$ to the left of $b$. It will first compare the signs of the two mp\_int variables. If they
+differ it will return immediately based on their signs. If the signs are equal then it will compare the digits
+individually. This function will return one of the compare conditions codes listed in figure \ref{fig:CMP}.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number1, number2;
+ int result;
+
+ if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{
+ printf("Error initializing the numbers. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number1 to 5 */
+ mp_set(&number1, 5);
+
+ /* set the number2 to -6 */
+ mp_set(&number2, 6);
+ if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{
+ printf("Error negating number2. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ switch(mp_cmp(&number1, &number2)) \{
+ case MP_GT: printf("number1 > number2"); break;
+ case MP_EQ: printf("number1 = number2"); break;
+ case MP_LT: printf("number1 < number2"); break;
+ \}
+
+ /* we're done with it. */
+ mp_clear_multi(&number1, &number2, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes
+successfully it should print the following.
+
+\begin{alltt}
+number1 > number2
+\end{alltt}
+
+\subsection{Single Digit}
+
+To compare a single digit against an mp\_int the following function has been provided.
+
+\index{mp\_cmp\_d}
+\begin{alltt}
+int mp_cmp_d(mp_int * a, mp_digit b);
+\end{alltt}
+
+This will compare $a$ to the left of $b$ using a signed comparison. Note that it will always treat $b$ as
+positive. This function is rather handy when you have to compare against small values such as $1$ (which often
+comes up in cryptography). The function cannot fail and will return one of the tree compare condition codes
+listed in figure \ref{fig:CMP}.
+
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number to 5 */
+ mp_set(&number, 5);
+
+ switch(mp_cmp_d(&number, 7)) \{
+ case MP_GT: printf("number > 7"); break;
+ case MP_EQ: printf("number = 7"); break;
+ case MP_LT: printf("number < 7"); break;
+ \}
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+If this program functions properly it will print out the following.
+
+\begin{alltt}
+number < 7
+\end{alltt}
+
+\section{Logical Operations}
+
+Logical operations are operations that can be performed either with simple shifts or boolean operators such as
+AND, XOR and OR directly. These operations are very quick.
+
+\subsection{Multiplication by two}
+
+Multiplications and divisions by any power of two can be performed with quick logical shifts either left or
+right depending on the operation.
+
+When multiplying or dividing by two a special case routine can be used which are as follows.
+\index{mp\_mul\_2} \index{mp\_div\_2}
+\begin{alltt}
+int mp_mul_2(mp_int * a, mp_int * b);
+int mp_div_2(mp_int * a, mp_int * b);
+\end{alltt}
+
+The former will assign twice $a$ to $b$ while the latter will assign half $a$ to $b$. These functions are fast
+since the shift counts and maskes are hardcoded into the routines.
+
+\begin{small} \begin{alltt}
+int main(void)
+\{
+ mp_int number;
+ int result;
+
+ if ((result = mp_init(&number)) != MP_OKAY) \{
+ printf("Error initializing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the number to 5 */
+ mp_set(&number, 5);
+
+ /* multiply by two */
+ if ((result = mp\_mul\_2(&number, &number)) != MP_OKAY) \{
+ printf("Error multiplying the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+ switch(mp_cmp_d(&number, 7)) \{
+ case MP_GT: printf("2*number > 7"); break;
+ case MP_EQ: printf("2*number = 7"); break;
+ case MP_LT: printf("2*number < 7"); break;
+ \}
+
+ /* now divide by two */
+ if ((result = mp\_div\_2(&number, &number)) != MP_OKAY) \{
+ printf("Error dividing the number. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+ switch(mp_cmp_d(&number, 7)) \{
+ case MP_GT: printf("2*number/2 > 7"); break;
+ case MP_EQ: printf("2*number/2 = 7"); break;
+ case MP_LT: printf("2*number/2 < 7"); break;
+ \}
+
+ /* we're done with it. */
+ mp_clear(&number);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt} \end{small}
+
+If this program is successful it will print out the following text.
+
+\begin{alltt}
+2*number > 7
+2*number/2 < 7
+\end{alltt}
+
+Since $10 > 7$ and $5 < 7$. To multiply by a power of two the following function can be used.
+
+\index{mp\_mul\_2d}
+\begin{alltt}
+int mp_mul_2d(mp_int * a, int b, mp_int * c);
+\end{alltt}
+
+This will multiply $a$ by $2^b$ and store the result in ``c''. If the value of $b$ is less than or equal to
+zero the function will copy $a$ to ``c'' without performing any further actions.
+
+To divide by a power of two use the following.
+
+\index{mp\_div\_2d}
+\begin{alltt}
+int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d);
+\end{alltt}
+Which will divide $a$ by $2^b$, store the quotient in ``c'' and the remainder in ``d'. If $b \le 0$ then the
+function simply copies $a$ over to ``c'' and zeroes $d$. The variable $d$ may be passed as a \textbf{NULL}
+value to signal that the remainder is not desired.
+
+\subsection{Polynomial Basis Operations}
+
+Strictly speaking the organization of the integers within the mp\_int structures is what is known as a
+``polynomial basis''. This simply means a field element is stored by divisions of a radix. For example, if
+$f(x) = \sum_{i=0}^{k} y_ix^k$ for any vector $\vec y$ then the array of digits in $\vec y$ are said to be
+the polynomial basis representation of $z$ if $f(\beta) = z$ for a given radix $\beta$.
+
+To multiply by the polynomial $g(x) = x$ all you have todo is shift the digits of the basis left one place. The
+following function provides this operation.
+
+\index{mp\_lshd}
+\begin{alltt}
+int mp_lshd (mp_int * a, int b);
+\end{alltt}
+
+This will multiply $a$ in place by $x^b$ which is equivalent to shifting the digits left $b$ places and inserting zeroes
+in the least significant digits. Similarly to divide by a power of $x$ the following function is provided.
+
+\index{mp\_rshd}
+\begin{alltt}
+void mp_rshd (mp_int * a, int b)
+\end{alltt}
+This will divide $a$ in place by $x^b$ and discard the remainder. This function cannot fail as it performs the operations
+in place and no new digits are required to complete it.
+
+\subsection{AND, OR and XOR Operations}
+
+While AND, OR and XOR operations are not typical ``bignum functions'' they can be useful in several instances. The
+three functions are prototyped as follows.
+
+\index{mp\_or} \index{mp\_and} \index{mp\_xor}
+\begin{alltt}
+int mp_or (mp_int * a, mp_int * b, mp_int * c);
+int mp_and (mp_int * a, mp_int * b, mp_int * c);
+int mp_xor (mp_int * a, mp_int * b, mp_int * c);
+\end{alltt}
+
+Which compute $c = a \odot b$ where $\odot$ is one of OR, AND or XOR.
+
+\section{Addition and Subtraction}
+
+To compute an addition or subtraction the following two functions can be used.
+
+\index{mp\_add} \index{mp\_sub}
+\begin{alltt}
+int mp_add (mp_int * a, mp_int * b, mp_int * c);
+int mp_sub (mp_int * a, mp_int * b, mp_int * c)
+\end{alltt}
+
+Which perform $c = a \odot b$ where $\odot$ is one of signed addition or subtraction. The operations are fully sign
+aware.
+
+\section{Sign Manipulation}
+\subsection{Negation}
+\label{sec:NEG}
+Simple integer negation can be performed with the following.
+
+\index{mp\_neg}
+\begin{alltt}
+int mp_neg (mp_int * a, mp_int * b);
+\end{alltt}
+
+Which assigns $-a$ to $b$.
+
+\subsection{Absolute}
+Simple integer absolutes can be performed with the following.
+
+\index{mp\_neg}
+\begin{alltt}
+int mp_abs (mp_int * a, mp_int * b);
+\end{alltt}
+
+Which assigns $\vert a \vert$ to $b$.
+
+\section{Integer Division and Remainder}
+To perform a complete and general integer division with remainder use the following function.
+
+\index{mp\_div}
+\begin{alltt}
+int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d);
+\end{alltt}
+
+This divides $a$ by $b$ and stores the quotient in $c$ and $d$. The signed quotient is computed such that
+$bc + d = a$. Note that either of $c$ or $d$ can be set to \textbf{NULL} if their value is not required. If
+$b$ is zero the function returns \textbf{MP\_VAL}.
+
+
+\chapter{Multiplication and Squaring}
+\section{Multiplication}
+A full signed integer multiplication can be performed with the following.
+\index{mp\_mul}
+\begin{alltt}
+int mp_mul (mp_int * a, mp_int * b, mp_int * c);
+\end{alltt}
+Which assigns the full signed product $ab$ to $c$. This function actually breaks into one of four cases which are
+specific multiplication routines optimized for given parameters. First there are the Toom-Cook multiplications which
+should only be used with very large inputs. This is followed by the Karatsuba multiplications which are for moderate
+sized inputs. Then followed by the Comba and baseline multipliers.
+
+Fortunately for the developer you don't really need to know this unless you really want to fine tune the system. mp\_mul()
+will determine on its own\footnote{Some tweaking may be required.} what routine to use automatically when it is called.
+
+\begin{alltt}
+int main(void)
+\{
+ mp_int number1, number2;
+ int result;
+
+ /* Initialize the numbers */
+ if ((result = mp_init_multi(&number1,
+ &number2, NULL)) != MP_OKAY) \{
+ printf("Error initializing the numbers. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* set the terms */
+ if ((result = mp_set_int(&number, 257)) != MP_OKAY) \{
+ printf("Error setting number1. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ if ((result = mp_set_int(&number2, 1023)) != MP_OKAY) \{
+ printf("Error setting number2. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* multiply them */
+ if ((result = mp_mul(&number1, &number2,
+ &number1)) != MP_OKAY) \{
+ printf("Error multiplying terms. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* display */
+ printf("number1 * number2 == \%lu", mp_get_int(&number1));
+
+ /* free terms and return */
+ mp_clear_multi(&number1, &number2, NULL);
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt}
+
+If this program succeeds it shall output the following.
+
+\begin{alltt}
+number1 * number2 == 262911
+\end{alltt}
+
+\section{Squaring}
+Since squaring can be performed faster than multiplication it is performed it's own function instead of just using
+mp\_mul().
+
+\index{mp\_sqr}
+\begin{alltt}
+int mp_sqr (mp_int * a, mp_int * b);
+\end{alltt}
+
+Will square $a$ and store it in $b$. Like the case of multiplication there are four different squaring
+algorithms all which can be called from mp\_sqr(). It is ideal to use mp\_sqr over mp\_mul when squaring terms.
+
+\section{Tuning Polynomial Basis Routines}
+
+Both of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional $O(n^2)$ approach that
+the Comba and baseline algorithms use. At $O(n^{1.464973})$ and $O(n^{1.584962})$ running times respectfully they require
+considerably less work. For example, a 10000-digit multiplication would take roughly 724,000 single precision
+multiplications with Toom-Cook or 100,000,000 single precision multiplications with the standard Comba (a factor
+of 138).
+
+So why not always use Karatsuba or Toom-Cook? The simple answer is that they have so much overhead that they're not
+actually faster than Comba until you hit distinct ``cutoff'' points. For Karatsuba with the default configuration,
+GCC 3.3.1 and an Athlon XP processor the cutoff point is roughly 110 digits (about 70 for the Intel P4). That is, at
+110 digits Karatsuba and Comba multiplications just about break even and for 110+ digits Karatsuba is faster.
+
+Toom-Cook has incredible overhead and is probably only useful for very large inputs. So far no known cutoff points
+exist and for the most part I just set the cutoff points very high to make sure they're not called.
+
+A demo program in the ``etc/'' directory of the project called ``tune.c'' can be used to find the cutoff points. This
+can be built with GCC as follows
+
+\begin{alltt}
+make XXX
+\end{alltt}
+Where ``XXX'' is one of the following entries from the table \ref{fig:tuning}.
+
+\begin{figure}[here]
+\begin{center}
+\begin{small}
+\begin{tabular}{|l|l|}
+\hline \textbf{Value of XXX} & \textbf{Meaning} \\
+\hline tune & Builds portable tuning application \\
+\hline tune86 & Builds x86 (pentium and up) program for COFF \\
+\hline tune86c & Builds x86 program for Cygwin \\
+\hline tune86l & Builds x86 program for Linux (ELF format) \\
+\hline
+\end{tabular}
+\end{small}
+\end{center}
+\caption{Build Names for Tuning Programs}
+\label{fig:tuning}
+\end{figure}
+
+When the program is running it will output a series of measurements for different cutoff points. It will first find
+good Karatsuba squaring and multiplication points. Then it proceeds to find Toom-Cook points. Note that the Toom-Cook
+tuning takes a very long time as the cutoff points are likely to be very high.
+
+\chapter{Modular Reduction}
+
+Modular reduction is process of taking the remainder of one quantity divided by another. Expressed
+as (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$.
+
+\begin{equation}
+a \equiv b \mbox{ (mod }c\mbox{)}
+\label{eqn:mod}
+\end{equation}
+
+Of particular interest to cryptography are reductions where $b$ is limited to the range $0 \le b < c^2$ since particularly
+fast reduction algorithms can be written for the limited range.
+
+Note that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation
+algorithm mp\_exptmod when an appropriate modulus is detected.
+
+\section{Straight Division}
+In order to effect an arbitrary modular reduction the following algorithm is provided.
+
+\index{mp\_mod}
+\begin{alltt}
+int mp_mod(mp_int *a, mp_int *b, mp_int *c);
+\end{alltt}
+
+This reduces $a$ modulo $b$ and stores the result in $c$. The sign of $c$ shall agree with the sign
+of $b$. This algorithm accepts an input $a$ of any range and is not limited by $0 \le a < b^2$.
+
+\section{Barrett Reduction}
+
+Barrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve
+a decent speedup over straight division. First a $mu$ value must be precomputed with the following function.
+
+\index{mp\_reduce\_setup}
+\begin{alltt}
+int mp_reduce_setup(mp_int *a, mp_int *b);
+\end{alltt}
+
+Given a modulus in $b$ this produces the required $mu$ value in $a$. For any given modulus this only has to
+be computed once. Modular reduction can now be performed with the following.
+
+\index{mp\_reduce}
+\begin{alltt}
+int mp_reduce(mp_int *a, mp_int *b, mp_int *c);
+\end{alltt}
+
+This will reduce $a$ in place modulo $b$ with the precomputed $mu$ value in $c$. $a$ must be in the range
+$0 \le a < b^2$.
+
+\begin{alltt}
+int main(void)
+\{
+ mp_int a, b, c, mu;
+ int result;
+
+ /* initialize a,b to desired values, mp_init mu,
+ * c and set c to 1...we want to compute a^3 mod b
+ */
+
+ /* get mu value */
+ if ((result = mp_reduce_setup(&mu, b)) != MP_OKAY) \{
+ printf("Error getting mu. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* square a to get c = a^2 */
+ if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{
+ printf("Error squaring. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now reduce `c' modulo b */
+ if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* multiply a to get c = a^3 */
+ if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now reduce `c' modulo b */
+ if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* c now equals a^3 mod b */
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt}
+
+This program will calculate $a^3 \mbox{ mod }b$ if all the functions succeed.
+
+\section{Montgomery Reduction}
+
+Montgomery is a specialized reduction algorithm for any odd moduli. Like Barrett reduction a pre--computation
+step is required. This is accomplished with the following.
+
+\index{mp\_montgomery\_setup}
+\begin{alltt}
+int mp_montgomery_setup(mp_int *a, mp_digit *mp);
+\end{alltt}
+
+For the given odd moduli $a$ the precomputation value is placed in $mp$. The reduction is computed with the
+following.
+
+\index{mp\_montgomery\_reduce}
+\begin{alltt}
+int mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
+\end{alltt}
+This reduces $a$ in place modulo $m$ with the pre--computed value $mp$. $a$ must be in the range
+$0 \le a < b^2$.
+
+Montgomery reduction is faster than Barrett reduction for moduli smaller than the ``comba'' limit. With the default
+setup for instance, the limit is $127$ digits ($3556$--bits). Note that this function is not limited to
+$127$ digits just that it falls back to a baseline algorithm after that point.
+
+An important observation is that this reduction does not return $a \mbox{ mod }m$ but $aR^{-1} \mbox{ mod }m$
+where $R = \beta^n$, $n$ is the n number of digits in $m$ and $\beta$ is radix used (default is $2^{28}$).
+
+To quickly calculate $R$ the following function was provided.
+
+\index{mp\_montgomery\_calc\_normalization}
+\begin{alltt}
+int mp_montgomery_calc_normalization(mp_int *a, mp_int *b);
+\end{alltt}
+Which calculates $a = R$ for the odd moduli $b$ without using multiplication or division.
+
+The normal modus operandi for Montgomery reductions is to normalize the integers before entering the system. For
+example, to calculate $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by
+multiplying it by $R$. Consider the following code snippet.
+
+\begin{alltt}
+int main(void)
+\{
+ mp_int a, b, c, R;
+ mp_digit mp;
+ int result;
+
+ /* initialize a,b to desired values,
+ * mp_init R, c and set c to 1....
+ */
+
+ /* get normalization */
+ if ((result = mp_montgomery_calc_normalization(&R, b)) != MP_OKAY) \{
+ printf("Error getting norm. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* get mp value */
+ if ((result = mp_montgomery_setup(&c, &mp)) != MP_OKAY) \{
+ printf("Error setting up montgomery. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* normalize `a' so now a is equal to aR */
+ if ((result = mp_mulmod(&a, &R, &b, &a)) != MP_OKAY) \{
+ printf("Error computing aR. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* square a to get c = a^2R^2 */
+ if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{
+ printf("Error squaring. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now reduce `c' back down to c = a^2R^2 * R^-1 == a^2R */
+ if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* multiply a to get c = a^3R^2 */
+ if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now reduce `c' back down to c = a^3R^2 * R^-1 == a^3R */
+ if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* now reduce (again) `c' back down to c = a^3R * R^-1 == a^3 */
+ if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{
+ printf("Error reducing. \%s",
+ mp_error_to_string(result));
+ return EXIT_FAILURE;
+ \}
+
+ /* c now equals a^3 mod b */
+
+ return EXIT_SUCCESS;
+\}
+\end{alltt}
+
+This particular example does not look too efficient but it demonstrates the point of the algorithm. By
+normalizing the inputs the reduced results are always of the form $aR$ for some variable $a$. This allows
+a single final reduction to correct for the normalization and the fast reduction used within the algorithm.
+
+For more details consider examining the file \textit{bn\_mp\_exptmod\_fast.c}.
+
+\section{Restricted Dimminished Radix}
+
+``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple
+digit shifting and small multiplications. In this case the ``restricted'' variant refers to moduli of the
+form $\beta^k - p$ for some $k \ge 0$ and $0 < p < \beta$ where $\beta$ is the radix (default to $2^{28}$).
+
+As in the case of Montgomery reduction there is a pre--computation phase required for a given modulus.
+
+\index{mp\_dr\_setup}
+\begin{alltt}
+void mp_dr_setup(mp_int *a, mp_digit *d);
+\end{alltt}
+
+This computes the value required for the modulus $a$ and stores it in $d$. This function cannot fail
+and does not return any error codes. After the pre--computation a reduction can be performed with the
+following.
+
+\index{mp\_dr\_reduce}
+\begin{alltt}
+int mp_dr_reduce(mp_int *a, mp_int *b, mp_digit mp);
+\end{alltt}
+
+This reduces $a$ in place modulo $b$ with the pre--computed value $mp$. $b$ must be of a restricted
+dimminished radix form and $a$ must be in the range $0 \le a < b^2$. Dimminished radix reductions are
+much faster than both Barrett and Montgomery reductions as they have a much lower asymtotic running time.
+
+Since the moduli are restricted this algorithm is not particularly useful for something like Rabin, RSA or
+BBS cryptographic purposes. This reduction algorithm is useful for Diffie-Hellman and ECC where fixed
+primes are acceptable.
+
+Note that unlike Montgomery reduction there is no normalization process. The result of this function is
+equal to the correct residue.
+
+\section{Unrestricted Dimminshed Radix}
+
+Unrestricted reductions work much like the restricted counterparts except in this case the moduli is of the
+form $2^k - p$ for $0 < p < \beta$. In this sense the unrestricted reductions are more flexible as they
+can be applied to a wider range of numbers.
+
+\index{mp\_reduce\_2k\_setup}
+\begin{alltt}
+int mp_reduce_2k_setup(mp_int *a, mp_digit *d);
+\end{alltt}
+
+This will compute the required $d$ value for the given moduli $a$.
+
+\index{mp\_reduce\_2k}
+\begin{alltt}
+int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d);
+\end{alltt}
+
+This will reduce $a$ in place modulo $n$ with the pre--computed value $d$. From my experience this routine is
+slower than mp\_dr\_reduce but faster for most moduli sizes than the Montgomery reduction.
+
+\chapter{Exponentiation}
+\section{Single Digit Exponentiation}
+\index{mp\_expt\_d}
+\begin{alltt}
+int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
+\end{alltt}
+This computes $c = a^b$ using a simple binary left-to-right algorithm. It is faster than repeated multiplications by
+$a$ for all values of $b$ greater than three.
+
+\section{Modular Exponentiation}
+\index{mp\_exptmod}
+\begin{alltt}
+int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
+\end{alltt}
+This computes $Y \equiv G^X \mbox{ (mod }P\mbox{)}$ using a variable width sliding window algorithm. This function
+will automatically detect the fastest modular reduction technique to use during the operation. For negative values of
+$X$ the operation is performed as $Y \equiv (G^{-1} \mbox{ mod }P)^{\vert X \vert} \mbox{ (mod }P\mbox{)}$ provided that
+$gcd(G, P) = 1$.
+
+This function is actually a shell around the two internal exponentiation functions. This routine will automatically
+detect when Barrett, Montgomery, Restricted and Unrestricted Dimminished Radix based exponentiation can be used. Generally
+moduli of the a ``restricted dimminished radix'' form lead to the fastest modular exponentiations. Followed by Montgomery
+and the other two algorithms.
+
+\section{Root Finding}
+\index{mp\_n\_root}
+\begin{alltt}
+int mp_n_root (mp_int * a, mp_digit b, mp_int * c)
+\end{alltt}
+This computes $c = a^{1/b}$ such that $c^b \le a$ and $(c+1)^b > a$. The implementation of this function is not
+ideal for values of $b$ greater than three. It will work but become very slow. So unless you are working with very small
+numbers (less than 1000 bits) I'd avoid $b > 3$ situations. Will return a positive root only for even roots and return
+a root with the sign of the input for odd roots. For example, performing $4^{1/2}$ will return $2$ whereas $(-8)^{1/3}$
+will return $-2$.
+
+This algorithm uses the ``Newton Approximation'' method and will converge on the correct root fairly quickly. Since
+the algorithm requires raising $a$ to the power of $b$ it is not ideal to attempt to find roots for large
+values of $b$. If particularly large roots are required then a factor method could be used instead. For example,
+$a^{1/16}$ is equivalent to $\left (a^{1/4} \right)^{1/4}$.
+
+\chapter{Prime Numbers}
+\section{Trial Division}
+\index{mp\_prime\_is\_divisible}
+\begin{alltt}
+int mp_prime_is_divisible (mp_int * a, int *result)
+\end{alltt}
+This will attempt to evenly divide $a$ by a list of primes\footnote{Default is the first 256 primes.} and store the
+outcome in ``result''. That is if $result = 0$ then $a$ is not divisible by the primes, otherwise it is. Note that
+if the function does not return \textbf{MP\_OKAY} the value in ``result'' should be considered undefined\footnote{Currently
+the default is to set it to zero first.}.
+
+\section{Fermat Test}
+\index{mp\_prime\_fermat}
+\begin{alltt}
+int mp_prime_fermat (mp_int * a, mp_int * b, int *result)
+\end{alltt}
+Performs a Fermat primality test to the base $b$. That is it computes $b^a \mbox{ mod }a$ and tests whether the value is
+equal to $b$ or not. If the values are equal then $a$ is probably prime and $result$ is set to one. Otherwise $result$
+is set to zero.
+
+\section{Miller-Rabin Test}
+\index{mp\_prime\_miller\_rabin}
+\begin{alltt}
+int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result)
+\end{alltt}
+Performs a Miller-Rabin test to the base $b$ of $a$. This test is much stronger than the Fermat test and is very hard to
+fool (besides with Carmichael numbers). If $a$ passes the test (therefore is probably prime) $result$ is set to one.
+Otherwise $result$ is set to zero.
+
+Note that is suggested that you use the Miller-Rabin test instead of the Fermat test since all of the failures of
+Miller-Rabin are a subset of the failures of the Fermat test.
+
+\subsection{Required Number of Tests}
+Generally to ensure a number is very likely to be prime you have to perform the Miller-Rabin with at least a half-dozen
+or so unique bases. However, it has been proven that the probability of failure goes down as the size of the input goes up.
+This is why a simple function has been provided to help out.
+
+\index{mp\_prime\_rabin\_miller\_trials}
+\begin{alltt}
+int mp_prime_rabin_miller_trials(int size)
+\end{alltt}
+This returns the number of trials required for a $2^{-96}$ (or lower) probability of failure for a given ``size'' expressed
+in bits. This comes in handy specially since larger numbers are slower to test. For example, a 512-bit number would
+require ten tests whereas a 1024-bit number would only require four tests.
+
+You should always still perform a trial division before a Miller-Rabin test though.
+
+\section{Primality Testing}
+\index{mp\_prime\_is\_prime}
+\begin{alltt}
+int mp_prime_is_prime (mp_int * a, int t, int *result)
+\end{alltt}
+This will perform a trial division followed by $t$ rounds of Miller-Rabin tests on $a$ and store the result in $result$.
+If $a$ passes all of the tests $result$ is set to one, otherwise it is set to zero. Note that $t$ is bounded by
+$1 \le t < PRIME\_SIZE$ where $PRIME\_SIZE$ is the number of primes in the prime number table (by default this is $256$).
+
+\section{Next Prime}
+\index{mp\_prime\_next\_prime}
+\begin{alltt}
+int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
+\end{alltt}
+This finds the next prime after $a$ that passes mp\_prime\_is\_prime() with $t$ tests. Set $bbs\_style$ to one if you
+want only the next prime congruent to $3 \mbox{ mod } 4$, otherwise set it to zero to find any next prime.
+
+\section{Random Primes}
+\index{mp\_prime\_random}
+\begin{alltt}
+int mp_prime_random(mp_int *a, int t, int size, int bbs,
+ ltm_prime_callback cb, void *dat)
+\end{alltt}
+This will find a prime greater than $256^{size}$ which can be ``bbs\_style'' or not depending on $bbs$ and must pass
+$t$ rounds of tests. The ``ltm\_prime\_callback'' is a typedef for
+
+\begin{alltt}
+typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat);
+\end{alltt}
+
+Which is a function that must read $len$ bytes (and return the amount stored) into $dst$. The $dat$ variable is simply
+copied from the original input. It can be used to pass RNG context data to the callback. The function
+mp\_prime\_random() is more suitable for generating primes which must be secret (as in the case of RSA) since there
+is no skew on the least significant bits.
+
+\textit{Note:} As of v0.30 of the LibTomMath library this function has been deprecated. It is still available
+but users are encouraged to use the new mp\_prime\_random\_ex() function instead.
+
+\subsection{Extended Generation}
+\index{mp\_prime\_random\_ex}
+\begin{alltt}
+int mp_prime_random_ex(mp_int *a, int t,
+ int size, int flags,
+ ltm_prime_callback cb, void *dat);
+\end{alltt}
+This will generate a prime in $a$ using $t$ tests of the primality testing algorithms. The variable $size$
+specifies the bit length of the prime desired. The variable $flags$ specifies one of several options available
+(see fig. \ref{fig:primeopts}) which can be OR'ed together. The callback parameters are used as in
+mp\_prime\_random().
+
+\begin{figure}[here]
+\begin{center}
+\begin{small}
+\begin{tabular}{|r|l|}
+\hline \textbf{Flag} & \textbf{Meaning} \\
+\hline LTM\_PRIME\_BBS & Make the prime congruent to $3$ modulo $4$ \\
+\hline LTM\_PRIME\_SAFE & Make a prime $p$ such that $(p - 1)/2$ is also prime. \\
+ & This option implies LTM\_PRIME\_BBS as well. \\
+\hline LTM\_PRIME\_2MSB\_OFF & Makes sure that the bit adjacent to the most significant bit \\
+ & Is forced to zero. \\
+\hline LTM\_PRIME\_2MSB\_ON & Makes sure that the bit adjacent to the most significant bit \\
+ & Is forced to one. \\
+\hline
+\end{tabular}
+\end{small}
+\end{center}
+\caption{Primality Generation Options}
+\label{fig:primeopts}
+\end{figure}
+
+\chapter{Input and Output}
+\section{ASCII Conversions}
+\subsection{To ASCII}
+\index{mp\_toradix}
+\begin{alltt}
+int mp_toradix (mp_int * a, char *str, int radix);
+\end{alltt}
+This still store $a$ in ``str'' as a base-``radix'' string of ASCII chars. This function appends a NUL character
+to terminate the string. Valid values of ``radix'' line in the range $[2, 64]$. To determine the size (exact) required
+by the conversion before storing any data use the following function.
+
+\index{mp\_radix\_size}
+\begin{alltt}
+int mp_radix_size (mp_int * a, int radix, int *size)
+\end{alltt}
+This stores in ``size'' the number of characters (including space for the NUL terminator) required. Upon error this
+function returns an error code and ``size'' will be zero.
+
+\subsection{From ASCII}
+\index{mp\_read\_radix}
+\begin{alltt}
+int mp_read_radix (mp_int * a, char *str, int radix);
+\end{alltt}
+This will read the base-``radix'' NUL terminated string from ``str'' into $a$. It will stop reading when it reads a
+character it does not recognize (which happens to include th NUL char... imagine that...). A single leading $-$ sign
+can be used to denote a negative number.
+
+\section{Binary Conversions}
+
+Converting an mp\_int to and from binary is another keen idea.
+
+\index{mp\_unsigned\_bin\_size}
+\begin{alltt}
+int mp_unsigned_bin_size(mp_int *a);
+\end{alltt}
+
+This will return the number of bytes (octets) required to store the unsigned copy of the integer $a$.
+
+\index{mp\_to\_unsigned\_bin}
+\begin{alltt}
+int mp_to_unsigned_bin(mp_int *a, unsigned char *b);
+\end{alltt}
+This will store $a$ into the buffer $b$ in big--endian format. Fortunately this is exactly what DER (or is it ASN?)
+requires. It does not store the sign of the integer.
+
+\index{mp\_read\_unsigned\_bin}
+\begin{alltt}
+int mp_read_unsigned_bin(mp_int *a, unsigned char *b, int c);
+\end{alltt}
+This will read in an unsigned big--endian array of bytes (octets) from $b$ of length $c$ into $a$. The resulting
+integer $a$ will always be positive.
+
+For those who acknowledge the existence of negative numbers (heretic!) there are ``signed'' versions of the
+previous functions.
+
+\begin{alltt}
+int mp_signed_bin_size(mp_int *a);
+int mp_read_signed_bin(mp_int *a, unsigned char *b, int c);
+int mp_to_signed_bin(mp_int *a, unsigned char *b);
+\end{alltt}
+They operate essentially the same as the unsigned copies except they prefix the data with zero or non--zero
+byte depending on the sign. If the sign is zpos (e.g. not negative) the prefix is zero, otherwise the prefix
+is non--zero.
+
+\chapter{Algebraic Functions}
+\section{Extended Euclidean Algorithm}
+\index{mp\_exteuclid}
+\begin{alltt}
+int mp_exteuclid(mp_int *a, mp_int *b,
+ mp_int *U1, mp_int *U2, mp_int *U3);
+\end{alltt}
+
+This finds the triple U1/U2/U3 using the Extended Euclidean algorithm such that the following equation holds.
+
+\begin{equation}
+a \cdot U1 + b \cdot U2 = U3
+\end{equation}
+
+Any of the U1/U2/U3 paramters can be set to \textbf{NULL} if they are not desired.
+
+\section{Greatest Common Divisor}
+\index{mp\_gcd}
+\begin{alltt}
+int mp_gcd (mp_int * a, mp_int * b, mp_int * c)
+\end{alltt}
+This will compute the greatest common divisor of $a$ and $b$ and store it in $c$.
+
+\section{Least Common Multiple}
+\index{mp\_lcm}
+\begin{alltt}
+int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
+\end{alltt}
+This will compute the least common multiple of $a$ and $b$ and store it in $c$.
+
+\section{Jacobi Symbol}
+\index{mp\_jacobi}
+\begin{alltt}
+int mp_jacobi (mp_int * a, mp_int * p, int *c)
+\end{alltt}
+This will compute the Jacobi symbol for $a$ with respect to $p$. If $p$ is prime this essentially computes the Legendre
+symbol. The result is stored in $c$ and can take on one of three values $\lbrace -1, 0, 1 \rbrace$. If $p$ is prime
+then the result will be $-1$ when $a$ is not a quadratic residue modulo $p$. The result will be $0$ if $a$ divides $p$
+and the result will be $1$ if $a$ is a quadratic residue modulo $p$.
+
+\section{Modular Inverse}
+\index{mp\_invmod}
+\begin{alltt}
+int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
+\end{alltt}
+Computes the multiplicative inverse of $a$ modulo $b$ and stores the result in $c$ such that $ac \equiv 1 \mbox{ (mod }b\mbox{)}$.
+
+\section{Single Digit Functions}
+
+For those using small numbers (\textit{snicker snicker}) there are several ``helper'' functions
+
+\index{mp\_add\_d} \index{mp\_sub\_d} \index{mp\_mul\_d} \index{mp\_div\_d} \index{mp\_mod\_d}
+\begin{alltt}
+int mp_add_d(mp_int *a, mp_digit b, mp_int *c);
+int mp_sub_d(mp_int *a, mp_digit b, mp_int *c);
+int mp_mul_d(mp_int *a, mp_digit b, mp_int *c);
+int mp_div_d(mp_int *a, mp_digit b, mp_int *c, mp_digit *d);
+int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c);
+\end{alltt}
+
+These work like the full mp\_int capable variants except the second parameter $b$ is a mp\_digit. These
+functions fairly handy if you have to work with relatively small numbers since you will not have to allocate
+an entire mp\_int to store a number like $1$ or $2$.
+
+\input{bn.ind}
+
+\end{document}
============================================================
--- bn_error.c a3f1d67e5952a5288a5e3b25ae1af448d0c55323
+++ bn_error.c a3f1d67e5952a5288a5e3b25ae1af448d0c55323
@@ -0,0 +1,43 @@
+#include <tommath.h>
+#ifdef BN_ERROR_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+static const struct {
+ int code;
+ char *msg;
+} msgs[] = {
+ { MP_OKAY, "Successful" },
+ { MP_MEM, "Out of heap" },
+ { MP_VAL, "Value out of range" }
+};
+
+/* return a char * string for a given code */
+char *mp_error_to_string(int code)
+{
+ int x;
+
+ /* scan the lookup table for the given message */
+ for (x = 0; x < (int)(sizeof(msgs) / sizeof(msgs[0])); x++) {
+ if (msgs[x].code == code) {
+ return msgs[x].msg;
+ }
+ }
+
+ /* generic reply for invalid code */
+ return "Invalid error code";
+}
+
+#endif
============================================================
--- bn_fast_mp_invmod.c 08f10544b85d8060d7f7afe57fed583c889e3c9c
+++ bn_fast_mp_invmod.c 08f10544b85d8060d7f7afe57fed583c889e3c9c
@@ -0,0 +1,145 @@
+#include <tommath.h>
+#ifdef BN_FAST_MP_INVMOD_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* computes the modular inverse via binary extended euclidean algorithm,
+ * that is c = 1/a mod b
+ *
+ * Based on slow invmod except this is optimized for the case where b is
+ * odd as per HAC Note 14.64 on pp. 610
+ */
+int
+fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
+{
+ mp_int x, y, u, v, B, D;
+ int res, neg;
+
+ /* 2. [modified] b must be odd */
+ if (mp_iseven (b) == 1) {
+ return MP_VAL;
+ }
+
+ /* init all our temps */
+ if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D, NULL)) != MP_OKAY) {
+ return res;
+ }
+
+ /* x == modulus, y == value to invert */
+ if ((res = mp_copy (b, &x)) != MP_OKAY) {
+ goto __ERR;
+ }
+
+ /* we need y = |a| */
+ if ((res = mp_abs (a, &y)) != MP_OKAY) {
+ goto __ERR;
+ }
+
+ /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
+ if ((res = mp_copy (&x, &u)) != MP_OKAY) {
+ goto __ERR;
+ }
+ if ((res = mp_copy (&y, &v)) != MP_OKAY) {
+ goto __ERR;
+ }
+ mp_set (&D, 1);
+
+top:
+ /* 4. while u is even do */
+ while (mp_iseven (&u) == 1) {
+ /* 4.1 u = u/2 */
+ if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
+ goto __ERR;
+ }
+ /* 4.2 if B is odd then */
+ if (mp_isodd (&B) == 1) {
+ if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+ /* B = B/2 */
+ if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+
+ /* 5. while v is even do */
+ while (mp_iseven (&v) == 1) {
+ /* 5.1 v = v/2 */
+ if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
+ goto __ERR;
+ }
+ /* 5.2 if D is odd then */
+ if (mp_isodd (&D) == 1) {
+ /* D = (D-x)/2 */
+ if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+ /* D = D/2 */
+ if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+
+ /* 6. if u >= v then */
+ if (mp_cmp (&u, &v) != MP_LT) {
+ /* u = u - v, B = B - D */
+ if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
+ goto __ERR;
+ }
+
+ if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
+ goto __ERR;
+ }
+ } else {
+ /* v - v - u, D = D - B */
+ if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
+ goto __ERR;
+ }
+
+ if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+
+ /* if not zero goto step 4 */
+ if (mp_iszero (&u) == 0) {
+ goto top;
+ }
+
+ /* now a = C, b = D, gcd == g*v */
+
+ /* if v != 1 then there is no inverse */
+ if (mp_cmp_d (&v, 1) != MP_EQ) {
+ res = MP_VAL;
+ goto __ERR;
+ }
+
+ /* b is now the inverse */
+ neg = a->sign;
+ while (D.sign == MP_NEG) {
+ if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
+ goto __ERR;
+ }
+ }
+ mp_exch (&D, c);
+ c->sign = neg;
+ res = MP_OKAY;
+
+__ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
+ return res;
+}
+#endif
============================================================
--- bn_fast_mp_montgomery_reduce.c 325a7d4683d34160114e1c5c4bdee24f78d53e34
+++ bn_fast_mp_montgomery_reduce.c 325a7d4683d34160114e1c5c4bdee24f78d53e34
@@ -0,0 +1,169 @@
+#include <tommath.h>
+#ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* computes xR**-1 == x (mod N) via Montgomery Reduction
+ *
+ * This is an optimized implementation of montgomery_reduce
+ * which uses the comba method to quickly calculate the columns of the
+ * reduction.
+ *
+ * Based on Algorithm 14.32 on pp.601 of HAC.
+*/
+int
+fast_mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
+{
+ int ix, res, olduse;
+ mp_word W[MP_WARRAY];
+
+ /* get old used count */
+ olduse = x->used;
+
+ /* grow a as required */
+ if (x->alloc < n->used + 1) {
+ if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* first we have to get the digits of the input into
+ * an array of double precision words W[...]
+ */
+ {
+ register mp_word *_W;
+ register mp_digit *tmpx;
+
+ /* alias for the W[] array */
+ _W = W;
+
+ /* alias for the digits of x*/
+ tmpx = x->dp;
+
+ /* copy the digits of a into W[0..a->used-1] */
+ for (ix = 0; ix < x->used; ix++) {
+ *_W++ = *tmpx++;
+ }
+
+ /* zero the high words of W[a->used..m->used*2] */
+ for (; ix < n->used * 2 + 1; ix++) {
+ *_W++ = 0;
+ }
+ }
+
+ /* now we proceed to zero successive digits
+ * from the least significant upwards
+ */
+ for (ix = 0; ix < n->used; ix++) {
+ /* mu = ai * m' mod b
+ *
+ * We avoid a double precision multiplication (which isn't required)
+ * by casting the value down to a mp_digit. Note this requires
+ * that W[ix-1] have the carry cleared (see after the inner loop)
+ */
+ register mp_digit mu;
+ mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK);
+
+ /* a = a + mu * m * b**i
+ *
+ * This is computed in place and on the fly. The multiplication
+ * by b**i is handled by offseting which columns the results
+ * are added to.
+ *
+ * Note the comba method normally doesn't handle carries in the
+ * inner loop In this case we fix the carry from the previous
+ * column since the Montgomery reduction requires digits of the
+ * result (so far) [see above] to work. This is
+ * handled by fixing up one carry after the inner loop. The
+ * carry fixups are done in order so after these loops the
+ * first m->used words of W[] have the carries fixed
+ */
+ {
+ register int iy;
+ register mp_digit *tmpn;
+ register mp_word *_W;
+
+ /* alias for the digits of the modulus */
+ tmpn = n->dp;
+
+ /* Alias for the columns set by an offset of ix */
+ _W = W + ix;
+
+ /* inner loop */
+ for (iy = 0; iy < n->used; iy++) {
+ *_W++ += ((mp_word)mu) * ((mp_word)*tmpn++);
+ }
+ }
+
+ /* now fix carry for next digit, W[ix+1] */
+ W[ix + 1] += W[ix] >> ((mp_word) DIGIT_BIT);
+ }
+
+ /* now we have to propagate the carries and
+ * shift the words downward [all those least
+ * significant digits we zeroed].
+ */
+ {
+ register mp_digit *tmpx;
+ register mp_word *_W, *_W1;
+
+ /* nox fix rest of carries */
+
+ /* alias for current word */
+ _W1 = W + ix;
+
+ /* alias for next word, where the carry goes */
+ _W = W + ++ix;
+
+ for (; ix <= n->used * 2 + 1; ix++) {
+ *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT);
+ }
+
+ /* copy out, A = A/b**n
+ *
+ * The result is A/b**n but instead of converting from an
+ * array of mp_word to mp_digit than calling mp_rshd
+ * we just copy them in the right order
+ */
+
+ /* alias for destination word */
+ tmpx = x->dp;
+
+ /* alias for shifted double precision result */
+ _W = W + n->used;
+
+ for (ix = 0; ix < n->used + 1; ix++) {
+ *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK));
+ }
+
+ /* zero oldused digits, if the input a was larger than
+ * m->used+1 we'll have to clear the digits
+ */
+ for (; ix < olduse; ix++) {
+ *tmpx++ = 0;
+ }
+ }
+
+ /* set the max used and clamp */
+ x->used = n->used + 1;
+ mp_clamp (x);
+
+ /* if A >= m then A = A - m */
+ if (mp_cmp_mag (x, n) != MP_LT) {
+ return s_mp_sub (x, n, x);
+ }
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_fast_s_mp_mul_digs.c 0672a145d0569d227d950c2555234afe2ab394d6
+++ bn_fast_s_mp_mul_digs.c 0672a145d0569d227d950c2555234afe2ab394d6
@@ -0,0 +1,103 @@
+#include <tommath.h>
+#ifdef BN_FAST_S_MP_MUL_DIGS_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* Fast (comba) multiplier
+ *
+ * This is the fast column-array [comba] multiplier. It is
+ * designed to compute the columns of the product first
+ * then handle the carries afterwards. This has the effect
+ * of making the nested loops that compute the columns very
+ * simple and schedulable on super-scalar processors.
+ *
+ * This has been modified to produce a variable number of
+ * digits of output so if say only a half-product is required
+ * you don't have to compute the upper half (a feature
+ * required for fast Barrett reduction).
+ *
+ * Based on Algorithm 14.12 on pp.595 of HAC.
+ *
+ */
+int
+fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
+{
+ int olduse, res, pa, ix, iz;
+ mp_digit W[MP_WARRAY];
+ register mp_word _W;
+
+ /* grow the destination as required */
+ if (c->alloc < digs) {
+ if ((res = mp_grow (c, digs)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* number of output digits to produce */
+ pa = MIN(digs, a->used + b->used);
+
+ /* clear the carry */
+ _W = 0;
+ for (ix = 0; ix <= pa; ix++) {
+ int tx, ty;
+ int iy;
+ mp_digit *tmpx, *tmpy;
+
+ /* get offsets into the two bignums */
+ ty = MIN(b->used-1, ix);
+ tx = ix - ty;
+
+ /* setup temp aliases */
+ tmpx = a->dp + tx;
+ tmpy = b->dp + ty;
+
+ /* this is the number of times the loop will iterrate, essentially its
+ while (tx++ < a->used && ty-- >= 0) { ... }
+ */
+ iy = MIN(a->used-tx, ty+1);
+
+ /* execute loop */
+ for (iz = 0; iz < iy; ++iz) {
+ _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
+ }
+
+ /* store term */
+ W[ix] = ((mp_digit)_W) & MP_MASK;
+
+ /* make next carry */
+ _W = _W >> ((mp_word)DIGIT_BIT);
+ }
+
+ /* setup dest */
+ olduse = c->used;
+ c->used = digs;
+
+ {
+ register mp_digit *tmpc;
+ tmpc = c->dp;
+ for (ix = 0; ix < digs; ix++) {
+ /* now extract the previous digit [below the carry] */
+ *tmpc++ = W[ix];
+ }
+
+ /* clear unused digits [that existed in the old copy of c] */
+ for (; ix < olduse; ix++) {
+ *tmpc++ = 0;
+ }
+ }
+ mp_clamp (c);
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_fast_s_mp_mul_high_digs.c 0d7785aa91e231bdc765d67ff4074ecc29d556a2
+++ bn_fast_s_mp_mul_high_digs.c 0d7785aa91e231bdc765d67ff4074ecc29d556a2
@@ -0,0 +1,95 @@
+#include <tommath.h>
+#ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* this is a modified version of fast_s_mul_digs that only produces
+ * output digits *above* digs. See the comments for fast_s_mul_digs
+ * to see how it works.
+ *
+ * This is used in the Barrett reduction since for one of the multiplications
+ * only the higher digits were needed. This essentially halves the work.
+ *
+ * Based on Algorithm 14.12 on pp.595 of HAC.
+ */
+int
+fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
+{
+ int olduse, res, pa, ix, iz;
+ mp_digit W[MP_WARRAY];
+ mp_word _W;
+
+ /* grow the destination as required */
+ pa = a->used + b->used;
+ if (c->alloc < pa) {
+ if ((res = mp_grow (c, pa)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* number of output digits to produce */
+ pa = a->used + b->used;
+ _W = 0;
+ for (ix = digs; ix <= pa; ix++) {
+ int tx, ty, iy;
+ mp_digit *tmpx, *tmpy;
+
+ /* get offsets into the two bignums */
+ ty = MIN(b->used-1, ix);
+ tx = ix - ty;
+
+ /* setup temp aliases */
+ tmpx = a->dp + tx;
+ tmpy = b->dp + ty;
+
+ /* this is the number of times the loop will iterrate, essentially its
+ while (tx++ < a->used && ty-- >= 0) { ... }
+ */
+ iy = MIN(a->used-tx, ty+1);
+
+ /* execute loop */
+ for (iz = 0; iz < iy; iz++) {
+ _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
+ }
+
+ /* store term */
+ W[ix] = ((mp_digit)_W) & MP_MASK;
+
+ /* make next carry */
+ _W = _W >> ((mp_word)DIGIT_BIT);
+ }
+
+ /* setup dest */
+ olduse = c->used;
+ c->used = pa;
+
+ {
+ register mp_digit *tmpc;
+
+ tmpc = c->dp + digs;
+ for (ix = digs; ix <= pa; ix++) {
+ /* now extract the previous digit [below the carry] */
+ *tmpc++ = W[ix];
+ }
+
+ /* clear unused digits [that existed in the old copy of c] */
+ for (; ix < olduse; ix++) {
+ *tmpc++ = 0;
+ }
+ }
+ mp_clamp (c);
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_fast_s_mp_sqr.c 5765234e01ae11780dcaade97742404013b1da42
+++ bn_fast_s_mp_sqr.c 5765234e01ae11780dcaade97742404013b1da42
@@ -0,0 +1,129 @@
+#include <tommath.h>
+#ifdef BN_FAST_S_MP_SQR_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* fast squaring
+ *
+ * This is the comba method where the columns of the product
+ * are computed first then the carries are computed. This
+ * has the effect of making a very simple inner loop that
+ * is executed the most
+ *
+ * W2 represents the outer products and W the inner.
+ *
+ * A further optimizations is made because the inner
+ * products are of the form "A * B * 2". The *2 part does
+ * not need to be computed until the end which is good
+ * because 64-bit shifts are slow!
+ *
+ * Based on Algorithm 14.16 on pp.597 of HAC.
+ *
+ */
+/* the jist of squaring...
+
+you do like mult except the offset of the tmpx [one that starts closer to zero]
+can't equal the offset of tmpy. So basically you set up iy like before then you min it with
+(ty-tx) so that it never happens. You double all those you add in the inner loop
+
+After that loop you do the squares and add them in.
+
+Remove W2 and don't memset W
+
+*/
+
+int fast_s_mp_sqr (mp_int * a, mp_int * b)
+{
+ int olduse, res, pa, ix, iz;
+ mp_digit W[MP_WARRAY], *tmpx;
+ mp_word W1;
+
+ /* grow the destination as required */
+ pa = a->used + a->used;
+ if (b->alloc < pa) {
+ if ((res = mp_grow (b, pa)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* number of output digits to produce */
+ W1 = 0;
+ for (ix = 0; ix <= pa; ix++) {
+ int tx, ty, iy;
+ mp_word _W;
+ mp_digit *tmpy;
+
+ /* clear counter */
+ _W = 0;
+
+ /* get offsets into the two bignums */
+ ty = MIN(a->used-1, ix);
+ tx = ix - ty;
+
+ /* setup temp aliases */
+ tmpx = a->dp + tx;
+ tmpy = a->dp + ty;
+
+ /* this is the number of times the loop will iterrate, essentially its
+ while (tx++ < a->used && ty-- >= 0) { ... }
+ */
+ iy = MIN(a->used-tx, ty+1);
+
+ /* now for squaring tx can never equal ty
+ * we halve the distance since they approach at a rate of 2x
+ * and we have to round because odd cases need to be executed
+ */
+ iy = MIN(iy, (ty-tx+1)>>1);
+
+ /* execute loop */
+ for (iz = 0; iz < iy; iz++) {
+ _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
+ }
+
+ /* double the inner product and add carry */
+ _W = _W + _W + W1;
+
+ /* even columns have the square term in them */
+ if ((ix&1) == 0) {
+ _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]);
+ }
+
+ /* store it */
+ W[ix] = _W;
+
+ /* make next carry */
+ W1 = _W >> ((mp_word)DIGIT_BIT);
+ }
+
+ /* setup dest */
+ olduse = b->used;
+ b->used = a->used+a->used;
+
+ {
+ mp_digit *tmpb;
+ tmpb = b->dp;
+ for (ix = 0; ix < pa; ix++) {
+ *tmpb++ = W[ix] & MP_MASK;
+ }
+
+ /* clear unused digits [that existed in the old copy of c] */
+ for (; ix < olduse; ix++) {
+ *tmpb++ = 0;
+ }
+ }
+ mp_clamp (b);
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_mp_2expt.c c0a974c10b34a7d5fa7e677ae3d1293a4e290138
+++ bn_mp_2expt.c c0a974c10b34a7d5fa7e677ae3d1293a4e290138
@@ -0,0 +1,44 @@
+#include <tommath.h>
+#ifdef BN_MP_2EXPT_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* computes a = 2**b
+ *
+ * Simple algorithm which zeroes the int, grows it then just sets one bit
+ * as required.
+ */
+int
+mp_2expt (mp_int * a, int b)
+{
+ int res;
+
+ /* zero a as per default */
+ mp_zero (a);
+
+ /* grow a to accomodate the single bit */
+ if ((res = mp_grow (a, b / DIGIT_BIT + 1)) != MP_OKAY) {
+ return res;
+ }
+
+ /* set the used count of where the bit will go */
+ a->used = b / DIGIT_BIT + 1;
+
+ /* put the single bit in its place */
+ a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT);
+
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_mp_abs.c 5ee072348880edcf0c2830885697a4233734580d
+++ bn_mp_abs.c 5ee072348880edcf0c2830885697a4233734580d
@@ -0,0 +1,39 @@
+#include <tommath.h>
+#ifdef BN_MP_ABS_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* b = |a|
+ *
+ * Simple function copies the input and fixes the sign to positive
+ */
+int
+mp_abs (mp_int * a, mp_int * b)
+{
+ int res;
+
+ /* copy a to b */
+ if (a != b) {
+ if ((res = mp_copy (a, b)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* force the sign of b to positive */
+ b->sign = MP_ZPOS;
+
+ return MP_OKAY;
+}
+#endif
============================================================
--- bn_mp_add.c 0cc7225dceeea5eb317eb215e4417ee0f23dd4ae
+++ bn_mp_add.c 0cc7225dceeea5eb317eb215e4417ee0f23dd4ae
@@ -0,0 +1,49 @@
+#include <tommath.h>
+#ifdef BN_MP_ADD_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* high level addition (handles signs) */
+int mp_add (mp_int * a, mp_int * b, mp_int * c)
+{
+ int sa, sb, res;
+
+ /* get sign of both inputs */
+ sa = a->sign;
+ sb = b->sign;
+
+ /* handle two cases, not four */
+ if (sa == sb) {
+ /* both positive or both negative */
+ /* add their magnitudes, copy the sign */
+ c->sign = sa;
+ res = s_mp_add (a, b, c);
+ } else {
+ /* one positive, the other negative */
+ /* subtract the one with the greater magnitude from */
+ /* the one of the lesser magnitude. The result gets */
+ /* the sign of the one with the greater magnitude. */
+ if (mp_cmp_mag (a, b) == MP_LT) {
+ c->sign = sb;
+ res = s_mp_sub (b, a, c);
+ } else {
+ c->sign = sa;
+ res = s_mp_sub (a, b, c);
+ }
+ }
+ return res;
+}
+
+#endif
============================================================
--- bn_mp_add_d.c d6830e293314b416b519fede793966d4ecbfde57
+++ bn_mp_add_d.c d6830e293314b416b519fede793966d4ecbfde57
@@ -0,0 +1,105 @@
+#include <tommath.h>
+#ifdef BN_MP_ADD_D_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* single digit addition */
+int
+mp_add_d (mp_int * a, mp_digit b, mp_int * c)
+{
+ int res, ix, oldused;
+ mp_digit *tmpa, *tmpc, mu;
+
+ /* grow c as required */
+ if (c->alloc < a->used + 1) {
+ if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ /* if a is negative and |a| >= b, call c = |a| - b */
+ if (a->sign == MP_NEG && (a->used > 1 || a->dp[0] >= b)) {
+ /* temporarily fix sign of a */
+ a->sign = MP_ZPOS;
+
+ /* c = |a| - b */
+ res = mp_sub_d(a, b, c);
+
+ /* fix sign */
+ a->sign = c->sign = MP_NEG;
+
+ return res;
+ }
+
+ /* old number of used digits in c */
+ oldused = c->used;
+
+ /* sign always positive */
+ c->sign = MP_ZPOS;
+
+ /* source alias */
+ tmpa = a->dp;
+
+ /* destination alias */
+ tmpc = c->dp;
+
+ /* if a is positive */
+ if (a->sign == MP_ZPOS) {
+ /* add digit, after this we're propagating
+ * the carry.
+ */
+ *tmpc = *tmpa++ + b;
+ mu = *tmpc >> DIGIT_BIT;
+ *tmpc++ &= MP_MASK;
+
+ /* now handle rest of the digits */
+ for (ix = 1; ix < a->used; ix++) {
+ *tmpc = *tmpa++ + mu;
+ mu = *tmpc >> DIGIT_BIT;
+ *tmpc++ &= MP_MASK;
+ }
+ /* set final carry */
+ ix++;
+ *tmpc++ = mu;
+
+ /* setup size */
+ c->used = a->used + 1;
+ } else {
+ /* a was negative and |a| < b */
+ c->used = 1;
+
+ /* the result is a single digit */
+ if (a->used == 1) {
+ *tmpc++ = b - a->dp[0];
+ } else {
+ *tmpc++ = b;
+ }
+
+ /* setup count so the clearing of oldused
+ * can fall through correctly
+ */
+ ix = 1;
+ }
+
+ /* now zero to oldused */
+ while (ix++ < oldused) {
+ *tmpc++ = 0;
+ }
+ mp_clamp(c);
+
+ return MP_OKAY;
+}
+
+#endif
============================================================
--- bn_mp_addmod.c b15c4348f1d5f51ccb10b50d1206032b4e0e0c4c
+++ bn_mp_addmod.c b15c4348f1d5f51ccb10b50d1206032b4e0e0c4c
@@ -0,0 +1,37 @@
+#include <tommath.h>
+#ifdef BN_MP_ADDMOD_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
+ */
+
+/* d = a + b (mod c) */
+int
+mp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
+{
+ int res;
+ mp_int t;
+
+ if ((res = mp_init (&t)) != MP_OKAY) {
+ return res;
+ }
+
+ if ((res = mp_add (a, b, &t)) != MP_OKAY) {
+ mp_clear (&t);
+ return res;
+ }
+ res = mp_mod (&t, c, d);
+ mp_clear (&t);
+ return res;
+}
+#endif
============================================================
--- bn_mp_and.c 74d28d927a0271c274f0ff8195651d793c2307a1
+++ bn_mp_and.c