Concours Général des Lycées 2005 — Matematica

Equilateral triangles, axial symmetries and complex affixes; conditions for collinearity and circumscribed circles, plus a study of functions describing extremal point sets.

In this exercise, we work in the plane $\mathcal{P}$ equipped with a direct orthonormal frame $(O;\vec{u},\vec{v})$.

1.1 Preliminaries of elementary geometry

1. Let $D$ and $D^{\prime }$ be two lines intersecting at a point $I$, and let $s$ and $s^{\prime }$ be the axial symmetries with axes $D$ and $D^{\prime }$ respectively. Show that $s^{\prime }\circ s$ is a rotation, and determine its characteristic elements.

2. Let $ABC$ be a direct equilateral triangle, $O$ the center of the circle circumscribed about $AC$. We denote by $s_1$, $s_2$ and $s_3$ the axial symmetries respectively with respect to the lines $(OA)$, $(OB)$ and $(OC)$, and by $r$ the rotation with center $O$ and angle $\frac{2\pi }{3}$. Let $M$ be a point of the plane, $M_1=s_1(M)$, $M_2=s_2(M)$, $M_3=s_3(M)$.

a. Show that $M_2=r^2(M_1)$ and $M_3=r(M_1)$, where $r^2$ denotes $r\circ r$.

b. What is the nature of the triangle $M_1{M}_2{M}_3$?

1.2 Complex numbers

The affix of the vector $\vec{u}$ equals $1$ and that of the vector $\vec{v}$ is the number $i$ (with $i^2=-1$), as is customary; we set $j=e^{2i\pi /3}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}$. We consider, for the plane $\mathcal{P}$, the points $O$, $A$, $B$ and $C$ with affixes respectively $0$, $1$, $j$ and $j^2$. We denote by $s_1$, $s_2$ and $s_3$ the axial symmetries respectively with respect to the lines $(OA)$, $(OB)$ and $(OC)$. Let finally $M$ be an arbitrary point of the plane $\mathcal{P}$, with affix $z=\rho e^{i\theta }$, $\rho \in {\mathbb{R}}^{\ast }$, $\theta \in \mathbb{R}$.

1. Let $M_1=s_1(M)$, $M_2=s_2(M)$, $M_3=s_3(M)$. Show that the points $M_1$, $M_2$ and $M_3$ have for affixes respectively $\bar{z}$, $j^2\bar{z}$ and $j\bar{z}$.

2. Let $M_4$ be the symmetric point of $M$ with respect to the line $(BC)$. Show that the point $J$ with affix $-\frac{1}{2}$ is the midpoint of the segment $[M_1{M}_4]$. Deduce the affix of $M_4$.

3. a. Under what condition are the points $M_2$, $M_3$ and $M_4$ collinear?

From now on suppose that $M_2$, $M_3$ and $M_4$ are not collinear; we denote by $\Omega$ the center of the circle circumscribed about the triangle $M_2{M}_3{M}_4$.

b. Justify the fact that $\Omega$ belongs to the line $(O{M}_1)$. In this case, we may write $\lambda e^{-i\theta }$ for the affix of $\Omega$, with $\lambda$ real.

c. Show that $\lambda =-\frac{1+2\rho \cos (\theta )}{\rho +2\cos (\theta )}$.

d. Deduce an expression of the radius $R$ of the circle circumscribed about the triangle $M_2{M}_3{M}_4$.

e. Show that this radius is equal to $1$ if and only if $\rho =1$ or $(\rho +\cos (\theta ){)}^2=1-3{\cos }^2(\theta )$.

4. Show that the circle circumscribed about the triangle $M_2{M}_3{M}_4$ has the same radius as the circle circumscribed about the triangle $M_1{M}_2{M}_3$ if and only if $M$ belongs to a set $\Gamma$ which we will specify geometrically. What can we say about the case of the two circles being concentric?

1.3 Study of functions

We consider the application $s$ defined for all $\theta \in [-\pi ;\pi ]$ by $s(\theta )=1-3{\cos }^3(\theta )$.

