A Caruso
email: caruso@lns.infn.it

F Consoli
email: consoli@lns.infn.it

D Rifuggiato

G Gallo

T Spartà

E Zappalà

A Longhitano

M Di

LNS ACTIVITY REPORT 2009 183 SLOW CHOPPER PROTOTYPE FOR THE SPIRAL 2PP PROJECT

A preliminary prototype of the slow chopper [1] for the Spiral 2 Preparatory Phase project [2] has been designed, developed and tested at INFN-LNS. The final version of the slow chopper will be placed along the beam line common to protons, deuterons and A/Q = 3 ions. This activity report shows the study, the hardware and the measurement results of the chopper prototype.

THE LOW ENERGY LINE

The low energy (LEBT) line of the Spiral 2 driver is designed to transport CW and high intensity beams of protons (5 mA), deuterons (5 mA) and ions (1 mA) with A/Q = 3 to the radiofrequency quadrupole (RFQ). The RFQ input energy is 20 keV/A and source voltages of 20, 40 and 60 kV are used for the 3 kind of particles. As shown in Figure 1, the chopper is located at the beginning of the common section just before the beam stop. The chopper will be used to progressively increase the beam power during accelerator tuning, to rapidly remove the beam in case of failure detection, to avoid hitting the wheel spokes of rotating targets similar to the one shown in Figure 2 (FULIS or S3 experiences).

CHOPPER REQUIREMENTS

The accelerator tuning is performed at quite low frequency. Due to the high beam power of 200 kW, a very large range of duty cycles will be used, starting from very low fractions (10 -4 ). The rotating target asks for pulse repetition rates around 1 kHz. In both cases rapid transition times are required to avoid fractions of beam, neither accelerated nor deviated, to be lost through the LINAC.

The chopper voltage depends on the ion source voltage, on the distance and length of the plates and on the beam stop location. Due to the LEBT line architecture and to the current intensity, the beam transversal section at the chopper location is quite large and relevant voltages have to be applied to the electrodes to compensate their distance.

In our case, the beam section has a diameter of 76 mm, the electrode hard-edge length considered in the beam dynamics simulations is of 160 mm, the deflection at the end of the plates is of 10 mm, and a total deviating voltage of 17 kV has therefore to be applied. Transient times for the pulse have to be shorter than 100 ns, and an amplitude stability of a few percents is required High reliability and easy maintenance are also important requirements of the device.

ELECTRODE GEOMETRY

The preliminary geometry shown in Figure 3 was designed to have a flat transversal field and to produce field maps for beam dynamic simulations. It was chosen to feed the chopper with one plate positively biased and one grounded, because this solution let a easier water cooling of the ground electrode if some beam is eventually lost. The deflection plane is horizontal because the beam section is smaller on this plane than on the vertical one. In Figure 4 the simulation for the electric field is shown. To obtain the deviating field, a pulse of 9.2 kV has to be applied to the electrode, whose capacitance is around 15 pF. The pulse duty cycle defines the attenuation on the beam.

SLOW CHOPPER DEVELOPMENT

The development of the Spiral 2 device regards a two years period. In this first year, the power circuit, the feed-through and the assembling concept have been studied and tested on a prototype.

The design approach was strongly addressed towards reliability and decreasing of the maintenance time, both being very important issues in high power accelerators.

Electrical design

The principle scheme of the chopper is represented in Figure 5. A high voltage switch, alternatively connects the electrode to ground or to the high voltage power supply, following the timing signal repetition rate and the duty cycle. A high voltage sealed connector is used as feedthrough. Numerical values, considered for the design, are summarized in Table 1. To fit the requirements, 10 Watt, off-the-shelf devices have been selected. A standard pulse/function generator AFG310 by Tektronix is used to drive the switch, while the main components of the system are:

• Power supply MPS10P10/24 by Spellman • Solid state switch HTS151-03-GSM by Behlke • Vacuum feed-through SHV-20 by Caburn • Coaxial cable HTC-50-7-2 by Draka Figure 6 shows the scheme of the electronic cabinet. The high voltage switch, the power supply and the 1 nF buffer capacitance are visible in the rack. The solid state switch consists of two identical mosfet switching paths that form a so-called half bridge circuit configuration. Both switching paths are controlled by a common logic driver. The power supply can deliver up to 10 kV, 1 mA. The switch and the electrode are connected by a low loss coaxial cable. Great care was taken to assemble these modules into the rack. Special attention was given for grounding and shielding all the components.

Mechanical design

The mechanical assembling of Figure 7 was designed to test the feed-through in operating conditions and to verify the assembling concept and the plate alignment. A standard beam line cross section with six gates was used to host the electrodes. Each electrode is constituted of a plate of 3 mm thick copper sheet supported by a copper column. They are inserted from opposite sides and each one is supported by its vacuum flange. The ground electrode is connected directly to the flange while the high voltage plate is brazed to the feed-through connector. The ceramic feed-through is a standard 20 kV single ended coaxial SHV connector. A capacitive pickup is inserted near the feed-through to be used to check the pulse presence, but the alarm board still has to be developed.

Feed-through study

A delicate point in the chopper realization is the proper high voltage feed-through. Different solutions were taken into account. A suitable numerical study was performed on this purpose. The MDC-Caburn SHVE20-1-W weldable feedthrough was therefore employed. In Figure 8 it is shown a section of it, with the indication of the two parameters d and r. The related electrostatic simulation, for a 10 kV feed, is shown in Figure 9. In the A point the voltage assumes its maximum. In Figure 10 the values of this maximum, for different values of d and r, are given.

EXPERIMENTAL RESULTS

A total capacitance of about 30 pF was measured at the feed-through connector input. The cable adds some 70 pF and the data sheet gives a value of 30 pF for the switch output capacitance. With a total capacitance lower than 150 pF, the system should be able to work up to a repetition rate of 1 kHz. Anyway, the measured and stable operating range (Figure 11) was smaller, and was limited by the current of the high voltage power supply. Some preliminary tests with a Spellman MPS10P20/24, 20 W power supply, were therefore performed, and the required 1 kHz repetition rate was reached. More tests about it have to be performed. Measurements of the transient times confirmed the data sheet performances: rise and fall times are around 30 ns (see Figure 12). Long time tests on the complete apparatus have been performed up to 10 kV, at the 50 Hz frequency, and with Duty Cycle in the range [0.01%, 99.99%] to check the circuit reliability and the stability of the pulse parameters. The amplitude stability is better then 1%, and no changes where observed in the delay between the driver and high voltage edges, which is of 160 ns as shown in Figure 13, for the 10 kV pulse at 700 Hz, and with 50% duty cycle.

Figure 13: Pulse jitter @700 Hz, DC = 50%, 10 kV, between the driver and the measured voltage at the switch output.

CONCLUSION AND PERSPECTIVES

The pulse amplitude, jitter and transition time measured on the prototype fulfil the requirements, while a more powerful high voltage supply has been required to achieve a 1 kHz repetition rate. A complete system (electronics and electrodes) is available today for beam tests and next efforts will be dedicated to the design of the alarm control card and of the computer control interface and to the manufacture of the final mechanical ensemble to be installed on the Spiral2 injector.

AKNOWLEDGEMENTS

INFN LNS is member of the SPIRAL 2 Preparatory Phase. This work is supported by the European Commission within the 7 th Framework Program: project n. 212692.

Figure 1 :

 1 Figure 1: The injector low energy lines and the slow chopper position.

Figure 2 :

 2 Figure 2: FULIS rotating target wheel (courtesy of C. Stodel)

Figure 3 :

 3 Figure 3: The electrode geometry; the plate bending angle is 20°.

Figure 4 :

 4 Figure 4: Electric field on the transversal plane and on the beam axis.

Figure 5 :

 5 Figure 5: Principle scheme of the chopper.

Figure 6 :

 6 Figure 6: Scheme of the electronic cabinet.

Figure 7 :

 7 Figure 7: Cross-section of the assembled electrodes.

Figure 8 :AFigure 9 :

 89 Figure 8: Section of the MDC-Caburn SHVE20-1-W feed-through.

Figure 10 :

 10 Figure 10: Field in the A point for the structure of Figure 8, for different values of the d and r parameters.

Figure 11 :

 11 Figure 11: Measured and stable prototype operating range.

Figure 12 :

 12 Figure 12: Measured rise and fall times.

Table 1 :

 1 Design Parameters for the Chopper Power Circuit

	Maximum voltage:	10 kV
	Rise/fall time under	100 ns
	Duty cycle variable from 0 to 100%
	Repetition frequency	from few hertz to 1 kHz


Alexandre Berzati
email: alexandre.berzati@cea.fr

Cécile Canovas
email: cecile.canovas@cea.fr

Jean-Guillaume Dumas
email: jean-guillaume.dumas@imag.fr

Louis Goubin
email: louis.goubin@prism.uvsq.fr

Fault Attacks on RSA Public Keys: Left-To-Right Implementations are also Vulnerable

Keywords: RSA, fault attacks, "Left-To-Right" exponentiation, number theory

After attacking the RSA by injecting fault and corresponding countermeasures, works appear now about the need for protecting RSA public elements against fault attacks. We provide here an extension of a recent attack [BCG08] based on the public modulus corruption. The difficulty to decompose the "Left-To-Right" exponentiation into partial multiplications is overcome by modifying the public modulus to a number with known factorization. This fault model is justified here by a complete study of faulty prime numbers with a fixed size. The good success rate of this attack combined with its practicability raises the question of using faults for changing algebraic properties of finite field based cryptosystems.

Introduction

