From b6a943f7197af1a5eb6bb028b9b808ec5016e30c Mon Sep 17 00:00:00 2001 From: Cy Schubert Date: Mon, 26 Jun 2023 15:56:52 -0700 Subject: heimdal: Vendor import f62e2f278 Heimdal 7.8.0 does not support OpenSSL 3.0. 7.9.0 will but it hasn't been released yet. We are importing f62e2f278 for its OpenSSL 3.0 support. --- lib/hcrypto/libtommath/etc/2kprime.1 | 2 + lib/hcrypto/libtommath/etc/2kprime.c | 81 +++++ lib/hcrypto/libtommath/etc/drprime.c | 67 ++++ lib/hcrypto/libtommath/etc/drprimes.28 | 25 ++ lib/hcrypto/libtommath/etc/drprimes.txt | 9 + lib/hcrypto/libtommath/etc/makefile | 44 +++ lib/hcrypto/libtommath/etc/makefile.icc | 67 ++++ lib/hcrypto/libtommath/etc/makefile.msvc | 24 ++ lib/hcrypto/libtommath/etc/mersenne.c | 138 ++++++++ lib/hcrypto/libtommath/etc/mont.c | 44 +++ lib/hcrypto/libtommath/etc/pprime.c | 411 +++++++++++++++++++++++ lib/hcrypto/libtommath/etc/prime.1024 | 414 +++++++++++++++++++++++ lib/hcrypto/libtommath/etc/prime.512 | 205 ++++++++++++ lib/hcrypto/libtommath/etc/timer.asm | 37 +++ lib/hcrypto/libtommath/etc/tune.c | 542 +++++++++++++++++++++++++++++++ lib/hcrypto/libtommath/etc/tune_it.sh | 107 ++++++ 16 files changed, 2217 insertions(+) create mode 100644 lib/hcrypto/libtommath/etc/2kprime.1 create mode 100644 lib/hcrypto/libtommath/etc/2kprime.c create mode 100644 lib/hcrypto/libtommath/etc/drprime.c create mode 100644 lib/hcrypto/libtommath/etc/drprimes.28 create mode 100644 lib/hcrypto/libtommath/etc/drprimes.txt create mode 100644 lib/hcrypto/libtommath/etc/makefile create mode 100644 lib/hcrypto/libtommath/etc/makefile.icc create mode 100644 lib/hcrypto/libtommath/etc/makefile.msvc create mode 100644 lib/hcrypto/libtommath/etc/mersenne.c create mode 100644 lib/hcrypto/libtommath/etc/mont.c create mode 100644 lib/hcrypto/libtommath/etc/pprime.c create mode 100644 lib/hcrypto/libtommath/etc/prime.1024 create mode 100644 lib/hcrypto/libtommath/etc/prime.512 create mode 100644 lib/hcrypto/libtommath/etc/timer.asm create mode 100644 lib/hcrypto/libtommath/etc/tune.c create mode 100755 lib/hcrypto/libtommath/etc/tune_it.sh (limited to 'lib/hcrypto/libtommath/etc') diff --git a/lib/hcrypto/libtommath/etc/2kprime.1 b/lib/hcrypto/libtommath/etc/2kprime.1 new file mode 100644 index 000000000000..c41ded1f9750 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/2kprime.1 @@ -0,0 +1,2 @@ +256-bits (k = 36113) = 115792089237316195423570985008687907853269984665640564039457584007913129603823 +512-bits (k = 38117) = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006045979 diff --git a/lib/hcrypto/libtommath/etc/2kprime.c b/lib/hcrypto/libtommath/etc/2kprime.c new file mode 100644 index 000000000000..95ed2de4227f --- /dev/null +++ b/lib/hcrypto/libtommath/etc/2kprime.c @@ -0,0 +1,81 @@ +/* Makes safe primes of a 2k nature */ +#include +#include + +static int sizes[] = {256, 512, 768, 1024, 1536, 2048, 3072, 4096}; + +int main(void) +{ + char buf[2000]; + size_t x; + mp_bool y; + mp_int q, p; + FILE *out; + clock_t t1; + mp_digit z; + + mp_init_multi(&q, &p, NULL); + + out = fopen("2kprime.1", "w"); + if (out != NULL) { + for (x = 0; x < (sizeof(sizes) / sizeof(sizes[0])); x++) { +top: + mp_2expt(&q, sizes[x]); + mp_add_d(&q, 3uL, &q); + z = -3; + + t1 = clock(); + for (;;) { + mp_sub_d(&q, 4uL, &q); + z += 4uL; + + if (z > MP_MASK) { + printf("No primes of size %d found\n", sizes[x]); + break; + } + + if ((clock() - t1) > CLOCKS_PER_SEC) { + printf("."); + fflush(stdout); + /* sleep((clock() - t1 + CLOCKS_PER_SEC/2)/CLOCKS_PER_SEC); */ + t1 = clock(); + } + + /* quick test on q */ + mp_prime_is_prime(&q, 1, &y); + if (y == MP_NO) { + continue; + } + + /* find (q-1)/2 */ + mp_sub_d(&q, 1uL, &p); + mp_div_2(&p, &p); + mp_prime_is_prime(&p, 3, &y); + if (y == MP_NO) { + continue; + } + + /* test on q */ + mp_prime_is_prime(&q, 3, &y); + if (y == MP_NO) { + continue; + } + + break; + } + + if (y == MP_NO) { + ++sizes[x]; + goto top; + } + + mp_to_decimal(&q, buf, sizeof(buf)); + printf("\n\n%d-bits (k = %lu) = %s\n", sizes[x], z, buf); + fprintf(out, "%d-bits (k = %lu) = %s\n", sizes[x], z, buf); + fflush(out); + } + fclose(out); + } + + return 0; +} diff --git a/lib/hcrypto/libtommath/etc/drprime.c b/lib/hcrypto/libtommath/etc/drprime.c new file mode 100644 index 000000000000..64e31ef10465 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/drprime.c @@ -0,0 +1,67 @@ +/* Makes safe primes of a DR nature */ +#include + +static int sizes[] = { 1+256/MP_DIGIT_BIT, 1+512/MP_DIGIT_BIT, 1+768/MP_DIGIT_BIT, 1+1024/MP_DIGIT_BIT, 1+2048/MP_DIGIT_BIT, 1+4096/MP_DIGIT_BIT }; + +int main(void) +{ + mp_bool res; + int x, y; + char buf[4096]; + FILE *out; + mp_int a, b; + + mp_init(&a); + mp_init(&b); + + out = fopen("drprimes.txt", "w"); + if (out != NULL) { + for (x = 0; x < (int)(sizeof(sizes)/sizeof(sizes[0])); x++) { +top: + printf("Seeking a %d-bit safe prime\n", sizes[x] * MP_DIGIT_BIT); + mp_grow(&a, sizes[x]); + mp_zero(&a); + for (y = 1; y < sizes[x]; y++) { + a.dp[y] = MP_MASK; + } + + /* make a DR modulus */ + a.dp[0] = -1; + a.used = sizes[x]; + + /* now loop */ + res = MP_NO; + for (;;) { + a.dp[0] += 4uL; + if (a.dp[0] >= MP_MASK) break; + mp_prime_is_prime(&a, 1, &res); + if (res == MP_NO) continue; + printf("."); + fflush(stdout); + mp_sub_d(&a, 1uL, &b); + mp_div_2(&b, &b); + mp_prime_is_prime(&b, 3, &res); + if (res == MP_NO) continue; + mp_prime_is_prime(&a, 3, &res); + if (res == MP_YES) break; + } + + if (res != MP_YES) { + printf("Error not DR modulus\n"); + sizes[x] += 1; + goto top; + } else { + mp_to_decimal(&a, buf, sizeof(buf)); + printf("\n\np == %s\n\n", buf); + fprintf(out, "%d-bit prime:\np == %s\n\n", mp_count_bits(&a), buf); + fflush(out); + } + } + fclose(out); + } + + mp_clear(&a); + mp_clear(&b); + + return 0; +} diff --git a/lib/hcrypto/libtommath/etc/drprimes.28 b/lib/hcrypto/libtommath/etc/drprimes.28 new file mode 100644 index 000000000000..9d438ad1dba5 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/drprimes.28 @@ -0,0 +1,25 @@ +DR safe primes for 28-bit digits. + +224-bit prime: +p == 26959946667150639794667015087019630673637144422540572481103341844143 + +532-bit prime: +p == 14059105607947488696282932836518693308967803494693489478439861164411992439598399594747002144074658928593502845729752797260025831423419686528151609940203368691747 + +784-bit prime: +p == 101745825697019260773923519755878567461315282017759829107608914364075275235254395622580447400994175578963163918967182013639660669771108475957692810857098847138903161308502419410142185759152435680068435915159402496058513611411688900243039 + +1036-bit prime: +p == 736335108039604595805923406147184530889923370574768772191969612422073040099331944991573923112581267542507986451953227192970402893063850485730703075899286013451337291468249027691733891486704001513279827771740183629161065194874727962517148100775228363421083691764065477590823919364012917984605619526140821798437127 + +1540-bit prime: +p == 38564998830736521417281865696453025806593491967131023221754800625044118265468851210705360385717536794615180260494208076605798671660719333199513807806252394423283413430106003596332513246682903994829528690198205120921557533726473585751382193953592127439965050261476810842071573684505878854588706623484573925925903505747545471088867712185004135201289273405614415899438276535626346098904241020877974002916168099951885406379295536200413493190419727789712076165162175783 + +2072-bit prime: +p == 542189391331696172661670440619180536749994166415993334151601745392193484590296600979602378676624808129613777993466242203025054573692562689251250471628358318743978285860720148446448885701001277560572526947619392551574490839286458454994488665744991822837769918095117129546414124448777033941223565831420390846864429504774477949153794689948747680362212954278693335653935890352619041936727463717926744868338358149568368643403037768649616778526013610493696186055899318268339432671541328195724261329606699831016666359440874843103020666106568222401047720269951530296879490444224546654729111504346660859907296364097126834834235287147 + +3080-bit prime: +p == 1487259134814709264092032648525971038895865645148901180585340454985524155135260217788758027400478312256339496385275012465661575576202252063145698732079880294664220579764848767704076761853197216563262660046602703973050798218246170835962005598561669706844469447435461092542265792444947706769615695252256130901271870341005768912974433684521436211263358097522726462083917939091760026658925757076733484173202927141441492573799914240222628795405623953109131594523623353044898339481494120112723445689647986475279242446083151413667587008191682564376412347964146113898565886683139407005941383669325997475076910488086663256335689181157957571445067490187939553165903773554290260531009121879044170766615232300936675369451260747671432073394867530820527479172464106442450727640226503746586340279816318821395210726268291535648506190714616083163403189943334431056876038286530365757187367147446004855912033137386225053275419626102417236133948503 + +4116-bit prime: +p == 1095121115716677802856811290392395128588168592409109494900178008967955253005183831872715423151551999734857184538199864469605657805519106717529655044054833197687459782636297255219742994736751541815269727940751860670268774903340296040006114013971309257028332849679096824800250742691718610670812374272414086863715763724622797509437062518082383056050144624962776302147890521249477060215148275163688301275847155316042279405557632639366066847442861422164832655874655824221577849928863023018366835675399949740429332468186340518172487073360822220449055340582568461568645259954873303616953776393853174845132081121976327462740354930744487429617202585015510744298530101547706821590188733515880733527449780963163909830077616357506845523215289297624086914545378511082534229620116563260168494523906566709418166011112754529766183554579321224940951177394088465596712620076240067370589036924024728375076210477267488679008016579588696191194060127319035195370137160936882402244399699172017835144537488486396906144217720028992863941288217185353914991583400421682751000603596655790990815525126154394344641336397793791497068253936771017031980867706707490224041075826337383538651825493679503771934836094655802776331664261631740148281763487765852746577808019633679 diff --git a/lib/hcrypto/libtommath/etc/drprimes.txt b/lib/hcrypto/libtommath/etc/drprimes.txt new file mode 100644 index 000000000000..7c97f67b9c5f --- /dev/null +++ b/lib/hcrypto/libtommath/etc/drprimes.txt @@ -0,0 +1,9 @@ +300-bit prime: +p == 2037035976334486086268445688409378161051468393665936250636140449354381298610415201576637819 + +540-bit prime: +p == 3599131035634557106248430806148785487095757694641533306480604458089470064537190296255232548883112685719936728506816716098566612844395439751206810991770626477344739 + +780-bit prime: +p == 6359114106063703798370219984742410466332205126109989319225557147754704702203399726411277962562135973685197744935448875852478791860694279747355800678568677946181447581781401213133886609947027230004277244697462656003655947791725966271167 + diff --git a/lib/hcrypto/libtommath/etc/makefile b/lib/hcrypto/libtommath/etc/makefile new file mode 100644 index 000000000000..85bb09efc430 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/makefile @@ -0,0 +1,44 @@ +LTM_CFLAGS += -Wall -W -Wextra -Wshadow -O3 -I../ +LTM_CFLAGS += $(CFLAGS) + +# default lib name (requires install with root) +# LIBNAME=-ltommath + +# libname when you can't install the lib with install +LIBNAME=../libtommath.a + +#provable primes +pprime: pprime.o + $(CC) $(LTM_CFLAGS) pprime.o $(LIBNAME) -o pprime + +# portable [well requires clock()] tuning app +tune: tune.o + $(CC) $(LTM_CFLAGS) tune.o $(LIBNAME) -o tune + ./tune_it.sh + +test_standalone: tune.o + # The benchmark program works as a testtool, too + $(CC) $(LTM_CFLAGS) tune.o $(LIBNAME) -o test + +# spits out mersenne primes +mersenne: mersenne.o + $(CC) $(LTM_CFLAGS) mersenne.o $(LIBNAME) -o mersenne + +# finds DR safe primes for the given config +drprime: drprime.o + $(CC) $(LTM_CFLAGS) drprime.o $(LIBNAME) -o drprime + +# finds 2k safe primes for the given config +2kprime: 2kprime.o + $(CC) $(LTM_CFLAGS) 2kprime.o $(LIBNAME) -o 2kprime + +mont: mont.o + $(CC) $(LTM_CFLAGS) mont.o $(LIBNAME) -o mont + + +clean: + rm -f *.log *.o *.obj *.exe pprime tune mersenne drprime mont 2kprime pprime.dat \ + tuning_list multiplying squaring test *.da *.dyn *.dpi *~ + rm -rf .libs + +.PHONY: tune diff --git a/lib/hcrypto/libtommath/etc/makefile.icc b/lib/hcrypto/libtommath/etc/makefile.icc new file mode 100644 index 000000000000..9217f7b1dc2d --- /dev/null +++ b/lib/hcrypto/libtommath/etc/makefile.icc @@ -0,0 +1,67 @@ +CC = icc + +CFLAGS += -I../ + +# optimize for SPEED +# +# -mcpu= can be pentium, pentiumpro (covers PII through PIII) or pentium4 +# -ax? specifies make code specifically for ? but compatible with IA-32 +# -x? specifies compile solely for ? [not specifically IA-32 compatible] +# +# where ? is +# K - PIII +# W - first P4 [Williamette] +# N - P4 Northwood +# P - P4 Prescott +# B - Blend of P4 and PM [mobile] +# +# Default to just generic max opts +CFLAGS += -O3 -xP -ip + +# default lib name (requires install with root) +# LIBNAME=-ltommath + +# libname when you can't install the lib with install +LIBNAME=../libtommath.a + +#provable primes +pprime: pprime.o + $(CC) pprime.o $(LIBNAME) -o pprime + +tune: tune.o + $(CC) $(CFLAGS) tune.o $(LIBNAME) -o tune + ./tune_it.sh + +# same app but using RDTSC for higher precision [requires 80586+], coff based gcc installs [e.g. ming, cygwin, djgpp] +tune86: tune.c + nasm -f coff timer.asm + $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86 + +# for cygwin +tune86c: tune.c + nasm -f gnuwin32 timer.asm + $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86 + +#make tune86 for linux or any ELF format +tune86l: tune.c + nasm -f elf -DUSE_ELF timer.asm + $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86l + +# spits out mersenne primes +mersenne: mersenne.o + $(CC) mersenne.o $(LIBNAME) -o mersenne + +# fines DR safe primes for the given config +drprime: drprime.o + $(CC) drprime.o $(LIBNAME) -o drprime + +# fines 2k safe primes for the given config +2kprime: 2kprime.o + $(CC) 2kprime.o $(LIBNAME) -o 2kprime + +mont: mont.o + $(CC) mont.o $(LIBNAME) -o mont + + +clean: + rm -f *.log *.o *.obj *.exe pprime tune mersenne drprime tune86 tune86l mont 2kprime pprime.dat *.il tuning_list diff --git a/lib/hcrypto/libtommath/etc/makefile.msvc b/lib/hcrypto/libtommath/etc/makefile.msvc new file mode 100644 index 000000000000..592a43715c1b --- /dev/null +++ b/lib/hcrypto/libtommath/etc/makefile.msvc @@ -0,0 +1,24 @@ +#MSVC Makefile +# +#Tom St Denis + +CFLAGS = /I../ /Ox /DWIN32 /W3 + +pprime: pprime.obj + cl pprime.obj ../tommath.lib + +mersenne: mersenne.obj + cl mersenne.obj ../tommath.lib + +tune: tune.obj + cl tune.obj ../tommath.lib + + +mont: mont.obj + cl mont.obj ../tommath.lib + +drprime: drprime.obj + cl drprime.obj ../tommath.lib + +2kprime: 2kprime.obj + cl 2kprime.obj ../tommath.lib diff --git a/lib/hcrypto/libtommath/etc/mersenne.c b/lib/hcrypto/libtommath/etc/mersenne.c new file mode 100644 index 000000000000..0c9f52fcf864 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/mersenne.c @@ -0,0 +1,138 @@ +/* Finds Mersenne primes using the Lucas-Lehmer test + * + * Tom St Denis, tomstdenis@gmail.com + */ +#include +#include + +static mp_err is_mersenne(long s, mp_bool *pp) +{ + mp_int n, u; + mp_err res; + int k; + + *pp = MP_NO; + + if ((res = mp_init(&n)) != MP_OKAY) { + return res; + } + + if ((res = mp_init(&u)) != MP_OKAY) { + goto LBL_N; + } + + /* n = 2^s - 1 */ + if ((res = mp_2expt(&n, (int)s)) != MP_OKAY) { + goto LBL_MU; + } + if ((res = mp_sub_d(&n, 1uL, &n)) != MP_OKAY) { + goto LBL_MU; + } + + /* set u=4 */ + mp_set(&u, 4uL); + + /* for k=1 to s-2 do */ + for (k = 1; k <= (s - 2); k++) { + /* u = u^2 - 2 mod n */ + if ((res = mp_sqr(&u, &u)) != MP_OKAY) { + goto LBL_MU; + } + if ((res = mp_sub_d(&u, 2uL, &u)) != MP_OKAY) { + goto LBL_MU; + } + + /* make sure u is positive */ + while (u.sign == MP_NEG) { + if ((res = mp_add(&u, &n, &u)) != MP_OKAY) { + goto LBL_MU; + } + } + + /* reduce */ + if ((res = mp_reduce_2k(&u, &n, 1uL)) != MP_OKAY) { + goto LBL_MU; + } + } + + /* if u == 0 then its prime */ + if (mp_iszero(&u) == MP_YES) { + mp_prime_is_prime(&n, 8, pp); + if (*pp != MP_YES) printf("FAILURE\n"); + } + + res = MP_OKAY; +LBL_MU: + mp_clear(&u); +LBL_N: + mp_clear(&n); + return res; +} + +/* square root of a long < 65536 */ +static long i_sqrt(long x) +{ + long x1, x2; + + x2 = 16; + do { + x1 = x2; + x2 = x1 - ((x1 * x1) - x) / (2 * x1); + } while (x1 != x2); + + if ((x1 * x1) > x) { + --x1; + } + + return x1; +} + +/* is the long prime by brute force */ +static int isprime(long k) +{ + long y, z; + + y = i_sqrt(k); + for (z = 2; z <= y; z++) { + if ((k % z) == 0) + return 0; + } + return 1; +} + + +int main(void) +{ + mp_bool pp; + long k; + clock_t tt; + + k = 3; + + for (;;) { + /* start time */ + tt = clock(); + + /* test if 2^k - 1 is prime */ + if (is_mersenne(k, &pp) != MP_OKAY) { + printf("Whoa error\n"); + return -1; + } + + if (pp == MP_YES) { + /* count time */ + tt = clock() - tt; + + /* display if prime */ + printf("2^%-5ld - 1 is prime, test took %ld ticks\n", k, (long)tt); + } + + /* goto next odd exponent */ + k += 2; + + /* but make sure its prime */ + while (isprime(k) == 0) { + k += 2; + } + } +} diff --git a/lib/hcrypto/libtommath/etc/mont.c b/lib/hcrypto/libtommath/etc/mont.c new file mode 100644 index 000000000000..4652410d0c09 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/mont.c @@ -0,0 +1,44 @@ +/* tests the montgomery routines */ +#include +#include +#include + +int main(void) +{ + mp_int modulus, R, p, pp; + mp_digit mp; + int x, y; + + srand(time(NULL)); + mp_init_multi(&modulus, &R, &p, &pp, NULL); + + /* loop through various sizes */ + for (x = 4; x < 256; x++) { + printf("DIGITS == %3d...", x); + fflush(stdout); + + /* make up the odd modulus */ + mp_rand(&modulus, x); + modulus.dp[0] |= 1uL; + + /* now find the R value */ + mp_montgomery_calc_normalization(&R, &modulus); + mp_montgomery_setup(&modulus, &mp); + + /* now run through a bunch tests */ + for (y = 0; y < 1000; y++) { + mp_rand(&p, x/2); /* p = random */ + mp_mul(&p, &R, &pp); /* pp = R * p */ + mp_montgomery_reduce(&pp, &modulus, mp); + + /* should be equal to p */ + if (mp_cmp(&pp, &p) != MP_EQ) { + printf("FAILURE!\n"); + exit(-1); + } + } + printf("PASSED\n"); + } + + return 0; +} diff --git a/lib/hcrypto/libtommath/etc/pprime.c b/lib/hcrypto/libtommath/etc/pprime.c new file mode 100644 index 000000000000..009a18cb9227 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/pprime.c @@ -0,0 +1,411 @@ +/* Generates provable primes + * + * See http://gmail.com:8080/papers/pp.pdf for more info. + * + * Tom St Denis, tomstdenis@gmail.com, http://tom.gmail.com + */ +#include +#include +#include "tommath.h" + +static int n_prime; +static FILE *primes; + +/* fast square root */ +static mp_digit i_sqrt(mp_word x) +{ + mp_word x1, x2; + + x2 = x; + do { + x1 = x2; + x2 = x1 - ((x1 * x1) - x) / (2u * x1); + } while (x1 != x2); + + if ((x1 * x1) > x) { + --x1; + } + + return x1; +} + + +/* generates a prime digit */ +static void gen_prime(void) +{ + mp_digit r, x, y, next; + FILE *out; + + out = fopen("pprime.dat", "wb"); + if (out != NULL) { + + /* write first set of primes */ + /* *INDENT-OFF* */ + r = 3uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 5uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 7uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 11uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 13uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 17uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 19uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 23uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 29uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + r = 31uL; fwrite(&r, 1uL, sizeof(mp_digit), out); + /* *INDENT-ON* */ + + /* get square root, since if 'r' is composite its factors must be < than this */ + y = i_sqrt(r); + next = (y + 1uL) * (y + 1uL); + + for (;;) { + do { + r += 2uL; /* next candidate */ + r &= MP_MASK; + if (r < 31uL) break; + + /* update sqrt ? */ + if (next <= r) { + ++y; + next = (y + 1uL) * (y + 1uL); + } + + /* loop if divisible by 3,5,7,11,13,17,19,23,29 */ + if ((r % 3uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 5uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 7uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 11uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 13uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 17uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 19uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 23uL) == 0uL) { + x = 0uL; + continue; + } + if ((r % 29uL) == 0uL) { + x = 0uL; + continue; + } + + /* now check if r is divisible by x + k={1,7,11,13,17,19,23,29} */ + for (x = 30uL; x <= y; x += 30uL) { + if ((r % (x + 1uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 7uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 11uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 13uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 17uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 19uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 23uL)) == 0uL) { + x = 0uL; + break; + } + if ((r % (x + 29uL)) == 0uL) { + x = 0uL; + break; + } + } + } while (x == 0uL); + if (r > 31uL) { + fwrite(&r, 1uL, sizeof(mp_digit), out); + printf("%9lu\r", r); + fflush(stdout); + } + if (r < 31uL) break; + } + + fclose(out); + } +} + +static void load_tab(void) +{ + primes = fopen("pprime.dat", "rb"); + if (primes == NULL) { + gen_prime(); + primes = fopen("pprime.dat", "rb"); + } + fseek(primes, 0L, SEEK_END); + n_prime = ftell(primes) / sizeof(mp_digit); +} + +static mp_digit prime_digit(void) +{ + int n; + mp_digit d; + + n = abs(rand()) % n_prime; + fseek(primes, n * sizeof(mp_digit), SEEK_SET); + fread(&d, 1uL, sizeof(mp_digit), primes); + return d; +} + + +/* makes a prime of at least k bits */ +static mp_err pprime(int k, int li, mp_int *p, mp_int *q) +{ + mp_int a, b, c, n, x, y, z, v; + mp_err res; + int ii; + static const mp_digit bases[] = { 2, 3, 5, 7, 11, 13, 17, 19 }; + + /* single digit ? */ + if (k <= (int) MP_DIGIT_BIT) { + mp_set(p, prime_digit()); + return MP_OKAY; + } + + if ((res = mp_init(&c)) != MP_OKAY) { + return res; + } + + if ((res = mp_init(&v)) != MP_OKAY) { + goto LBL_C; + } + + /* product of first 50 primes */ + if ((res = + mp_read_radix(&v, + "19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190", + 10)) != MP_OKAY) { + goto LBL_V; + } + + if ((res = mp_init(&a)) != MP_OKAY) { + goto LBL_V; + } + + /* set the prime */ + mp_set(&a, prime_digit()); + + if ((res = mp_init(&b)) != MP_OKAY) { + goto LBL_A; + } + + if ((res = mp_init(&n)) != MP_OKAY) { + goto LBL_B; + } + + if ((res = mp_init(&x)) != MP_OKAY) { + goto LBL_N; + } + + if ((res = mp_init(&y)) != MP_OKAY) { + goto LBL_X; + } + + if ((res = mp_init(&z)) != MP_OKAY) { + goto LBL_Y; + } + + /* now loop making the single digit */ + while (mp_count_bits(&a) < k) { + fprintf(stderr, "prime has %4d bits left\r", k - mp_count_bits(&a)); + fflush(stderr); +top: + mp_set(&b, prime_digit()); + + /* now compute z = a * b * 2 */ + if ((res = mp_mul(&a, &b, &z)) != MP_OKAY) { /* z = a * b */ + goto LBL_Z; + } + + if ((res = mp_copy(&z, &c)) != MP_OKAY) { /* c = a * b */ + goto LBL_Z; + } + + if ((res = mp_mul_2(&z, &z)) != MP_OKAY) { /* z = 2 * a * b */ + goto LBL_Z; + } + + /* n = z + 1 */ + if ((res = mp_add_d(&z, 1uL, &n)) != MP_OKAY) { /* n = z + 1 */ + goto LBL_Z; + } + + /* check (n, v) == 1 */ + if ((res = mp_gcd(&n, &v, &y)) != MP_OKAY) { /* y = (n, v) */ + goto LBL_Z; + } + + if (mp_cmp_d(&y, 1uL) != MP_EQ) + goto top; + + /* now try base x=bases[ii] */ + for (ii = 0; ii < li; ii++) { + mp_set(&x, bases[ii]); + + /* compute x^a mod n */ + if ((res = mp_exptmod(&x, &a, &n, &y)) != MP_OKAY) { /* y = x^a mod n */ + goto LBL_Z; + } + + /* if y == 1 loop */ + if (mp_cmp_d(&y, 1uL) == MP_EQ) + continue; + + /* now x^2a mod n */ + if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2a mod n */ + goto LBL_Z; + } + + if (mp_cmp_d(&y, 1uL) == MP_EQ) + continue; + + /* compute x^b mod n */ + if ((res = mp_exptmod(&x, &b, &n, &y)) != MP_OKAY) { /* y = x^b mod n */ + goto LBL_Z; + } + + /* if y == 1 loop */ + if (mp_cmp_d(&y, 1uL) == MP_EQ) + continue; + + /* now x^2b mod n */ + if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2b mod n */ + goto LBL_Z; + } + + if (mp_cmp_d(&y, 1uL) == MP_EQ) + continue; + + /* compute x^c mod n == x^ab mod n */ + if ((res = mp_exptmod(&x, &c, &n, &y)) != MP_OKAY) { /* y = x^ab mod n */ + goto LBL_Z; + } + + /* if y == 1 loop */ + if (mp_cmp_d(&y, 1uL) == MP_EQ) + continue; + + /* now compute (x^c mod n)^2 */ + if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2ab mod n */ + goto LBL_Z; + } + + /* y should be 1 */ + if (mp_cmp_d(&y, 1uL) != MP_EQ) + continue; + break; + } + + /* no bases worked? */ + if (ii == li) + goto top; + + { + char buf[4096]; + + mp_to_decimal(&n, buf, sizeof(buf)); + printf("Certificate of primality for:\n%s\n\n", buf); + mp_to_decimal(&a, buf, sizeof(buf)); + printf("A == \n%s\n\n", buf); + mp_to_decimal(&b, buf, sizeof(buf)); + printf("B == \n%s\n\nG == %lu\n", buf, bases[ii]); + printf("----------------------------------------------------------------\n"); + } + + /* a = n */ + mp_copy(&n, &a); + } + + /* get q to be the order of the large prime subgroup */ + mp_sub_d(&n, 1uL, q); + mp_div_2(q, q); + mp_div(q, &b, q, NULL); + + mp_exch(&n, p); + + res = MP_OKAY; +LBL_Z: + mp_clear(&z); +LBL_Y: + mp_clear(&y); +LBL_X: + mp_clear(&x); +LBL_N: + mp_clear(&n); +LBL_B: + mp_clear(&b); +LBL_A: + mp_clear(&a); +LBL_V: + mp_clear(&v); +LBL_C: + mp_clear(&c); + return res; +} + + +int main(void) +{ + mp_int p, q; + char buf[4096]; + int k, li; + clock_t t1; + + srand(time(NULL)); + load_tab(); + + printf("Enter # of bits: \n"); + fgets(buf, sizeof(buf), stdin); + sscanf(buf, "%d", &k); + + printf("Enter number of bases to try (1 to 8):\n"); + fgets(buf, sizeof(buf), stdin); + sscanf(buf, "%d", &li); + + + mp_init(&p); + mp_init(&q); + + t1 = clock(); + pprime(k, li, &p, &q); + t1 = clock() - t1; + + printf("\n\nTook %d ticks, %d bits\n", t1, mp_count_bits(&p)); + + mp_to_decimal(&p, buf, sizeof(buf)); + printf("P == %s\n", buf); + mp_to_decimal(&q, buf, sizeof(buf)); + printf("Q == %s\n", buf); + + return 0; +} diff --git a/lib/hcrypto/libtommath/etc/prime.1024 b/lib/hcrypto/libtommath/etc/prime.1024 new file mode 100644 index 000000000000..5636e2da0985 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/prime.1024 @@ -0,0 +1,414 @@ +Enter # of bits: +Enter number of bases to try (1 to 8): +Certificate of primality for: +36360080703173363 + +A == +89963569 + +B == +202082249 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +4851595597739856136987139 + +A == +36360080703173363 + +B == +66715963 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +19550639734462621430325731591027 + +A == +4851595597739856136987139 + +B == +2014867 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +10409036141344317165691858509923818734539 + +A == +19550639734462621430325731591027 + +B == +266207047 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1049829549988285012736475602118094726647504414203 + +A == +10409036141344317165691858509923818734539 + +B == +50428759 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +77194737385528288387712399596835459931920358844586615003 + +A == +1049829549988285012736475602118094726647504414203 + +B == +36765367 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +35663756695365208574443215955488689578374232732893628896541201763 + +A == +77194737385528288387712399596835459931920358844586615003 + +B == +230998627 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +16711831463502165169495622246023119698415848120292671294127567620396469803 + +A == +35663756695365208574443215955488689578374232732893628896541201763 + +B == +234297127 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +6163534781560285962890718925972249753147470953579266394395432475622345597103528739 + +A == +16711831463502165169495622246023119698415848120292671294127567620396469803 + +B == +184406323 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +814258256205243497704094951432575867360065658372158511036259934640748088306764553488803787 + +A == +6163534781560285962890718925972249753147470953579266394395432475622345597103528739 + +B == +66054487 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +176469695533271657902814176811660357049007467856432383037590673407330246967781451723764079581998187 + +A == +814258256205243497704094951432575867360065658372158511036259934640748088306764553488803787 + +B == +108362239 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +44924492859445516541759485198544012102424796403707253610035148063863073596051272171194806669756971406400419 + +A == +176469695533271657902814176811660357049007467856432383037590673407330246967781451723764079581998187 + +B == +127286707 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +20600996927219343383225424320134474929609459588323857796871086845924186191561749519858600696159932468024710985371059 + +A == +44924492859445516541759485198544012102424796403707253610035148063863073596051272171194806669756971406400419 + +B == +229284691 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +6295696427695493110141186605837397185848992307978456138112526915330347715236378041486547994708748840844217371233735072572979 + +A == +20600996927219343383225424320134474929609459588323857796871086845924186191561749519858600696159932468024710985371059 + +B == +152800771 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +3104984078042317488749073016454213579257792635142218294052134804187631661145261015102617582090263808696699966840735333252107678792123 + +A == +6295696427695493110141186605837397185848992307978456138112526915330347715236378041486547994708748840844217371233735072572979 + +B == +246595759 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +26405175827665701256325699315126705508919255051121452292124404943796947287968603975320562847910946802396632302209435206627913466015741799499 + +A == +3104984078042317488749073016454213579257792635142218294052134804187631661145261015102617582090263808696699966840735333252107678792123 + +B == +4252063 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +11122146237908413610034600609460545703591095894418599759742741406628055069007082998134905595800236452010905900391505454890446585211975124558601770163 + +A == +26405175827665701256325699315126705508919255051121452292124404943796947287968603975320562847910946802396632302209435206627913466015741799499 + +B == +210605419 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1649861642047798890580354082088712649911849362201343649289384923147797960364736011515757482030049342943790127685185806092659832129486307035500638595572396187 + +A == +11122146237908413610034600609460545703591095894418599759742741406628055069007082998134905595800236452010905900391505454890446585211975124558601770163 + +B == +74170111 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +857983367126266717607389719637086684134462613006415859877666235955788392464081914127715967940968197765042399904117392707518175220864852816390004264107201177394565363 + +A == +1649861642047798890580354082088712649911849362201343649289384923147797960364736011515757482030049342943790127685185806092659832129486307035500638595572396187 + +B == +260016763 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +175995909353623703257072120479340610010337144085688850745292031336724691277374210929188442230237711063783727092685448718515661641054886101716698390145283196296702450566161283 + +A == +857983367126266717607389719637086684134462613006415859877666235955788392464081914127715967940968197765042399904117392707518175220864852816390004264107201177394565363 + +B == +102563707 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +48486002551155667224487059713350447239190772068092630563272168418880661006593537218144160068395218642353495339720640699721703003648144463556291315694787862009052641640656933232794283 + +A == +175995909353623703257072120479340610010337144085688850745292031336724691277374210929188442230237711063783727092685448718515661641054886101716698390145283196296702450566161283 + +B == +137747527 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +13156468011529105025061495011938518171328604045212410096476697450506055664012861932372156505805788068791146986282263016790631108386790291275939575123375304599622623328517354163964228279867403 + +A == +48486002551155667224487059713350447239190772068092630563272168418880661006593537218144160068395218642353495339720640699721703003648144463556291315694787862009052641640656933232794283 + +B == +135672847 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +6355194692790533601105154341731997464407930009404822926832136060319955058388106456084549316415200519472481147942263916585428906582726749131479465958107142228236909665306781538860053107680830113869123 + +A == +13156468011529105025061495011938518171328604045212410096476697450506055664012861932372156505805788068791146986282263016790631108386790291275939575123375304599622623328517354163964228279867403 + +B == +241523587 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +3157116676535430302794438027544146642863331358530722860333745617571010460905857862561870488000265751138954271040017454405707755458702044884023184574412221802502351503929935224995314581932097706874819348858083 + +A == +6355194692790533601105154341731997464407930009404822926832136060319955058388106456084549316415200519472481147942263916585428906582726749131479465958107142228236909665306781538860053107680830113869123 + +B == +248388667 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +390533129219992506725320633489467713907837370444962163378727819939092929448752905310115311180032249230394348337568973177802874166228132778126338883671958897238722734394783244237133367055422297736215754829839364158067 + +A == +3157116676535430302794438027544146642863331358530722860333745617571010460905857862561870488000265751138954271040017454405707755458702044884023184574412221802502351503929935224995314581932097706874819348858083 + +B == +61849651 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +48583654555070224891047847050732516652910250240135992225139515777200432486685999462997073444468380434359929499498804723793106565291183220444221080449740542884172281158126259373095216435009661050109711341419005972852770440739 + +A == +390533129219992506725320633489467713907837370444962163378727819939092929448752905310115311180032249230394348337568973177802874166228132778126338883671958897238722734394783244237133367055422297736215754829839364158067 + +B == +62201707 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +25733035251905120039135866524384525138869748427727001128764704499071378939227862068500633813538831598776578372709963673670934388213622433800015759585470542686333039614931682098922935087822950084908715298627996115185849260703525317419 + +A == +48583654555070224891047847050732516652910250240135992225139515777200432486685999462997073444468380434359929499498804723793106565291183220444221080449740542884172281158126259373095216435009661050109711341419005972852770440739 + +B == +264832231 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +2804594464939948901906623499531073917980499195397462605359913717827014360538186518540781517129548650937632008683280555602633122170458773895504894807182664540529077836857897972175530148107545939211339044386106111633510166695386323426241809387 + +A == +25733035251905120039135866524384525138869748427727001128764704499071378939227862068500633813538831598776578372709963673670934388213622433800015759585470542686333039614931682098922935087822950084908715298627996115185849260703525317419 + +B == +54494047 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +738136612083433720096707308165797114449914259256979340471077690416567237592465306112484843530074782721390528773594351482384711900456440808251196845265132086486672447136822046628407467459921823150600138073268385534588238548865012638209515923513516547 + +A == +2804594464939948901906623499531073917980499195397462605359913717827014360538186518540781517129548650937632008683280555602633122170458773895504894807182664540529077836857897972175530148107545939211339044386106111633510166695386323426241809387 + +B == +131594179 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +392847529056126766528615419937165193421166694172790666626558750047057558168124866940509180171236517681470100877687445134633784815352076138790217228749332398026714192707447855731679485746120589851992221508292976900578299504461333767437280988393026452846013683 + +A == +738136612083433720096707308165797114449914259256979340471077690416567237592465306112484843530074782721390528773594351482384711900456440808251196845265132086486672447136822046628407467459921823150600138073268385534588238548865012638209515923513516547 + +B == +266107603 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +168459393231883505975876919268398655632763956627405508859662408056221544310200546265681845397346956580604208064328814319465940958080244889692368602591598503944015835190587740756859842792554282496742843600573336023639256008687581291233481455395123454655488735304365627 + +A == +392847529056126766528615419937165193421166694172790666626558750047057558168124866940509180171236517681470100877687445134633784815352076138790217228749332398026714192707447855731679485746120589851992221508292976900578299504461333767437280988393026452846013683 + +B == +214408111 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +14865774288636941404884923981945833072113667565310054952177860608355263252462409554658728941191929400198053290113492910272458441655458514080123870132092365833472436407455910185221474386718838138135065780840839893113912689594815485706154461164071775481134379794909690501684643 + +A == +168459393231883505975876919268398655632763956627405508859662408056221544310200546265681845397346956580604208064328814319465940958080244889692368602591598503944015835190587740756859842792554282496742843600573336023639256008687581291233481455395123454655488735304365627 + +B == +44122723 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1213301773203241614897109856134894783021668292000023984098824423682568173639394290886185366993108292039068940333907505157813934962357206131450244004178619265868614859794316361031904412926604138893775068853175215502104744339658944443630407632290152772487455298652998368296998719996019 + +A == +14865774288636941404884923981945833072113667565310054952177860608355263252462409554658728941191929400198053290113492910272458441655458514080123870132092365833472436407455910185221474386718838138135065780840839893113912689594815485706154461164071775481134379794909690501684643 + +B == +40808563 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +186935245989515158127969129347464851990429060640910951266513740972248428651109062997368144722015290092846666943896556191257222521203647606911446635194198213436423080005867489516421559330500722264446765608763224572386410155413161172707802334865729654109050873820610813855041667633843601286843 + +A == +1213301773203241614897109856134894783021668292000023984098824423682568173639394290886185366993108292039068940333907505157813934962357206131450244004178619265868614859794316361031904412926604138893775068853175215502104744339658944443630407632290152772487455298652998368296998719996019 + +B == +77035759 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +83142661079751490510739960019112406284111408348732592580459037404394946037094409915127399165633756159385609671956087845517678367844901424617866988187132480585966721962585586730693443536100138246516868613250009028187662080828012497191775172228832247706080044971423654632146928165751885302331924491683 + +A == +186935245989515158127969129347464851990429060640910951266513740972248428651109062997368144722015290092846666943896556191257222521203647606911446635194198213436423080005867489516421559330500722264446765608763224572386410155413161172707802334865729654109050873820610813855041667633843601286843 + +B == +222383587 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443 + +A == +83142661079751490510739960019112406284111408348732592580459037404394946037094409915127399165633756159385609671956087845517678367844901424617866988187132480585966721962585586730693443536100138246516868613250009028187662080828012497191775172228832247706080044971423654632146928165751885302331924491683 + +B == +23407687 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1663606652988091811284014366560171522582683318514519379924950390627250155440313691226744227787921928894551755219495501365555370027257568506349958010457682898612082048959464465369892842603765280317696116552850664773291371490339084156052244256635115997453399761029567033971998617303988376172539172702246575225837054723 + +A == +3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443 + +B == +213701827 + +G == 2 +---------------------------------------------------------------- + + +Took 33057 ticks, 1048 bits +P == 1663606652988091811284014366560171522582683318514519379924950390627250155440313691226744227787921928894551755219495501365555370027257568506349958010457682898612082048959464465369892842603765280317696116552850664773291371490339084156052244256635115997453399761029567033971998617303988376172539172702246575225837054723 +Q == 3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443 diff --git a/lib/hcrypto/libtommath/etc/prime.512 b/lib/hcrypto/libtommath/etc/prime.512 new file mode 100644 index 000000000000..cb6ec302fb82 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/prime.512 @@ -0,0 +1,205 @@ +Enter # of bits: +Enter number of bases to try (1 to 8): +Certificate of primality for: +85933926807634727 + +A == +253758023 + +B == +169322581 + +G == 5 +---------------------------------------------------------------- +Certificate of primality for: +23930198825086241462113799 + +A == +85933926807634727 + +B == +139236037 + +G == 11 +---------------------------------------------------------------- +Certificate of primality for: +6401844647261612602378676572510019 + +A == +23930198825086241462113799 + +B == +133760791 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +269731366027728777712034888684015329354259 + +A == +6401844647261612602378676572510019 + +B == +21066691 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +37942338209025571690075025099189467992329684223707 + +A == +269731366027728777712034888684015329354259 + +B == +70333567 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +15306904714258982484473490774101705363308327436988160248323 + +A == +37942338209025571690075025099189467992329684223707 + +B == +201712723 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1616744757018513392810355191503853040357155275733333124624513530099 + +A == +15306904714258982484473490774101705363308327436988160248323 + +B == +52810963 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +464222094814208047161771036072622485188658077940154689939306386289983787983 + +A == +1616744757018513392810355191503853040357155275733333124624513530099 + +B == +143566909 + +G == 5 +---------------------------------------------------------------- +Certificate of primality for: +187429931674053784626487560729643601208757374994177258429930699354770049369025096447 + +A == +464222094814208047161771036072622485188658077940154689939306386289983787983 + +B == +201875281 + +G == 5 +---------------------------------------------------------------- +Certificate of primality for: +100579220846502621074093727119851331775052664444339632682598589456666938521976625305832917563 + +A == +187429931674053784626487560729643601208757374994177258429930699354770049369025096447 + +B == +268311523 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1173616081309758475197022137833792133815753368965945885089720153370737965497134878651384030219765163 + +A == +100579220846502621074093727119851331775052664444339632682598589456666938521976625305832917563 + +B == +5834287 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +191456913489905913185935197655672585713573070349044195411728114905691721186574907738081340754373032735283623 + +A == +1173616081309758475197022137833792133815753368965945885089720153370737965497134878651384030219765163 + +B == +81567097 + +G == 5 +---------------------------------------------------------------- +Certificate of primality for: +57856530489201750164178576399448868489243874083056587683743345599898489554401618943240901541005080049321706789987519 + +A == +191456913489905913185935197655672585713573070349044195411728114905691721186574907738081340754373032735283623 + +B == +151095433 + +G == 7 +---------------------------------------------------------------- +Certificate of primality for: +13790529750452576698109671710773784949185621244122040804792403407272729038377767162233653248852099545134831722512085881814803 + +A == +57856530489201750164178576399448868489243874083056587683743345599898489554401618943240901541005080049321706789987519 + +B == +119178679 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +7075985989000817742677547821106534174334812111605018857703825637170140040509067704269696198231266351631132464035671858077052876058979 + +A == +13790529750452576698109671710773784949185621244122040804792403407272729038377767162233653248852099545134831722512085881814803 + +B == +256552363 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +1227273006232588072907488910282307435921226646895131225407452056677899411162892829564455154080310937471747140942360789623819327234258162420463 + +A == +7075985989000817742677547821106534174334812111605018857703825637170140040509067704269696198231266351631132464035671858077052876058979 + +B == +86720989 + +G == 5 +---------------------------------------------------------------- +Certificate of primality for: +446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763 + +A == +1227273006232588072907488910282307435921226646895131225407452056677899411162892829564455154080310937471747140942360789623819327234258162420463 + +B == +182015287 + +G == 2 +---------------------------------------------------------------- +Certificate of primality for: +5290203010849586596974953717018896543907195901082056939587768479377028575911127944611236020459652034082251335583308070846379514569838984811187823420951275243 + +A == +446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763 + +B == +5920567 + +G == 2 +---------------------------------------------------------------- + + +Took 3454 ticks, 521 bits +P == 5290203010849586596974953717018896543907195901082056939587768479377028575911127944611236020459652034082251335583308070846379514569838984811187823420951275243 +Q == 446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763 diff --git a/lib/hcrypto/libtommath/etc/timer.asm b/lib/hcrypto/libtommath/etc/timer.asm new file mode 100644 index 000000000000..35890d9852fd --- /dev/null +++ b/lib/hcrypto/libtommath/etc/timer.asm @@ -0,0 +1,37 @@ +; x86 timer in NASM +; +; Tom St Denis, tomstdenis@iahu.ca +[bits 32] +[section .data] +time dd 0, 0 + +[section .text] + +%ifdef USE_ELF +[global t_start] +t_start: +%else +[global _t_start] +_t_start: +%endif + push edx + push eax + rdtsc + mov [time+0],edx + mov [time+4],eax + pop eax + pop edx + ret + +%ifdef USE_ELF +[global t_read] +t_read: +%else +[global _t_read] +_t_read: +%endif + rdtsc + sub eax,[time+4] + sbb edx,[time+0] + ret + \ No newline at end of file diff --git a/lib/hcrypto/libtommath/etc/tune.c b/lib/hcrypto/libtommath/etc/tune.c new file mode 100644 index 000000000000..e7b99fce2895 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/tune.c @@ -0,0 +1,542 @@ +/* Tune the Karatsuba parameters + * + * Tom St Denis, tstdenis82@gmail.com + */ +#include "../tommath.h" +#include "../tommath_private.h" +#include +#include +#include + +/* + Please take in mind that both multiplicands are of the same size. The balancing + mechanism in mp_balance works well but has some overhead itself. You can test + the behaviour of it with the option "-o" followed by a (small) positive number 'x' + to generate ratios of the form 1:x. +*/ + +static uint64_t s_timer_function(void); +static void s_timer_start(void); +static uint64_t s_timer_stop(void); +static uint64_t s_time_mul(int size); +static uint64_t s_time_sqr(int size); +static void s_usage(char *s); + +static uint64_t s_timer_function(void) +{ +#if _POSIX_C_SOURCE >= 199309L +#define LTM_BILLION 1000000000 + struct timespec ts; + + /* TODO: Sets errno in case of error. Use? */ + clock_gettime(CLOCK_MONOTONIC, &ts); + return (((uint64_t)ts.tv_sec) * LTM_BILLION + (uint64_t)ts.tv_nsec); +#else + clock_t t; + t = clock(); + if (t < (clock_t)(0)) { + return (uint64_t)(0); + } + return (uint64_t)(t); +#endif +} + +/* generic ISO C timer */ +static uint64_t s_timer_tmp; +static void s_timer_start(void) +{ + s_timer_tmp = s_timer_function(); +} +static uint64_t s_timer_stop(void) +{ + return s_timer_function() - s_timer_tmp; +} + + +static int s_check_result; +static int s_number_of_test_loops; +static int s_stabilization_extra; +static int s_offset = 1; + +#define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1) +static uint64_t s_time_mul(int size) +{ + int x; + mp_err e; + mp_int a, b, c, d; + uint64_t t1; + + if ((e = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + + if ((e = mp_rand(&a, size * s_offset)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + if ((e = mp_rand(&b, size)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + + s_timer_start(); + for (x = 0; x < s_number_of_test_loops; x++) { + if ((e = mp_mul(&a,&b,&c)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + if (s_check_result == 1) { + if ((e = s_mp_mul(&a,&b,&d)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + if (mp_cmp(&c, &d) != MP_EQ) { + /* Time of 0 cannot happen (famous last words?) */ + t1 = 0uLL; + goto LTM_ERR; + } + } + } + + t1 = s_timer_stop(); +LTM_ERR: + mp_clear_multi(&a, &b, &c, &d, NULL); + return t1; +} + +static uint64_t s_time_sqr(int size) +{ + int x; + mp_err e; + mp_int a, b, c; + uint64_t t1; + + if ((e = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + + if ((e = mp_rand(&a, size)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + + s_timer_start(); + for (x = 0; x < s_number_of_test_loops; x++) { + if ((e = mp_sqr(&a,&b)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + if (s_check_result == 1) { + if ((e = s_mp_sqr(&a,&c)) != MP_OKAY) { + t1 = UINT64_MAX; + goto LTM_ERR; + } + if (mp_cmp(&c, &b) != MP_EQ) { + t1 = 0uLL; + goto LTM_ERR; + } + } + } + + t1 = s_timer_stop(); +LTM_ERR: + mp_clear_multi(&a, &b, &c, NULL); + return t1; +} + +struct tune_args { + int testmode; + int verbose; + int print; + int bncore; + int terse; + int upper_limit_print; + int increment_print; +} args; + +static void s_run(const char *name, uint64_t (*op)(int), int *cutoff) +{ + int x, count = 0; + uint64_t t1, t2; + if ((args.verbose == 1) || (args.testmode == 1)) { + printf("# %s.\n", name); + } + for (x = 8; x < args.upper_limit_print; x += args.increment_print) { + *cutoff = INT_MAX; + t1 = op(x); + if ((t1 == 0uLL) || (t1 == UINT64_MAX)) { + fprintf(stderr,"%s failed at x = INT_MAX (%s)\n", name, + (t1 == 0uLL)?"wrong result":"internal error"); + exit(EXIT_FAILURE); + } + *cutoff = x; + t2 = op(x); + if ((t2 == 0uLL) || (t2 == UINT64_MAX)) { + fprintf(stderr,"%s failed (%s)\n", name, + (t2 == 0uLL)?"wrong result":"internal error"); + exit(EXIT_FAILURE); + } + if (args.verbose == 1) { + printf("%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1); + } + if (t2 < t1) { + if (count == s_stabilization_extra) { + count = 0; + break; + } else if (count < s_stabilization_extra) { + count++; + } + } else if (count > 0) { + count--; + } + } + *cutoff = x - s_stabilization_extra * args.increment_print; +} + +static long s_strtol(const char *str, char **endptr, const char *err) +{ + const int base = 10; + char *_endptr; + long val; + errno = 0; + val = strtol(str, &_endptr, base); + if ((val > INT_MAX || val < 0) || (errno != 0)) { + fprintf(stderr, "Value %s not usable\n", str); + exit(EXIT_FAILURE); + } + if (_endptr == str) { + fprintf(stderr, "%s\n", err); + exit(EXIT_FAILURE); + } + if (endptr) *endptr = _endptr; + return val; +} + +static int s_exit_code = EXIT_FAILURE; +static void s_usage(char *s) +{ + fprintf(stderr,"Usage: %s [TvcpGbtrSLFfMmosh]\n",s); + fprintf(stderr," -T testmode, for use with testme.sh\n"); + fprintf(stderr," -v verbose, print all timings\n"); + fprintf(stderr," -c check results\n"); + fprintf(stderr," -p print benchmark of final cutoffs in files \"multiplying\"\n"); + fprintf(stderr," and \"squaring\"\n"); + fprintf(stderr," -G [string] suffix for the filenames listed above\n"); + fprintf(stderr," Implies '-p'\n"); + fprintf(stderr," -b print benchmark of bncore.c\n"); + fprintf(stderr," -t prints space (0x20) separated results\n"); + fprintf(stderr," -r [64] number of rounds\n"); + fprintf(stderr," -S [0xdeadbeef] seed for PRNG\n"); + fprintf(stderr," -L [3] number of negative values accumulated until the result is accepted\n"); + fprintf(stderr," -M [3000] upper limit of T-C tests/prints\n"); + fprintf(stderr," -m [1] increment of T-C tests/prints\n"); + fprintf(stderr," -o [1] multiplier for the second multiplicand\n"); + fprintf(stderr," (Not for computing the cut-offs!)\n"); + fprintf(stderr," -s 'preset' use values in 'preset' for printing.\n"); + fprintf(stderr," 'preset' is a comma separated string with cut-offs for\n"); + fprintf(stderr," ksm, kss, tc3m, tc3s in that order\n"); + fprintf(stderr," ksm = karatsuba multiplication\n"); + fprintf(stderr," kss = karatsuba squaring\n"); + fprintf(stderr," tc3m = Toom-Cook 3-way multiplication\n"); + fprintf(stderr," tc3s = Toom-Cook 3-way squaring\n"); + fprintf(stderr," Implies '-p'\n"); + fprintf(stderr," -h this message\n"); + exit(s_exit_code); +} + +struct cutoffs { + int KARATSUBA_MUL, KARATSUBA_SQR; + int TOOM_MUL, TOOM_SQR; +}; + +const struct cutoffs max_cutoffs = +{ INT_MAX, INT_MAX, INT_MAX, INT_MAX }; + +static void set_cutoffs(const struct cutoffs *c) +{ + KARATSUBA_MUL_CUTOFF = c->KARATSUBA_MUL; + KARATSUBA_SQR_CUTOFF = c->KARATSUBA_SQR; + TOOM_MUL_CUTOFF = c->TOOM_MUL; + TOOM_SQR_CUTOFF = c->TOOM_SQR; +} + +static void get_cutoffs(struct cutoffs *c) +{ + c->KARATSUBA_MUL = KARATSUBA_MUL_CUTOFF; + c->KARATSUBA_SQR = KARATSUBA_SQR_CUTOFF; + c->TOOM_MUL = TOOM_MUL_CUTOFF; + c->TOOM_SQR = TOOM_SQR_CUTOFF; + +} + +int main(int argc, char **argv) +{ + uint64_t t1, t2; + int x, i, j; + size_t n; + + int printpreset = 0; + /*int preset[8];*/ + char *endptr, *str; + + uint64_t seed = 0xdeadbeef; + + int opt; + struct cutoffs orig, updated; + + FILE *squaring, *multiplying; + char mullog[256] = "multiplying"; + char sqrlog[256] = "squaring"; + s_number_of_test_loops = 64; + s_stabilization_extra = 3; + + MP_ZERO_BUFFER(&args, sizeof(args)); + + args.testmode = 0; + args.verbose = 0; + args.print = 0; + args.bncore = 0; + args.terse = 0; + + args.upper_limit_print = 3000; + args.increment_print = 1; + + /* Very simple option parser, please treat it nicely. */ + if (argc != 1) { + for (opt = 1; (opt < argc) && (argv[opt][0] == '-'); opt++) { + switch (argv[opt][1]) { + case 'T': + args.testmode = 1; + s_check_result = 1; + args.upper_limit_print = 1000; + args.increment_print = 11; + s_number_of_test_loops = 1; + s_stabilization_extra = 1; + s_offset = 1; + break; + case 'v': + args.verbose = 1; + break; + case 'c': + s_check_result = 1; + break; + case 'p': + args.print = 1; + break; + case 'G': + args.print = 1; + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + /* manual strcat() */ + for (i = 0; i < 255; i++) { + if (mullog[i] == '\0') { + break; + } + } + for (j = 0; i < 255; j++, i++) { + mullog[i] = argv[opt][j]; + if (argv[opt][j] == '\0') { + break; + } + } + for (i = 0; i < 255; i++) { + if (sqrlog[i] == '\0') { + break; + } + } + for (j = 0; i < 255; j++, i++) { + sqrlog[i] = argv[opt][j]; + if (argv[opt][j] == '\0') { + break; + } + } + break; + case 'b': + args.bncore = 1; + break; + case 't': + args.terse = 1; + break; + case 'S': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + str = argv[opt]; + errno = 0; + seed = (uint64_t)s_strtol(argv[opt], NULL, "No seed given?\n"); + break; + case 'L': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + s_stabilization_extra = (int)s_strtol(argv[opt], NULL, "No value for option \"-L\"given"); + break; + case 'o': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + s_offset = (int)s_strtol(argv[opt], NULL, "No value for the offset given"); + break; + case 'r': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + s_number_of_test_loops = (int)s_strtol(argv[opt], NULL, "No value for the number of rounds given"); + break; + + case 'M': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + args.upper_limit_print = (int)s_strtol(argv[opt], NULL, "No value for the upper limit of T-C tests given"); + break; + case 'm': + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + args.increment_print = (int)s_strtol(argv[opt], NULL, "No value for the increment for the T-C tests given"); + break; + case 's': + printpreset = 1; + args.print = 1; + opt++; + if (opt >= argc) { + s_usage(argv[0]); + } + str = argv[opt]; + KARATSUBA_MUL_CUTOFF = (int)s_strtol(str, &endptr, "[1/4] No value for KARATSUBA_MUL_CUTOFF given"); + str = endptr + 1; + KARATSUBA_SQR_CUTOFF = (int)s_strtol(str, &endptr, "[2/4] No value for KARATSUBA_SQR_CUTOFF given"); + str = endptr + 1; + TOOM_MUL_CUTOFF = (int)s_strtol(str, &endptr, "[3/4] No value for TOOM_MUL_CUTOFF given"); + str = endptr + 1; + TOOM_SQR_CUTOFF = (int)s_strtol(str, &endptr, "[4/4] No value for TOOM_SQR_CUTOFF given"); + break; + case 'h': + s_exit_code = EXIT_SUCCESS; + /* FALLTHROUGH */ + default: + s_usage(argv[0]); + } + } + } + + /* + mp_rand uses the cryptographically secure + source of the OS by default. That is too expensive, too slow and + most important for a benchmark: it is not repeatable. + */ + s_mp_rand_jenkins_init(seed); + mp_rand_source(s_mp_rand_jenkins); + + get_cutoffs(&orig); + + updated = max_cutoffs; + if ((args.bncore == 0) && (printpreset == 0)) { + struct { + const char *name; + int *cutoff, *update; + uint64_t (*fn)(int); + } test[] = { +#define T_MUL_SQR(n, o, f) { #n, &o##_CUTOFF, &(updated.o), MP_HAS(S_MP_##o) ? f : NULL } + /* + The influence of the Comba multiplication cannot be + eradicated programmatically. It depends on the size + of the macro MP_WPARRAY in tommath.h which needs to + be changed manually (to 0 (zero)). + */ + T_MUL_SQR("Karatsuba multiplication", KARATSUBA_MUL, s_time_mul), + T_MUL_SQR("Karatsuba squaring", KARATSUBA_SQR, s_time_sqr), + T_MUL_SQR("Toom-Cook 3-way multiplying", TOOM_MUL, s_time_mul), + T_MUL_SQR("Toom-Cook 3-way squaring", TOOM_SQR, s_time_sqr), +#undef T_MUL_SQR + }; + /* Turn all limits from bncore.c to the max */ + set_cutoffs(&max_cutoffs); + for (n = 0; n < sizeof(test)/sizeof(test[0]); ++n) { + if (test[n].fn) { + s_run(test[n].name, test[n].fn, test[n].cutoff); + *test[n].update = *test[n].cutoff; + *test[n].cutoff = INT_MAX; + } + } + } + if (args.terse == 1) { + printf("%d %d %d %d\n", + updated.KARATSUBA_MUL, + updated.KARATSUBA_SQR, + updated.TOOM_MUL, + updated.TOOM_SQR); + } else { + printf("KARATSUBA_MUL_CUTOFF = %d\n", updated.KARATSUBA_MUL); + printf("KARATSUBA_SQR_CUTOFF = %d\n", updated.KARATSUBA_SQR); + printf("TOOM_MUL_CUTOFF = %d\n", updated.TOOM_MUL); + printf("TOOM_SQR_CUTOFF = %d\n", updated.TOOM_SQR); + } + + if (args.print == 1) { + printf("Printing data for graphing to \"%s\" and \"%s\"\n",mullog, sqrlog); + + multiplying = fopen(mullog, "w+"); + if (multiplying == NULL) { + fprintf(stderr, "Opening file \"%s\" failed\n", mullog); + exit(EXIT_FAILURE); + } + + squaring = fopen(sqrlog, "w+"); + if (squaring == NULL) { + fprintf(stderr, "Opening file \"%s\" failed\n",sqrlog); + exit(EXIT_FAILURE); + } + + for (x = 8; x < args.upper_limit_print; x += args.increment_print) { + set_cutoffs(&max_cutoffs); + t1 = s_time_mul(x); + set_cutoffs(&orig); + t2 = s_time_mul(x); + fprintf(multiplying, "%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1); + fflush(multiplying); + if (args.verbose == 1) { + printf("MUL %d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1); + fflush(stdout); + } + set_cutoffs(&max_cutoffs); + t1 = s_time_sqr(x); + set_cutoffs(&orig); + t2 = s_time_sqr(x); + fprintf(squaring,"%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1); + fflush(squaring); + if (args.verbose == 1) { + printf("SQR %d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1); + fflush(stdout); + } + } + printf("Finished. Data for graphing in \"%s\" and \"%s\"\n",mullog, sqrlog); + if (args.verbose == 1) { + set_cutoffs(&orig); + if (args.terse == 1) { + printf("%d %d %d %d\n", + KARATSUBA_MUL_CUTOFF, + KARATSUBA_SQR_CUTOFF, + TOOM_MUL_CUTOFF, + TOOM_SQR_CUTOFF); + } else { + printf("KARATSUBA_MUL_CUTOFF = %d\n", KARATSUBA_MUL_CUTOFF); + printf("KARATSUBA_SQR_CUTOFF = %d\n", KARATSUBA_SQR_CUTOFF); + printf("TOOM_MUL_CUTOFF = %d\n", TOOM_MUL_CUTOFF); + printf("TOOM_SQR_CUTOFF = %d\n", TOOM_SQR_CUTOFF); + } + } + } + exit(EXIT_SUCCESS); +} diff --git a/lib/hcrypto/libtommath/etc/tune_it.sh b/lib/hcrypto/libtommath/etc/tune_it.sh new file mode 100755 index 000000000000..5e0fe7c3e374 --- /dev/null +++ b/lib/hcrypto/libtommath/etc/tune_it.sh @@ -0,0 +1,107 @@ +#!/bin/sh + +die() { + echo "$1 failed" + echo "Exiting" + exit $2 +} +# A linear congruential generator is sufficient for the purpose. +SEED=3735928559 +LCG() { + SEED=$(((1103515245 * $SEED + 12345) % 2147483648)) + echo $SEED +} +median() { +# read everything besides the header from file $1 +# | cut-out the required column $2 +# | sort all the entries numerically +# | show only the first $3 entries +# | show only the last entry + tail -n +2 $1 | cut -d' ' -f$2 | sort -n | head -n $3 | tail -n 1 +} + +MPWD=$(dirname $(readlink -f "$0")) +FILE_NAME="tuning_list" +TOMMATH_CUTOFFS_H="$MPWD/../tommath_cutoffs.h" +BACKUP_SUFFIX=".orig" +RNUM=0 + +############################################################################# +# It would be a good idea to isolate these processes (with e.g.: cpuset) # +# # +# It is not a good idea to e.g: watch high resolution videos while this # +# test are running if you do not have enough memory to avoid page faults. # +############################################################################# + +# Number of rounds overall. +LIMIT=100 +# Number of loops for each input. +RLOOPS=10 +# Offset ( > 0 ) . Runs tests with asymmetric input of the form 1:OFFSET +# Please use another destination for TOMMATH_CUTOFFS_H if you change OFFSET, because the numbers +# with an offset different from 1 (one) are not usable as the general cut-off values +# in "tommath_cutoffs.h". +OFFSET=1 +# Number ( >= 3 ) of positive results (TC-is-faster) accumulated until it is accepted. +# Due to the algorithm used to compute the median in this Posix compliant shell script +# the value needs to be 3 (three), not less, to keep the variation small. +LAG=3 +# Keep the temporary file $FILE_NAME. Set to 0 (zero) to remove it at the end. +# The file is in a format fit to feed into R directly. If you do it and find the median +# of this program to be off by more than a couple: please contact the authors and report +# the numbers from this program and R and the standard deviation. This program is known +# to get larger errors if the standard deviation is larger than ~50. +KEEP_TEMP=1 + +echo "You might like to watch the numbers go up to $LIMIT but it will take a long time!" + +# Might not have sufficient rights or disc full. +echo "km ks tc3m tc3s" > $FILE_NAME || die "Writing header to $FILE_NAME" $? +i=1 +while [ $i -le $LIMIT ]; do + RNUM=$(LCG) + printf "\r%d" $i + "$MPWD"/tune -t -r $RLOOPS -L $LAG -S "$RNUM" -o $OFFSET >> $FILE_NAME || die "tune" $? + i=$((i + 1)) +done + +if [ $KEEP_TEMP -eq 0 ]; then + rm -v $FILE_NAME || die "Removing $KEEP_TEMP" $? +fi + +echo "Writing cut-off values to \"$TOMMATH_CUTOFFS_H\"." +echo "In case of failure: a copy of \"$TOMMATH_CUTOFFS_H\" is in \"$TOMMATH_CUTOFFS_H$BACKUP_SUFFIX\"" + +cp -v $TOMMATH_CUTOFFS_H $TOMMATH_CUTOFFS_H$BACKUP_SUFFIX || die "Making backup copy of $TOMMATH_CUTOFFS_H" $? + +cat << END_OF_INPUT > $TOMMATH_CUTOFFS_H || die "Writing header to $TOMMATH_CUTOFFS_H" $? +/* LibTomMath, multiple-precision integer library -- Tom St Denis */ +/* SPDX-License-Identifier: Unlicense */ +/* + Current values evaluated on an AMD A8-6600K (64-bit). + Type "make tune" to optimize them for your machine but + be aware that it may take a long time. It took 2:30 minutes + on the aforementioned machine for example. + */ +END_OF_INPUT + +# The Posix shell does not offer an array data type so we create +# the median with 'standard tools'^TM + +# read the file (without the first line) and count the lines +i=$(tail -n +2 $FILE_NAME | wc -l) +# our median point will be at $i entries +i=$(( (i / 2) + 1 )) +TMP=$(median $FILE_NAME 1 $i) +echo "#define MP_DEFAULT_KARATSUBA_MUL_CUTOFF $TMP" +echo "#define MP_DEFAULT_KARATSUBA_MUL_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(km) Appending to $TOMMATH_CUTOFFS_H" $? +TMP=$(median $FILE_NAME 2 $i) +echo "#define MP_DEFAULT_KARATSUBA_SQR_CUTOFF $TMP" +echo "#define MP_DEFAULT_KARATSUBA_SQR_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(ks) Appending to $TOMMATH_CUTOFFS_H" $? +TMP=$(median $FILE_NAME 3 $i) +echo "#define MP_DEFAULT_TOOM_MUL_CUTOFF $TMP" +echo "#define MP_DEFAULT_TOOM_MUL_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(tc3m) Appending to $TOMMATH_CUTOFFS_H" $? +TMP=$(median $FILE_NAME 4 $i) +echo "#define MP_DEFAULT_TOOM_SQR_CUTOFF $TMP" +echo "#define MP_DEFAULT_TOOM_SQR_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(tc3s) Appending to $TOMMATH_CUTOFFS_H" $? + -- cgit v1.2.3