1. a. Study the variations of $s$. Specify its extrema, the values of $\theta$ for which $s(\theta )$ is zero, the set $E$ of $\theta \in [-\pi ;\pi ]$ such that $s(\theta )\ge 0$.

b. Deduce the shape of the curve described by the point of affix $s(\theta )e^{i\theta }$ when $\theta$ varies. We will specify the points of intersection with the axes and possibly some particular points (for $\theta =\frac{\pi }{6}$, $\frac{\pi }{4}$, $\frac{\pi }{3}$, for example). We will indicate the symmetries of the curve.

2. Let the function $r_1$ be defined for all $\theta \in E$ by $r_1(\theta )=\sqrt{1-3{\cos }^2(\theta )}-\cos (\theta )$.

a. Determine the values of $\theta$ for which $r_1(\theta )$ is zero.

b. Deduce the shape of the curve described by the point of affix $r_1(\theta )e^{i\theta }$ when $\theta$ varies.

3. Draw, then look for being extremely precise, the set of points $M$ such that the triangle $M_2{M}_3{M}_4$ defined in part 2 has a circumscribed circle of radius $1$.

Topic: Geometria piana, Algebra, Trigonometria Metodo: Trigonometria, Simmetria, Coordinate Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria, Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Triangoli equalaterali, simmetrie assiali e affixi complessi; condizioni di collinearità e cerchi circonscritti, oltre a uno studio delle funzioni che descrivono i set di punti estremi.

In questo esercizio, lavoriamo nel piano $\mathcal{P}$ dotato di un quadro ortonormale diretto $(O;\vec{u},\vec{v})$.

1.1 Preliminarie di geometria elementare

1. Lasciate che $D$ e $D^{\prime }$ siano due linee che si incrociano in un punto $I$, e lasciate che $s$ e $s^{\prime }$ siano rispettivamente le simmetrie assiali con gli assi $D$ e $D^{\prime }$. Indicare che $s^{\prime }\circ s$ è una rotazione e determinare i suoi elementi caratteristici.

2. $ABC$ sia un triangolo equilaterale diretto, $O$ il centro del cerchio circoscritto intorno a $AC$. Indichiamo con $s_1$, $s_2$ e $s_3$ rispettivamente le simmetrie assiali rispetto alle linee $(OA)$, $(OB)$ e $(OC)$, e con $r$ la rotazione con centro $O$ e angolo $\frac{2\pi }{3}$. $M$ sia un punto del piano, $M_1=s_1(M)$, $M_2=s_2(M)$, $M_3=s_3(M)$.

a. Indicare che $M_2=r^2(M_1)$ e $M_3=r(M_1)$, dove $r^2$ indica $r\circ r$.

b. Qual è la natura del triangolo $M_1{M}_2{M}_3$?

1.2 Numeri complessi

L’affisso del vettore $\vec{u}$ è uguale a $1$ e quello del vettore $\vec{v}$ è il numero $i$ (con $i^2=-1$), come è usuale; impostamo $j=e^{2i\pi /3}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}$. Per il piano $\mathcal{P}$ consideriamo i punti $O$, $A$, $B$ e $C$ con affixi rispettivamente $0$, $1$, $j$ e $j^2$. Indichiamo con $s_1$, $s_2$ e $s_3$ rispettivamente le simmetrie assiali rispetto alle linee $(OA)$, $(OB)$ e $(OC)$. Infine $M$ sia un punto arbitrario del piano $\mathcal{P}$, con l’affisso $z=\rho e^{i\theta }$, $\rho \in {\mathbb{R}}^{\ast }$, $\theta \in \mathbb{R}$.

1. Lasciate $M_1=s_1(M)$, $M_2=s_2(M)$, $M_3=s_3(M)$. Indicare che i punti $M_1$, $M_2$ e $M_3$ hanno per gli affixi rispettivamente $\bar{z}$, $j^2\bar{z}$ e $j\bar{z}$.

2. $M_4$ sia il punto simmetrico di $M$ rispetto alla linea $(BC)$. Indicare che il punto $J$ con affisso $-\frac{1}{2}$ è il punto medio del segmento $[M_1{M}_4]$. Riduzione dell’affisso di $M_4$.