Injecting faults during the execution of cryptographic algorithms is a powerful way to recover secret information. Such a principle was first published by Bellcore researchers [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults[END_REF][START_REF] Boneh | On the Importance of Eliminating Errors in Cryptographic Computations[END_REF] against multiple public key cryptosystems. Indeed, these papers provide successful applications including RSA in both standard and CRT modes. This work was completed, and named Differential Fault Analysis (DFA), by E. Biham and A. Shamir with applications to secret key cryptosystems [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF]. The growing popularity of this kind of attack, in the last decade, was based on the ease for modifying the behavior of an execution [BECN + 04] and the difficulty for elaborating efficient countermeasures [START_REF] Blömer | A New CRT-RSA Algorithm Secure Against Bellcore Attack[END_REF][START_REF] Wagner | Cryptanalysis of a provably secure CRT-RSA algorithm[END_REF][START_REF] Giraud | Fault-Resistant RSA Implementation[END_REF].

Many applications against the RSA cryptosystem, based on fault injection, have been published. The first ones dealt with the perturbation of the private key or temporary values during the computation [BDL97, BDJ + 98, BDL01]. The perturbation of public elements was considered as a real threat when J-P. Seifert published an attack on the RSA signature check mechanism [START_REF] Seifert | On Authenticated Computing and RSA-Based Authentication[END_REF][START_REF] Muir | Seifert's RSA Fault Attack : Simplified Analysis and Generalizations[END_REF]. This paper first mentions the possibility of modifying the public modulus N such that the faulty one is prime or easy to factor. Then, E. Brier et al. extended this work to the full recovery of the private exponent d for various RSA implementations [START_REF] Brier | Why One Should Also Secure RSA Public Key Elements[END_REF]. Both works are based on the assumption that the fault occurs before performing the RSA modular exponentiation. A. Berzati et al. first address the issue of modifying the modulus during the exponentiation [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF].Still this work was limited to an application against "Right-To-Left" type exponentiation algorithms.

In this paper we aim to generalize the previous attack to "Left-To-Right" type exponentiations. Under the fault assumption that the modulus can become a number with a known factorization, we prove that it is possible to recover the whole private exponent. We provide a detailed study of this fault model, based on number theory, to show its consistency and its practicability for various kinds of perturbation. Finally, we propose an algorithm to recover the whole private exponent that is efficient either in terms of fault number or in computational time.

Background

Notations

Let N , the public modulus, be the product of two large prime numbers p and q. The length of N is denoted by n. Let e be the public exponent, coprime to ϕ(N ) = (p -1) • (q -1), where ϕ(•) denotes Euler's totient function. The public key exponent e is linked to the private exponent d by the equation e • d ≡ 1 mod ϕ(N ). The private exponent d is used to perform the following operations. RSA Signature: The signature of a message m is given by S ≡ ṁd mod N where ṁ = µ(m) for some hash and/or deterministic padding function µ.

RSA

The signature S is validated by checking that S e ≡ ṁ mod N . 2 : for i from (n -1) downto 0 3 : for i from 0 upto (n -1) 3 :

Modular exponentiation algorithms

A := A 2 mod N ; 4 : if (d i == 1) 4 : if (d i == 1) 5 : A := (A • B) mod N ; 5 : A := (A • m)
= n-1 i=0 2 i • d i .
Their polynomial complexity with respect to the input length make them very interesting to perform modular exponentiation.

The Algorithm 1 describes a way to compute modular exponentiations by scanning bits of d from least significant bits (LSB) to most significant bits (MSB). That is why it is usually referred to as the "Right-To-Left" modular exponentiation algorithm. This is that specific implementation that is attacked in [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF] by corrupting the public modulus of RSA.

The dual algorithm that implements the binary modular exponentiation is the "Left-To-Right" exponentiation described in Algorithm 2. This algorithm scans bits of the exponent from MSB to LSB and is lighter than "Right-To-Left" one in terms of memory consumption.

3 Modification of the modulus and extension attempt 3.1 Previous work J-P. Seifert first addressed the issue of corrupting RSA public key elements [START_REF] Seifert | On Authenticated Computing and RSA-Based Authentication[END_REF][START_REF] Muir | Seifert's RSA Fault Attack : Simplified Analysis and Generalizations[END_REF]. This fault attack aims to make a signature verification mechanism accept false signatures by modifying the value of the public modulus N .

No information about the private exponent d is revealed with this fault attack. Its efficiency is linked to the attacker's ability to reproduce the fault model chosen for the modification of the modulus. Seifert's work inspired the authors of [START_REF] Brier | Why One Should Also Secure RSA Public Key Elements[END_REF] who first used the public modulus perturbation to recover the whole private key d. The attacker has to perform a perturbation campaign to gather a large enough number of (message, faulty signature) pairs. As in Seifert's attack, the fault on the modulus is induced before executing the exponentiation. Three methods based on the use of Chinese Remainder Theorem and the resolution of quite small discrete logarithms are proposed in [START_REF] Brier | Why One Should Also Secure RSA Public Key Elements[END_REF] and [START_REF] Clavier | De la sécurité physique des crypto-systèmes embarqués[END_REF] to recover the private exponent from the set of gathered pairs. A new fault attack against "Right-To-Left" exponentiation has been presented lately [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF]. This work completes the state-of-the-art by allowing the attacker to use other fault models for recovering the private exponent. The details of this work are presented below. The value of the faulty modulus N is not known by the attacker. However, the time location of the fault is a parameter known by the attacker and used to perform the cryptanalysis. This fault model has been chosen for its simplicity and practicability in smart card context [START_REF] Giraud | DFA on AES[END_REF][START_REF] Blömer | Wagner's Attack on a secure CRT-RSA Algorithm Reconsidered[END_REF]. Furthermore, it can be easily adapted to 16-bit or 32-bit architectures.

Public

Faulty computation.

Let d = n-1 i=0 2 i • d i be the binary representation of d. The output of a RSA signature can be written as:

S ≡ ṁ n-1 i=0 2 i •di mod N (1)
We consider that a fault has occurred j steps before the end of the exponentiation, during the computation of a square. According to the fault model described, all subsequent operations are performed with a faulty modulus N . We denote by A ≡ ṁ

(n-j-1) i=0

2 i •di mod N the internal register value and by B the result of the faulty square:

B ≡ ṁ2 (n-j-1) mod N 2 mod N (2)
Hence, the faulty signature Ŝ can be written as:

Ŝ ≡ A • B n-1 i=(n-j) 2 [i-(n-j)] •di mod N (3) ≡ [( ṁ (n-j-1) i=0 2 i •di mod N ) (4) •( ṁ2 (n-j-1) mod N ) n-1 i=(n-j) 2 [i-(n-j)+1] •di ] mod N
From the previous expression of Ŝ, one can first notice that the fault injection splits the computation into a correct (computed with N ) and a faulty part (computed with N ). A part of d is used during the faulty computation. This is exactly the secret exponent part that will be recovered in the following analysis.

Attack principle.

From both correct signature S and faulty one Ŝ (obtained from the same message m), the attacker can recover the isolated part of the private key

d (1) = n-1 i=n-j 2 i • d i .
Indeed, he tries to find simultaneously candidate values for the faulty modulus N ′ (according to the random byte fault assumption) and for the part of the exponent d ′

(1) that satisfies:

Ŝ ≡ S • ṁ-d ′ (1) mod N • ṁ2 (n-j-1) mod N
According to [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF], the pair (d ′ (1) , N ′ ) that satisfies ( 5) is the right one with a probability very close to 1. Then, the subsequent secret bits will be found by repeating this attack using the knowledge of the already found most significant bits of d and a signature faulted earlier in the process. In terms of fault number, the whole private key recovery requires an average of (n/l) faulty signatures, where l is the average number of bits recovered each time. As a consequence, this few number of required faults makes the attack both efficient and practicable.

Application to the "Left-To-Right" modular exponentiation

In this section, we try to apply the previously explained fault attack to the "Left-To-Right" implementation of RSA. Under the same fault model, we wanted to know what does prevent an attacker from reproducing the attack against the dual implementation. We denote by A the internal register value just before the modification of the modulus N :

A ≡ ṁ n-1 i=j 2 i-j •di mod N (6)
Hence, knowing that the first perturbed operation is a square, the faulty signature Ŝ can be written as:

Ŝ ≡ A 2 • ṁdj-1 2 • ṁdj-2 2 . . . 2 • ṁd0 mod N (7) ≡ A 2 j • ṁ j-1 i=0 2 i •di mod N
By observing (7), one can notice that the perturbation has two consequences on the faulty signature Ŝ. First, it splits the computation into a correct part (i.e: the internal register value A) and a faulty one, like for the perturbation of the"Right-To-Left" exponentiation [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF]. The other one is the addition of j cascaded squares of the local variable A, computed modulo N . This added operation defeats the previous attack on the "Right-To-Left" exponentiation [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF] because of the difficulty to compute square roots in RSA rings.

Our idea for generalizing the previous attack to "Left-To-Right" exponentiation is to take advantage of the modulus modification to change the algebraic properties of the RSA ring. In other words, if N is a prime number, then it is possible to compute square roots in polynomial time. Moreover, it is actually sufficient that N is B-smooth with B small enough to enable an easy factorization of N , then the Chinese Remainder Theorem enables also to compute square roots in polynomial time. We show next anyway that the number of primes N is sufficient to provide a realistic fault model.

Fault model

According to the previous section, the square root problem can be overcome by perturbing the modulus N such that N is prime. In this section we will study the consistency and the practicability of such a fault model. Even though this model has already been adopted in Seifert's attack [START_REF] Muir | Seifert's RSA Fault Attack : Simplified Analysis and Generalizations[END_REF][START_REF] Seifert | On Authenticated Computing and RSA-Based Authentication[END_REF], we propose next further experimental evidences of the practicability of this model.

Theoretical estimations

Let us first estimate the number of primes with a fixed number of bits. From [Dus98, Theorem 1.10], we have the following bounds for the number of primes π below a certain integer x:

π(x) ≥ x ln(x) 1 + 1 ln(x) + 1.8 ln 2 (x)
, for x ≥ 32299. (8)

π(x) ≤ x ln(x) 1 + 1 ln(x) + 2.51 ln 2 (x)
, for x ≥ 355991.

Then, for numbers of exactly t bits such that t ≥ 19 bits, the number of primes is π t = π(2 t )π(2 t-1 ). By using the previous bounds (8), the probability that a t-bit number is prime, pr t = π t 2 t-1 , satisfies:

pr t > Inf (t) > 1.442t 5 -3.690t 4 + 0.080t 3 -22.828t 2 + 28.267t -10.810 t 3 (t -1) 3 (9)
pr t < Sup(t) < 1.443t 5 -3.689t 4 + 6.476t 3 -35.619t 2 + 41.060t -15.073 t 3 (t -1) 3

For instance, if t = 1024 bits:

Inf (1024) ≈ 1 709.477
and Sup(1024) ≈ 1 709.474 Therefore around one 1024-bit number out of 709 is prime; and among the 2048bit numbers, more than one out of 1419 is prime.

For example, we construct the following sets N i according to a random byte fault model. In other words, if ⊕ is the bit by bit exclusive OR, then1 : 8 . Would the set N be composed of randomly selected values, then the proportion of primes in each N i would follow (9). In order to estimate the number of faulty primes, we suppose this is the case for N 0 and that this proportion is doubled in N i for i ≥ 1, since all the fault numbers in these sets are odd. For n = 1024, according to (9), we can estimate pr 1024 and thus the average number of faulty primes is (2 • 128 -1)256/709.47 ≈ 92.011. For n = 2048, the average number of primes becomes (2 • 256 -1)256/1419.25 ≈ 92.172. Now for n = 1024 but with errors of length f bits, the number of faulty primes should be around (2 • 1024 f -1)2 f /709.47. This gives approximately 11731 faulty primes with 16 bits errors and more than 381 millions with 32 bits.

N i = {N ⊕ R 8 • 2 8i , R 8 = 0 .. 255} Let N = n 8 -1 i=0 N i .
Moreover, consider the subset of N comprising only odd numbers of size n. If the fault is on f bits, then the latter is of size k = 2 f -1 (2 n f -1). Let Pk be the random variable expressing the expected number of primes in this set. This variable follows a binomial law B(k, 2pr t ). Then we can give the following confidence interval of primes (with a and b integer bounds):

Pr[a ≤ Pk ≤ b] = b i=a k i (2pr t ) i (1 -2pr t ) k-i (10)
Equation (10) combined with the estimation of pr 1024 shows for instance that the number of faulty primes of 1024 bits with errors of size 8 is comprised between [50, 140] in more than 99.999% of the cases.

Obviously N is not a set of randomly chosen elements; howbeit, empirical evidence shows that such sets behave quite like random sets of elements, as shown below.

Experimental results

We have computed such sets for randomly selected RSA moduli and counted the number of primes in those sets. The repartition seems to follow a binomial rule (as expected) and we have the following experimental data to support our belief (see Figure 1).

As shown in Table 1 it was anyway never the case that no prime was found in a set N (more than that we always found more than 18 primes in such a set). This experimental lower-bound equals to the one obtained by considering a random set. The same observation can be done for the upper-bound. Hence, our obtained results confirm our theoretical analysis. The presented results can be extended to other fault models. The Table 1 presents also theoretical expected results when 16-bit or 32-bit architectures are targeted. For instance, with n = 1024 and a 16-bit architecture, the theoretical average number of primes is 11731.3 and equation (10) shows that the number of primes should be between [11200,12300] in more than 99.999% of the cases.

Arch

Consequences

This study strengthen J-P. Seifert's assumption [START_REF] Seifert | On Authenticated Computing and RSA-Based Authentication[END_REF][START_REF] Muir | Seifert's RSA Fault Attack : Simplified Analysis and Generalizations[END_REF] of considering only prime modification of the modulus. We have showed that our fault model can be considered as a random modification of the public modulus. Then, an average of 356 faults on N will be required to obtain a prime N in the case of a 1024-bit RSA.

Additional remark. By carefully studying the experimental results, one can notice that, for a given modulus N , the byte location of the fault influences the number of prime found in the subset. Thus, if the attacker has the ability of setting the byte location of the fault, he can increase his chances to get a prime faulty modulus and therefore, dramatically reduce the number of faulty signatures required to perform the attack.

The Algorithm of Tonelli and Shanks

The algorithm of Tonelli and Shanks [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF] is a probabilistic and quite efficient algorithm used to compute square roots modulo P , where P is a prime number. The principle of the algorithm is based on the isomorphism between * and the additive group Z/ (P -1) Z. Suppose P -1 is written as:

P -1 = 2 e • r, with r odd. ( 11
)
Then, the cyclic group G of order 2 e is a subgroup of Z/ (P -1) Z. Let z be a generator of G, if a is a quadratic residue modulo N , then:

a (P -1)/2 ≡ (a r ) 2 e-1 ≡ 1 mod P (12)
Noticing that a r mod P is a square in G, then it exists an integer k ∈ [[0 :

2 e -1]] such that a r • z k = 1 in G (13)
And so, a r+1 • z k = a in G. Hence, the square root of a, is given by

a 1/2 ≡ a (r+1)/2 • z k/2 mod P (14)
Both main operations of this algorithm are:

• Finding the generator z of the subgroup G,

• Computing the exponent k.

The whole complexity of this algorithm is that of finding k, O ln 4 P binary operations or O (ln P ) exponentiations. The details of the above algorithm are described in [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF]. In practice, on a Pentium IV 3.2GHz, the GIVARO2 implementation of this algorithm takes on average 7/1000 of a second to find a square root for a 1024-bit prime modulus.

Smooth modulus

As in [START_REF] Muir | Seifert's RSA Fault Attack : Simplified Analysis and Generalizations[END_REF], what we really need for the faulty modulus is only to be easily factorable. This is the case e.g. if the faulty N has one large prime factor and a smooth cofactor. For instance, just testing for divisibility by the 25 first primes (below 100), of 1024-bits faulty moduli on a 8-bit architecture, already roughly multiplies by 3 the number of easily usable faulty moduli. Then, one can also compute square roots modulo a non prime modulus as long as the factorization is known. The idea is first to find square roots modulo each prime factors of N ; then to lift them independently to get square roots modulo each prime power; and finally to combine them using the Chinese Remainder Theorem (see e.g. [Sho05, §13.3.3] for more details). The number of square roots increases but since they are computed on comparatively smaller primes, the overall complexity thus remains O ln 4 N binary operations. For the sake of simplicity, in the following we consider only prime faulty moduli.

Final modular check.

The purpose of the two first steps is to cancel the effects on the faulty signature due to the perturbation. Now, from the j k -th square root of R (d ′ (k) , Ni) the attacker will simulate an error-free end of execution by computing:

S ′ ≡ R (d ′ (k) , Ni) 1/2 j k mod Ni 2 j k • ṁd ′ (k) mod N (17)
Finally, he checks if the following equation is satisfied:

S ′ ≡ S mod N (18)
As in the "Right-To-Left" attack [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF], when this latter condition is satisfied, it means that the candidate pair is very probably the searched one (see Sect. 6.3). Moreover, the knowledge of the already found least significant bits of d is used to reproduce the attack on the subsequent secret bits. As a consequence, the attacker has to collect a set of faulty signatures Ŝk by injecting the fault at different steps j k before the end of the exponentiation. Moreover, multiple faulty signature Ŝk,f have to be gathered for a given step j k to take into account the probability for having a faulty signature Ŝk computed under a prime N , that is to say exploitable by the cryptanalysis. This set ( Ŝk,f , j k ) k,f is sorted in descending fault location. If faults are injected regularly, each sorted pair is used to recover a l-bit part of the exponent such that for the k-th pair ( Ŝk,f , j k ), the recovered part of d is

d (k) = j k -1 i=0 2 i • d i = k•l-1 i=0 2 i • d i .
These results can be applied for faults that are not injected regularly (i.e: j kj k-1 = l k < l max ). The attack algorithm is given in more details next.

Performance

Fault number

Our fault model is based on modifications of the modulus N , with a fault of size l bits, such that its corresponding faulty value is prime. In Section 4.1, we have shown that the probability for a t-bit number to be prime, pr t , can be bounded. Now, let the number of fault to make N prime be the random variable F t . We have seen that the average number of faults to make N prime per faulted part is:

2 l (2 • 2 l -1)Sup(t) < µ (F t ) < 2 l (2 • 2 l -1)Inf (t) (19)
For large values of t (i.e: at least 1024 or 2048-bit RSA), we can use the pinching (or sandwich) theorem to approximate this value asymptotically :

µ (F t ) ∼ t 1.4427 • (2 -1 2 l ) (20)
From a given faulty signature, the attacker can recover a l-bit part of d. There are at most n/l such parts for an RSA of size n. This shows that the average number of faults required for a whole private key satisfies:

Number of faults = O n 2 2.8854 • l tries (21)
This number can be dramatically reduced if the attacker has the ability to chose the byte location of the fault (see Sect. 4.1) or if the fault model is larger (i.e: smooth modulus, different architectures targeted . . . ).

Computational complexity

We now give the overall complexity of the attck. The size of the dictionary, D length , is let as an attack parameter since the attacker can fix a limit if the chosen fault model requires more resources than he can get. According to our previous analysis (see Sect. 4.1), D length = 46 for a random byte fault assumption.

Theorem 1. Algorithm 3 is correct and its average complexity for a random byte fault perturbation of the modulus satisfies:

C attack = O 2 8+l • n 3 • (n + l) 16 • l exponentiations Proof.
Correctness as been shown in section 5. Now for the complexity, the attacker has to test all possible candidate pairs (d ′ (k) , Ni ). The number of pairs depends on the size of the dictionary of prime modulus denoted by D length and the window recovery length l:

|(d ′ (k) , Ni )| = 2 l • D length (22)
For each pair the attacker first computes R (d ′ (k) , Ni) (see (15)) by executing a modular exponentiation of the message and a multiplication. Then, he performs a series of at most j k quadratic residuosity tests and, for each success, a square root is computed. By noticing that the probability to fail in the test follows a geometric probability law, the average number of performed tests4 is 1 Pr[Test fails] = 2. As a consequence, the average complexity of this step is:

C Square roots (k) = O (2 • C T est + C T onelli & Shanks ) (23) = O (j k • n) exponentiations
The last step of the attack is the final check (see ( 17)). It requires to compute j k modular squares and a modular exponentiation of the message followed by a multiplication. The latter computation is also bounded by O(j k • n) exponentiations. Now in the case of a fixed size dictionary the average number of primes of this dictionary for a byte modification of the modulus is N f aults per blocs = 2 8 n/8 D length . Then, the attack has to test all of the gathered faulty signatures in order to recover the whole exponent. Hence, as j k is bounded by k • l, the overall computational complexity is bounded by:

C attack = n/l k=0 N f aults per blocs • C Square roots (k) • 2 l • D length (24) = O 2 8+l • n 3 • (n + l) 16 • l
The presented attack is thus longer than the "Right-To-Left" one [BCG08], the principal reason being the extra number of faulty pairs to analyze in order to get a prime modulus.

False-acceptance probability

As defined in [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF], the false-acceptance probability is the probability for a wrong pair (d ′ (k) , Ni ) to satisfy (18). In our case, the computation of the final check is done in Z/N Z and requires extra squares. As a consequence the false-acceptance probability given in [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF] Moreover, because of the quadratic residuosity tests (see Sect. 5.2), false candidates can be rejected before computing the final check. Hence, the final check will not always be done. The probability that a wrong pair pass all the j k tests is given by: Pr R (d ′ (k) , Ni) is a j k -times quadratic residue (26)

= j k -1 i=0 Pr R (d ′ (k) , Ni)
1/2 i is a quadratic residue = 1 2 j k This probability indicates that, for recovering the k-th part of d, only one out of 2 j k wrong pairs will pass all the quadratic residuosity tests. Eventually, the false-acceptance probability can be upper-bounded:

Pr[F.A] < min 1 2 j k , (N -1)•2 l •D length N •(2 l •D length -1) , 2 l •D length N (27)
This expression first shows that because of the last term

2 l •D length N
, the falseacceptance probability is highly negligible for commonly used RSA length. Furthermore, one can advantageously notice that the final check can be avoided when the number of consecutive quadratic residuosity tests to pass is large enough (i.e: 2 j k > D length • 2 l ).

Conclusion

In this paper, we generalize the fault attack presented in [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF] to "Left-To-Right" implementation of RSA by assuming that the faulty modulus can be prime. Although this model has been already used [START_REF] Seifert | On Authenticated Computing and RSA-Based Authentication[END_REF], this paper provides a detailed theoretical analysis in fault attack context. Furthermore this analysis proves that such a fault model is not only practicable but extendible to different architectures. This emphases the need for protecting RSA public elements during the execution.

More generally the use of a faulty prime modulus to compute square roots in polynomial time raises the question of using faults for changing algebraic properties of the underlying finite domain. This paper provides an element of answer that may be completed by future fault exploitations.

  Decryption: Decrypting a ciphertext C boils down to compute m ≡ C d mod N ≡ C n-1 i=0 2 i •di mod N where d i stands for the i-th bit of d. If no error occurs during computation, transmission or decryption of C, then m equals m.

Algorithm 1 :

 1 "Right-To-Left" modular exponentiation Algorithm 2: "Left-To-Right" modular exponentiation INPUT: m, d, N INPUT: m, d, N OUTPUT: A ≡ m d mod N OUTPUT: A ≡ m d mod N 1 : A:=1; 1 : A:=1; 2 : B:=m;

  Then the cardinality of N and N i are |N i | = 256 and |N | = 256 • n

Figure 1 :

 1 Figure 1: Experimental distribution of primes among faulty RSA moduli

  has to be adapted by replacing the search space for N by the dictionary length D length :0 < Pr[F.A] < min (N -1)•2 l •D length N •(2 l •D length -1) , 2 l •D length N(25)

  Binary exponentiation algorithms are often used for computing the RSA modular exponentiation ṁd mod N where the exponent d is expressed in a binary form as d

				mod N ;
	6 :	end if	6 :	end if
	7 :	B := B 2 mod N ;	7 : end for
	8 : end for	8 : return A;
	9 : return A;

Table 1 :

 1 Experimental counts of primes in N .

	.	bits |N | Exp. # Prop.	# of	# of primes
		of primes		draws	Min.	Avg. Max.
	8-bit 1024 2 15 8-bit 2048 2 16 16-bit 1024 2 22 11731.3 92.01 92.17 32-bit 1024 2 37 3.8 • 10 8	1 356 1 711 1 357 1 360	77067 44499 34153 11268 11732.0 12250 52 90.6658 138 54 90.7924 132

[1-(n-j)] •d ′ (1) mod N ′(5)

For the sake of clarity we assume that a byte fault can take

8 values. In fact, it can take only 2 8 -1. Indeed, the error can not be null otherwise the value of N is unchanged and the fault can not be exploited.

GIVARO is an open source C++ library over the GNU Multi-Precision Library. It is available on http://packages.debian.org/fr/sid/libgivaro-dev

This computation is possible only when d ′ k is invertible in Z/Z Ni ; in our case all the considered N i are primes and Euclid's algorithm always computes the inverse.

The test fails when tested value is not a quadratic residue. But all the Ni are prime. Let be z i a generator in Z/ Ni Z, all the elements of the group can be expressed as a power of z i . Hence one element out of 2 is a power of z i 2 and a quadratic residue.

Acknowledgment

We would like to thank Sonia Belaid and Louis Schimchowitsch for finding an error in the faulty primes search program, in an earlier version of this report.

Cryptanalysis

The purpose of our fault attack against the "Left-To-Right" exponentiation is similar to the attack against the "Right-To-Left" one [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF]. The modulus N is transiently modified to a prime value during a squaring, j k steps before the end of the exponentiation. Then, from a correct/faulty signature pair (S, Ŝk ), the attack aims to recover the part of private exponent d (k) = j k -1 i=0 2 i • d i isolated by the fault. By referring to [START_REF] Berzati | Perturbating RSA Public Keys: an Improved Attack[END_REF], the following analysis can be easily adapted for faults that first occurs during a multiplication.

Dictionary of prime modulus.

The first step consists in computing a dictionary of prime faulty modulus candidates ( Ni ). The attacker tests all possible values obtained by modifying N according to a chosen fault model. Then, values for N are tested using the probabilistic Miller-Rabin algorithm [START_REF] Michael | Probabilistic algorithm for testing primality[END_REF]. According to our study (see Sect. 4.1), for a random byte fault assumption, the faulty modulus dictionary will contain 46 entries in average either for a 1024-bit or a 2048-bit RSA. The size of the dictionary depends on the fault model (see Table 1).

Computation of square roots.

For each entry Ni of the modulus dictionary, the attacker chooses a candidate value for the searched part of the private exponent d ′ (k) . Now he can compute 3 :

For the right pair (d (k) , N ), R (d (k) , N) is expected to be a multiple quadratic residue (i.e: a j k -th quadratic residue, see Sect. 3.3). As a result, if

is not a quadratic residue, the attacker can directly deduce that the candidate pair (d ′ (k) , Ni ) is a wrong one. The quadratic residuosity test can be done in our case because all precomputed candidate values for the faulty modulus are prime numbers. The test is based on Fermat's theorem: for d (k) from 0 upto 2 l -1 9:


Athanasios Batakis

Benoit

Benoît Testud

Multifractal Analysis of inhomogeneous Bernoulli products

Keywords: Multifractal Analysis of inhomogeneous Bernoulli products Hausdorff dimension, multifractal analysis, Gibbs measure, phase transition

Introduction

Let us consider the dyadic tree T (even though all the results in this paper can be easily generalised to any ℓ-adic structure, ℓ ∈ N), let Σ = {0, 1} N be its limit (Cantor) set and denote by (F n ) n∈N the associated filtration with the usual 0 -1 encoding.

For ǫ 1 , ..., ǫ n ∈ {0, 1} we denote by I ǫ 1 ...ǫn the cylinder of the nth generation defined by I ǫ 1 ...ǫn = {x = (i 1 , ..., i n , i n+1 , ...) ∈ Σ ; i 1 = ǫ 1 , ..., i n = ǫ n }. For every x ∈ Σ, I n (x) stands for the cylinder of F n containing x.

If (p n ) n is a sequence of weights, p n ∈ (0, 1), we are interested in Borel measures µ on Σ defined in the following way

µ(I ǫ 1 ...ǫn ) = n j=1 p 1-ǫ j j
(1p j ) ǫ j .

(1)

A measure of this form will be referred to as an inhomogeneous Bernoulli product. The aim of this paper is to study multifractal properties of such measures.

The particular case where the sequence (p n ) is constant is well-known and provides an example of measure satisfying the multifractal formalism (see e.g [START_REF] Falconer | Techniques in Fractal Geometry[END_REF]). In the general case, Bisbas [START_REF] Bisbas | A multifractal analysis of an interesting class of measures[END_REF] gave a sufficient condition on the sequence (p n ) ensuring 1 that µ is a multifractal measure (i.e. the level sets are not empty). However, the work of Bisbas does not provide the dimension of the level sets E α associated to the measure µ.

Let us give a brief description of multifractal formalism. For a probability measure m on Σ, we define the local dimension (also called Hölder exponent) of m at x ∈ Σ by

α(x) = lim inf n→+∞ α n (x) = lim inf n→+∞ - log m(I n (x)) n log 2 .
The aim of multifractal analysis is to find the Hausdorff dimension, dim(E α ), of the level set E α = {x : α(x) = α} for α > 0. The function f (α) = dim(E α ) is called the singularity spectrum (or multifractal spectrum) of m and we say that m is a multifractal measure when f (α) > 0 for several α ′ s.

The concepts underlying the multifractal decomposition of a measure go back to an early paper of Mandelbrot [START_REF] Mandelbrot | Intermittent turbulence in self-similar cascades : Divergence of high moments and dimension of the carrier[END_REF]. In the 80's multifractal measures were used by physicists to study various models arising from natural phenomena. In fully developped turbulence they were used by Frisch and Parisi [START_REF] Frisch | On the singularity structure of fully developed turbulence[END_REF] to investigate the intermittent behaviour in the regions of high vorticity. In dynamical system theory they were used by Benzi et al. [START_REF] Benzi | On the multifractal nature of fully developed turbulence and chaotic system[END_REF] to measure how often a given region of the attractor is visited. In diffusion-limited aggregation (DLA) they were used by Meakin et al. [START_REF] Meakin | Scaling properties for the surfaces of fractal and nonfractal objects : An infinite hierarchy of critical exponents[END_REF] to describe the probability of a random walk landing to the neighborhood of a given site on the aggregate.

In order to determine the function f (α), Hentschel and Procaccia [START_REF] Hentschel | The infinite number of generalized dimensions of fractals and strange attractors[END_REF] used ideas based on Renyi entropies [START_REF] Rényi | Probability Theory[END_REF] to introduce the generalized dimensions D q defined by

D q = lim n→+∞ 1 q -1 log
I∈Fn m(I) q n log 2 , (see also [START_REF] Grassberger | Characterization of strange sets[END_REF][START_REF] Grassberger | Generalized dimension of strange attractors[END_REF]). From a physical and heuristical point of view, Halsey et al.

[HJK + 86] showed that the singularity spectrum f (α) and the generalized dimensions D q can be derived from each other. The Legendre transform turned out to be a useful tool linking f (α) and D q . More precisely, it was suggested that

f (α) = dim(E α ) = τ * (α) = inf(αq + τ (q), q ∈ R), (2)
where

τ (q) = lim sup n→+∞ τ n (q) with τ n (q) = 1 n log 2 log I∈Fn m(I) q .
(The sum runs over the cylinders I such that m(I) = 0.) The function τ (q) is called the L q -spectrum of m and if the limit exists τ (q) = (q -1)D q .

Relation (2) is called the multifractal formalism and in many aspects it is analogous to the well-known thermodynamic formalism developed by Bowen [START_REF] Bowen | Equilibrium states and the ergodic theory of Anosov diffeomorphisms[END_REF] and Ruelle [START_REF] Ruelle | Thermodynamic Formalism[END_REF]. In general, the main problem is to obtain the minoration dim(E α ) ≥ τ * (α).

For number of measures, this formalism can be verified rigorously. In particular, if the sequence (p n ) is constant or periodic, the measure µ given by (1) satisfies the multifractal formalism (e.g. [START_REF] Falconer | Techniques in Fractal Geometry[END_REF]). It is also the case for invariant measures in some dynamical systems (e.g [START_REF] Collet | Hausdorff dimension of singularities for invariant measures of expanding dynamical systems[END_REF][START_REF] Fan | Sur la dimension des mesures[END_REF][START_REF] Rand | The singularity spectrum f (α) for cookie-cutter[END_REF]), for self-similars measures under separation conditions (e.g [CM92, Fen03, LN99, Ols95, Rie95, Ye05]) and for quasiindependent measures(e.g [START_REF] Brown | On the Multifractal Analysis of Measures[END_REF][START_REF] Heurteaux | Estimations de la dimension inférieure et de la dimension supérieure des mesures[END_REF][START_REF] Testud | Mesures quasi-bernoulli au sens faible : résultats et exemples[END_REF]). Despite all these investigations mentioned, the exact range of the validity of the multifractal formalism is still not known. Olsen [START_REF] Olsen | A multifractal formalism[END_REF] give a rigorous approach of multifractal formalism in a general context. This work and the paper of Brown, Michon and Peyrière [START_REF] Brown | On the Multifractal Analysis of Measures[END_REF] enlighten the link between the minoration dim(E α ) ≥ τ * (α) and the existence of auxiliary measures m q (the so-called Gibbs measure [START_REF] Michon | Mesures de Gibbs sur les Cantor réguliers[END_REF]) satisfying

∀n, ∀I ∈ F n , 1 C m(I) q 2 -nτ (q) ≤ m q (I) ≤ Cm(I) q 2 -nτ (q) ,
where the constant C > 0 is independent of n and I. In fact, it is shown in [START_REF] Bennasr | Analyse multifractale de mesures[END_REF]BBH02] that the existence of a measure m q satisfying m q (I) ≤ Cm(I) q 2 -nτ (q) , is sufficient to obtain the minoration dim(E α ) ≥ τ * (α) for α = -τ ′ (q). In this situation, the values of α for which the multifractal formalism may fail lie in intervals (-τ ′ (q + ), -τ ′ (q -)) where q is a point of non differentiability of τ (τ ′ (q + ) and τ ′ (q -) stands for the right and the left derivatives respectively). Such a point q will be called a phase transition.

