Mines Informatique MP-PC-PSI 2019

A2019 --- INFO

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH,
CHIMIE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVEP.

CONCOURS 2019
ÉPREUVE D'INFORMATIQUE COMMUNE

Durée de l'épreuve : 1 heure 30 minutes

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve est commune aux candidats des filières MP, PC et PSI
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE COMMUNE
L'énoncé de cette épreuve comporte 9 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur

d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.
AUTOUR DES NOMBRES PREMIERS

Préambule

Chiffrer les données est nécessaire pour assurer la confidentialité lors 
d'échanges d'informations
sensibles. Dans ce domaine, les nombres premiers servent de base au principe de 
clés publique et
privée qui permettent, au travers d'algorithmes, d'échanger des messages 
chiffrés. La sécurité de
cette méthode de chiffrement repose sur l'existence d'opérations mathématiques 
peu coûteuses en
temps d'exécution mais dont l'inversion (c'est-à-dire la détermination des 
opérandes de départ à
partir du résultat) prend un temps exorbitant. On appelle ces opérations « 
fonctions à sens unique ».
Une telle opération est, par exemple, la multiplication de grands nombres 
premiers. Il est aisé de
calculer leur produit. Par contre, connaissant uniquement ce produit, il est 
très difficile de déduire
les deux facteurs premiers.

Le sujet étudie différentes questions sur les nombres premiers.

Les programmes demandés sont à rédiger en langage Python 3. Si toutefois le 
candidat utilise une
version antérieure de Python, il doit le préciser. Il n'est pas nécessaire 
d'avoir réussi à écrire le code
d'une fonction pour pouvoir s'en servir dans une autre question. Les questions 
portant sur les bases
de données sont à traiter en langage SQL.

Définitions, rappels et notations

Un nombre premier est un entier naturel qui admet exactement deux diviseurs : 1 
et lui-même.
Ainsi 1 n'est pas considéré comme premier.

e Un flottant est la représentation d'un nombre réel en mémoire.

e Quand une fonction Python est définie comme prenant un « nombre » en 
paramètre cela signifie
que ce paramètre pourra être indifféremment un flottant ou un entier.

e On note |x| la partie entière de x.

e abs(x) renvoie la valeur absolue de x. La valeur renvoyée est du même type de 
données que celle
en argument.

int(x) convertit vers un entier. Lorsque x est un flottant positif ou nul, elle 
renvoie la partie
entière de x, c'est-à-dire l'entier n tel queen  1) on calcule :

x, = reste de la division euclidienne de x°_, par M (2)

où M est le produit de deux nombres premiers quelconques et x, une valeur 
initiale nommée
« graine » choisie aléatoirement. On utilise ici l'horloge de l'ordinateur 
comme source pour %o.
Puis, pour chaque x;, s'il est impair, on additionne 2° à A.

 Q11 - On répète (2) pour à parcourant [1,N -- 1], quelle sera la valeur de À 
si x; est impair à
chaque itération ?

U Q12 - Compléter (avec le nombre de lignes que vous jugerez nécessaire) la 
fonction bbs (N)
donnée ci-dessous qui réalise ces itérations. La graine est un entier 
représentant la fraction de
secondes du temps courant, par exemple 1528287738.7931523 donne la graine 
7931523. Le paramètre
N est un entier non nul.

def bbs(N):

pl = 24375763

p2 = 28972763

M = pl *x p2

#Æ calculer la graine
(à compléter)

A = 0

for i in range(N):
if ... (à compléter) # si xi est impair

À = À + 2x%xxi
#Æ calculer le nouvel xi
xi -- ... (à compléter)
return (A)

Le test probabiliste de primalité le plus simple est le test de primalité de 
Fermat. Ce test utilise
la contraposée du petit théorème de Fermat qu'on peut évoquer comme suit : si a 
EUR [2,p -- 1] est
premier et que le reste de la division euclidienne de a?! par p vaut 1, alors 
il y a de "fortes" chances
pour que p soit premier.