3. a. In che condizione i punti $M_2$, $M_3$ e $M_4$ sono collineari?

D’ora in poi supponiamo che $M_2$, $M_3$ e $M_4$ non siano collineari; indichiamo con $\Omega$ il centro del cerchio circondato intorno al triangolo $M_2{M}_3{M}_4$.

b. giustificare il fatto che $\Omega$ appartiene alla linea $(O{M}_1)$. In questo caso, possiamo scrivere $\lambda e^{-i\theta }$ per l’affisso di $\Omega$, con $\lambda$ reale.

c. Mostra che $\lambda =-\frac{1+2\rho \cos (\theta )}{\rho +2\cos (\theta )}$.

d. Deduce un’espressione del raggio $R$ del cerchio circondato intorno al triangolo $M_2{M}_3{M}_4$.

e. Indicare che questo raggio è uguale a $1$ se e solo se $\rho =1$ o $(\rho +\cos (\theta ){)}^2=1-3{\cos }^2(\theta )$.

4. Mostra che il cerchio circondato intorno al triangolo $M_2{M}_3{M}_4$ ha lo stesso raggio del cerchio circondato intorno al triangolo $M_1{M}_2{M}_3$ se e solo se $M$ appartiene a un insieme $\Gamma$ che specificheremo geometricamente. Cosa possiamo dire del caso in cui i due cerchi siano concentrici?

1.3 Studio delle funzioni

Si considera l’applicazione $s$ definita per tutti $\theta \in [-\pi ;\pi ]$ da $s(\theta )=1-3{\cos }^3(\theta )$.

1. a. Studiare le variazioni di $s$. Indicare il suo estremo, i valori di $\theta$ per i quali $s(\theta )$ è zero, l’insieme $E$ di $\theta \in [-\pi ;\pi ]$ tale che $s(\theta )\ge 0$.

b. Ridurre la forma della curva descritta dal punto di affisso $s(\theta )e^{i\theta }$ quando $\theta$ varia. Specificheremo i punti di intersezione con gli assi e eventualmente alcuni punti particolari (per $\theta =\frac{\pi }{6}$, $\frac{\pi }{4}$, $\frac{\pi }{3}$, ad esempio). Indicheremo le simmetrie della curva.

2. La funzione $r_1$ deve essere definita per tutti $\theta \in E$ da $r_1(\theta )=\sqrt{1-3{\cos }^2(\theta )}-\cos (\theta )$.

a. Determinare i valori di $\theta$ per i quali $r_1(\theta )$ è zero.

b. Ridurre la forma della curva descritta dal punto di affisso $r_1(\theta )e^{i\theta }$ quando $\theta$ varia.

3. Disegna, poi cerca di essere estremamente preciso, l’insieme dei punti $M$ in modo tale che il triangolo $M_2{M}_3{M}_4$ definito nella parte 2 abbia un cerchio circonscritto di raggio $1$.

src_cgen_2005__Q01

A continuous function on [0;1] with f(0)=f(1)=0 satisfying a translation-displacement condition; prove f(x)=0 has at least seven solutions, then give an example.

Let $f:[0;1]⟶\mathbb{R}$ be a numerical function defined and continuous on the interval $[0;1]$. We suppose that $f(0)=f(1)=0$ and that for all real $x$ of the interval $\left[0;\frac{6}{10}\right]$, $f\left(x+\frac{4}{10}\right)\ne f(x)$.

1. Show that the equation $f(x)=0$ has at least seven solutions on $[0;1]$.

2. Give an example of a function $f$ verifying the hypotheses; we may content ourselves with a clear graphical representation.

Topic: Insiemi e funzioni, Algebra Metodo: Casework Abilita: Astrazione, Lettura attenta Area: Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Una funzione continua su [0;1] con f(0)=f(1)=0 che soddisfa una condizione di spostamento della traduzione; dimostra che f(x)=0 ha almeno sette soluzioni, quindi da un esempio.