If the weights p n are not all the same, the measure µ defined by (1) is in general no shift-invariant and we cannot apply classical tools of ergodic theory, as Shannon-McMillan theorem (e.g [START_REF] Billingsley | Ergodic Theory and Information[END_REF]), to get a lower bound of dim(E α ) and the differentiability of the function τ .

Let us introduce the other following level sets defined by

E α = {x ; α(x) ≤ α} , F α = x ; lim sup n→∞ α n (x) ≥ α , and
F α = x ; lim sup n→∞ α n (x) = α .
We can now state our main results. In section 2, we prove the following.

Theorem 1.1 Let µ be an inhomogeneous Bernoulli product on Σ and q ∈ R. We have

lim inf n→∞ -qτ ′ n (q) + τ n (q) ≤ dim E -τ ′ (q -) ∩ F -τ ′ (q + ) ≤ sup τ * (-τ ′ (q + )), τ * (-τ ′ (q -)) .
The proof of the lower bound relies on the construction of a special inhomogeneous Bernoulli product which has the dimension of the studied level set.

In section 3 we study the case α = -τ ′ (q). The existence of τ ′ (q) is not sufficient to ensure the validity of multifractal formalism for such values of α ′ s. However, we prove that the multifractal formalism holds if the sequence (τ n (q)) converges. More precisely, we have Theorem 1.2 Suppose that the sequence (τ n (q)) converges at a point q ∈ R. If τ ′ (q) exists and if α = -τ ′ (q), we have

