Donatien Garnier / MiniTLS-GPL

A super trimmed down TLS stack, GPL licensed

Dependents:   MiniTLS-HTTPS-Example

MiniTLS - A super trimmed down TLS/SSL Library for embedded devices Author: Donatien Garnier Copyright (C) 2013-2014 AppNearMe Ltd

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

math/numtheory/fp_isprime.c@4:cbaf466d717d, 2014-06-10 (annotated)

Committer:
MiniTLS
Date:
Tue Jun 10 14:23:09 2014 +0000
Revision:
4:cbaf466d717d
Parent:
0:35aa5be3b78d 
Fixes for mbed

Who changed what in which revision?

UserRevisionLine numberNew contents of line
MiniTLS 0:35aa5be3b78d 1 /* TomsFastMath, a fast ISO C bignum library.
MiniTLS 0:35aa5be3b78d 2 *
MiniTLS 0:35aa5be3b78d 3 * This project is meant to fill in where LibTomMath
MiniTLS 0:35aa5be3b78d 4 * falls short. That is speed ;-)
MiniTLS 0:35aa5be3b78d 5 *
MiniTLS 0:35aa5be3b78d 6 * This project is public domain and free for all purposes.
MiniTLS 0:35aa5be3b78d 7 *
MiniTLS 0:35aa5be3b78d 8 * Tom St Denis, tomstdenis@gmail.com
MiniTLS 0:35aa5be3b78d 9 */
MiniTLS 0:35aa5be3b78d 10 #include <tfm.h>
MiniTLS 0:35aa5be3b78d 11
MiniTLS 0:35aa5be3b78d 12 /* a few primes */
MiniTLS 0:35aa5be3b78d 13 static const fp_digit primes[256] = {
MiniTLS 0:35aa5be3b78d 14 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
MiniTLS 0:35aa5be3b78d 15 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
MiniTLS 0:35aa5be3b78d 16 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
MiniTLS 0:35aa5be3b78d 17 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
MiniTLS 0:35aa5be3b78d 18 0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
MiniTLS 0:35aa5be3b78d 19 0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
MiniTLS 0:35aa5be3b78d 20 0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
MiniTLS 0:35aa5be3b78d 21 0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
MiniTLS 0:35aa5be3b78d 22
MiniTLS 0:35aa5be3b78d 23 0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
MiniTLS 0:35aa5be3b78d 24 0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
MiniTLS 0:35aa5be3b78d 25 0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
MiniTLS 0:35aa5be3b78d 26 0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
MiniTLS 0:35aa5be3b78d 27 0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
MiniTLS 0:35aa5be3b78d 28 0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
MiniTLS 0:35aa5be3b78d 29 0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
MiniTLS 0:35aa5be3b78d 30 0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
MiniTLS 0:35aa5be3b78d 31
MiniTLS 0:35aa5be3b78d 32 0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
MiniTLS 0:35aa5be3b78d 33 0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
MiniTLS 0:35aa5be3b78d 34 0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
MiniTLS 0:35aa5be3b78d 35 0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
MiniTLS 0:35aa5be3b78d 36 0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
MiniTLS 0:35aa5be3b78d 37 0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
MiniTLS 0:35aa5be3b78d 38 0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
MiniTLS 0:35aa5be3b78d 39 0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
MiniTLS 0:35aa5be3b78d 40
MiniTLS 0:35aa5be3b78d 41 0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
MiniTLS 0:35aa5be3b78d 42 0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
MiniTLS 0:35aa5be3b78d 43 0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
MiniTLS 0:35aa5be3b78d 44 0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
MiniTLS 0:35aa5be3b78d 45 0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
MiniTLS 0:35aa5be3b78d 46 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
MiniTLS 0:35aa5be3b78d 47 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
MiniTLS 0:35aa5be3b78d 48 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
MiniTLS 0:35aa5be3b78d 49 };
MiniTLS 0:35aa5be3b78d 50
MiniTLS 0:35aa5be3b78d 51 int fp_isprime(fp_int *a)
MiniTLS 0:35aa5be3b78d 52 {
MiniTLS 0:35aa5be3b78d 53 fp_int b;
MiniTLS 0:35aa5be3b78d 54 fp_digit d;
MiniTLS 0:35aa5be3b78d 55 int r, res;
MiniTLS 0:35aa5be3b78d 56
MiniTLS 0:35aa5be3b78d 57 /* do trial division */
MiniTLS 0:35aa5be3b78d 58 for (r = 0; r < 256; r++) {
MiniTLS 0:35aa5be3b78d 59 fp_mod_d(a, primes[r], &d);
MiniTLS 0:35aa5be3b78d 60 if (d == 0) {
MiniTLS 0:35aa5be3b78d 61 return FP_NO;
MiniTLS 0:35aa5be3b78d 62 }
MiniTLS 0:35aa5be3b78d 63 }
MiniTLS 0:35aa5be3b78d 64
MiniTLS 0:35aa5be3b78d 65 /* now do 8 miller rabins */
MiniTLS 0:35aa5be3b78d 66 fp_init(&b);
MiniTLS 0:35aa5be3b78d 67 for (r = 0; r < 8; r++) {
MiniTLS 0:35aa5be3b78d 68 fp_set(&b, primes[r]);
MiniTLS 0:35aa5be3b78d 69 fp_prime_miller_rabin(a, &b, &res);
MiniTLS 0:35aa5be3b78d 70 if (res == FP_NO) {
MiniTLS 0:35aa5be3b78d 71 return FP_NO;
MiniTLS 0:35aa5be3b78d 72 }
MiniTLS 0:35aa5be3b78d 73 }
MiniTLS 0:35aa5be3b78d 74 return FP_YES;
MiniTLS 0:35aa5be3b78d 75 }
MiniTLS 0:35aa5be3b78d 76
MiniTLS 0:35aa5be3b78d 77 /* $Source: /cvs/libtom/tomsfastmath/src/numtheory/fp_isprime.c,v $ */
MiniTLS 0:35aa5be3b78d 78 /* $Revision: 1.1 $ */
MiniTLS 0:35aa5be3b78d 79 /* $Date: 2007/01/24 21:25:19 $ */