$f:[0;1]⟶\mathbb{R}$ deve essere una funzione numerica definita e continua nell’intervallo $[0;1]$. Supponiamo che $f(0)=f(1)=0$ e che per tutti i $x$ reali dell’intervallo $\left[0;\frac{6}{10}\right]$, $f\left(x+\frac{4}{10}\right)\ne f(x)$.

1. Mostra che l’equazione $f(x)=0$ ha almeno sette soluzioni su $[0;1]$.

2. Date un esempio di una funzione $f$ che verifica le ipotesi; possiamo accontentarci di una rappresentazione grafica chiara.

src_cgen_2005__Q02

Iterating the incenter (then later the orthocenter) of a triangle from three non-collinear points; prove convergence of the sequence of points and study what changes when using the orthocenter.

We consider in the plane three points $A_0$, $B$, $C$ that are non-collinear.

1. We denote by $A_1$ the center of the circle inscribed in the triangle $A_{0}BC$ (that is, the point of intersection of the interior bisectors of the triangle $A_{0}BC$). We pursue the process by considering $A_2$, center of the circle inscribed in the triangle $A_{1}BC$, etc. Thus, for every natural integer $i$, $A_{i+1}$ is the center of the circle inscribed in the triangle $A_{i}BC$. Show that there exists a point $A$, limit of the sequence $(A_n)$, that is to say that $A{A}_n$ tends towards $0$ when $n$ tends to its position.

2. What becomes of the previous result if, at each step, for $i=0,1,2,\dots$, we take $A_{i+1}$ to be the orthocenter of the triangle $A_{i}BC$ instead of the center of the inscribed circle?

Topic: Geometria piana Metodo: Ricorsione, Estremalità Abilita: Ragionamento geometrico, Astrazione Area: Geometria Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Iterare l’incentro (poi più tardi l’ortocentro) di un triangolo da tre punti non collineari; dimostrare la convergenza della sequenza di punti e studiare quali cambiamenti si verificano con l’uso dell’ortocentro.

Consideramo nel piano tre punti $A_0$, $B$, $C$ che non sono collineari.

1. Indichiamo con $A_1$ il centro del cerchio inscritto nel triangolo $A_{0}BC$ (cioè il punto di intersezione dei bisettori interni del triangolo $A_{0}BC$). Proseguiamo il processo considerando $A_2$, il centro del cerchio inscritto nel triangolo $A_{1}BC$, ecc. Pertanto, per ogni intero naturale $i$, $A_{i+1}$ è il centro del cerchio iscritto nel triangolo $A_{i}BC$. Mostrare che esiste un punto $A$, limite della sequenza $(A_n)$, cioè che $A{A}_n$ tende verso $0$ quando $n$ tende verso la sua posizione.

2. Che cosa succede al risultato precedente se, ad ogni passo, per $i=0,1,2,\dots$, prendiamo $A_{i+1}$ per essere l’ortocentro del triangolo $A_{i}BC$ invece del centro del cerchio inciso?

src_cgen_2005__Q03

Discrete logarithm modulo a prime: primitive roots, definition and existence of the discrete log, an elementary algorithm, and Adleman’s index-calculus method with a probabilistic complexity analysis.

If $m_1$ and $m_2$ are two integers such that $m_1\le m_2$, we denote by $[m_1;m_2]$ the set of integers $k$ such that $m_1\le k\le m_2$.

If $a$, $b$ and $n$ are three integers, we note $a\equiv b(\mathrm{modulo}n)$ when $a$ and $b$ are congruent modulo $n$, that is to say when $b-a$ is a multiple of $n$.

Throughout this exercise, $p$ designates a prime number.

4.1 Definition of the discrete logarithm

For all $A\in \mathbb{N}$, we note $(A\mathrm{mod}p)$ the remainder of the Euclidean division of $A$ by $p$. It is the unique integer of $[0;p-1]$ congruent to $A$ modulo $p$.

An integer $x\in [1;p-1]$ is called a primitive root modulo $p$ when the set of the $(x^k\mathrm{mod}p)$ for $k\in N$ is the set $[1;p-1]$, that is to say when the powers of $x$, computed modulo $p$, describe $[1;p-1]$ entirely.