dim (E α ∩ F α ) = τ * (α) = αq + τ (q).
(3)

We easily deduce the following

Corollary 1.3 If p n tend to p, as n → ∞, then τ µ = τ (p, .
) and the mesure µ satisfies the multifractal formalism. Nevertheless, the measure µ can be singular with respect to the (homogeneous) Bernoulli measure associated to p.

Theorem 1.2 leads us to study the differentiability of the L q -spectrum τ (q). In section 4, we will see that the L q -spectrum of an inhomogeneous Bernoulli product may be a very irregular function. In particular, Theorem 1.4 There exist inhomogeneous Bernoulli products presenting a dense set of phase transitions on (1, +∞).

The are several examples of measures presenting phase transitions (see for instance [START_REF] Testud | Phase transitions for the multifractal analysis of self-similar measures[END_REF] and the references therein). The example we propose in this work differs from previous ones at three points : first the phase transitions are situated at points q > 1 and not at negative ones, where constructions are easier to carry out. Secondly, the set of transitions is dense in [1, ∞), that means as ≪ bad ≫ as can be. And finally, the measure presenting this pathologie is just a Bernoulli product ! Let us also point out that with some minor modifications our method can also apply to create a dense set of phase transitions within (0, 1).

Proof of Theorem 1.1

We begin by a preliminary result.