LH Q13 --- En combinant les résultats du test de primalité de Fermat pour a = 
2, a = 3, a = 5
et a = 7, écrire une fonction premier_rapide(n_max) qui renvoie un nombre 
aléatoire inférieur
strictement à n_max qui a de fortes chances d'être premier. Le paramètre n_max 
est un entier
supérieur à 12.

H Q14 - On souhaite caractériser le taux d'erreurs de premier_rapide.

Écrire une fonction stats_bbs_fermat(N, nb) qui contrôle pour nb nombres, 
inférieurs ou égaux
à N, générés par premier_rapide, qu'ils sont réellement premiers. Cette 
fonction renvoie le taux
relatif d'erreur ainsi que la liste des faux nombres premiers trouvés. Les 
paramètres N et nb sont
des entiers strictement positifs.
Partie III. Compter les nombres premiers

La question de la répartition des nombres premiers a été étudiée par de 
nombreux mathémati-
ciens, dont Euclide, Riemann, Gauss et Legendre. On étudie dans cette partie 
les propriétés de la
fonction T(n), qui renvoie le nombre de nombres premiers appartenant à |1,n].

ITL.a Calcul de r(n) via un crible

2 Q15- Écrire une fonction Pi (N) qui calcule la valeur exacte de r(n) pour 
tout entier n de [1.N]|.
Les nombres premiers sont déduits de la liste Liste_bool renvoyée par la 
fonction erato_iter de
la question 8. On demande que Pi(N) renvoie son résultat sous la forme d'une 
liste de [n, T(n)].
Par exemple Pi(4) renvoie la liste [[1, O[, [2, 1}, [3, 2}, [4, 2/1.

Un seul appel à erato_iter est autorisé et on exige une fonction dont la 
complexité, en dehors de
cet appel, est linéaire en fonction de N. Le paramètre N est un entier 
supérieur à 1.

Il a été prouvé que Rtn)=1 < m(n) pour tout n > 5393. On souhaite vérifier 
cette inégalité en se
basant sur la fonction Pi (N) écrite en Question 15.

LH Q16 - Écrire une fonction verif_Pi(N) qui renvoie True si l'inégalité est 
vérifiée jusqu'à N
inclus, False sinon. Le paramètre N est un entier supposé supérieur ou égal à 
5393.

IITI.b Calcul d'une valeur approchée de T(n)

Le calcul de T(n) dépend de la capacité à calculer de manière exhaustive tous 
les nombres premiers
de [1,N], or le temps nécessaire à ce calcul devient rapidement très grand 
lorsque N augmente.
Il existe en revanche diverses méthodes pour calculer une valeur approchée de 
r(n). Une méthode
utilise la fonction logarithme intégral li, dont une représentation graphique 
est fournie en figure 1,
et qui est définie comme :

i:R'\{1} --R (3)

| -- 17 x

0 7 Six > 1, l'intégrale impropre doit être interpré-
NX tée comme sa valeur principale de Cauchy qui est

: \1/ définie comme :
un un (ff) 6

L'intérêt de li pour compter les nombres premiers
vient de la propriété suivante :

0.0 0.5 1.0 1.5 2.0 2.5
X

FIGURE 1 -- Allure de li sur [0,2.5] lim r(Læ]) -- | (5)

T--00 li(x)

On souhaite développer un programme permettant de calculer une valeur approchée 
de li. On
compare ensuite les résultats obtenus à une implémentation de référence qui est 
nommée ref_li,
réputée très précise.
Écart relatif

Estimation de li par quadrature numérique

On choisit d'utiliser la méthode des rectangles à droite. On appelle pas la 
base des rectangles. La
figure 4 illustre cette méthode appliquée au calcul de la valeur principale 
définie équation (4).

Par souci de simplification, on suppose que pas est choisi de manière à ce que 
1 et x soient multiples
de pas et on utilise EUR -- pas dans l'équation (4).

LH Q17 -- La fonction qui est évaluée sur l'intervalle d'intégration est 
supposée avoir une complexité
constante quelles que soient ses valeurs d'entrée. Quelle est la complexité en 
temps de la méthode
des rectangles à droite ? On prendra soin d'expliciter en fonction de quelle 
variable d'entrée cette
complexité est exprimée.

LH Q18 -- Dans les mêmes conditions d'évaluation, quelle est la complexité en 
temps de la méthode
des rectangles centrés ? Donner aussi celle de la méthode des trapèzes.

 Q19 - Écrire une fonction inv_1n_rect_d(a, b, pas) qui calcule par la méthode 
des rectangles
à droite une valeur approchée de [' HO) avec un incrément valant pas. On 
suppose dans cette
question que a < b et que 1 n'appartient pas à l'intervalle {a, b] de sorte que la fonction intégrée est définie et continue sur |a, b|. On considère que le réel b -- a est un multiple du réel pas. Les paramètres a, b et pas sont des flottants. J Q20 - Écrire une fonction 1i_d(x, pas) qui calcule une valeur approchée de li(x) avec la méthode des rectangles à droite en se basant sur inv_I1n_rect_d. Six -- 1 la fonction renvoie --o. On rappelle qu'on suppose que pas est choisi de manière à ce que 1 et x soient multiples de pas et qu'on utilise EUR -- pas dans l'équation (4). Les paramètres x et pas sont des flottants. Analyse des résultats de l1i_d Après avoir testé 1i_d on obtient plusieurs résultats surprenants. 100 - 102 1071 - 101 1 1072 E < 1 e ] e 107? ] 10° : f 100 Écart absolu --100 10! --10? 0.0 0.5 1.0 1.5 2.0 2.5 FIGURE 2 -- Écart relatif entre li_d FIGURE 3 -- Écart absolu entre li_d (pas = 107*) et l'implémentation de (pas = 107*) et l'implémentation de référence ref _li. référence ref _li. LH Q21 - Expliquer le comportement de l'écart relatif entre 1i_d et ref_1li, illustré figure 2 au voisinage de x © 1.4. LH Q22 - On constate un écart absolu important entre li_d et ref_1li au delà de x -- 1, illustré figure 3. Expliquer succinctement d'où vient ce phénomène. On ne demande pas une démonstration mathématique rigoureuse. Pour répondre à cette question on pourra remarquer qu'au premier ordre RG oe "OS quand 1 e e In(æ) e [1 --EEUR,1+EUR]) avec EUR 1. Une analyse géométrique de la figure 4 peut aussi s'avérer utile. e -- 0 et s'interroger sur la valeur que devrait avoir l'intégrale impropre de sur un intervalle LH Q23 - Proposer, en justifiant votre choix, une ou des modifications de l'algorithme utilisé afin d'éliminer le problème constaté sur l'écart absolu. Il n'est pas demandé d'écrire le code mettant en OEuvre ces propositions. 10 - --.-- In(x) © Points évalués pour les rectangles à droite 103 _ La T 10? _ / m / 101 - pas | - US = = = sn un us ss ll ms us mx 7 " 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 I.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 X FIGURE 4 -- Rectangles utilisés par la méthode des rectangles à droite au voisinage de 1 afin de calculer la valeur principale de Cauchy introduite dans l'équation (4). Les paramètres sont pas = EUR = 10 * Estimation de li via Ei L'approche par quadrature numérique n'est pas satisfaisante. Non seulement elle rend le temps d'exécution de 1i_d prohibitif quand x augmente mais de plus l'utilisateur doit choisir un pas sans règle claire à appliquer pour garantir une précision donnée. La fonction exponentielle intégrale Ei permet de pallier ce problème. Ei:R* --kR (6) T et x > | -- dt
_ot

Pour le cas x > 0 on utilise la valeur principale de Cauchy telle que vue pour 
li.
Le lien entre li et Ei est :

li(x) = Ei(In(x)) (7)

Afin d'évaluer numériquement la valeur de Ei en un point on se base sur son 
développement (dit
en série de Puiseux) sur RT* :

x"

Ei(x) = ++In(x) +5 LT (8)

Avec y © 0.577215664901 la constante d''Euler-Mascheroni.
Comme l'évaluation de la somme jusqu'à l'infini est impossible on utilise en 
pratique la somme

suivante :

x"

Ei,(x) = 9 + n(x) + ÿ LT (9)

Le choix de n se fait en comparant Ei,,_, à E1,, jusqu'à ce qu'ils soient 
considérés comme suffisament
proches.

L'évaluation via un ordinateur de ce développement est numériquement stable 
jusqu'à x -- 40. Au
delà les résultats sont entachés d'erreurs de calcul et d'autres méthodes 
doivent être utilisées.

D Q24 - Écrire une fonction li_dev(x) qui calcule li(x) en se basant sur Ei, et 
la fonction
sont_proches de la question 2 (on pourra utiliser la fonction associée même si 
la question n'a pas
été traitée). li_dev doit renvoyer False si :

e Ei,_1 et E1, ne peuvent pas être considérés comme proches au bout de MAXIT 
itérations.

e la valeur de x ne permet pas d'aboutir à un résultat.
Prendre MAXIT = 100 se révèle largement suffisant à l'usage.
On demande à ce que la complexité dans le pire des cas soit O(MAXIT). Le 
paramètre x est un
flottant quelconque.

Partie IV. Analyse de performance de code

Au cours du développement des fonctions nécessaires à la manipulation des 
nombres premiers on
s'aperçoit que le choix des algorithmes pour évaluer chaque fonction est 
primordial pour garantir
des performances acceptables. On souhaite donc mener des tests à grande échelle 
pour évaluer les
performances réelles du code qui a été développé. Pour ce faire on effectue un 
grand nombre de tests
sur une multitude d'ordinateurs. Les données sont ensuite centralisées dans une 
base de données
composée de deux tables.
La première table est ordinateurs et permet de stocker des informations sur les 
ordinateurs utilisés
pour les tests. Ses attributs sont :

e nom TEXT, clé primaire, le nom de l'ordinateur.

e gflops INTEGER la puissance de l'ordinateur en milliards d'opérations 
flottantes par seconde.

e ram INTEGER la quantité de mémoire vive de l'ordinateur en Go.
Exemple du contenu de cette table :
nyarlathotep114 69
nyarlathotep119 137
shubniggurath42 133
azathoth137 89

16
8

La seconde table est fonctions et stocke les informations sur les tests 
effectués pour différentes
fonctions en cours de développement. Ses attributs sont :
e id INTEGER l'identifiant du test effectué.
e nom TEXT le nom de la fonction testée (par exemple li, Ei, etc).
e algorithme TEXT le nom de l'algorithme qui permet le calcul de la fonction 
testée (par exemple

BBS si on teste une fonction de génération de nombres aléatoires).

e teste_sur TEXT le nom du PC sur lequel le test a été effectué.
e temps_exec INTEGER le temps d'exécution du test en millisecondes.
Exemple du contenu de cette table :

1d nom

1 li

2 li

3 li

2154 Ei

2155 aleatoire

algorithme
rectangles
rectangles
trapezes

puiseux
BBS

teste_sur

nyarlathotepi65
shubniggurath28
nyarlathotepi65

nyarlathotepi4s
azathoth14is

temps_exec

LH Q25 - Expliquer pourquoi il n'est pas possible d'utiliser l'attribut nom 
comme clé primaire de

la table fonctions.

J Q26 - Écrire des requêtes SQL permettant de :

1. Connaiïtre le nombre d'ordinateurs disponibles et leur quantité moyenne de 
mémoire vive.

2. Extraire les noms des PC sur lesquels l'algorithme rectangles n'a pas été 
testé pour la

fonction nommée li.

3. Pour la fonction nommée Ei, trier les résultats des tests du plus lent au 
plus rapide. Pour
chaque test retenir le nom de l'algorithme utilisé, le nom du pc sur lequel il 
a été effectué et

la puissance du PC.

Fin de l'épreuve.