Thus for $p=5$:

• $1$ is not a primitive root modulo $5$ since its powers always equal $1$.
• $2$ is a primitive root modulo $5$, since: $(2^0\mathrm{mod}5)=1$, $(2^1\mathrm{mod}5)=2$, $(2^2\mathrm{mod}5)=4$, $(2^3\mathrm{mod}5)=3$.
• $3$ is a primitive root modulo $5$, since: $(3^0\mathrm{mod}5)=1$, $(3^1\mathrm{mod}5)=3$, $(3^2\mathrm{mod}5)=4$, $(3^3\mathrm{mod}5)=2$.
• $4$ is not a primitive root of $5$ since $(4^k\mathrm{mod}5)$, $k\in N$ takes alternately the value $1$ or $4$.

1. In this question we take $p=7$. Determine the primitive roots modulo $7$.

We admit henceforth that, whatever the prime number $p$, there exists at least one primitive root modulo $p$. In what follows, we designate by $g$ a primitive root modulo $p$.

2. a. Show that the set $\{g^k\mathrm{mod}p\}$ for $k\in [0;p-2]$ is $[1;p-1]$. b. Let $A\in [1;p-1]$. Justify the existence and uniqueness of an integer $a\in [1;p-2]$ such that $A=(g^a\mathrm{mod}p)$.

$a$ is called the logarithm of base $g$ modulo $p$ of $A$; we note it $\ell (A)$.

c. Let $b$ be a natural integer congruent to $a$ modulo $p$. Calculate $g^b\mathrm{mod}p$.

3. An elementary solution to determine $\ell (A)$ consists in computing the integers $\{g^k\mathrm{mod}p\}$, for $k=0,1,\dots$, until we find $A$. a. Describe an algorithm that realizes this work. b. In this question, we take $p=53$, $A=40$, $g=20$ (we will admit that $20$ is indeed a primitive root modulo $53$). Programming the previous algorithm on a calculator, determine $\ell (A)$.

4.2 Computation of the discrete logarithm by Adleman’s method

This part exploits the fact that the knowledge of the logarithms of a few integers allows one to rapidly determine the logarithm of any integer.

1. We place ourselves in the case $p=113$, $g=55$ and we give $\ell (2)=60$, $\ell (3)=5$. Find $\ell (54)$.

We suppose henceforth, for the rest of this part, the prime numbers $p_1,\dots ,p_n$ strictly less than $p$ and the integers $a_1,\dots ,a_n$ such that, for all $i\in [1;n]$, the prime factors of $(g^i\mathrm{mod}p)$ belong to $[p_1;\cdots ;p_n]$. For each $i\in [1;n]$, we thus have a relation $(g^{a_i}\mathrm{mod}p)=p_1^{e_{i,1}}{p}_2^{e_{i,2}}\cdots p_n^{e_{i,n}}$ where the $e_{i,j}$ for $(i,j)\in [1;n{]}^2$ are natural integers.

2. Show that, for all $i\in [1;n]$, $a_i=e_{i,1}\ell (p_1)+e_{i,2}\ell (p_2)+\cdots +e_{i,n}\ell (p_n)(\mathrm{modulo}(p-1))$.

3. In this question we take $p=53$, $g=20$, $n=2$, $p_1=2$, $p_2=5$. a. With the help of $g$ and $g^3$, determine $\ell (2)$ and $\ell (5)$. b. Deduce $\ell (40)$. c. How many integers of $[1;52]$ can be written in the form $2^{\alpha }{5}^{\beta }$, with $\alpha$ and $\beta$ natural integers?

4. Let $A\in [1;p-1]$. a. Show that the set $\{g^{s}A\mathrm{mod}p\}$ for $s\in [0;p-2]$ is $[1;p-1]$. b. We suppose known $s\in N$ such that $(g^{s}A\mathrm{mod}p)$ factorizes with the help of $p_1,\dots ,p_n$ uniquely. We suppose known $\ell (p_1),\dots ,\ell (p_n)$, deduce $\ell (A)$. c. With $p=53$ and $g=20$, determine $\ell (30)$.