Lemma 2.1 If µ is an inhomogeneous Bernoulli product, then the functions (τ ′′ µ,n ) are locally uniformly bounded on (0, +∞).

Proof We denote by β(p i ) the homogeneous Bernoulli measure of parameter p i and by τ (p i , q) it's τ function, τ (p i , q) = log 2 (p q i + (1p i ) q ). Using the fact that µ is the product of β(p i ) we easily obtain

τ µ,n (q) = 1 n n i=1 τ (p i , q).
It is therefore sufficient to show that, for any q 0 > 0, there exists a constant C = C(q 0 ) such that for all p ∈ (0, 1) and all q > q 0 , ∂ 2 τ (p, q) ∂q 2 ≤ C. We have

∂ 2 τ (p, q) ∂q 2 = p q (log 2 p) 2 + (1 -p) q (log 2 (1 -p)) 2 p q + (1 -p) q - (p q log 2 p + (1 -p) q log 2 (1 -p)) 2 (p q + (1 -p) q ) 2 = p q (1 -p) q ((log 2 p) 2 + (log 2 (1 -p)) 2 -2 log 2 p log 2 (1 -p)) (p q + (1 -p) q ) 2 = p q (1 -p) q log 2 p 1-p 2 (p q + (1 -p) q ) 2 ≤ [4p(1 -p)] q (log 2 p 1 -p ) 2 ≤ [4p(1 -p)] q 0 (log 2 p 1 -p ) 2 ,
which is uniformly bounded on p ∈ (0, 1) and the proof is complete. • Lemma 2.1 allows us to give estimates for the lower and the upper Hausdorff dimension of the measure µ. They are respectively defined by

dim * (µ) = inf{dim(E), µ(E) > 0} ; dim * (µ) = inf{dim(E), µ(E) = 1}.
We say that µ is exact if dim * (µ) = dim * (µ) and we note dim(µ) the common value. In the same way, we can define the lower and the upper Packing dimension Dim of the measure µ. It is well known that there exist some relations between these quantities and the derivatives of the function τ µ (q) at q = 1. More precisely, it is proved in [START_REF] Fan | Sur la dimension des mesures[END_REF][START_REF] Heurteaux | Estimations de la dimension inférieure et de la dimension supérieure des mesures[END_REF] that

-τ ′ µ (1+) ≤ dim * (µ) ≤ h * (µ) ≤ h * (µ) ≤ Dim * (µ) ≤ -τ ′ µ (1-),
where h * (µ) and h * (µ) stand for the lower and the upper entropy of the measure µ, defined as

h * (µ) = lim inf - 1 n log 2 I∈Fn µ(I) log µ(I) = lim inf -τ ′ µn (1)
and

h * (µ) = lim sup - 1 n log 2 I∈Fn µ(I) log µ(I) = lim sup -τ ′ µn (1).
By Lemma 2.1, we deduce (see [START_REF] Batakis | On relations between entropy and Hausdorff dimension of measures[END_REF][START_REF] Heurteaux | Estimations de la dimension inférieure et de la dimension supérieure des mesures[END_REF]) the following remark.

Remark 2.2 If µ is an inhomogeneous Bernoulli product then dim µ = -τ ′ µ (1 + ) = h * (µ) = lim inf n→∞ -τ ′ µn (1) and Dim µ = -τ ′ µ (1 -) = h * (µ) = lim sup n→∞ -τ ′ µn (1).
Fix q ∈ R. To prove Theorem 1.1, we construct an auxiliary measure ν supported by the set E -τ ′ (q -) ∩ F -τ ′ (q + ) . More precisely, we consider a sequence of measures ν n satisfying

