# HG changeset patch # User Matt Johnston # Date 1103471839 0 # Node ID a96ff234ff19107fbedd4a55f7829c9e50571b60 # Parent d29b64170cf0c2e21de7fb694ffad42e90500418# Parent cc04b085e7dd68007d69d297bda5e6ca952e4ad7 propagate of fc94c38452d9fd684a8e1eb9e3a73120aac0d38f and 3e4de4cbef3d9035a7b2f0c25e9f86e297f9f6d1 from branch 'au.asn.ucc.matt.ltm-orig' to 'au.asn.ucc.matt.ltm-db' diff -r d29b64170cf0 -r a96ff234ff19 Makefile.in --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Makefile.in Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,128 @@ +#Makefile for GCC +# +#Tom St Denis + +VPATH=@srcdir@ +srcdir=@srcdir@ + +# Dropbear takes flags from the toplevel makefile +CFLAGS += -I$(srcdir) + +#CFLAGS += -I./ -Wall -W -Wshadow -Wsign-compare + +#for speed +#CFLAGS += -O3 -funroll-loops + +#for size +#CFLAGS += -Os + +#x86 optimizations [should be valid for any GCC install though] +#CFLAGS += -fomit-frame-pointer + +VERSION=0.30 + +default: libtommath.a + +#default files to install +LIBNAME=libtommath.a +HEADERS=tommath.h + +#LIBPATH-The directory for libtomcrypt to be installed to. +#INCPATH-The directory to install the header files for libtommath. +#DATAPATH-The directory to install the pdf docs. +DESTDIR= +LIBPATH=/usr/lib +INCPATH=/usr/include +DATAPATH=/usr/share/doc/libtommath/pdf + +OBJECTS=bncore.o bn_mp_init.o bn_mp_clear.o bn_mp_exch.o bn_mp_grow.o bn_mp_shrink.o \ +bn_mp_clamp.o bn_mp_zero.o bn_mp_set.o bn_mp_set_int.o bn_mp_init_size.o bn_mp_copy.o \ +bn_mp_init_copy.o bn_mp_abs.o bn_mp_neg.o bn_mp_cmp_mag.o bn_mp_cmp.o bn_mp_cmp_d.o \ +bn_mp_rshd.o bn_mp_lshd.o bn_mp_mod_2d.o bn_mp_div_2d.o bn_mp_mul_2d.o bn_mp_div_2.o \ +bn_mp_mul_2.o bn_s_mp_add.o bn_s_mp_sub.o bn_fast_s_mp_mul_digs.o bn_s_mp_mul_digs.o \ +bn_fast_s_mp_mul_high_digs.o bn_s_mp_mul_high_digs.o bn_fast_s_mp_sqr.o bn_s_mp_sqr.o \ +bn_mp_add.o bn_mp_sub.o bn_mp_karatsuba_mul.o bn_mp_mul.o bn_mp_karatsuba_sqr.o \ +bn_mp_sqr.o bn_mp_div.o bn_mp_mod.o bn_mp_add_d.o bn_mp_sub_d.o bn_mp_mul_d.o \ +bn_mp_div_d.o bn_mp_mod_d.o bn_mp_expt_d.o bn_mp_addmod.o bn_mp_submod.o \ +bn_mp_mulmod.o bn_mp_sqrmod.o bn_mp_gcd.o bn_mp_lcm.o bn_fast_mp_invmod.o bn_mp_invmod.o \ +bn_mp_reduce.o bn_mp_montgomery_setup.o bn_fast_mp_montgomery_reduce.o bn_mp_montgomery_reduce.o \ +bn_mp_exptmod_fast.o bn_mp_exptmod.o bn_mp_2expt.o bn_mp_n_root.o bn_mp_jacobi.o bn_reverse.o \ +bn_mp_count_bits.o bn_mp_read_unsigned_bin.o bn_mp_read_signed_bin.o bn_mp_to_unsigned_bin.o \ +bn_mp_to_signed_bin.o bn_mp_unsigned_bin_size.o bn_mp_signed_bin_size.o \ +bn_mp_xor.o bn_mp_and.o bn_mp_or.o bn_mp_rand.o bn_mp_montgomery_calc_normalization.o \ +bn_mp_prime_is_divisible.o bn_prime_tab.o bn_mp_prime_fermat.o bn_mp_prime_miller_rabin.o \ +bn_mp_prime_is_prime.o bn_mp_prime_next_prime.o bn_mp_dr_reduce.o \ +bn_mp_dr_is_modulus.o bn_mp_dr_setup.o bn_mp_reduce_setup.o \ +bn_mp_toom_mul.o bn_mp_toom_sqr.o bn_mp_div_3.o bn_s_mp_exptmod.o \ +bn_mp_reduce_2k.o bn_mp_reduce_is_2k.o bn_mp_reduce_2k_setup.o \ +bn_mp_radix_smap.o bn_mp_read_radix.o bn_mp_toradix.o bn_mp_radix_size.o \ +bn_mp_fread.o bn_mp_fwrite.o bn_mp_cnt_lsb.o bn_error.o \ +bn_mp_init_multi.o bn_mp_clear_multi.o bn_prime_sizes_tab.o bn_mp_exteuclid.o bn_mp_toradix_n.o \ +bn_mp_prime_random_ex.o bn_mp_get_int.o bn_mp_sqrt.o bn_mp_is_square.o bn_mp_init_set.o \ +bn_mp_init_set_int.o + +libtommath.a: $(OBJECTS) + $(AR) $(ARFLAGS) libtommath.a $(OBJECTS) + $(RANLIB) libtommath.a + +install: libtommath.a + install -d -g root -o root $(DESTDIR)$(LIBPATH) + install -d -g root -o root $(DESTDIR)$(INCPATH) + install -g root -o root $(LIBNAME) $(DESTDIR)$(LIBPATH) + install -g root -o root $(HEADERS) $(DESTDIR)$(INCPATH) + +test: libtommath.a demo/demo.o + $(CC) demo/demo.o libtommath.a -o test + +mtest: test + cd mtest ; $(CC) $(CFLAGS) mtest.c -o mtest -s + +timing: libtommath.a + $(CC) $(CFLAGS) -DTIMER demo/demo.c libtommath.a -o ltmtest -s + +# makes the LTM book DVI file, requires tetex, perl and makeindex [part of tetex I think] +docdvi: tommath.src + cd pics ; make + echo "hello" > tommath.ind + perl booker.pl + latex tommath > /dev/null + latex tommath > /dev/null + makeindex tommath + latex tommath > /dev/null + +# poster, makes the single page PDF poster +poster: poster.tex + pdflatex poster + rm -f poster.aux poster.log + +# makes the LTM book PDF file, requires tetex, cleans up the LaTeX temp files +docs: docdvi + dvipdf tommath + rm -f tommath.log tommath.aux tommath.dvi tommath.idx tommath.toc tommath.lof tommath.ind tommath.ilg + cd pics ; make clean + +#LTM user manual +mandvi: bn.tex + echo "hello" > bn.ind + latex bn > /dev/null + latex bn > /dev/null + makeindex bn + latex bn > /dev/null + +#LTM user manual [pdf] +manual: mandvi + pdflatex bn >/dev/null + rm -f bn.aux bn.dvi bn.log bn.idx bn.lof bn.out bn.toc + +clean: + -rm -f *.bat *.pdf *.o *.a *.obj *.lib *.exe *.dll etclib/*.o demo/demo.o test ltmtest mpitest mtest/mtest mtest/mtest.exe \ + *.idx *.toc *.log *.aux *.dvi *.lof *.ind *.ilg *.ps *.log *.s mpi.c + -cd etc && make clean + -cd pics && make clean + +zipup: clean manual poster docs + perl gen.pl ; mv mpi.c pre_gen/ ; \ + cd .. ; rm -rf ltm* libtommath-$(VERSION) ; mkdir libtommath-$(VERSION) ; \ + cp -R ./libtommath/* ./libtommath-$(VERSION)/ ; \ + tar -c libtommath-$(VERSION)/* | bzip2 -9vvc > ltm-$(VERSION).tar.bz2 ; \ + zip -9 -r ltm-$(VERSION).zip libtommath-$(VERSION)/* diff -r d29b64170cf0 -r a96ff234ff19 bn_mp_exptmod.c diff -r d29b64170cf0 -r a96ff234ff19 bn_mp_mul.c diff -r d29b64170cf0 -r a96ff234ff19 bn_mp_sqr.c diff -r d29b64170cf0 -r a96ff234ff19 bn_prime_sizes_tab.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/bn_prime_sizes_tab.c Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,51 @@ +/* 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 + */ +#include + +/* this table gives the # of rabin miller trials for a prob of failure lower than 2^-96 */ +static const struct { + int k, t; +} sizes[] = { +{ 128, 28 }, +{ 256, 16 }, +{ 384, 10 }, +{ 512, 7 }, +{ 640, 6 }, +{ 768, 5 }, +{ 896, 4 }, +{ 1024, 4 }, +{ 1152, 3 }, +{ 1280, 3 }, +{ 1408, 3 }, +{ 1536, 3 }, +{ 1664, 3 }, +{ 1792, 2 } }; + +/* returns # of RM trials required for a given bit size */ +int mp_prime_rabin_miller_trials(int size) +{ + int x; + + for (x = 0; x < (int)(sizeof(sizes)/(sizeof(sizes[0]))); x++) { + if (sizes[x].k == size) { + return sizes[x].t; + } else if (sizes[x].k > size) { + return (x == 0) ? sizes[0].t : sizes[x - 1].t; + } + } + return 1; +} + + diff -r d29b64170cf0 -r a96ff234ff19 bncore.c diff -r d29b64170cf0 -r a96ff234ff19 demo/test.c diff -r d29b64170cf0 -r a96ff234ff19 etc/tuning/morwong.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/etc/tuning/morwong.txt Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,389 @@ +8, 39531752 +9, 30698772 +10, 28898844 +11, 27048918 +12, 25315654 +13, 23599056 +14, 21815794 +15, 20232524 +16, 18549258 +17, 16949322 +18, 15349386 +19, 14949402 +20, 14682746 +21, 14599416 +22, 14149434 +23, 13899444 +24, 13616122 +25, 13266136 +26, 12982814 +27, 12666160 +28, 12399504 +29, 12199512 +30, 11866192 +31, 11566204 +32, 11216218 +33, 11066224 +34, 10766236 +35, 10582910 +36, 10349586 +37, 10282922 +38, 10249590 +39, 10199592 +40, 10132928 +41, 10132928 +42, 10399584 +43, 10049598 +44, 10049598 +45, 10049598 +46, 9949602 +47, 9882938 +48, 9916270 +49, 9849606 +50, 9782942 +51, 9749610 +52, 9749610 +53, 9832940 +54, 9732944 +55, 9749610 +56, 9732944 +57, 9632948 +58, 9666280 +59, 9666280 +60, 9666280 +61, 9582950 +62, 9599616 +63, 9532952 +64, 9616282 +65, 9499620 +66, 9449622 +67, 9516286 +68, 9416290 +69, 9466288 +70, 9399624 +71, 9416290 +72, 9399624 +73, 9416290 +74, 9449622 +75, 9416290 +76, 9432956 +77, 9416290 +78, 9432956 +79, 9416290 +80, 9482954 +81, 9432956 +82, 9432956 +83, 9449622 +84, 9482954 +85, 9449622 +86, 9482954 +87, 9466288 +88, 9449622 +89, 9482954 +90, 9466288 +91, 9516286 +92, 9466288 +93, 9516286 +94, 9466288 +95, 9516286 +96, 9499620 +97, 9532952 +98, 9532952 +99, 9516286 +100, 9549618 +101, 9566284 +102, 9549618 +103, 9582950 +104, 9582950 +105, 9632948 +106, 9632948 +107, 9716278 +108, 9632948 +109, 9649614 +110, 9632948 +111, 9682946 +112, 9666280 +113, 9732944 +114, 9782942 +115, 9682946 +116, 9799608 +117, 9949602 +118, 9766276 +119, 9766276 +120, 9782942 +121, 9816274 +122, 9799608 +123, 9849606 +124, 9832940 +125, 9932936 +126, 9932936 +127, 10066264 +128, 9932936 +129, 9966268 +130, 10066264 +131, 9999600 +132, 10032932 +133, 10049598 +134, 10082930 +135, 10116262 +136, 10182926 +137, 10166260 +138, 10182926 +139, 10199592 +140, 10266256 +141, 10282922 +142, 10332920 +143, 10349586 +144, 10349586 +145, 10399584 +146, 10516246 +147, 10399584 +148, 10399584 +149, 10416250 +150, 10416250 +151, 10449582 +152, 10532912 +153, 10466248 +154, 10416250 +155, 10432916 +156, 10416250 +157, 10532912 +158, 10549578 +159, 10466248 +160, 10532912 +161, 10516246 +162, 10582910 +163, 10516246 +164, 10516246 +165, 10582910 +166, 10549578 +167, 10599576 +168, 10666240 +169, 10632908 +170, 10616242 +171, 10649574 +172, 10566244 +173, 10682906 +174, 10599576 +175, 10616242 +176, 10582910 +177, 10649574 +178, 10599576 +179, 10616242 +180, 10632908 +181, 10666240 +182, 10632908 +183, 10699572 +184, 10666240 +185, 10716238 +186, 10682906 +187, 10682906 +188, 10682906 +189, 10699572 +190, 10782902 +191, 10816234 +192, 10749570 +193, 10732904 +194, 10749570 +195, 10749570 +196, 10766236 +197, 10782902 +198, 10799568 +199, 10782902 +200, 10816234 +8, 18446744069448082980 +9, 26048958 +10, 24415690 +11, 22815754 +12, 21349146 +13, 19665880 +14, 18032612 +15, 16516006 +16, 14882738 +17, 13399464 +18, 12116182 +19, 11749530 +20, 11532872 +21, 11232884 +22, 10999560 +23, 10782902 +24, 10666240 +25, 10216258 +26, 9916270 +27, 9699612 +28, 9399624 +29, 9149634 +30, 9032972 +31, 8599656 +32, 8349666 +33, 8016346 +34, 7716358 +35, 7449702 +36, 7166380 +37, 7133048 +38, 7083050 +39, 7016386 +40, 6949722 +41, 6899724 +42, 6933056 +43, 6816394 +44, 6816394 +45, 6699732 +46, 6849726 +47, 7266376 +48, 6799728 +49, 6749730 +50, 6683066 +51, 6516406 +52, 6483074 +53, 6399744 +54, 6416410 +55, 6333080 +56, 6266416 +57, 6183086 +58, 6283082 +59, 6166420 +60, 6266416 +61, 6049758 +62, 6049758 +63, 5983094 +64, 5949762 +65, 5899764 +66, 5866432 +67, 5833100 +68, 5816434 +69, 5799768 +70, 5783102 +71, 5699772 +72, 5716438 +73, 5766436 +74, 5699772 +75, 5733104 +76, 5683106 +77, 5633108 +78, 5666440 +79, 5633108 +80, 5649774 +81, 5633108 +82, 5666440 +83, 5616442 +84, 5699772 +85, 5699772 +86, 5983094 +87, 5933096 +88, 6099756 +89, 5749770 +90, 5799768 +91, 5816434 +92, 5883098 +93, 5916430 +94, 5849766 +95, 5749770 +96, 5916430 +97, 5816434 +98, 5749770 +99, 5833100 +100, 5866432 +101, 6099756 +102, 6016426 +103, 5816434 +104, 5616442 +105, 5683106 +106, 5733104 +107, 5699772 +108, 5766436 +109, 5699772 +110, 5666440 +111, 5616442 +112, 5683106 +113, 5733104 +114, 5766436 +115, 5583110 +116, 5566444 +117, 5583110 +118, 5649774 +119, 5633108 +120, 5683106 +121, 5649774 +122, 5649774 +123, 5916430 +124, 5766436 +125, 5599776 +126, 5616442 +127, 5683106 +128, 5599776 +129, 5699772 +130, 5716438 +131, 5749770 +132, 5799768 +133, 5816434 +134, 5866432 +135, 5916430 +136, 5983094 +137, 6066424 +138, 6066424 +139, 6149754 +140, 6249750 +141, 6266416 +142, 6533072 +143, 6383078 +144, 6316414 +145, 6483074 +146, 6449742 +147, 6449742 +148, 6466408 +149, 6449742 +150, 6483074 +151, 6499740 +152, 6499740 +153, 6516406 +154, 6499740 +155, 6533072 +156, 6549738 +157, 6616402 +158, 6566404 +159, 6566404 +160, 6566404 +161, 6633068 +162, 6599736 +163, 6599736 +164, 6583070 +165, 6616402 +166, 6616402 +167, 6616402 +168, 6649734 +169, 6666400 +170, 6666400 +171, 6683066 +172, 6666400 +173, 6733064 +174, 6783062 +175, 6699732 +176, 6783062 +177, 6783062 +178, 6783062 +179, 6949722 +180, 6949722 +181, 6949722 +182, 6933056 +183, 6883058 +184, 6799728 +185, 7033052 +186, 7083050 +187, 6883058 +188, 6916390 +189, 6999720 +190, 7016386 +191, 6983054 +192, 6933056 +193, 7099716 +194, 7099716 +195, 7099716 +196, 7083050 +197, 7099716 +198, 7066384 +199, 7083050 +200, 7099716 + +Karatsuba Multiplier Cutoff: 70 +Karatsuba Squaring Cutoff: 116 diff -r d29b64170cf0 -r a96ff234ff19 etc/tuning/plod.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/etc/tuning/plod.txt Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,390 @@ +static gcc3.2.1 +8, 10763083022 +9, 8731135392 +10, 8283139944 +11, 7867362475 +12, 7444327653 +13, 7080711166 +14, 6720311143 +15, 6174334366 +16, 5758211592 +17, 5310146691 +18, 4934837262 +19, 4845026643 +20, 4808635899 +21, 4705978642 +22, 4637640999 +23, 4562910250 +24, 4498588248 +25, 4431288135 +26, 4365730339 +27, 4304060185 +28, 4245564825 +29, 4158227082 +30, 4084164405 +31, 4013151778 +32, 3948402079 +33, 3873113901 +34, 3819703326 +35, 3758040019 +36, 3713873303 +37, 3682402795 +38, 3675516805 +39, 3665721067 +40, 3653508535 +41, 3644694256 +42, 3634443778 +43, 3622761784 +44, 3617677891 +45, 3601731232 +46, 3594229129 +47, 3584239999 +48, 3578168863 +49, 3568747707 +50, 3563680942 +51, 3552132837 +52, 3546535036 +53, 3537026053 +54, 3532690062 +55, 3530645935 +56, 3517990435 +57, 3511844931 +58, 3524407951 +59, 3503995587 +60, 3498440712 +61, 3490858969 +62, 3485180392 +63, 3488661349 +64, 3479908069 +65, 3705227131 +66, 3469542342 +67, 3466325719 +68, 3465820384 +69, 3461375398 +70, 3460148488 +71, 3455986714 +72, 3452254999 +73, 3450682381 +74, 3462528321 +75, 3453588556 +76, 3454083670 +77, 3457375651 +78, 3459532852 +79, 3457783105 +80, 3457224032 +81, 3456356743 +82, 3457637218 +83, 3455475598 +84, 3457588015 +85, 3458784793 +86, 3463837992 +87, 3461411719 +88, 3461882104 +89, 3462925813 +90, 3461742318 +91, 3463500567 +92, 3466875822 +93, 3468508159 +94, 3475959531 +95, 3471664621 +96, 3472840635 +97, 3468354190 +98, 3476156227 +99, 3477589951 +100, 3477924730 +101, 3477721105 +102, 3482452294 +103, 3486231675 +104, 3488122918 +105, 3494132743 +106, 3496456464 +107, 3498625402 +108, 3503456512 +109, 3511624230 +110, 3511698429 +111, 3521258629 +112, 3521114290 +113, 3538344058 +114, 3534536145 +115, 3535474852 +116, 3543671416 +117, 3550273054 +118, 3555987991 +119, 3564402387 +120, 3564966036 +121, 3574456237 +122, 3581544468 +123, 3589574722 +124, 3590243835 +125, 3607690570 +126, 3603835098 +127, 3614553871 +128, 3621585633 +129, 3627185433 +130, 3638041368 +131, 3643569853 +132, 3650099725 +133, 3655197790 +134, 3666759163 +135, 3670036993 +136, 3677662603 +137, 3692026077 +138, 3695667120 +139, 3703015072 +140, 3709060014 +141, 3722619711 +142, 3961168006 +143, 3742564704 +144, 3744822465 +145, 3766348432 +146, 3768542629 +147, 3761170905 +148, 3760472506 +149, 3770597493 +150, 3774803245 +151, 3787814146 +152, 3769302172 +153, 3776419866 +154, 3774543492 +155, 3772203745 +156, 3777044845 +157, 3830703823 +158, 3801561894 +159, 3783683044 +160, 3783934240 +161, 3783404836 +162, 3783995062 +163, 3780910653 +164, 3784660860 +165, 3792781413 +166, 3788789127 +167, 3790347937 +168, 3800003887 +169, 3801798672 +170, 3802375911 +171, 3796540288 +172, 3800735452 +173, 3819776500 +174, 3811912999 +175, 3808459237 +176, 3986202106 +177, 3817351401 +178, 4161821377 +179, 4098030481 +180, 3964649227 +181, 3829593039 +182, 3906976549 +183, 3881003239 +184, 3828696105 +185, 3843488554 +186, 3834931599 +187, 3836671593 +188, 3837136363 +189, 3851219271 +190, 3852210226 +191, 3847715844 +192, 3843134424 +193, 3857401393 +194, 3856845723 +195, 3861346546 +196, 3862108942 +197, 3871399512 +198, 3875555779 +199, 3871960017 +200, 3868555966 +8, 9998019847 +9, 8112719494 +10, 7666821171 +11, 7270651356 +12, 6876799561 +13, 6460185180 +14, 6271353688 +15, 5572977279 +16, 5129928238 +17, 4663432314 +18, 4283655934 +19, 4182338574 +20, 4121785918 +21, 4030862187 +22, 3952692765 +23, 3872742780 +24, 3794493700 +25, 3707061876 +26, 3636390589 +27, 3543314677 +28, 3449649708 +29, 3372795516 +30, 3285271903 +31, 3214136109 +32, 3120224676 +33, 3040654564 +34, 2959830636 +35, 2867552502 +36, 2788670850 +37, 2767141536 +38, 2741473353 +39, 2717960943 +40, 2718671943 +41, 2685295489 +42, 2682424413 +43, 2662266840 +44, 2664347466 +45, 2636339644 +46, 2620922107 +47, 2605340305 +48, 2590075704 +49, 2566357824 +50, 2558147586 +51, 2539004770 +52, 2527568605 +53, 2508636420 +54, 2489025645 +55, 2479408146 +56, 2463215091 +57, 2436782461 +58, 2433128616 +59, 2419112079 +60, 2403462571 +61, 2378977491 +62, 2377973760 +63, 2356101849 +64, 2339063134 +65, 2324000979 +66, 2307373672 +67, 2293543860 +68, 2271394873 +69, 2259311622 +70, 2237170399 +71, 2220093969 +72, 2211080854 +73, 2196626124 +74, 2197712520 +75, 2196007890 +76, 2189716114 +77, 2191637361 +78, 2189268283 +79, 2183878113 +80, 2181678571 +81, 2178809298 +82, 2175383422 +83, 2174292687 +84, 2168604601 +85, 2173904635 +86, 2166229174 +87, 2166717825 +88, 2157826308 +89, 2156720644 +90, 2155717524 +91, 2152827906 +92, 2151295815 +93, 2148347050 +94, 2141565582 +95, 2145904603 +96, 2140514149 +97, 2136785677 +98, 2146814553 +99, 2140084342 +100, 2135675701 +101, 2130618826 +102, 2132557701 +103, 2136272818 +104, 2128485541 +105, 2124976582 +106, 2125628134 +107, 2121694765 +108, 2120612188 +109, 2128098618 +110, 2115573730 +111, 2121975234 +112, 2116319173 +113, 2112458632 +114, 2111251672 +115, 2112994632 +116, 2106747331 +117, 2343645321 +118, 2112892899 +119, 2106345406 +120, 2109520632 +121, 2111651403 +122, 2108802208 +123, 2108160670 +124, 2106500899 +125, 2106635679 +126, 2110818288 +127, 2104816428 +128, 2122281697 +129, 2154237739 +130, 2175271369 +131, 2202475416 +132, 2213810550 +133, 2257735950 +134, 2295610746 +135, 2312037906 +136, 2325799101 +137, 2479330737 +138, 2498572332 +139, 2559991446 +140, 2604135666 +141, 2625670147 +142, 2605407784 +143, 2547260022 +144, 2604600897 +145, 2704192557 +146, 2604338418 +147, 2610528138 +148, 2608159422 +149, 2627735718 +150, 2628565845 +151, 2624089824 +152, 2631465699 +153, 2651211846 +154, 2648246964 +155, 2648273322 +156, 2676230052 +157, 2775038886 +158, 2676298398 +159, 2669379396 +160, 2674033107 +161, 2725404096 +162, 2690395257 +163, 2690300772 +164, 2685161598 +165, 2717064093 +166, 2722663374 +167, 2712459540 +168, 2717776251 +169, 2737761450 +170, 2739853401 +171, 2740351518 +172, 2734908417 +173, 2768779437 +174, 2768375574 +175, 2765940537 +176, 2768918475 +177, 2804013975 +178, 2800135104 +179, 2795696631 +180, 2797841586 +181, 2834275920 +182, 2826912978 +183, 2825852676 +184, 2826697509 +185, 2857451745 +186, 2862833427 +187, 2860371837 +188, 2857683912 +189, 2895603777 +190, 2902579347 +191, 2891658744 +192, 2897834355 +193, 2929218435 +194, 2932943373 +195, 2933661258 +196, 2928966570 +197, 2972420745 +198, 2966698428 +199, 2968447254 +200, 2966822157 + +Karatsuba Multiplier Cutoff: 73 +Karatsuba Squaring Cutoff: 127 diff -r d29b64170cf0 -r a96ff234ff19 etc/tuning/sultana.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/etc/tuning/sultana.txt Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,94 @@ +gcc3.2.3 +New best: 49820000, 8 +New best: 42080000, 9 +New best: 40310000, 10 +New best: 38590000, 11 +New best: 36840000, 12 +New best: 34990000, 13 +New best: 33130000, 14 +New best: 31170000, 15 +New best: 29210000, 16 +New best: 27090000, 17 +New best: 25330000, 18 +New best: 24860000, 19 +New best: 24510000, 20 +New best: 24130000, 21 +New best: 23760000, 22 +New best: 23380000, 23 +New best: 22980000, 24 +New best: 22580000, 25 +New best: 22180000, 26 +New best: 21760000, 27 +New best: 21360000, 28 +New best: 20920000, 29 +New best: 20510000, 30 +New best: 20060000, 31 +New best: 19640000, 32 +New best: 19190000, 33 +New best: 18740000, 34 +New best: 18270000, 35 +New best: 17870000, 36 +New best: 17720000, 37 +New best: 17640000, 38 +New best: 17570000, 39 +New best: 17500000, 40 +New best: 17400000, 41 +New best: 17330000, 42 +New best: 17250000, 43 +New best: 17170000, 44 +New best: 17080000, 45 +New best: 17000000, 46 +New best: 16920000, 47 +New best: 16840000, 48 +New best: 16750000, 49 +New best: 16670000, 50 +New best: 16590000, 51 +New best: 16510000, 52 +New best: 16420000, 53 +New best: 16340000, 54 +New best: 16260000, 55 +New best: 16180000, 56 +New best: 16090000, 57 +New best: 16010000, 58 +New best: 15940000, 59 +New best: 15780000, 61 +New best: 15710000, 62 +New best: 15610000, 63 +New best: 15540000, 64 +New best: 15450000, 65 +New best: 15380000, 66 +New best: 15300000, 67 +New best: 15230000, 68 +New best: 15160000, 69 +New best: 15080000, 70 +New best: 15000000, 71 +New best: 14930000, 72 +New best: 14880000, 73 +New best: 14870000, 75 +New best: 14860000, 76 +New best: 14840000, 77 +New best: 14810000, 79 +New best: 14790000, 81 +New best: 14770000, 83 +New best: 14750000, 85 +New best: 14730000, 87 +New best: 14720000, 89 +New best: 14710000, 90 +New best: 14700000, 91 +New best: 14690000, 92 +New best: 14680000, 93 +New best: 14670000, 95 +New best: 14660000, 96 +New best: 14620000, 97 +New best: 14610000, 98 +New best: 14600000, 100 +New best: 14580000, 101 +New best: 14570000, 103 +New best: 14550000, 105 +New best: 14530000, 109 +New best: 14510000, 113 +New best: 14500000, 116 + 200 : 21530000 + +Karatsuba Multiplier Cutoff: 64 +Karatsuba Squaring Cutoff: 116 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/README --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/README Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,13 @@ +To use the pretty graphs you have to first build/run the ltmtest from the root directory of the package. +Todo this type + +make timing ; ltmtest + +in the root. It will run for a while [about ten minutes on most PCs] and produce a series of .log files in logs/. + +After doing that run "gnuplot graphs.dem" to make the PNGs. If you managed todo that all so far just open index.html to view +them all :-) + +Have fun + +Tom \ No newline at end of file diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/add.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/add.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,16 @@ +224 11069160 +448 9156136 +672 8089755 +896 7399424 +1120 6389352 +1344 5818648 +1568 5257112 +1792 4982160 +2016 4527856 +2240 4325312 +2464 4051760 +2688 3767640 +2912 3612520 +3136 3415208 +3360 3258656 +3584 3113360 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/addsub.png Binary file logs/k7/addsub.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/expt.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/expt.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,7 @@ +513 664 +769 256 +1025 117 +2049 17 +2561 9 +3073 5 +4097 2 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/expt.png Binary file logs/k7/expt.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/expt_dr.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/expt_dr.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,7 @@ +532 1088 +784 460 +1036 240 +1540 92 +2072 43 +3080 15 +4116 6 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/graphs.dem --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/graphs.dem Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +set terminal png color +set size 1.75 +set ylabel "Operations per Second" +set xlabel "Operand size (bits)" + +set output "addsub.png" +plot 'add.log' smooth bezier title "Addition", 'sub.log' smooth bezier title "Subtraction" + +set output "mult.png" +plot 'sqr.log' smooth bezier title "Squaring (without Karatsuba)", 'sqr_kara.log' smooth bezier title "Squaring (Karatsuba)", 'mult.log' smooth bezier title "Multiplication (without Karatsuba)", 'mult_kara.log' smooth bezier title "Multiplication (Karatsuba)" + +set output "expt.png" +plot 'expt.log' smooth bezier title "Exptmod (Montgomery)", 'expt_dr.log' smooth bezier title "Exptmod (Dimminished Radix)" + +set output "invmod.png" +plot 'invmod.log' smooth bezier title "Modular Inverse" + diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/invmod.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/invmod.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,32 @@ +112 16248 +224 8192 +336 5320 +448 3560 +560 2728 +672 2064 +784 1704 +896 2176 +1008 1184 +1120 976 +1232 1280 +1344 1176 +1456 624 +1568 912 +1680 504 +1792 452 +1904 658 +2016 608 +2128 336 +2240 312 +2352 288 +2464 264 +2576 408 +2688 376 +2800 354 +2912 198 +3024 307 +3136 173 +3248 162 +3360 256 +3472 145 +3584 226 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/invmod.png Binary file logs/k7/invmod.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/mult.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/mult.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 322904 +1344 151592 +1792 90472 +2240 59984 +2688 42624 +3136 31872 +3584 24704 +4032 19704 +4480 16096 +4928 13376 +5376 11272 +5824 9616 +6272 8360 +6720 7304 +7168 1664 +7616 1472 +8064 1328 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/mult.png Binary file logs/k7/mult.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/mult_kara.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/mult_kara.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 322872 +1344 151688 +1792 90480 +2240 59984 +2688 42656 +3136 32144 +3584 25840 +4032 21328 +4480 17856 +4928 14928 +5376 12856 +5824 11256 +6272 9880 +6720 8984 +7168 7928 +7616 7200 +8064 6576 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/sqr.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/sqr.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 415472 +1344 223736 +1792 141232 +2240 97624 +2688 71400 +3136 54800 +3584 16904 +4032 13528 +4480 10968 +4928 9128 +5376 7784 +5824 6672 +6272 5760 +6720 5056 +7168 4440 +7616 3952 +8064 3512 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/sqr_kara.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/sqr_kara.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 420464 +1344 224800 +1792 142808 +2240 97704 +2688 71416 +3136 54504 +3584 38320 +4032 32360 +4480 27576 +4928 23840 +5376 20688 +5824 18264 +6272 16176 +6720 14440 +7168 11688 +7616 10752 +8064 9936 diff -r d29b64170cf0 -r a96ff234ff19 logs/k7/sub.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/k7/sub.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,16 @@ +224 9728504 +448 8573648 +672 7488096 +896 6714064 +1120 5950472 +1344 5457400 +1568 5038896 +1792 4683632 +2016 4384656 +2240 4105976 +2464 3871608 +2688 3650680 +2912 3463552 +3136 3290016 +3360 3135272 +3584 2993848 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/README --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/README Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,13 @@ +To use the pretty graphs you have to first build/run the ltmtest from the root directory of the package. +Todo this type + +make timing ; ltmtest + +in the root. It will run for a while [about ten minutes on most PCs] and produce a series of .log files in logs/. + +After doing that run "gnuplot graphs.dem" to make the PNGs. If you managed todo that all so far just open index.html to view +them all :-) + +Have fun + +Tom \ No newline at end of file diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/add.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/add.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,16 @@ +224 8113248 +448 6585584 +672 5687678 +896 4761144 +1120 4111592 +1344 3995154 +1568 3532387 +1792 3225400 +2016 2963960 +2240 2720112 +2464 2533952 +2688 2307168 +2912 2287064 +3136 2150160 +3360 2035992 +3584 1936304 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/addsub.png Binary file logs/p4/addsub.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/expt.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/expt.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,7 @@ +513 195 +769 68 +1025 31 +2049 4 +2561 2 +3073 1 +4097 0 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/expt.png Binary file logs/p4/expt.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/expt_dr.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/expt_dr.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,7 @@ +532 393 +784 158 +1036 79 +1540 27 +2072 12 +3080 4 +4116 1 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/graphs.dem --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/graphs.dem Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +set terminal png color +set size 1.75 +set ylabel "Operations per Second" +set xlabel "Operand size (bits)" + +set output "addsub.png" +plot 'add.log' smooth bezier title "Addition", 'sub.log' smooth bezier title "Subtraction" + +set output "mult.png" +plot 'sqr.log' smooth bezier title "Squaring (without Karatsuba)", 'sqr_kara.log' smooth bezier title "Squaring (Karatsuba)", 'mult.log' smooth bezier title "Multiplication (without Karatsuba)", 'mult_kara.log' smooth bezier title "Multiplication (Karatsuba)" + +set output "expt.png" +plot 'expt.log' smooth bezier title "Exptmod (Montgomery)", 'expt_dr.log' smooth bezier title "Exptmod (Dimminished Radix)" + +set output "invmod.png" +plot 'invmod.log' smooth bezier title "Modular Inverse" + diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/invmod.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/invmod.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,32 @@ +112 13608 +224 6872 +336 4264 +448 2792 +560 2144 +672 1560 +784 1296 +896 1672 +1008 896 +1120 736 +1232 1024 +1344 888 +1456 472 +1568 680 +1680 373 +1792 328 +1904 484 +2016 436 +2128 232 +2240 211 +2352 200 +2464 177 +2576 293 +2688 262 +2800 251 +2912 137 +3024 216 +3136 117 +3248 113 +3360 181 +3472 98 +3584 158 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/invmod.png Binary file logs/p4/invmod.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/mult.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/mult.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 77600 +1344 35776 +1792 19688 +2240 13248 +2688 9424 +3136 7056 +3584 5464 +4032 4368 +4480 3568 +4928 2976 +5376 2520 +5824 2152 +6272 1872 +6720 1632 +7168 650 +7616 576 +8064 515 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/mult.png Binary file logs/p4/mult.png has changed diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/mult_kara.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/mult_kara.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 77752 +1344 35832 +1792 19688 +2240 14704 +2688 10832 +3136 8336 +3584 6600 +4032 5424 +4480 4648 +4928 3976 +5376 3448 +5824 3016 +6272 2664 +6720 2384 +7168 2120 +7616 1912 +8064 1752 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/sqr.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/sqr.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 128088 +1344 63640 +1792 37968 +2240 25488 +2688 18176 +3136 13672 +3584 4920 +4032 3912 +4480 3160 +4928 2616 +5376 2216 +5824 1896 +6272 1624 +6720 1408 +7168 1240 +7616 1096 +8064 984 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/sqr_kara.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/sqr_kara.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,17 @@ +896 127456 +1344 63752 +1792 37920 +2240 25440 +2688 18200 +3136 13728 +3584 10968 +4032 9072 +4480 7608 +4928 6440 +5376 5528 +5824 4768 +6272 4328 +6720 3888 +7168 3504 +7616 3176 +8064 2896 diff -r d29b64170cf0 -r a96ff234ff19 logs/p4/sub.log --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/logs/p4/sub.log Sun Dec 19 15:57:19 2004 +0000 @@ -0,0 +1,16 @@ +224 7355896 +448 6162880 +672 5218984 +896 4622776 +1120 3999320 +1344 3629480 +1568 3290384 +1792 2954752 +2016 2737056 +2240 2563320 +2464 2451928 +2688 2310920 +2912 2139048 +3136 2034080 +3360 1890800 +3584 1808624 diff -r d29b64170cf0 -r a96ff234ff19 mtest/mpi-config.h diff -r d29b64170cf0 -r a96ff234ff19 mtest/mpi.c diff -r d29b64170cf0 -r a96ff234ff19 mtest/mpi.h diff -r d29b64170cf0 -r a96ff234ff19 pics/makefile diff -r d29b64170cf0 -r a96ff234ff19 tommath.h