kc3-lang/libtommath

diff --git a/bn_mp_prime_is_prime.c b/bn_mp_prime_is_prime.c
index d05cd87..d8755a0 100644
--- a/bn_mp_prime_is_prime.c
+++ b/bn_mp_prime_is_prime.c
@@ -192,7 +192,7 @@ int mp_prime_is_prime(const mp_int *a, int t, int *result)
           Sorenson, Jonathan; Webster, Jonathan (2015).
            "Strong Pseudoprimes to Twelve Prime Bases".
        */
-      /* 318665857834031151167461 */
+                                   /* 318665857834031151167461 */
       if ((err =   mp_read_radix(&b, "437ae92817f9fc85b7e5", 16)) != MP_OKAY) {
          goto LBL_B;
       }
@@ -200,14 +200,20 @@ int mp_prime_is_prime(const mp_int *a, int t, int *result)
       if (mp_cmp(a,&b) == MP_LT) {
          p_max = 12;
       }
-      /* 3317044064679887385961981 */
-      if ((err = mp_read_radix(&b, "2be6951adc5b22410a5fd", 16)) != MP_OKAY) {
-         goto LBL_B;
-      }
+      else {                       /* 3317044064679887385961981 */
+         if ((err = mp_read_radix(&b, "2be6951adc5b22410a5fd", 16)) != MP_OKAY) {
+            goto LBL_B;
+         }
 
-      if (mp_cmp(a,&b) == MP_LT) {
-         p_max = 13;
+         if (mp_cmp(a,&b) == MP_LT) {
+            p_max = 13;
+         }
+         else {
+            err = MP_VAL;
+            goto LBL_B;
+         }
       }
+
       // for compatibility with the current API (well, compatible within a sign's width)
       if (p_max < t) {
          p_max = t;
diff --git a/bn_mp_prime_rabin_miller_trials.c b/bn_mp_prime_rabin_miller_trials.c
index d400902..785a60b 100644
--- a/bn_mp_prime_rabin_miller_trials.c
+++ b/bn_mp_prime_rabin_miller_trials.c
@@ -17,17 +17,24 @@
 static const struct {
    int k, t;
 } sizes[] = {
-   {   128,    28 },
+   {    80,    -1 }, /* Use deterministic algorithm for size <= 80 bits */
+   {    81,    39 },
+   {    96,    37 },
+   {   128,    32 },
+   {   160,    27 },
+   {   192,    21 },
    {   256,    16 },
    {   384,    10 },
    {   512,     7 },
    {   640,     6 },
    {   768,     5 },
    {   896,     4 },
-   {  1024,     4 }
+   {  1024,     4 },
+   {  2048,     2 },
+   {  4096,     1 },
 };
 
-/* returns # of RM trials required for a given bit size */
+/* returns # of RM trials required for a given bit size and max. error of 2^(-96)*/
 int mp_prime_rabin_miller_trials(int size)
 {
    int x;
diff --git a/doc/bn.tex b/doc/bn.tex
index 2c4d36a..e81d039 100644
--- a/doc/bn.tex
+++ b/doc/bn.tex
@@ -1824,6 +1824,73 @@ require ten tests whereas a 1024-bit number would only require four tests.
 
 You should always still perform a trial division before a Miller-Rabin test though.
 
+A small table, broke in two for typographical reasons, with the number of rounds of Miller-Rabin tests is shown below.
+The first column is the number of bits $b$ in the prime $p = 2^b$, the numbers in the first row represent the 
+probability that the number that all of the Miller-Rabin tests deemed a pseudoprime is actually a composite. There is a deterministic test for numbers smaller than $2^{80}$.
+
+\begin{table}[h]
+\begin{center}
+\begin{tabular}{c c c c c c c}
+\textbf{bits} & $\mathbf{2^{-80}}$ & $\mathbf{2^{-96}}$ & $\mathbf{2^{-112}}$ & $\mathbf{2^{-128}}$ & $\mathbf{2^{-160}}$ & $\mathbf{2^{-192}}$ \\
+80    & 31 & 39 & 47 & 55 & 71 & 87  \\
+96    & 29 & 37 & 45 & 53 & 69 & 85  \\
+128   & 24 & 32 & 40 & 48 & 64 & 80  \\
+160   & 19 & 27 & 35 & 43 & 59 & 75  \\
+192   & 15 & 21 & 29 & 37 & 53 & 69  \\
+256   & 10 & 15 & 20 & 27 & 43 & 59  \\
+384   & 7  & 9  & 12 & 16 & 25 & 38  \\
+512   & 5  & 7  & 9  & 12 & 18 & 26  \\
+768   & 4  & 5  & 6  & 8  & 11 & 16  \\
+1024  & 3  & 4  & 5  & 6  & 9  & 12  \\
+1536  & 2  & 3  & 3  & 4  & 6  & 8   \\
+2048  & 2  & 2  & 3  & 3  & 4  & 6   \\
+3072  & 1  & 2  & 2  & 2  & 3  & 4   \\
+4096  & 1  & 1  & 2  & 2  & 2  & 3   \\
+6144  & 1  & 1  & 1  & 1  & 2  & 2   \\
+8192  & 1  & 1  & 1  & 1  & 2  & 2   \\
+12288 & 1  & 1  & 1  & 1  & 1  & 1   \\
+16384 & 1  & 1  & 1  & 1  & 1  & 1   \\
+24576 & 1  & 1  & 1  & 1  & 1  & 1   \\
+32768 & 1  & 1  & 1  & 1  & 1  & 1
+\end{tabular}
+\caption{ Number of Miller-Rabin rounds. Part I } \label{table:millerrabinrunsp1}
+\end{center}
+\end{table}
+\newpage
+\begin{table}[h]
+\begin{center}
+\begin{tabular}{c c c c c c c c}
+\textbf{bits} &$\mathbf{2^{-224}}$ & $\mathbf{2^{-256}}$ & $\mathbf{2^{-288}}$ & $\mathbf{2^{-320}}$ & $\mathbf{2^{-352}}$ & $\mathbf{2^{-384}}$ & $\mathbf{2^{-416}}$\\
+80    & 103 & 119 & 135 & 151 & 167 & 183 & 199 \\
+96    & 101 & 117 & 133 & 149 & 165 & 181 & 197 \\
+128   & 96  & 112 & 128 & 144 & 160 & 176 & 192 \\
+160   & 91  & 107 & 123 & 139 & 155 & 171 & 187 \\
+192   & 85  & 101 & 117 & 133 & 149 & 165 & 181 \\
+256   & 75  & 91  & 107 & 123 & 139 & 155 & 171 \\
+384   & 54  & 70  & 86  & 102 & 118 & 134 & 150 \\
+512   & 36  & 49  & 65  & 81  & 97  & 113 & 129 \\
+768   & 22  & 29  & 37  & 47  & 58  & 70  & 86  \\
+1024  & 16  & 21  & 26  & 33  & 40  & 48  & 58  \\
+1536  & 10  & 13  & 17  & 21  & 25  & 30  & 35  \\
+2048  & 8   & 10  & 13  & 15  & 18  & 22  & 26  \\
+3072  & 5   & 7   & 8	& 10  & 12  & 14  & 17  \\
+4096  & 4   & 5   & 6	& 8   & 9   & 11  & 12  \\
+6144  & 3   & 4   & 4	& 5   & 6   & 7   & 8	\\
+8192  & 2   & 3   & 3	& 4   & 5   & 6   & 6	\\
+12288 & 2   & 2   & 2	& 3   & 3   & 4   & 4	\\
+16384 & 1   & 2   & 2	& 2   & 3   & 3   & 3	\\
+24576 & 1   & 1   & 2	& 2   & 2   & 2   & 2	\\
+32768 & 1   & 1   & 1	& 1   & 2   & 2   & 2
+\end{tabular}
+\caption{ Number of Miller-Rabin rounds. Part II } \label{table:millerrabinrunsp2}
+\end{center}
+\end{table}
+
+Determining the probability needed to pick the right column is a bit harder. Fips 186.4, for example has $2^{-80}$ for $512$ bit large numbers, $2^{-112}$ for $1024$ bits, and $2^{128}$ for $1536$ bits. It can be seen in table \ref{table:millerrabinrunsp1} that those combinations follow the diagonal from $(512,2^{-80})$ downwards and to the right to gain a lower probabilty of getting a composite declared a pseudoprime for the same amount of work or less.
+
+If this version of the library has the strong Lucas-Selfridge and/or the Frobenius-Underwood test implemented only one or two rounds of the Miller-Rabin test with a random base is necesssary for numbers larger than or equal to $1024$ bits.
+
+
 \section{Strong Lucas-Selfridge Test}
 \index{mp\_prime\_strong\_lucas\_selfridge}
 \begin{alltt}