∀I ∈ F n , ν n (I) = µ(I) q
I∈Fn µ(I) q = µ(I) q |I| τµ,n(q) .

(4) (|I| = 2 -n stands for the diameter of I). The following lemma implies that the sequence (ν n ) converges in the weak * sense to a probability measure ν which is by construction an inhomogeneous Bernoulli product.

Lemma 2.3 Let n ∈ N and I ∈ F n . If µ is an inhomogeneous Bernoulli product, we have ν n (I) = ν n+1 (I).
Proof Take n > 0 and I ∈ F n . We can compute

ν n+1 (I) = J∈F 1 µ(IJ) q I∈Fn J∈F 1 µ(IJ) q = µ(I) q (p q n+1 + (1 -p n+1 ) q ) I∈Fn (p q n+1 + (1 -p n+1 ) q )µ(I) q
and therefore ν n+1 (I) = ν n (I) for all I ∈ F n .

• By remark 2.2, we then deduce that the Hausdorff and the Packing dimension of ν are given by an entropy formula. In other terms, we have

dim ν = lim inf n→∞ -τ ′ ν,n (1) = h * (ν) and Dim ν = lim sup n→∞ -τ ′ ν,n (1) = h * (ν).
Now we can prove Theorem 1.1.

Proof of Theorem 1.1 The upper bound is a well known fact of multifractal formalism (see for instance [START_REF] Brown | On the Multifractal Analysis of Measures[END_REF]). In fact we have

1. If α ≤ -τ ′ (0 + ) then dim E α ≤ dim E α ≤ τ * (α). 2. If α ≥ -τ ′ (0 -) then dim F α ≤ dim F α ≤ τ * (α).
3. -τ ′ (0 + ) ≤ α ≤ -τ ′ (0 -) then τ * (α) = τ (0) = 1 and the upper bound follows.

Relation (4) easily gives τ ν,n (s) = τ µ,n (qs)sτ µ,n (q). From remark 2.2, using the inhomogeneous Bernoulli property of µ and ν, we deduce that

-τ ′ ν (1 + ) = lim inf -τ ′ ν,n (1) = lim inf -qτ ′ µ,n (q) + τ µ,n (q) .
The following lemma then implies the lower bound.

Lemma 2.4 We have ν E -τ ′ (q -) ∩ F -τ ′ (q + ) = 1.

Remark 2.5 Contrary to more regular situations (e.g [BBH02, Heu98, Ols95]), we cannot obtain the more precise result ν E -τ ′ (q -) ∩ F -τ ′ (q + ) = 1 where

E α = {x ; α(x) ≥ α} , F α = x ; lim sup n→∞ α n (x) ≤ α .
Proof of Lemma 2.4 For η > 0 we put β = -τ ′ µ (q -) + η and we prove that ν(Σ \ E β ) = 0. In a similar way, it can be shown that ν(Σ \ F γ ) = 0 for γ < -τ ′ µ (q + ). The lemma then easily follows.

It suffices to show that Σ

\ E β = x ∈ Σ ; lim inf n→∞ α n (x) > β is of 0 ν-measure. Consider the collection R n (β) of cylinders I ∈ F n satisfying log µ(I) log |I| > β. It is clear that Σ \ E β ⊂ lim inf n→∞ Rn (β) with Rn (β) = {x ∈ Σ ; I n (x) ∈ R n (β)}.
Let (τ µ,n k ) k∈N be the subsequence of (τ µ,n ) n∈N such that lim k→∞ τ µ,n k (q) = τ µ (q). Using the convergence of τ µ,n k (q) we can choose (and fix) t < 0 such that for k big enough

τ µ (q + t) -τ µ,n k (q) < -β - η 2 t = τ ′ µ (q -) - η 2 t. Since µ(I) -t |I| βt ≤ 1 if I ∈ R n (β), we have ν( Rn k (β)) = I∈Rn k (β) ν(I) = I∈Rn k (β) µ(I) q |I| τµ,n k (q) = I∈Rn k (β) µ(I) q+t |I| τµ,n k (q)-βt µ(I) -t |I| βt ≤ I∈Rn k (β) µ(I) q+t |I| τµ,n k (q)-βt ≤ |I| -η 4 t I∈Fn k µ(I) q+t |I| τµ(q+t)-η 4 t ≤ |I| -η 4 t I∈Fn k µ(I) q+t |I| τµ,n k (q+t) = |I| -η 4 t .
For the last inequality, we used the fact that τ µ (q + t) = lim sup τ µ,n (q + t). We deduce that lim inf n→∞ ν( Rn (β)) = 0 and the lemma easily follows.

•

The proof of Theorem 1.1 is now completed. •

3 Proof of Theorem 1.2

We will use the following result.

Proposition 3.1 For q ∈ R, let (τ µ,n k ) be the subsequence of (τ µ,n ) such that

lim k→∞ τ µ,n k (q) = lim sup n→∞ τ µ,n (q) = τ µ (q).
Then, we have

τ ′ µ (q -) ≤ lim inf k→∞ τ ′ µ,n k (q) ≤ lim sup k→∞ τ ′ µ,n k (q) ≤ τ ′ µ (q + )
where τ ′ µ (q -) and τ ′ µ (q + ) stand for the left and the right hand dérivative of τ µ at q. Hence, if τ ′ µ (q) exists, we have

lim k→∞ τ ′ µ,n k = τ ′ µ (q).
Proof We only prove the inequality lim sup

k→∞ τ ′ µ,n k (q) ≤ τ ′ µ (q + ). The proof of τ ′ µ (q -) ≤ lim inf k→∞ τ ′ µ,n k (q) is similar.
Take ǫ > 0 and q > q such that τ µ (q)τ µ (q) qq τ ′ µ (q + ) < ǫ/3.

We can chose k big enough to have

|τ µ,n k (q) -τ µ (q)| |q -q| < ǫ/3
and τ µ,n k (q) ≤ τ µ (q) + (qq)ǫ/3.

We then obtain

τ ′ µ (q + ) ≥ τ µ (q) -τ µ (q) q -q -ǫ/3 = τ µ (q) -τ µ,n k (q) + τ µ,n k (q) -τ µ,n k (q) + τ µ,n k (q) -τ µ (q) q -q -ǫ/3 ≥ -ǫ/3 + τ ′ µ,n k (q) -ǫ/3 -ǫ/3 = τ ′ µ,n k (q) -ǫ
and the proof easily follows.

•

We can now prove Theorem 1.2.

Proof of Theorem 1.2. Let ν be the Gibbs-measure defined in Lemma 2.3. Since

τ ν,n (s) = τ µ,n (qs) -sτ µ,n (q)
we get τ ′ ν,n (1) = qτ ′ µ,n (q)τ µ,n (q). Using the convergence of τ µ,n (q) we deduce from Proposition 3.1 that

lim n→∞ τ ′ ν,n (1) = lim n→∞ qτ ′ µ,n (q) -τ µ,n (q) = qτ ′ µ (q) -τ µ (q).
Since ν is also an inhomogeneous Bernoulli product, we deduce from remark 2.2 that τ ′ ν (1) exists and dim ν = Dim ν = -τ ′ ν (1) = -qτ ′ µ (q) + τ µ (q).

On the other hand, for I ∈ F n , we have log ν(I)

log |I| = q log µ(I) log |I| + τ µ,n (q). Since lim n→∞ log ν(I n (x)) log |I n (x)| = dim ν = Dim ν ; ν-a.s.
we obtain that lim

n→∞ log µ(I n (x)) log |I n (x)| = -τ ′ µ (q), ν-a.s. We conclude that dim (E α ∩ F α ) ≥ dim ν = τ * µ (α).
The opposite inequality being always valid, the proof is done. •

We end this section with a few comments about Theorem 1.2.

As mentionned in the introduction of the paper, the validity of the multifractal formalism is often easier to obtain for the values of α that can be written α = -τ ′ (q). However, the following example shows that there exist inhomogeneous Bernoulli products that do not satisfy the multifractal formalism even at their differentiability points α = -τ ′ (q). Thus, the convergence of the sequence (τ n (q)) is really necessary for the validity of the multifractal formalism in our context.

To see that, let (n k ) k≥1 be a sequence of integers such that

n 1 = 1, n k < n k+1 and lim k→+∞ n k+1 n k = +∞,
and consider the inhomogeneous Bernoulli product µ given by the sequence (p n ) such that

p i = p if n 2n-1 ≤ i < n 2n and p i = p if n 2n ≤ i < n 2n+1 , with 0 < p < p < 1/2.
The calculation of the function τ is classical. By observing that

