ARM Shanghai IoT Team (Internal) / newMiniTLS-GPL

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Fork of MiniTLS-GPL by Donatien Garnier

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 $ */