5. We return to the general case. a. What is the number of integers of $[1;p-1]$ that are a power of $p_1$? b. Deduce the probability for that an integer $s\in [0;p-2]$ is such that $(g^{s}A\mathrm{mod}p)$ is a power of $p_1$. c. Show that the probability $P$ for that an integer $s\in [0;p-2]$ is such that $(g^{s}A\mathrm{mod}p)$ factorizes with the help of $p_1$ and $p_2$ uniquely verifies: $\frac{(\ln (p-1){)}^2}{2(p-1)\left(\ln p_1\right)\left(\ln p_2\right)}\le P\le \frac{1}{p-1}\left(\frac{\ln (p-1)}{\ln p_1}+1\right)\left(\frac{\ln (p-1)}{\ln p_2}+1\right).$ d. Generalize the result to the case of $n$ prime numbers $p_1,\dots ,p_n$.

Topic: Teoria dei Numeri, Algebra, Probabilità Metodo: Congruenze, Conteggio, Fattorizzazione Abilita: Manipolazione algebrica, Conteggio sistematico, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Logaritmo discreto modulo a primo: radici primitive, definizione e esistenza del registro discreto, un algoritmo elementare e il metodo di calcolo dell’indice di Adleman con un’analisi di complessità probabilistica.

Se $m_1$ e $m_2$ sono due integri tali da $m_1\le m_2$, indichiamo con $[m_1;m_2]$ l’insieme di integri $k$ tali da $m_1\le k\le m_2$.

Se $a$, $b$ e $n$ sono tre integri, si nota $a\equiv b(\mathrm{modulo}n)$ quando $a$ e $b$ sono modulo congruente $n$, cioè quando $b-a$ è un multiple di $n$.

Durante tutto questo esercizio, $p$ designa un numero primo.

4.1 Definizione del logaritmo discreto

Per tutti $A\in \mathbb{N}$, notiamo $(A\mathrm{mod}p)$ il resto della divisione euclidiana di $A$ da $p$. È il numero intero unico di $[0;p-1]$ congruente a $A$ modulo $p$.

Un numero intero $x\in [1;p-1]$ è chiamato modulo radice primitiva $p$ quando l’insieme del $(x^k\mathrm{mod}p)$ per $k\in N$ è l’insieme $[1;p-1]$, vale a dire quando le potenze di $x$, modulo calcolato $p$, descrivono interamente $[1;p-1]$.

Per $p=5$: - $1$ non è un modulo radice primitivo $5$ poiché le sue potenze sono sempre uguali a $1$. - $2$ è un modulo radice primitivo $5$, poiché: $(2^0\mathrm{mod}5)=1$, $(2^1\mathrm{mod}5)=2$, $(2^2\mathrm{mod}5)=4$, $(2^3\mathrm{mod}5)=3$. - $3$ è un modulo radicale primitivo $5$, poiché: $(3^0\mathrm{mod}5)=1$, $(3^1\mathrm{mod}5)=3$, $(3^2\mathrm{mod}5)=4$, $(3^3\mathrm{mod}5)=2$. - $4$ non è una radice primitiva di $5$ poiché $(4^k\mathrm{mod}5)$, $k\in N$ prende alternativamente il valore $1$ o $4$.

In questa domanda prendiamo $p=7$. Determinare le radici primitive modulo $7$.

Admettiamo che, qualunque sia il numero primo $p$, esiste almeno un modulo radice primitivo $p$. In quanto segue, indichiamo con $g$ un modulo radice primitivo $p$.

2. a. Indicare che l’insieme $\{g^k\mathrm{mod}p\}$ per $k\in [0;p-2]$ è $[1;p-1]$. b. Lasciate $A\in [1;p-1]$. Giustificare l’esistenza e l’unicità di un numero intero $a\in [1;p-2]$ tale che $A=(g^a\mathrm{mod}p)$.

$a$ è chiamato il logaritmo di base $g$ modulo $p$ di $A$; lo notiamo $\ell (A)$.

