changeset 145:a96ff234ff19 libtommath

propagate of fc94c38452d9fd684a8e1eb9e3a73120aac0d38f and 3e4de4cbef3d9035a7b2f0c25e9f86e297f9f6d1 from branch 'au.asn.ucc.matt.ltm-orig' to 'au.asn.ucc.matt.ltm-db'
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 15:57:19 +0000
parents d29b64170cf0 (current diff) cc04b085e7dd (diff)
children 81bc23421b45
files bn_mp_exptmod.c bn_mp_mul.c bn_mp_sqr.c bncore.c mtest/mpi-config.h mtest/mpi.c mtest/mpi.h pics/makefile tommath.h
diffstat 35 files changed, 1404 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /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)/*
--- /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, [email protected], http://math.libtomcrypt.org
+ */
+#include <tommath.h>
+
+/* 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;
+}
+
+
--- /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
--- /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
--- /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
--- /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
--- /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
Binary file logs/k7/addsub.png has changed
--- /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
Binary file logs/k7/expt.png has changed
--- /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
--- /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"
+
--- /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
Binary file logs/k7/invmod.png has changed
--- /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
Binary file logs/k7/mult.png has changed
--- /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
--- /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
--- /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
--- /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
--- /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
--- /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
Binary file logs/p4/addsub.png has changed
--- /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
Binary file logs/p4/expt.png has changed
--- /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
--- /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"
+
--- /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
Binary file logs/p4/invmod.png has changed
--- /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
Binary file logs/p4/mult.png has changed
--- /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
--- /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
--- /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
--- /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