Test de Primalite de Miller-Rabin
CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, École polytechnique, Institut Polytechnique de Paris, CNRS, France
[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K Bug [Le bug de l'an 2000]]
[Real Numbers don't exist in Computers and Floating Point Computations aren't safe. [Les Nombres Réels n'existent pas dans les Ordinateurs et les Calculs Flottants ne sont pas sûrs.]]
[N'oubliez pas de visiter Une Machine Virtuelle à Explorer l'Espace-Temps et au-delà où vous trouverez plus de 10.000 images et animations à la frontière de l'Art et de la Science]
(Site WWW CMAP28 : cette page a été créée le 02/03/2026 et mise à jour le 02/03/2026 12:40:08 -CET-)
/*************************************************************************************************************************************/
/* */
/* T E S T D E P R I M A L I T E U T I L I S A N T ' Miller-Rabin ' : */
/* */
/* */
/* Author of 'TestPrimalite_MillerRabin_AvecBasesMagiques.01$vv$I' : */
/* */
/* Jean-Francois COLONNA (LACTAMME, 20250827093714). */
/* */
/*************************************************************************************************************************************/
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <inttypes.h>
#include <stdio.h>
#define FI_uint__ static inline EntierNonSigne
#define F__uint__ static EntierNonSigne
#define FI_void static inline void
#define F__bool static bool
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* Q U E L Q U E S O U T I L S D E B A S E : */
/* */
/*************************************************************************************************************************************/
#define ABSO(x) (((x) > 0) ? (x) : (-(x)))
#define MIN2(x,y) (((x) < (y)) ? (x) : (y))
#define MAX2(x,y) (((x) > (y)) ? (x) : (y))
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* A R I T H M E T I Q U E M O D U L A I R E S E C U R I S E E A V E C ' __int128 ' : */
/* */
/*************************************************************************************************************************************/
FI_uint__ MultiplicationModulo(EntierNonSigne a,EntierNonSigne b,EntierNonSigne m)
{
#if (PRECISION_ENTIERE == PRECISION_ENTIERE__64_BITS)
__uint128_t r = (__uint128_t)a * b;
return (EntierNonSigne)(r % m);
#else
#endif
#if (PRECISION_ENTIERE == PRECISION_ENTIERE_128_BITS)
/* Ce qui suit est plus complique qu'avec la version 'PRECISION_ENTIERE__64_BITS' car, */
/* en effet, avec 'PRECISION_ENTIERE_128_BITS' on aurait besoin de '__uint256_t' qui, */
/* malheureusement n'existe pas... */
EntierNonSigne result = 0;
a = a % m;
while (b > 0)
{
if (b & 1)
{
result = (result + a) % m;
}
else
{
}
a = (a << 1) % m;
b >>= 1;
}
return result;
#else
#endif
}
FI_uint__ ExponentiationModulo(EntierNonSigne a,EntierNonSigne e,EntierNonSigne m)
{
EntierNonSigne r = 1;
while (e)
{
if (e & 1)
{
r = MultiplicationModulo(r,a,m);
}
else
{
}
a = MultiplicationModulo(a,a,m);
e >>= 1;
}
return r;
}
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* D E C O M P O S I T I O N ' n-1 = d*(2^s) ' : */
/* */
/*************************************************************************************************************************************/
FI_void DecompositionFermat(EntierNonSigne nombre,EntierNonSigne *d,unsigned int *s)
{
EntierNonSigne NombreMoins1 = nombre - 1;
unsigned int k = 0;
while ((NombreMoins1 & 1) == 0)
{
NombreMoins1 >>= 1;
k++;
}
*d = NombreMoins1;
*s = k;
}
F__bool BasesMillerRabin(EntierNonSigne nombre,EntierNonSigne base)
{
if ((base % nombre) == 0)
{
return true;
}
else
{
}
EntierNonSigne d;
unsigned int s;
DecompositionFermat(nombre,&d,&s);
EntierNonSigne x = ExponentiationModulo(base % nombre,d,nombre);
EntierNonSigne NombreMoins1 = nombre - 1;
if ((x == 1) || (x == NombreMoins1))
{
return true;
}
else
{
}
for (unsigned int r = 1 ; r < s ; r++)
{
x = MultiplicationModulo(x,x,nombre);
if (x == NombreMoins1)
{
return true;
}
else
{
}
}
return false;
}
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* T A B L E D E S I N T E R V A L L E S E T B A S E S S U F F I S A N T E S : */
/* */
/*************************************************************************************************************************************/
struct mr_bound
{
EntierNonSigne limit;
const uint32_t *bases;
size_t nbases;
};
#define sizeof_BASE(base) (sizeof(base)/sizeof(uint32_t))
/* Introduit le 20251014161411 pour plus de parametrage... */
static const uint32_t BASE_1_1[] = {2, 3};
static const uint32_t BASE_1_2[] = {2, 3, 5};
static const uint32_t BASE_1_3[] = {2, 3, 5, 7};
static const uint32_t BASE_1_4[] = {2, 3, 5, 7, 11};
static const uint32_t BASE_1_5[] = {31, 73};
static const uint32_t BASE_1_6[] = {2, 3, 5, 7, 11, 13};
static const uint32_t BASE_1_7[] = {2, 3, 5, 7, 11, 13, 17};
static const struct mr_bound MR___TABLE_1[] =
{
{
1373653ULL, BASE_1_1, sizeof_BASE(BASE_1_1)
},
{
25326001ULL, BASE_1_2, sizeof_BASE(BASE_1_2)
},
{
118670087467ULL, BASE_1_3, sizeof_BASE(BASE_1_3)
},
{
2152302898747ULL, BASE_1_4, sizeof_BASE(BASE_1_4)
},
{
3474749660383ULL, BASE_1_5, sizeof_BASE(BASE_1_5)
},
{
341550071728321ULL, BASE_1_6, sizeof_BASE(BASE_1_6)
},
{
3825123056546413051ULL, BASE_1_7, sizeof_BASE(BASE_1_7)
},
{
0ULL, NULL, 0
/* Sentinelle... */
}
};
/* Sources : Jaeschke (1993), Sorenson & Webster (2015). */
static const uint32_t BASE_2_00[] = {2};
static const uint32_t BASE_2_01[] = {2, 3};
static const uint32_t BASE_2_02[] = {31, 73};
static const uint32_t BASE_2_03[] = {2, 3, 5};
static const uint32_t BASE_2_04[] = {2, 3, 5, 7};
static const uint32_t BASE_2_05[] = {2, 7, 61};
static const uint32_t BASE_2_06[] = {2, 13, 23, 1662803};
static const uint32_t BASE_2_07[] = {2, 3, 5, 7, 11};
static const uint32_t BASE_2_08[] = {2, 3, 5, 7, 11, 13};
static const uint32_t BASE_2_09[] = {2, 3, 5, 7, 11, 13, 17};
static const uint32_t BASE_2_10[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
static const uint32_t BASE_2_11[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
static const uint32_t BASE_2_12[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
static const uint32_t BASE_2_13[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
static const uint32_t BASE_2_14[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71};
/* Les bases {BASE_2_10,BASE_2_11,BASE_2_12,BASE_2_13} ont ete introduites le 20250930155736 */
static const struct mr_bound MR___TABLE_2[] =
{
{
2047ULL, BASE_2_00, sizeof_BASE(BASE_2_00)
},
{
1373653ULL, BASE_2_01, sizeof_BASE(BASE_2_01)
},
{
9080191ULL, BASE_2_02, sizeof_BASE(BASE_2_02)
},
{
25326001ULL, BASE_2_03, sizeof_BASE(BASE_2_03)
},
{
3215031751ULL, BASE_2_04, sizeof_BASE(BASE_2_04)
},
{
4759123141ULL, BASE_2_05, sizeof_BASE(BASE_2_05)
},
{
1122004669633ULL, BASE_2_06, sizeof_BASE(BASE_2_06)
},
{
2152302898747ULL, BASE_2_07, sizeof_BASE(BASE_2_07)
},
{
3474749660383ULL, BASE_2_08, sizeof_BASE(BASE_2_08)
},
{
341550071728321ULL, BASE_2_09, sizeof_BASE(BASE_2_09)
},
{
3825123056546413051ULL, BASE_2_10, sizeof_BASE(BASE_2_10)
},
#if (PRECISION_ENTIERE == PRECISION_ENTIERE__64_BITS)
{
0x7fffffffffffffffULL, BASE_2_11, sizeof_BASE(BASE_2_11)
},
#else
#endif
#if (PRECISION_ENTIERE == PRECISION_ENTIERE_128_BITS)
{
(EntierNonSigne)((1844674407370955161ULL)*10)+6, BASE_2_11, sizeof_BASE(BASE_2_11)
/* Initialisation un peu "tordue" de 18446744073709551616", mais inevitable... */
/* */
/* En effet, le compilateur 'gcc' reconnait le type 'int128', mais ne permet pas */
/* d'initialiser les variables de ce type avec des constantes "superieures" au type */
/* "long int". Par contre, il autorise des calculs sur de telles constantes qui conduisent */
/* a des valeurs 'int128'. C'est difficile a comprendre... */
},
{
(EntierNonSigne)((3186658578340311511ULL)*100000)+67461, BASE_2_12, sizeof_BASE(BASE_2_12)
/* Initialisation un peu "tordue" de 318665857834031151167461", mais inevitable... */
},
{
(EntierNonSigne)((3317044064679887385ULL)*1000000)+961981, BASE_2_13, sizeof_BASE(BASE_2_13)
/* Initialisation un peu "tordue" de 3317044064679887385961981", mais inevitable... */
},
{
(EntierNonSigne)((0xffffffffffffffff)<<63)+0xffffffffffffffffULL, BASE_2_14, sizeof_BASE(BASE_2_14)
/* Initialisation un peu "tordue" de 0x7fffffffffffffffffffffffffffffff", mais inevitable... */
/* On notera que l'on ne peut pas ecrire : */
/* */
/* (0x7fffffffffffffff)<<64 */
/* */
/* car cela donne le message : */
/* */
/* warning: left shift count >= width of type */
/* */
},
#else
#endif
{
0ULL, NULL, 0
},
};
/* Ces nouvelles definitions introduites le 20250828144642 viennent de : */
/* */
/* https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test */
/* */
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* T E S T D E P R I M A L I T E D E T E R M I N I S T E */
/* P O U R L E S N O M B R E S E N T I E R S I N F E R I E U R S */
/* A 2^64 O U 2^128 S U I V A N T L A V E R S I O N : */
/* */
/*************************************************************************************************************************************/
static const uint32_t first_prime=2;
static const uint32_t premiers_nombres_premiers[] = {
3, 5, 7, 11, 13, 17, 19, 23, 29
, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
, 73, 79, 83, 89, 97,101,103,107,109,113
,127,131,137,139,149,151,157,163,167,173
,179,181,191,193,197,199,211,223,227,229
,233,239,241,251,257,263,269,271,277,281
};
/* De ces 59 premiers nombres premiers, seuls les premiers sont utilises et leur nombre */
/* est donne par 'NOMBRE_DE_PREMIERS_NOMBRES_PREMIERS_UTILISES'... */
#define NOMBRE_DE_PREMIERS_NOMBRES_PREMIERS_UTILISES 19
static const uint32_t nombre_de_premiers_nombres_premiers = MIN2(NOMBRE_DE_PREMIERS_NOMBRES_PREMIERS_UTILISES,sizeof(premiers_nombres_premiers)/sizeof(uint32_t));
bool IsPrime(EntierNonSigne nombre)
{
if (nombre < first_prime)
{
return false;
}
else
{
}
if ((nombre % first_prime) == 0)
{
return (nombre == first_prime);
}
else
{
}
/* Petit crible rapide... */
for (size_t i=0 ; i < nombre_de_premiers_nombres_premiers ; i++)
{
if (nombre == premiers_nombres_premiers[i])
{
return true;
}
else
{
}
if (nombre % premiers_nombres_premiers[i] == 0)
/* Ainsi, on teste si 'n' est un nombre dit "friable"... */
{
return false;
}
else
{
}
}
/* Choix de l'ensemble de bases selon nombre. */
const struct mr_bound *row = MR___TABLE_2;
/* Le 20250828144642, passage de 'MR___TABLE_1' a 'MR___TABLE_2' a cause du faux positif : */
/* */
/* 1373653 = 829 x 1657 */
/* */
/* Mais, en fait cela ne changeait rien, par contre ce qui suit, oui... */
while ((row->limit) && (nombre >= row->limit))
/* Le 20250828144642, passage de 'nombre > ' a 'nombre >= ' a cause du faux positif : */
/* */
/* 1373653 = 829 x 1657 */
/* */
{
row++;
}
const uint32_t *bases;
size_t nbases;
if (row->limit)
{
bases = row->bases;
nbases = row->nbases;
}
else
{
/* Cas general : 7 bases fixes (Jaeschke ameliore). */
static const EntierNonSigne bigbases[] = {2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL};
for (size_t i=0 ; i < (sizeof(bigbases)/sizeof(EntierNonSigne)) ; i++)
{
if (!BasesMillerRabin(nombre,bigbases[i]))
{
return false;
}
else
{
}
}
return true;
}
for (size_t i=0 ; i < nbases ; i++)
{
if (!BasesMillerRabin(nombre,bases[i]))
{
return false;
}
else
{
}
}
return true;
}
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* A C C E S A U N O M B R E P R E M I E R S T R I C T E M E N T P R E C E D E N T : */
/* */
/*************************************************************************************************************************************/
#define PAS_DE_PARCOURS_DES_NOMBRES_ENTIERS 2
/* Introduit le 20250922105429 pour mettre en place un indicateur de progression... */
F__uint__ PreviousPrime(EntierNonSigne n)
{
EntierNonSigne NombrePremier=((n/2)*2)+1;
/* Afin de partir sur un nombre impair... */
if (n > premiers_nombres_premiers[0])
{
int iterer=true;
while (iterer == true)
{
static EntierNonSigne decrement=PAS_DE_PARCOURS_DES_NOMBRES_ENTIERS;
NombrePremier = NombrePremier - decrement;
if (IsPrime(NombrePremier))
{
iterer = false;
}
else
{
}
}
}
else
{
if (n == premiers_nombres_premiers[0])
{
NombrePremier = first_prime;
}
else
{
exit(false);
}
}
return NombrePremier;
}
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* A C C E S A U N O M B R E P R E M I E R S T R I C T E M E N T S U I V A N T : */
/* */
/*************************************************************************************************************************************/
F__uint__ NextPrime(EntierNonSigne n)
{
EntierNonSigne NombrePremier=n;
int iterer=true;
while (iterer == true)
{
static EntierNonSigne increment=1;
/* L'increment est egal a 1 au debut du processus, au cas ou 'n' serait egal a 2... */
NombrePremier = NombrePremier + increment;
if (IsPrime(NombrePremier))
{
iterer = false;
if ((NombrePremier & 1) == 1)
{
increment = PAS_DE_PARCOURS_DES_NOMBRES_ENTIERS;
/* Des qu'un nombre premier impair est rencontre, l'increment est optimise a 2... */
}
else
{
}
}
else
{
}
}
return NombrePremier;
}
/*===================================================================================================================================*/
/*************************************************************************************************************************************/
/* */
/* G E S T I O N D E S A R G U M E N T S D ' A P P E L : */
/* */
/*************************************************************************************************************************************/
#define GET_ARGUMENT(chaine,valeur) \
{ \
const char *s=chaine; \
valeur=ATOL(chaine); \
/* Introduit le 20251023100021 afin de permettre des valeurs negatives en particulier dans */ \
/* 'v $xu/""*""/TestPrimalite_MillerRabin_AvecBasesMagiques.03$vv$c DernierNombreEn'. */ \
}
Copyright © Jean-François COLONNA, 2026-2026.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2026-2026.