µ(I ǫ 1 ...ǫn0 ) q + µ(I ǫ 1 ...ǫn1 ) q = [(p q n+1 + (1 -p n+1 ) q ]µ(I ǫ 1 ...ǫn ) q ,
we easily deduce that

I∈Fn µ(I) q = n k=1 [p q k + (1 -p k ) q ].
Then, if N n is the number of integer k ≤ n such that p k = p, we have

τ n (q) = N n n log 2 (p q + (1 -p) q ) + (1 - N n n ) log 2 (p q + (1 -p) q ).
Since that lim inf n Nn n = 0 and lim sup n Nn n = 1, we get τ (q) = sup(log 2 (p q + (1p) q ), log 2 (p q + (1p) q ). So, except for q = 0 and q = 1, τ ′ (q) exists. Moreover,

∀I ∈ F n , µ(I) ≥ µ(I 00•••0 ) = p Nn pn-Nn .
Thus,

∀I ∈ F n , - log 2 (µ(I)) n ≤ N n n (-log 2 p) + (1 - N n n )(-log 2 p),
and we have

∀I ∈ F n , lim inf n - log 2 (µ(I)) n ≤ inf(-log 2 p, -log 2 p) = -log 2 p.
Finally, iflog 2 p < α = -τ ′ (q) <log 2 p, we have E -τ ′ (q) = ∅ and the multifractal formalism is not satisfied for a such α.

Moreover, this example shows that the function τ may be not differentiable at the positive values of q. Therefore, the situation differs from this one obtained by Heurteaux [START_REF] Heurteaux | Estimations de la dimension inférieure et de la dimension supérieure des mesures[END_REF] for quasi-Bernoulli measure for which τ is differentiable on R. It also differs from this one obtained by Testud in [START_REF] Testud | Phase transitions for the multifractal analysis of self-similar measures[END_REF] for weak quasi-Bernoulli measure for which the phase transitions only appears for q < 0.

In fact, the function τ of an inhomogeneous Bernoulli product may be very irregular. This is the object following section.

Proof of Theorem 1.4

From now, we denote par τ (p, .) the τ function of the homogeneous Bernoulli product of parameter p. Moreover, whenever we use the notation p i for a weight in (0, 1) we will also note τ i = τ (p i , .).

Before the proof of Theorem 1.4, we present a few lemmas.

Lemma 4.1 For any p 1 < p 2 < p 3 in (0, 1/2) consider the functions τ 1 = τ (p 1 , .), τ 2 = τ (p 2 , .) and τ 3 = τ (p 3 , .). We have that

τ 1 -τ 2 τ 2 -τ 3 is decreasing on (1, +∞).
Although the proof only uses elementary calculus, it is a litte bit "tricky" and cannot be omitted.

Proof of Lemma 4.1 Taking into account the trivial equality

τ (p ′ , q) -τ (p ′′ , q) = p ′ p ′′ ∂τ ∂p (p, q)dp
we only need to show that if p ′ < p ′′ then ∂τ ∂p (p ′ , q) : ∂τ ∂p (p ′′ , q) is decreasing on

q ∈ (1, ∞). We get ∂τ ∂p (p ′ , q) : ∂τ ∂p (p ′′ , q) = 1 p ′ 1 -(-1 + 1/p ′ ) q-1 1 + (-1 + 1/p ′ ) q : 1 p ′′ 1 -(-1 + 1/p ′′ ) q-1 1 + (-1 + 1/p ′′ ) q = p ′′ 1 -s 1 q-1 1 + s 1 q : p ′ 1 -s 2 q-1 1 + s 2 q
where s 1 = -1 + 1/p ′ > 1 and

s 2 = -1 + 1/p ′′ > 1.
If we set f (s, q) = ln 1s q-1 1 + s q , with s, q > 1, it is sufficient to prove that

∂f ∂s f (s, q)
is decreasing in q. We calculate ∂f ∂s f (s, q) = (q -1)s q-2 s q-1 -1 -qs q-1 s q + 1 .

By multiplying by s, we need to show that (q -1)s q-1 s q-1 -1 -qs q s q + 1 is decreasing which is equivalent to q -1 + q-1 s q-1 -1q + q s q +1 being decreasing.

Put Q = q -1 ; it remains to show that q -1 s q-1 -1

+ q s q + 1 = Q s Q -1 + Q s Q+1 + 1 + 1 s Q+1 + 1 decreases in Q > 0.
The last term being decreasing it suffices to show that

Q s Q -1 + Q s Q+1 + 1
is doing the same. By taking derivatives we need to show that

s Q+1 (s Q -1 -s Q ln s Q ) + s Q -1 -ln s Q ≤ 0. Since, (s Q -1 -s Q ln s Q ) < 0, it suffices to show that s Q (s Q -1 -s Q ln s Q ) + s Q -1 -ln s Q = s 2Q -s 2Q ln s Q -ln s Q -1 = g(s Q ) ≤ 0 where g(x) = x 2 -x 2 ln x -ln x -1. Moreover, the sign of g ′ (x) = x -x ln x 2 -1/x is the same of the sign of x 2 -x 2 ln x 2 -1 if x > 1.
Since, y -1 ≤ y ln y for y > 1, we deduce that g is decreasing on (1, +∞). By observing than g(1) = 0, we obtain that ∂f ∂s f (s, q)

is decreasing on (1, +∞) and the Lemma 4.1 is proved.

• Lemma 4.2 Take τ = λτ (p 1 , .) + (1 -λ)τ (p 2 , .
) with 0 < p 1 < p 2 < 1/2 and λ ∈ (0, 1). For p 0 ∈ (0, 1/2) one of the following occurs :

1. either τ (q) = τ (p 0 , q), for all q > 1, 2. either there exists q 0 > 1 such that τ (q) > τ (p 0 , q) for 1 < q < q 0 and τ (q) < τ (p , q) for q > q 0 . In this case q 0 is then the unique point of (1, +∞) for which τ (q) = τ (p 0 , q).

Proof of Lemma 4.2. Let us first remark that τ and τ (p 0 , .) can coincide at one point only if p 0 ∈ (p 1 , p 2 ). Moreover, τ (q) = τ (p 0 , q) implies τ (p 1 , q)τ (p 0 , q) τ (p 0 , q)τ (p 2 , q) = 1λ λ .

By Lemma 4.1 this can only occur once and Lemma 4.2 easily follows on the decreasing property of the ratio.

• Lemma 4.3 Take λ 1 , λ 2 ∈ (0, 1) such that λ 1 + λ 2 = 1 , 1 < p 1 < p 2 < 1/2 and set τ = λ 1 τ 1 + λ 2 τ 2 . Fix 1 < q 1 <
q 2 < +∞ and consider p 1 < p 4 < p 2 < p 5 < 1/2 such that τ (p 4 , q 1 ) = τ (q 1 ). Then there is a unique convex combination τ of τ 1 , τ 4 and τ 5 such that τ (q 1 ) = τ (q 1 ) and τ (q 2 ) = τ (q 2 ).

Furthermore, for i = 1, 2, we have τ ′ (q i ) = τ ′ (q i ) and τ (q) = τ (q) if 1 < q = q i .

Proof of Lemma 4.3.

First note that it is easy to see that there exists p 4 ∈ (p 1 , p 2 ) such that τ (p 4 , q 1 ) = τ (q 1 ).

It then suffices to show that the linear system    λ 3 τ 1 (q 1 ) +λ 4 τ 4 (q 1 ) +λ 5 τ 5 (q 1 ) = τ (q 1 ) λ 3 τ 1 (q 2 ) +λ 4 τ 4 (q 2 ) +λ 5 τ 5 (q 2 ) = τ (q 2 ) λ 3 +λ 4 +λ 5 = 1

(S) has a unique positive solution (λ 3 , λ 4 , λ 5 ). The existence of a unique solution is easy to verify. Let us show that this solution is positive.

First note that λ 4 = 1. Indeed, if λ 4 = 1, since τ (q 1 ) = τ 4 (q 1 ), we have λ 3 (τ 1 (q 1 )τ 5 (q 1 )) = 0. Thus, λ 3 = λ 5 = 0 and τ (q 2 ) = τ 4 (q 2 ) which is not possible by Lemma 4.2. Therefore, since τ (q 1 ) = τ 4 (q 1 ), the first equation of the system gives that λ 3 λ 3 + λ 5 τ 1 (q 1 ) + λ 5 λ 3 + λ 5 τ 5 (q 1 ) = λ 1 τ 1 (q 1 ) + λ 2 τ 2 (q 1 ) ∈ (τ 5 (q 1 ), τ 1 (q 1 ))

(5)

This implies that λ 3 λ 3 +λ 5 ∈ (0, 1). We deduce that λ 3 λ 5 > 0. Moreover, since τ 5 < τ 2 , we also have λ 3 λ 3 +λ 5 > λ 1 . Let us show that λ 3 and λ 5 are positive. Otherwise, by the above remark, we have λ 3 < 0, λ 5 < 0 and λ 4 > 0. By the system (S) we have

τ 4 (q) = λ 1 -λ 3 λ 4 τ 1 (q) + λ 2 λ 4 τ 2 (q) - λ 5 λ 4 τ 5 (q)
at the points q = q 1 and q = q 2 . We then obtain that

λ 1 -λ 3 λ 4 τ 1 -τ 4 τ 4 -τ 2 (q) = λ 2 λ 4 - λ 5 λ 4 τ 4 -τ 5 τ 4 -τ 2 (q)
for q = q 1 and q = q 2 . Since p 1 < p 4 < p 2 , by Lemma 4.1 the function τ 1 -τ 4 τ 4 -τ 2 is decreasing. On the other hand, since p 4 < p 2 < p 5 , Lemma 4.1 implies that the function τ 4 -τ 5 τ 4 -τ 2 = 1+ τ 2 -τ 5 τ 4 -τ 2 is increasing. Thus, these functions cannot coincide at two points so we conclude that λ 3 and λ 5 are positive.

Let us now prove that λ 4 > 0. By (5) we have λ 3 λ 3 + λ 5 τ 1 (q 1 ) + λ 5 λ 3 + λ 5 τ 5 (q 1 ) = λ 1 τ 1 (q 1 ) + λ 2 τ 2 (q 1 ) which gives that λ 2 τ 2 (q 1 ) = λ 3 λ 3 + λ 5 λ 1 τ 1 (q 1 ) + λ 5 λ 3 + λ 5 τ 5 (q 1 ).

Using Lemma 4.1, for q > q 1 we get

λ 2 τ 2 (q) > λ 3 λ 3 + λ 5 -λ 1 τ 1 (q) + λ 5 λ 3 + λ 5 τ 5 (q) and λ 1 τ 1 (q) + λ 2 τ 2 (q) > λ 3 λ 3 + λ 5 τ 1 (q) + λ 5 λ 3 + λ 5 τ 5 (q).
In particular, for q = q 2 we find that λ 3 τ 1 (q 2 ) + λ 5 τ 5 (q 2 ) + λ 4 τ (q 2 ) < τ (q 2 ) = λ 3 τ 1 (q 2 ) + λ 4 τ 4 (q 2 ) + λ 5 τ 5 (q 2 ) and we deduce that λ 4 τ (q 2 ) < λ 4 τ 4 (q 2 ).

Since τ (q 1 ) = τ 4 (q 1 ), it follows from Lemma 4.1 that λ 4 > 0.

The last assertion follows directly from the independancy of the vector families

     τ 1 (q 1 ) τ 4 (q 1 ) τ 5 (q 1 )   ,   τ 1 (q 2 ) τ 4 (q 2 ) τ 5 (q 2 )   ,   τ ′ 1 (q i ) τ ′ 4 (q i ) τ ′ 5 (q i )      and      τ 1 (q 1 ) τ 4 (q 1 ) τ 5 (q 1 )   ,   τ 1 (q 2 ) τ 4 (q 2 ) τ 5 (q 2 )   ,   τ 1 (q) τ 4 (q) τ 5 (q)      ,
which can be easily established.

•

Remark 4.4 In the proof of Lemma 4.3 it is clear that when p 5 is close to p 2 , the solution of the system (S) converges to (λ 1 , 0, λ 2 ) and τ converges to τ .

The following result generalizes Lemma 4.3 for any convex combination of functions τ (p i , .). Lemma 4.5 Let τ be a convex combination of functions τ (p i , .) where 0 < p i ≤ 1/2, i = 1, ..., n ≥ 2. For any 1 < q 1 < q 2 < ∞ there exists another convex combination τ of functions τ (p ′ j , .) such that -τ (q i ) = τ (q i ) and τ ′ (q i ) = τ ′ (q i ), i = 1, 2, -for q ∈ {q 1 , q 2 }, τ (q) = τ (q). Proof of Lemma 4.5.

The case n = 2 is given by Lemma 4.3. The case n > 2 is easy to derive. Suppose τ = n k=1 λ k τ (p k , .) and let τ 1 = τ (p 1 , .) and τ 2 = τ (p 2 , .) be the first two functions of the convex combination. By Lemma 4.3 there exists a convex combination τ of three τ (p, .) functions such that 1. 1 λ 1 +λ 2 (λ 1 τ 1 (q i ) + λ 2 τ 2 (q i )) = τ (q i ) , for i = 1, 2 2. 1 λ 1 +λ 2 (λ 1 τ ′ 1 (q i ) + λ 2 τ ′ 2 (q i )) = τ ′ (q i ) for i = 1, 2. The function τ = (λ 1 +λ 2 )τ + n k=3 λ k τ (p k , .) satisfies then the conclusion of Lemma 4.5. •

The modified family of qi 's defined by qi =      q i if i ∈ {2n -3, 2n -2} q ′ if i = 2n -3 q ′′ if i = 2n -2 have the same properties as the initial q i 's. Moreover, ρ n+1 = max(ρ n , τ n+1 ) is not differentiable at points q 1 , • • • , q 2n . We proceed as above for the construction of the measures µ n+1 and ν n+1 which have spectra τ n+1 and ρ n+1 respectively.

To end the proof we use Cantor's diagonal argument : take (ℓ k ) k as before and define the measure ν by applying the weight distribution of ν k on dyadique intervals of length between 2 -ℓ k and 2 -ℓ k+1 . The spectrum of the measure ν equals then τ = sup n∈N ρ n = sup n∈N τ n . By construction, the set of non-derivability points of the function τ is infinite and has q 0 as accumulation point.

•

Remark 4.8 The second case of the proof of Theorem 4.7 seems to be inexistent (in our numerical simulations) but we have not been able to prove that only the first case arises.

Let us now give some hints concerning the proof of Theorem 1.4.

Fix (q n ) n a sequence of real numbers, dense in [1, ∞) and nested in the sense that q 2n+1 < q 2n+2 and {q 1 , ..., q 2n } ∩ [q 2n+1 -1 2 n , q 2n+2 + 1 2 n ] = ∅ for all n ≥ 0. We can then follow the proof of Theorem 4.7 until case 2, the first case being carried out exactly in the same way.

The second case has to be slightly modified. The technical, but not difficult, part is to ensure that the modified q i 's still form a dense subset of [1, ∞) and that the difference of the left and right derivative at the q i 's does not go to 0. To do that we take p 5 sufficiently close to p 2 (in the construction of τ n+1 ) to have :

-|q iqi | < 1 2 n inf 1≤j<j ′ ≤2n+2 |q jq j ′ | -|δ n (q i )δ n+1 (q i )| < 1 2 n δ n (q i ), where δ n (q i ) stands for the difference between the right and left derivative at q i of sup 1≤k≤n τ k . The proof of Theorem 1.4 is then completed in the same way as above. •

Références

  , I. Bhouri, and Y. Heurteaux. The validity of the multifractal formalism : results and examples. Advances in Mathematics, 165 : 264-284, 2002.

The following lemma is easy and the proof is left to the reader. Lemma 4.6 For any p 1 , ..., p n and any convex combination τ of τ (p 1 , .), ..., τ (p n , .) there exists an inhomogeneous Bernoulli measure µ whose multifractal spectrum equals τ .

We can now prove Theorem 1.4.

Proof of Theorem 1.4

In fact, and in order to avoid technicalities, we only prove the following easier version of Theorem 1.4 and then indicate the changes needed to extend the proof in the general case.

Theorem 4.7 There exists an inhomogeneous Bernoulli product µ such that the spectrum τ of µ has an infinite set of the phase transitions on (1, +∞). Moreover, this set has a finite point of accumulation.

Proof The strategy of the demonstration is the following : we first find inhomogeneous Bernoulli products that are not derivable at a finite number of predefined points and we construct the measure µ using Cantor's diagonal argument.

Fix (q n ) n≥1 a sequence of real numbers nested in the sense that 1 < q 1 < ... < q 2n-1 < q 2n+1 < q 2n+2 < q 2n < ... < q 2 for all n ≥ 1 and ∩ n (q 2n+1 , q 2n+2 ) = {q 0 }. In particular, lim q n = q 0 . Let p 1 , p 2 ∈ (0, 1/2) and consider τ 1 = 1 2 τ (p 1 , .) + 1 2 τ (p 2 , .). By Lemma 4.6 we can construct a Bernoulli product µ 1 of spectrum τ 1 . Then, Lemma 4.5 implies the existence of a convex combination τ 2 of τ (p i , .)'s functions, such that

We can define a measure µ 2 of spectrum τ 2 . Using µ 1 and µ 2 , we can construct a measure ν 2 of spectrum ρ 2 = max{τ 1 , τ 2 }. To do that, we take a sequence of integers

On dyadique intervals of length between 2 -ℓ 2k and 2 -ℓ 2k+1

we apply the weight distribution of µ 1 and on dyadique intervals of length between 2 -ℓ 2k+1 and 2 -ℓ 2k+2 we apply the weight distribution of µ 2 , where k ∈ N. It is easy to verify that the resulting inhomogeneous measure ν 2 has spectrum ρ 2 = max{τ 1 , τ 2 }. The spectrum of ν 2 is not differentiable at q 1 and q 2 . We proceed by induction to construct a measure ν n which has a non differentiable spectrum for points q 1 , • • • , q 2n-2 . Suppose the measures ν 1 = µ 1 , µ 2 , ν 2 ,..., µ n , ν n constructed and denote by ρ n = max{τ 1 , ...τ n } where τ i is the spectrum of the measure µ i , i ∈ {1..., n}. Let us construct µ n+1 and ν n+1 .

One of the following two cases hold :

Case 1 Lemma 4.5 provides a function τ n+1 satisfying :

1. τ n+1 (q 2n-i ) = ρ n (q 2n-i ) for i = 0, 1 and τ n+1 (q) = ρ n (q) if q ∈ {q 2n-1 , q 2n }, 2. τ ′ n+1 (q 2n-1 ) > ρ ′ n (q 2n-1 ) , τ ′ n+1 (q 2n ) < ρ ′ n (q 2n ) Therefore we have τ n+1 > ρ n on (q 2n-1 , q 2n ) and τ n+1 < ρ n on (1, ∞) \ [q 2n-1 , q 2n ]. Let µ n+1 be the inhomogeneous Bernoulli measure of spectrum τ n+1 . To define the measure ν n+1 we use the previous procedure convenably adapted : Take (ℓ k ) k a sequence of integers such that ℓ k+1 k

On dyadique intervals of length between 2 -ℓ (n+1)k+i and 2 -ℓ (n+1)k+i+1 apply the weight distribution of µ i , where i = 1, ..., n + 1 and k ∈ N. It is easy to verify that the resulting inhomogeneous measure ν n+1 has spectrum ρ n+1 = max{τ 1 , ...τ n+1 } on (1, ∞). Remark that this spectrum equals τ n+1 on [q 2n-1 , q 2n ] and

Clearly, in this case, the function

Case 2 Lemma 4.5 provides for all choices of p 5 > p 2 a function τ n+1 satisfying :

1. τ n+1 (q 2n-i ) = ρ n (q 2n-i ) , for i = 0, 1 and τ n+1 (q) = ρ n (q) if q ∈ {q 2n-1 , q 2n }, 2. τ ′ n+1 (q 2n-1 ) < ρ ′ n (q 2n-1 ) , τ ′ n+1 (q 2n ) > ρ ′ n (q 2n ) In this case, τ n+1 < ρ n on (q 2n-1 , q 2n ) and τ n+1 > ρ n on (q 2n-3 , q 2n-1 ) ∪ (q 2n , q 2n-2 ).

The function ρn+1 = max(ρ n , τ n+1 ) is not differentiable at q 2n-1 and q 2n but we lose the phase transitions q 2n-3 , q 2n-2 and we don't know what happens for the other phase transitions q 1 , • • • , q 2n-4 . To avoid this problem we use remark 4.4. From this, when p 5 converges to p 2 , τ n+1 converges to the convex combination T of τ (p i , .) functions which is equal to ρ n on (q 2n-3 , q 2n-2 ). Since T differs from ρ n on (q 2n-5 , q 2n-3 ) and (q 2n-2 , q 2n-4 ), we can choose p 5 sufficiently close to p 2 such that τ n+1 q 2n-3 + q 2n-5 2 < ρ n q 2n-3 + q 2n-5 2 and τ n+1 q 2n-2 + q 2n-4 2 < ρ n q 2n-2 + q 2n-4 2 .

We deduce that there exist q 2n-5 < q ′ < q 2n-3 and q 2n-2 < q ′′ < q 2n-4 such that τ n+1 = ρ n at q ′ and q ′′ and τ n+1 < ρ n on (q 1 , q ′ ) and (q ′′ , q 2 ).