c. $b$ sia un intero naturale congruente a $a$ modulo $p$. Calcolare $g^b\mathrm{mod}p$.

3. Una soluzione elementare per determinare $\ell (A)$ consiste nel calcolare gli enti $\{g^k\mathrm{mod}p\}$, per $k=0,1,\dots$, fino a trovare $A$. a. Descrivere un algoritmo che realizza questo lavoro. b. In questa domanda, prendiamo $p=53$, $A=40$, $g=20$ (ammetteremo che $20$ è effettivamente un modulo radice primitivo $53$). Programmare l’algoritmo precedente su una calcolatrice, determinare $\ell (A)$.

4.2 Calcolo del logaritmo discreto con il metodo di Adleman

Questa parte sfrutta il fatto che la conoscenza dei logaritmi di alcuni numeri interi consente di determinare rapidamente il logaritmo di qualsiasi numero intero.

**1. ** Ci mettiamo nel caso $p=113$, $g=55$ e diamo $\ell (2)=60$, $\ell (3)=5$. Trova $\ell (54)$.

Supponiamo da ora in poi, per il resto di questa parte, i numeri primi $p_1,\dots ,p_n$ strettamente inferiori a $p$ e gli enti $a_1,\dots ,a_n$ in modo tale che, per tutti $i\in [1;n]$, i fattori primi di $(g^i\mathrm{mod}p)$ appartengono a $[p_1;\cdots ;p_n]$. Per ogni $i\in [1;n]$, abbiamo quindi una relazione $(g^{a_i}\mathrm{mod}p)=p_1^{e_{i,1}}{p}_2^{e_{i,2}}\cdots p_n^{e_{i,n}}$ in cui $e_{i,j}$ per $(i,j)\in [1;n{]}^2$ sono integri naturali.

**2. ** Indicare che, per tutti $i\in [1;n]$, $a_i=e_{i,1}\ell (p_1)+e_{i,2}\ell (p_2)+\cdots +e_{i,n}\ell (p_n)(\mathrm{modulo}(p-1))$.

In questa domanda prendiamo $p=53$, $g=20$, $n=2$, $p_1=2$, $p_2=5$. a. Con l’aiuto di $g$ e $g^3$, determinare $\ell (2)$ e $\ell (5)$. b. Riduzione $\ell (40)$. c. Quanti integri di $[1;52]$ possono essere scritti nella forma $2^{\alpha }{5}^{\beta }$, con $\alpha$ e $\beta$ integri naturali?

**4. ** Lasciate $A\in [1;p-1]$. a. Indicare che l’insieme $\{g^{s}A\mathrm{mod}p\}$ per $s\in [0;p-2]$ è $[1;p-1]$. b. Supponiamo conosciuto $s\in N$ in modo tale che $(g^{s}A\mathrm{mod}p)$ factorizza con l’aiuto di $p_1,\dots ,p_n$ in modo unico. Supponiamo conosciuto $\ell (p_1),\dots ,\ell (p_n)$, dedurre $\ell (A)$. c. Con $p=53$ e $g=20$, determinare $\ell (30)$.

Ritorniamo al caso generale. a. Qual è il numero di integri di $[1;p-1]$ che sono una potenza di $p_1$? b. Ridurre la probabilità che un intero $s\in [0;p-2]$ sia tale che $(g^{s}A\mathrm{mod}p)$ sia una potenza di $p_1$. c. Mostra che la probabilità $P$ per un intero $s\in [0;p-2]$ è tale che $(g^{s}A\mathrm{mod}p)$ fattorizza con l’aiuto di $p_1$ e $p_2$ verifica in modo unico: $\frac{(\ln (p-1){)}^2}{2(p-1)\left(\ln p_1\right)\left(\ln p_2\right)}\le P\le \frac{1}{p-1}\left(\frac{\ln (p-1)}{\ln p_1}+1\right)\left(\frac{\ln (p-1)}{\ln p_2}+1\right).$ . Generalizza il risultato al caso di $n$ numeri primi $p_1,\dots ,p_n$.

src_cgen_2005__Q04