Jean-Pierre Ponssard
email: jean-pierre.ponssard@polytechnique.edu

Catherine Thomas

Amit Khandelwal

Bruce Kogut

Benjamin Lockwood

Guy Meunier

Dmitri Nizovtsev

Hendrik G Van Oss

Capacity Investment under Demand Uncertainty. An Empirical Study of the US Cement Industry, 1994-2006*

Keywords: Capacity Investment, Demand Uncertainty, Imports, Cement. JEL Classifications: D24, D81, F18, L61

Uncertainty about the level of demand is thought to influence irreversible capacity decisions. This paper examines some implications of the theory literature on this topic in an empirical study of the US cement industry between 1994 and 2006. Firms in this sector have the ability to deliver cement either from domestic plants or from imports. Since cement is costly to transport via land, the difference in marginal cost between local production and imports varies across local markets. The marginal cost of imports is lower in areas with access to a sea port, decreasing the relative value of investing in local capacity sufficient to supply positive local demand shocks. In the presence of uncertain demand, firms may choose to serve these markets via both domestic production and imports. Consistent with the theory, we find a negative relationship between the average level of excess capacity and demand volatility only for coastal areas. An increase in demand volatility is associated with an increase in excess capacity only in landlocked areas. More generally, the paper shows that the cost of imports relative to the cost of domestic production affects the relationship between uncertainty and domestic capacity decisions. The results suggest that a unilateral climate policy in the US may induce a partial international relocation of capacity in carbon intensive industries, such as cement, by increasing the relative cost of domestic production.

Introduction

Several important theory papers investigate the relationship between the optimal level of capacity and demand uncertainty. Ordinarily the relationship is ambiguous. We study this relationship in the context of the US cement industry where firms may have access to two technologies: capital-intensive local production at a low marginal cost, and a flexible technology corresponding to importing at a higher marginal cost that includes transport costs. The research question can be summarized as follows: Does variation in access to imports help explain variation in the relationship between local demand uncertainty and the domestic capacity decisions made by cement producers in the US?

We show that there is a negative relationship between the level of excess cement production capacity and demand volatility in coastal regions in the US between 1994 and2006, where the incremental marginal cost associated with importing cement is lower. In landlocked regions where the relative cost difference is greater, increases in demand volatility are associated with increases in excess capacity. The average plant size is also increasing with demand volatility within landlocked regions but not within coastal regions.

There are four major reasons why the US cement industry is an attractive industry in which to study the role of uncertainty in investment decisions. First, the industry is regionally segmented, and there are many plants located throughout the country in varying economic environments. Second, capacity decisions are the major firm-level decision in the industry since cement production is capital intensive. Third, demand for cement in each regional market is largely uncertain. It follows the general business cycle as well as the local cycles typical of the construction industry. Last, in recent decades, long-haul maritime imports have played an increasing role in absorbing fluctuations in US domestic demand. Importantly, a large fraction of the installed base of US cement capacity is controlled by the large multinational firms that dominate this industry worldwide. Following [START_REF] Kogut | Operating Flexibility, Global Manufacturing, and the Option Value of a Multinational Network[END_REF] these firms may use their global production networks to adapt to the demand fluctuations in a given market.

The theoretical framework analyzing capacity decisions under this type of uncertainty goes back to the Rothschild andStiglitz papers (1970, 1971). These authors investigate the monotonicity properties of an irreversible decision when risk increases. They provide a necessary and sufficient condition for such a property to hold, point out that this will rarely be the case, and indeed provide a number of economic examples in which it does not. This work can be related to the option value literature originating with [START_REF] Henry | Investment decisions under uncertainty: The "irreversibility effect[END_REF], [START_REF] Arrow | Environmental Preservation, Uncertainty, and Irreversibility[END_REF], and fully developed by [START_REF] Dixit | Investment Under Uncertainty[END_REF]. There the question concerns the impact of a future learning phase on the current irreversible decision. As has been widely noted, the relationship between uncertainty in general and investment is theoretically ambiguous.

Our empirical analysis relies on an analytical model tailored to the cement industry developed by [START_REF] Meunier | Capacity decisions with demand fluctuations and carbon leakage[END_REF]. In a setting of oligopolistic competition in a local market, each firm has to decide its capacity when facing uncertain demand. Once the level of demand in a given time period is revealed, the firm may use imports to complement domestic production if local capacity is saturated. The optimal capacity choice is monotonic with respect to the level of uncertainty, contingent on the cost of imports relative to the domestic production cost. Specifically, capacity is increasing with uncertainty if the cost of imports is relatively large, and decreasing if the cost of imports is relatively small. This contingent property is at the crux of our empirical analysis.

There are a number of papers which relate directly or indirectly to our work. The closest paper is Rob and Vettas (2003). In their model, as in ours, FDI and exports (domestic production and imports, respectively, in our model) will co-exist under some circumstances. Much of the prior existing theory on FDI offers only limited explanation of this empirical regularity, as noted by [START_REF] Blonigen | In Search of Substitution between Foreign Production and Exports[END_REF] and Head and Ries (2001). However, Rob and Vettas focus on the optimal strategy mix between FDI and exports as demand grows over time, while we focus on the optimal strategy mix (between domestic production and imports) as demand uncertainty varies across settings with differing variable costs of imports.

A number of theory papers have studied the impact of uncertainty on capacity decisions. Firms are predicted to select a higher capacity with uncertainty [START_REF] Gabszewicz | Demand Fluctuations and Capacity Utilization under Duopoly[END_REF]. [START_REF] Demers | Investment under Uncertainty, Irreversibility and the Arrival of Information Over Time[END_REF] analyzes capacity choice in a dynamic oligopolistic Markov model. The author shows that the equilibrium capacity is also increasing with uncertainty. In this model the firm is constrained to always produce as much as its earlier capacity commitment, possibly more with a penalty cost, but never less. These theory models assume only one technology, and can hence be viewed as analogous to the conditions in landlocked markets in our analysis, where the import technology is prohibitively costly. We allow firms access to two technologies -domestic production and imports -in coastal markets. This two-technology setting generates the contrasting predictions in different geographic markets which we explore in the data.

Capacity decisions may also be analyzed as a strategic entry barrier. Typically, a monopoly or an oligopoly may operate with excess capacity to deter entry. There have been many theoretical contributions that justify such strategic behavior, such as [START_REF] Spence | Entry, capacity, investment and oligopolistic pricing[END_REF] and [START_REF] Dixit | The role of investment in entry-deterrence[END_REF]. A number of empirical studies have tested this hypothesis in specific industry studies, see for instance [START_REF] Ghemawat | Capacity expansion in the titanium dioxide industry[END_REF] and [START_REF] Mathis | Excess capacity as a barrier to entry in the US titanium industry[END_REF]. As noted by [START_REF] Lieberman | Excess capacity as a barrier to entry: An empirical appraisal[END_REF], the empirical results have in general failed to provide strong supporting evidence. Our focus in this paper is on the role played by uncertainty in capacity decisions, and we attempt to control for incentives to engage in preemptive behavior by controlling for local demand growth in the empirical work.

To sum up, we rely on a model of capacity decisions designed for the cement industry. This model exhibits original monotonicity properties between capacity and uncertainty which vary depending on the relative cost of a second production technology. Empirical evidence from the US cement industry supports the model's predictions.

The significance of our empirical contribution comes from the observation that, whereas the relationship between uncertainty and investment is a major focus of macroeconomic study, there is a limited amount of work at the micro level. [START_REF] Carruth | What do we know about Investment under Uncertainty?[END_REF] survey the existing empirical work. Studies of plant or firmlevel variation in investment and uncertainty, including [START_REF] Leahy | The effect of uncertainty on investment: some stylized facts[END_REF] and Guiso and Pirigi (1999), focus on roles played by cross-industry variation in investment irreversibility and also, to a lesser extent, on differences in market structure. [START_REF] Bloom | Uncertainty and Investment Dynamics[END_REF] evaluate the predictions of a dynamic model about how uncertainty affects the responsiveness of investment to shocks to demand using firm-level data from the UK. [START_REF] Goldberg | Exchange rates and investment in United States industry[END_REF] finds a negative relationship between investment and exchange rate variability in some sectors, but [START_REF] Campa | Investment in manufacturing, exchange rates and external exposure[END_REF] find that exchange rate variability has no significant effect on investment levels in US manufacturing. There are even fewer industry-level studies. Notable exceptions include the studies of the North Sea oil by [START_REF] Hurn | Geology or economics? Testing models of irreversible investment using North Sea Oil Data[END_REF] and [START_REF] Favero | A duration model of irreversible oil investment: Theory and empirical evidence[END_REF]. [START_REF] Bell | Irreversible Investments and Volatile Markets[END_REF] find no relationship between product demand volatility at the country level and capacity investment in the chemical processing industry. Most micro-level empirical work is based on variation in the option value of delaying investment, dynamics and adjustment processes. Our approach is closer to the original perspective taken in Rothschild and Stiglitz in that we are interested in the impact of the level of demand volatility on irreversible decisions.

The Meunier and Ponssard model was originally devised to investigate the "leakage" issue in the cement industry. A high unilateral carbon price increases the domestic cost of production relative to foreign imports, hence production and CO2 emissions may simply "leak" to other countries rather than decline overall. The model predicts that the implementation of a unilateral climate policy may have a negative long term impact on local investment levels, amplifying the short term competitiveness impact usually captured in static models. Our empirical findings provide an indirect way to test this prediction. In this study, landlocked districts are analogous to domestic countries prior to the imposition of a unilateral carbon price, and coastal districts reflect the ex-post case. Based on this analogy, our findings suggest that there is indeed a relocation effect of capacity due to a high domestic carbon price. We return to this point in the concluding section.

The paper is organized as follows: Section 2 provides some background on the cement industry and describes the data used in the study. The analytical model that sustains our empirical testing is described in Section 3. Section 4 develops the methodology employed and Section 5 describes the empirical results. General implications of these results are addressed in the concluding section.

The cement industry

General characteristics of the cement industry

There are a limited number of competitors in any one geographical location in this industry. As described in D' Aspremont et al. (2000), demand for cement is more or less proportional to the density of the population. Production takes place in large plants and, once built, the capacity of a given plant cannot be increased without large reinvestment. In addition, markets are horizontally differentiated. Quality-wise cement is a homogenous good, but a high transportation cost relative to the production cost creates strong spatial differentiation.

Local demand tends to be quite volatile, generating significant regional differences between supply and demand. These differences need to be balanced with inter-regional flows, some from adjacent regions, others, in particular if the region is on the coast, through long haul flows. 1 The conditions for long haul transportation of cement changed drastically in the late seventies (Dumez and Jeunemaitr , 2000). Because of technological change, it became possible to transport cement in bulk quantities safely and cheaply in very large ocean-going vessels, which, however, remain too large to pass through the US river system. This triggered a major change for the US cement industry. The import of cement to areas such as Florida, California, New York, and Texas increased steadily, coming from South America, Europe, or Asian countries. It was also at this time that the world cement industry entered a phase of ownership concentration, indirectly driven by this enlargement of its strategic market. In 2007, as stated by analysts' reports, the top five cement firms accounted for approximately 20% total world market share. The world cement industry may be seen as a network of regional oligopolies, [START_REF] Ghemawat | Strategic Interaction across Countries and Multinational Agglomeration: An Application to the Cement Industry[END_REF]. e Major cement firms such as Cemex, Holcim and Lafarge typically operate a large number of plants. 2 The existence of such networks allows these firms to optimize their sourcing of production at any point in time depending on local supply and demand conditions. 3 Their short term optimization depends on their available capacities in the various markets and on the relative production and freight costs. As such they have a competitive edge over smaller firms that are limited to a given regional market. Traders may also be active to complement the lack of local capacities. These traders may indeed react quickly to an occasional disequilibrium but they do not have the long term efficiency to sustain long haul trade flows. They often prefer to sell the market positions obtained at peak demand to local players when the downturn comes.

The US cement industry

We now turn to the data on the US cement market used in this study, noting that demand fluctuates at the local level within the US. Our primary data is published by the U.S. Geological Survey (USGS) and summarized in the annual Minerals Yearbook. 4 In the data, the US is divided up into 23 regional districts, the boundaries and groupings of which differ slightly across years. We construct time series data by district for cement capacity, production, and demand, grouping together districts where necessary. 5 The data are summarized in Table 1 and pairwise correlation coefficients for the key variables used in the study are given in Table 2.

(Excerpt from) Table 1: a classification of US cement markets

The USGS breaks down total imports of cement and clinker by customs district. Major import terminals include Tampa, FL, New Orleans, LA, Los Angeles, CA, Miami, FL, and Houston-Galveston, TX. Smaller import terminals are spread out over the East Coast of the US and include Baltimore, MD, New York City, NY, Norfolk VA, and Philadelphia, PA. 6In each year, there are also imports to Detroit, MI and other northern Midwestern districts from Canada. All of our results are robust to classifying both the Michigan and Wisconsin district and the Ohio district as coastal rather than landlocked, reflecting their accessibility via lake transport from Canada. 7Our study employs data from 1994 to 2006. Since the lifespan of a cement plant may exceed 40 years, it is important to study a relatively long time period to understand capacity decisions. Graph 1 presents the evolution of cement consumption and imports between 1980 and 2006. Over the first part of this time period, up to the early 1990s, the cement industry was considered a mature business (for a discussion on the US cement industry at that time, see Scherer's postface in Dumez and Jeunemaitre, 2000). A large fraction of the US industry was acquired by European (and Mexican) companies (this acquisition wave is discussed in Collomb and Ponssard, 1984). It is also at the beginning of this period that technical change made long haul imports feasible and relatively cheap. By the early 1990s, the US cement industry had been partly restructured and imports came in to the country largely via the new domestic players.8 In the early 2000s, according to industry sources, global cement players such as Cemex, Holcim, Lafarge, and Lehigh (Heidelberger) operated import terminals located in the East coast. We may certainly hypothesize that the proposed adjustment process of domestic capacities to cope with demand fluctuations had taken place.

One further point is worth attention. Imports are indeed positively correlated with aggregate domestic consumption. The regression coefficient capturing this correlation (the "beta" of a regression of the percentage deviation from the mean level of imports on the equivalent for domestic demand) is computed to be 2.55, which demonstrates that imports are correlated with domestic consumption and tend to be more volatile.

District-level capacity is measured in our data as the finish grinding capacity in thousand metric tons, and is based on the grinding capacity required to produce a plant's normal output mix, including both portland and masonry cement, allowing for downtime for routine maintenance. Production, also in thousand metric tons, includes cement produced using imported clinker. The USGS Minerals Yearbook also includes data on the number of active plants by district -which allows us to measure average plant size in each year -and the percentage of plants that are dry and wet process.9 Table 1 summarizes the levels of capacity investment in each district in 1994 and 2006. There was an increase of 26% in the total metric tonnage of cement capacity in the US over this time period. The total number of plants declined by 5 to 113 in 2006, meaning that the average plant size increased by 31%. There was also a 15% increase in the percentage of plants that used the relatively efficient dry or both wet and dry process rather than wet process technology.

These aggregate measures mask substantial variation across districts. The standard deviation of the percentage change in capacity is 29%. Much of the variation in capacity across districts corresponds with variation in regional economic growth, and so to seek to understand the roles played by demand volatility we must also control for the role of demand growth in explaining these patterns. We measure demand growth as the average percentage change in the level of demand over the prior four years.

To measure demand uncertainty for each district, we construct a measure of the variance in demand levels over the past four years and the current year. To avoid overstating uncertainty we de-trend the data to account for changes in demand levels that are consistent with patterns that are arguably predictable. Since this measure of variation will be a function of the level of demand, we also normalize our uncertainty measure to facilitate comparison of uncertainty across districts of different sizes. To do this, we regress demand by district over the past five years on a constant and take the standard deviation of the five residual values, divided by the mean demand level over the five years. Panel B of Table 1 lists the district level mean demand growth and demand volatility over the data period.

We note that our measure of volatility is backwards-looking since it is constructed using district-level data from the last four years. Any increase in volatility is due to the level of demand in the current year being less similar to the level of demand for the past three years than is the level of demand four years ago to the prior three years. As will be described in Section 4, we also classify districts into high and low demand volatility districts, capturing whether the level of volatility is higher or lower than the mean level across districts over the entire time period.11

The analytical model applied to the US data

As mentioned in the introduction, our empirical analysis is based on the model developed by [START_REF] Meunier | Capacity decisions with demand fluctuations and carbon leakage[END_REF]. The model features a local oligopoly that faces demand fluctuations. It was designed to study the impact of the EU-ETS on investments in the EU cement industry. In this section, we describe its application to the present context, and discuss its key predictions.

Each firm may source its production from plants in two areas, some located in the "home" market and some located abroad, i.e. "foreign" plants from which it may import. Home plants have a lower variable cost and are capacity constrained. Foreign plants have a higher variable cost, when including the cost of transport to the home market, and are not capacity constrained because there are many of them that can potentially export to this home market.

Our focus is on the dependence of the capacity decisions at home on import costs as demand uncertainty increases. Imports will be required at peak demand levels, given the home capacity constraint. Consequently, the optimal capacity depends on the relative cost of import costs versus domestic production costs. Intuitively, the lower the import cost the more beneficial it is to import and the lower the optimal capacity should be. This intuition can be related to the original paper by [START_REF] Rothschild | Increasing risk ii: Its economic consequences[END_REF] (example D in Section 2) in which a rigid input (capital) may be combined with a flexible one (labor). There, the choice of capacity depends on the relative elasticity of substitution between the two inputs.

In our application to the cement industry, the market is the US district. In each district there are local plants. These local markets differ according to the cost of importing cement. It will be assumed that these costs are higher in landlocked districts (i.e. with no access to the ocean) than in coastal ones (i.e. with access to the ocean). In practice, the import costs are subject to a number of other factors such as the price of oil, or the overall macroeconomic conditions. However, it will remain true at all times that it is more expensive to import into a landlocked district than into a coastal one. We implicitly assume that adjacent markets follow similar business cycles so the balance of supply and demand mostly comes from long haul flows, or from a ripple effect.12 This appears to be borne out in the data. The mean district pairwise correlation in deviations from mean excess capacity between 1994 and 2006 is positive, and the mean pairwise correlation for geographically proximate districts tends to be more strongly positively correlated. 13The inverse demand function in each district is assumed to be linear: p = a + bq, in which p is the price, q the quantity on the market, and a and b are two positive parameters. Uncertainty is introduced through the random variable  assumed to be uniformly distributed on the interval [-1; +1] with density ½. The parameter  measures the range of demand variation, the case of no uncertainty corresponds to  = 0.

N firms operate in the market. Each firm has access to two technologies: a home one and a foreign one. The cost function for the home technology consists of two terms: a linear investment cost c k relative to a capacity choice denoted k, and a linear production cost c h . 14 The cost function for the foreign technology involves a linear production cost c f and no investment cost. In the case of no uncertainty the home technology is preferred to the foreign one, c h + c k < c f and demand is high enough to make production worthwhile, a > c h + c k . Furthermore,  is limited so that in all realized demand states, it is worth producing with the home technology: 0 ≤ ≤ a -c h .

The decision process takes place in three stages. First, the firms decide their capacity k relative to the home technology. Second, uncertainty is resolved for the time period in question, and the realized value of is revealed to the firm. Third, the production decisions (q h , q f ) using respectively the home and foreign technologies are made by the firm. It is explicitly assumed that the production decisions of any given firm do not depend on the capacity of its competitors. This assumption means that firms will not select their capacity to pre-empt competitors, but only to face demand fluctuations optimally.

Meunier and Ponssard derive the optimal capacity k*. Consider first the case of a monopoly, N=1 (we show later on that the results are not substantially affected when N>1). The optimal capacity is better understood using a two dimensional diagram with axes as volatility  and cost of imports c f . The diagram defines four zones, labeled from 1 to 4 (see Graph 2). The analytical expression of the optimal capacity depends on the zone. It is given in Table 2, which also provides straightforward comparative statics properties.

Qualitatively, the optimal capacity is increasing as the cost of imports increases; eventually, as one may expect, it does not depend on this cost. The influence of volatility depends on whether the cost of imports is high or low (to be precise, greater or lower than 2c k +c h ). If it is high (along the "landlocked" vertical line), the optimal one group was the average correlation less than the overall average (0.109 in the Midwestern group). This was due to a relatively large negative correlation between the Arkansas and Oklahoma and the Iowa, Nebraska, and South Dakota districts. We note that these two districts, while close, are separated by Kansas and Missouri. 14 The introduction of a fixed component in the investment cost is immaterial for the analysis.

capacity is increasing with volatility; if it is low (along the "coastal" vertical line), it is decreasing with volatility.

Graph 2: The structure of the optimal capacity as a function of volatility and the cost of imports.

[a-c h -c k ]/2b Independent of c f Independent of  2 [a-c h +-(2c k ) 1/2 )]/2b Independent of c f Independent in  3 [a-(c h +c f )/2+-2c k /(c f -c h ))]/2b Increasing in c f Increasing in if c f > 2c k +c h Decreasing in if c f < 2c k +c h 4 [a-c f -2b +[c f -c k -c h )] 1/2 /b Increasing in c f

Decreasing in 

A nice prediction of the model is that the higher the volatility the more important the differences between the excess capacity ratios selected by a coastal firm relative to a landlocked firm (formally it is easy to check that  2 k*/  c f ≥ 0). This is illustrated in Graph 3. The difference between C and D is larger than the difference between A and B This prediction will be tested. Whether the excess ratios are actually increasing with uncertainty for a landlocked district and decreasing for a coastal one depends on the actual value of the cost of imports relative to the critical level 2c k +c h . This prediction will also be tested.

A

For completeness, the frontiers of the zones identified in Graph 2 are given in Table 4.

Table 4: the frontiers of the zones that define the optimal capacity

Frontier

Analytical expression Zones 1 and 2  = c k Zones 2 and 3

 = c f -c h ) 2 /4 c k Zones 3 and 4  = c f -c h ) 2 /4(c f -c h -c k )
Zones 4 and 1

 = c f -(c h +c k )
Consider now the case of N firms, with N>1. Denote k*(N;) the optimal capacity decision as a function of N and  Meunier and Ponssard prove that, at the Nash equilibrium, the capacity satisfies k*(N;) = 2k*(1;)/(N+1). As a consequence, the excess capacity ratio due to the presence of uncertainty, k*(N;)/k*(N;), does not depend on the market structure, even if capacity does.

We now turn to the evaluation of the model's predictions using the US data. The table below (an excerpt from Table 5) presents excess capacity (capacity less production) divided by the level of capacity on average for the districts in each of four categories. These categories mirror Graph 3: landlocked and coastal districts and low and high volatility districts. We see that the excess capacity in low demand volatility districts is the same across coastal and landlocked districts; on average, 20% of capacity is unused in each of these district groups. Among high volatility districts, however, coastal districts have much lower levels of excess capacity on average than landlocked districts. As noted in the preceding section, it is likely that the phenomenon under study appeared over the course of the 1980s, as the availability of cheap long haul transportation developed. Table 5 also shows the change in average excess capacity in each of the four categories between 1994 and 2006.

(An excerpt from)

In the context of the model, if we consider that the plant efficient scale has increased over time, it makes more sense to increase average plant capacity in a landlocked district than in a coastal one. In a similar way, since we expect that dry kilns are more efficient than wet kilns, there are more investment opportunities to make this technological change in a landlocked district than in coastal one. Table 5 demonstrates that this indeed seems to be the case.

We see large percentage increases in excess capacity, average plant size, and percentage dry process plants in high volatility landlocked districts. We see the smallest percentage increases (or largest percentage decrease) in high volatility coastal districts. These broad patterns are consistent with the predictions of the model. But, since the growth rates of these variables are clouded by variation in demand growth, we now look at cross sections of the data at different points in time.

We analyze the relationship between demand volatility and the ratio of capacity to production at the start of our data sample, in 1994, and at the end, in 2006. We regress this measure of excess capacity in each district on an indicator variable for whether the district is high volatility over the time period, an indicator variable for whether it is landlocked, and the interaction of these two indicator variables. We also control for whether the district experiences high growth over the data period, and the interaction of the high growth and landlocked indicator variables. Table 6 presents these results for 1994 and 2006.

(Excerpt from) In panel B of Table 6, the tests of significance of the relevant linear combinations of coefficients reveal that in 1994 higher demand volatility coastal districts have significantly lower levels of excess capacity than low demand volatility coastal districts. High volatility landlocked districts also have somewhat lower excess capacity than low volatility landlocked districts, although this relationship is not significant. By 2006, the average level of excess capacity in high volatility coastal districts has fallen even further.

There has been no corresponding reduction in landlocked districts; rather the average level of excess capacity in high volatility landlocked districts in 2006 is very similar to the level in low volatility landlocked districts.

Estimation Strategy

We now turn to analyze the patterns revealed in Table 6 in more detail. We examine the level of excess capacity in each district by investigating variation in the yearly capacity level less the mean production level in the district over time divided by the yearly capacity level. We use the mean production by district over the time period 1994-2006 in the numerator of the dependent variable here to ensure that any variation in a district over time reflects firms' decisions related to capacity choices rather than yearly fluctuations in production, which will vary systematically with annual local demand. We regress this dependent variable on district-level demand growth, demand volatility, and the interaction of each of these measures with an indicator for whether the district is landlocked or coastal. We include the landlocked indicator variable and year fixed effects as control variables. This specification reveals how variation in excess capacity is related to variation in local demand conditions in cross section.

The estimated equation is:

    t i i i t i G i t i G t i V t i G t i Year i L L V L G V G y , , , , , , . * * (1)               
where y it is the measure of excess capacity in district i in year t, G it and V it are the yearly values of district demand growth and volatility, respectively, and L i is the landlocked indicator variable.

As is common in the analysis of panel data, we confront serial correlation in the independent variables since each observation of demand growth and demand volatility is constructed using data from the previous four years. The landlocked indicator variable is, of course, constant over time. Since we have only 23 districts in this study, clustering standard errors to allow for correlation within district is inappropriate. We report the robust unclustered standard errors and the standard errors produced by a nonparametric bootstrap estimation, clustering the draws in the bootstrap repetitions by district. We draw inference about the statistical significance of linear combinations of the estimated coefficients, and about the difference between linear combinations, using the bootstrapped standard errors.

We test whether differences in the estimated coefficients are significantly different from zero, and significantly different from each other, in ways that are consistent with the predictions of the model. Starting with the group of coastal districts, we test whether there is a significant difference in excess capacity for districts at the 5 th and 95 th percentiles of district-level demand volatility. We do the same for the group of landlocked districts. We then ask whether there is a significant difference in levels of excess capacity between coastal and landlocked districts at the 5 th percentile of demand volatility and at the 95 th percentile of demand volatility.

The estimation described in equation ( 1) does not include district fixed effects and so district-level factors other than whether the district is landlocked may be contributing to the results. The second specification we estimate includes district fixed effects in equation ( 1), and hence omits non-time varying district characteristics. This specification tells us whether changes in demand growth or volatility within a district are associated with changes in the level of excess capacity which, since the denominator is timeinvariant, corresponds to changes in the level of capacity within-district. Once again, we present the results with both unclustered and bootstrapped standard errors.

Using the output from this specification, we ask whether a change capacity is associated with an increase in volatility for different district groups, using the bootstrapped standard errors. The impact of the change in volatility is restricted to be constant at all levels of growth or volatility in this linear specification. Hence, to test whether a change in demand volatility is associated with a change in the level of excess capacity in coastal districts, we examine the significance of the coefficient estimate for demand volatility. To test whether a change in demand volatility is associated with a change in capacity in landlocked districts, we test whether the linear combination of the coefficients on demand volatility and the interaction of demand volatility and the landlocked indicator is significantly different from zero. We then test whether changes in demand volatility have significantly different effects on capacity in coastal versus landlocked districts.

Last, we note that our data contains some information on the quality of capacity by district. We know that, in this industry, larger plants are on average more efficient and also that dry process plants are more efficient that wet process plants. The model has similar predictions for upgrading the quality of capacity as for the amount of capacity. Accordingly, we examine whether plant size and the percentage of dry process capacity within-district are related to demand uncertainty in a way consistent with the predictions of the model. We estimate equation (1) including district fixed effects with the average plant size and the percentage of dry process capacity as the dependent variables.

Results

Panel A of Table 7 presents the results from the first regression specification, equation (1). Columns 1 and 2 reveal that, on average, greater volatility is associated with lower levels of excess capacity controlling for demand growth and production levels. This appears to contradict previous models which consider only one production technology and predict a positive association between demand volatility and capacity. Higher levels of demand growth are positively associated with excess capacity, but not significantly so. Columns 3 and 4 show that the negative relationship between demand volatility and excess capacity varies across districts by separating the data into coastal and landlocked districts and investigating whether the relationship holds in each subgroup.

We see that higher volatility is associated with lower excess capacity only in coastal districts. Panel B of Table 7 constructs the linear combinations of relevant coefficient estimates for different groups of districts. The level of excess capacity is significantly lower in coastal districts with higher demand volatility than in coastal districts with lower demand volatility. For landlocked districts, where high transport costs allows firms access to only one production technology, the difference in excess capacity between high and low volatility districts is not significantly different from zero. Moreover, we note that excess capacity in high volatility coastal districts is significantly lower than excess capacity in high volatility landlocked districts.

The results for the second specification, equation (1) including district fixed effects, are given in Table 8. Changes in capacity are on average positively associated with changes in demand volatility, although the relationship is not significant with the bootstrapped standard errors. Columns 3 and 4 show that there is a significant positive coefficient on the interaction of demand volatility and the variable indicating that a district is landlocked. Panel B of the table contains the linear combinations of estimated coefficients and the analysis of significant differences. We see that there is a positive relationship between changes in volatility and changes in capacity in landlocked districts that is significant at the 5% level. There is also a significant difference in the response to changes in volatility between landlocked and coastal districts -the relationship is significantly more positive in landlocked districts.

Table 9 contains the results for the estimation of equation ( 1) including district fixed effects with average plant size and the percentage of dry process plants as the dependent variables. The findings for average plant size are consistent with the model's predictions. An increase in demand volatility is, on average, associated with an increase in the average plant size in a district. This positive relationship is, however, limited to landlocked districts. The tests of significance of the linear combinations of the coefficients reveal that the slope of the relationship between average plant size and demand volatility is significantly more positive for landlocked than for coastal districts.

The corresponding results in Table 9 for the percentage of dry process plants offer no empirical support of the model's predictions. There are no significant differences in the relationship between percentage dry process and demand volatility and whether a district is landlocked. We note, though, that many districts began the data period with 100% dry process plants, as shown in Table 1, and offer no variation throughout the period from which to draw inference.

Concluding comments

This paper provides some empirical evidence about the theory of irreversible decisions under uncertainty at the micro-level. It shows that the capacity decisions of US cement firms are consistent with the theory: the amount of domestic excess capacity over an uncertain business cycle depends on the relative cost of imports, which varies from coastal to landlocked markets. The positive relationship between demand uncertainty and investment predicted by theory models with only one technology is present in landlocked districts where imports are prohibitively costly. The paper also provides a new rationale to explain the co-existence of home production and imports in the US cement market by large multinational firms. Adding demand volatility to the proximityconcentration tradeoff described in [START_REF] Brainard | An Empirical Assessment of the Proximity-Concentration Trade-off Between Multinational Sales and Trade[END_REF] can explain why we see imports and domestic production -even in the long run -in districts where the variable cost of imported cement is not too much greater than domestic production. The greater the demand volatility in these districts, the larger the average ratio of imports to FDI. Specifically, we show that coastal districts with high demand volatility have significantly lower levels of excess capacity than coastal districts with low demand volatility, controlling for the level of demand and recent demand growth. Landlocked districts look very different. Investment in capacity, and the average plant size, both increase with demand volatility in these districts.

We are able to infer significant differences in the relationship between excess capacity and demand volatility between coastal and landlocked districts even though our analysis is based on fairly aggregated data and covers only 12 years. A simple regression with 23 observations of the average district-level excess capacity on indicator variables for whether the district is landlocked, whether it has high demand volatility on average over the entire period, and the interaction of the two, while allowing for the role of demand growth to vary with whether the district is coastal or not, reveals that high demand volatility coastal districts have significantly lower levels of excess capacity than when demand volatility is low. This suggests to us that our more detailed analysis is capturing meaningful correlations in the data.

A number of other caveats should be made. Some important features of the industry are not taken into account explicitly in the model or the empirical work. These include the existence of independent importers (pure traders, grinding stations, ready mix companies…), strategic behavior for preemption purposes, and further local variation in geography of each market (large urban areas or other types of market). Extending the model to incorporate these features is left to future research. It may also be interesting to extend the empirical analysis to other cement markets. Preliminary analysis using data from the industry source Cembureau reveals that coastal countries, such as the UK, have significantly lower levels of excess capacity than landlocked countries such as Switzerland. A country like Spain exhibits both landlocked and coastal markets and, as such, is a good candidate for inclusion in a further test, but detailed regional data is less readily available for Spain than for the US.

From a policy perspective, this paper provides a contribution to the current debate on the impact of unilateral climate policies. The EU implemented a unilateral policy in 2004 with a cap and trade scheme for carbon intensive industry (such as cement production, electricity, glass, oil refineries, steel…). Other industrialized countries such as the US may engage in similar policies in the future. This has triggered an intense debate about the effectiveness of unilateral policies in sectors that are subject to international competition, which includes most of the carbon intensive sectors except electricity [START_REF] Grubb | Allocation and competitiveness in the EU emissions trading scheme: policy overview[END_REF]. In theory, we expect a reduction in market share and a decline in investment from home producers, and a concomitant increase in imports from countries with no similar climate policy (for a discussion in the cement case see for instance [START_REF] Demailly | CO2 abatement, competitiveness and leakage in the European cement industry under the EU ETS: grandfathering versus output-based allocation[END_REF]Quirion, 2006 or Ponssard and[START_REF] Ponssard | EU emissions trading and the cement sector: a spatial competition analysis[END_REF]. This would reduce the efficiency of unilateral policies in curbing worldwide emissions through the so-called leakage effect -an increase in foreign emissions substituting for any decrease in domestic emissions.

So far there is very little empirical evidence to support the conclusions derived from these analytical models [START_REF] Ellerman | Pricing Carbon, The European Union Emissions Trading Scheme[END_REF]. Still, the debate remains open since existing empirical work cannot yet capture long run effects. This paper provides an important indirect contribution. It substantiates that there are indeed long term effects on investment levels associated with a change in the relative costs of imports when demand is subject to uncertainty. The recent failure of the United Nations Climate Change Conference in Copenhagen to agree to implement a uniform carbon tax across international markets reinforces the importance of these considerations.

Graph 1 :

 1 Demand and imports in the US cement market, 1980-2006.

  Three districts -Ohio, and Eastern and Western Pennsylvania -saw declines in capacity. Northern Texas and the district containing Georgia, Virginia, West Virginia, South Carolina, and Maryland saw the largest absolute increases in capacity. The percentage increases were largest in Kansas, the district containing Kentucky, Mississippi, and Tennessee, Northern Texas, and Florida, at 85%, 74%, 68%, and 67%, respectively. The largest increases in average plant size took place in the Colorado and Wyoming district, which also saw a plant closure. Other large increases were seen in Kansas and Northern Texas. There were no decreases in average plant size in any district. 7 of the 23 districts had 100% dry or both wet and dry process plants in 1994, 10 of the remaining 16 districts saw an increase in the percentage of dry process plants, and 2 districts saw a decline.10 The demand data is aggregated by the USGS up from the state-level cement shipments to final customer. It includes cement produced from imported clinker and imported cement shipped by domestic producers and importers. Table 1, panel A, also summarizes the demand data by district in 1994 and 2006.

Table 3 : the analytical expression of the optimal capacity and its comparative statics properties

 3

	Zone Optimal capacity	Comparative statics properties
	1

Table 5 : Excess Capacity ((Capacity-Production)/Capacity) by District Group

 5

		2006
		Low	High
		Volatility	Volatility
	Landlocked	0.20	0.15
		(0.06)	(0.08)
	Coastal	0.20	0.10
		(0.05)	(0.10)

Table 5 :

 5

		Excess Capacity
		((Capacity-Production)/Capacity)
		Percentage Change 1994-2006
		Low Volatility	High Volatility
	Landlocked	9.23	42.41
		(47.57)	(109.31)
	Coastal	29.08	-18.38
		(60.36)	(94.46)
		Average Plant Size ('000 metric tons)
		Percentage Change 1994-2006
		Low Volatility	High Volatility
	Landlocked	28.62	56.65
		(15.86)	(30.98)
	Coastal	18.77	17.59
		(21.37)	(16.21)
		% Dry Process
		Percentage Point Change 1994-2006
		Low Volatility	High Volatility
	Landlocked	13%	29%
		(23%)	(21%)
	Coastal	45%	-3%
		(66%)	(5%)

Table 1 : Summary Statistics Panel A

 1 We take the number of plants from Table3of the USGS Minerals Survey in each year. The percentage dry technology is taken from Table5, which is based on the number of white cement plants. The total number of white cement plants is on occasion less than the total number of plants. This means the percentage dry technology does not reflect a percentage of the total number of plants.

				1994					2006
						Percentage Dry					Percentage Dry
	District				Average Plant	(or Wet and				Average Plant	(or Wet and
	Number District Name	Demand	Active Plants*	Capacity	Size	Dry)*	Demand	Active Plants*	Capacity	Size	Dry)*
		000 metric tons	#	000 metric tons 000 metric tons	%	000 metric tons	#	000 metric tons 000 metric tons	%
	Alabama	1432	5	4573	914.6	100%	1798	5	6036	1207.2	100%
	Alaska, Hawaii, Oregon, Washington	3168	4	2295	573.8	75%	4307	4	2540	635.0	67%
	Arizona, New Mexico	2823	3	2288	762.7	100%	5511	3	3310	1103.3	100%
	Arkansas, Oklahoma	1994	4	2694	673.5	50%	2730	4	3260	815.0	50%
	California, Northern	2872	3	2776	925.3	100%	4761	3	2853	951.0	100%
	California, Southern	5328	8	7933	991.6	100%	9549	8	10238	1279.8	100%
	Colorado, Wyoming	2021	4	2377	594.3	75%	3107	3	3450	1150.0	100%
	Florida	5623	6	4382	730.3	50%	11180	7	7301	1043.0	100%
	Georgia, Virginia, West Virginia, South Carolina, Maryland	9461	11	8586	780.5	60%	14716	10	11636	1163.6	78%
	Idaho, Montana, Nevada, Utah	3112	6	2422	403.7	33%	5443	6	3750	625.0	50%
	Illinois	3593	4	3217	804.3	100%	4555	4	3420	855.0	100%
	Indiana	1876	4	2867	716.8	50%	2173	4	3720	930.0	75%
	Iowa, Nebraska, South Dakota	3112	6	5758	959.7	100%	4182	5	6048	1209.6	100%
	Kansas	1277	4	1801	450.3	50%	1546	4	3329	832.3	75%
	Kentucky, Mississippi, Tennessee	3794	4	2128	532.0	50%	4765	4	3700	925.0	75%
	Michigan, Wisconsin	5992	5	6532	1306.4	67%	6578	5	7328	1465.6	67%
	Missouri	2386	5	5059	1011.8	60%	2626	5	6958	1391.6	60%
	New York, Maine	3691	5	4141	828.2	20%	5207	5	4203	840.6	50%
	Ohio	3482	3	1588	529.3	50%	3727	2	1304	652.0	50%
	Pennsylvania, Eastern	1967	8	4878	609.8	71%	2172	7	4530	647.1	67%
	Pennsylvania, Western	2529	4	2009	502.3	25%	3030	3	1770	590.0	33%
	Texas, Northern	3817	6	4512	752.0	50%	6499	6	7594	1265.7	67%
	Texas, Southern	5759	6	5529	921.5	100%	10668	6	5850	975.0	100%
	Panel B
				1994-2006
			High Demand	High Demand	Mean Demand	Mean Demand
	District	Landlocked	Growth	Volatility	Growth 1994-	Volatility 1994-
	Number District Name	Indicator	Indicator	Indicator	2006	2006
	Alabama	1	0	0	0.020	0.024
	Alaska, Hawaii, Oregon, Washington	0	0	0	0.020	0.012
	Arizona, New Mexico	1	1	0	0.059	0.024
	Arkansas, Oklahoma	1	0	1	0.031	0.037
	California, Northern	0	1	0	0.053	0.027
	California, Southern	0	1	1	0.064	0.032
	Colorado, Wyoming	1	1	1	0.043	0.041
	Florida	0	1	0	0.061	0.023
	Georgia, Virginia, West Virginia, South Carolina, Maryland	0	1	0	0.033	0.021
	Idaho, Montana, Nevada, Utah	1	1	0	0.037	0.025
	Illinois	1	0	0	0.021	0.028
	Indiana	1	0	0	0.014	0.028
	Iowa, Nebraska, South Dakota	1	0	0	0.026	0.016
	Kansas	1	0	1	0.011	0.030
	Kentucky, Mississippi, Tennessee	1	0	1	0.013	0.032
	Michigan, Wisconsin	1	0	0	0.014	0.026
	Missouri	1	0	1	0.018	0.030
	New York, Maine	0	0	0	0.029	0.026
	Ohio	1	0	0	0.008	0.025
	Pennsylvania, Eastern	0	0	1	0.016	0.044
	Pennsylvania, Western	1	0	1	0.023	0.042
	Texas, Northern	1	1	1	0.054	0.046
	Texas, Southern	0	1	0	0.048	0.028

*

Panel B: Tests of significance of the differences in capacity quality across district groups, based on bootstrapped standard errors.

		From column 4. Average Plant Size.	From column 8. Percentage Dry Process.
				Significant			Significant
				difference			difference
				across			across
		Coastal	Landlocked	columns?	Coastal	Landlocked	columns?
	Demand Volatility	-25.80	86.55***	Yes**	0.05	0.1	No
		[34.12]	[36.33]		[0.05]	[0.2]

While possible to stock limited quantities of clinker from month to month, particularly during the winter when cold temperatures may prohibit construction activity, producers do not stock finished cement from year to year. From

to 2006 district-level cement stocks at year-end relative to annual production remained at around 7 to 8%, in high and low demand years. 2 According to their 2009 websites, Cemex operates in 79 plants (in 50 countries), Holcim 151 plants (in 70 countries, and Lafarge 166 plants (in 79 countries).3 It is quite difficult to obtain quantitative data on this subject. Multinationals use subsidiaries to make these long haul flows. The actual market share of the global players differs across countries, along with their involvement in the import/export flows. Multinationals' market share is typically higher in developed economies such as the US or in Europe than in emerging countries such as China or South America. Our framework is designed for countries where multinationals dominate production. See[START_REF] Salvo | Inferring Market Power under the Threat of Entry: The Case of the Brazilian Cement Industry[END_REF] for a discussion of the role of imports on domestic competition in Brazil.

We are grateful to Hendrik G. van Oss for advice on interpreting this data.

The district containing Alaska, Hawaii, Oregon, and Washington, the district containing Georgia, Virginia, West Virginia, South Carolina, Maryland, and the district containing Michigan and Wisconsin, sometimes appear in the minerals yearbook broken up into different groupings.

This list is not comprehensive. Annual statistics can be found in Table18of the Cement Yearbook.

Alabama has limited imports from the terminal at Mobile, although the largest cities in this district are located relatively far inland. Arizona imports cement from Mexico at Nogales, an inland border crossing. Nonetheless, all our results are robust to classifying both or each of these districts as coastal rather than landlocked. These results and the results from other alternative district classifications are available from the authors on request.

At different times over the course of the period studied here, various importers were subject to antidumping charges brought against them by the US government and antidumping duties were subsequently imposed. While this may have affected the relative cost of imports overall, the relative price difference between local production and imports remained much greater for landlocked than for coastal districts.

The statistics for the percentage of plants that are dry or wet process come from Table5of the USGS annual yearbook each year which details the technology in clinker plants only. The data on the total number of plants in each district used in the study are taken from Table3each year which details all white cement plants by district.

While regulation may play a role in capacity decisions, it is more likely to act as a very local constraint and unlikely to matter differently in landlocked and coastal districts. ,

[START_REF] Carruth | What do we know about Investment under Uncertainty?[END_REF] contain a discussion about the relative merits of different measures of uncertainty.Guiso and Pirigi (1999) is one of very few studies that uses survey data on manager's certainty about future demand as a measure of firm-level uncertainty.

This explains why in the model firms do not export from their domestic production capacity. As for exporting towards foreign markets, we note that US exports remain a very low percentage ofUS annual production -at around 1% between 2002 and 2006.

We measured the pairwise correlation coefficient in deviations from mean capacity over production for each pair of districts. Of the 253 correlation coefficients, the mean is 0.12 and only 95 of the coefficients are negative. We grouped the districts into 7 regions and found the average within each group. In only

research assistance. Jean-Pierre Ponssard's research on this project has been partly supported by the École Polytechnique Chair for Business Economics.


I Duursma
email: duursma@unilim.fr

P Gaudry
email: fgaudry@lix.polytechnique.fr

F Morain
email: moraing@lix.polytechnique.fr

Speeding up the discrete log computation on curves with automorphisms

We show how to speed up the discrete log computations on curves having automorphisms of large order, thus generalizing the attacks on anomalous binary elliptic curves. This includes the rst known attack on most of the hyperelliptic curves described in the literature.

Introduction

The use of elliptic curves in cryptography was rst suggested by Miller 28] and Koblitz 19], following the work of Lenstra on integer factorization 23]. Many people improved on these ideas and the domain is ourishing. (See for instance the many books on that topic, e.g. [START_REF] Koblitz | A course in number theory and cryptography[END_REF][START_REF] Menezes | Elliptic curve public key cryptosystems[END_REF].) Koblitz 20] was the rst to suggest using hyperelliptic curves for the same goal.

The security of many cryptosystems based on curves relies on the di culty of the discrete log problem. In some special cases, it was shown that this problem was rather easy 26], 11], 44], 38], 40]. Apart from new lifting ideas [START_REF] Silverman | The XEDNI calculus and the elliptic curve discrete logarithm problem[END_REF][START_REF] Kim | Elliptic logarithm over a nite eld and the lifting to Q[END_REF][START_REF] Cheon | Elliptic curve discrete logarithms and Wieferich primes[END_REF][START_REF] Chen | On the elliptic curve discrete logarithm problem[END_REF][START_REF] Jacobson | Analysis of the Xedni calculus attack[END_REF] that remain to be tested, it seems that the discrete log on elliptic curves still resists. On ordinary curves, the only known attack is a parallelized version of Pollard's rho method 50]. The Certicom challenge 1 records the state of the art in the eld.

Among the curves suggested for cryptographic use, the so-called Anomalous Binary Curves (ABC curves) have been shown to be somewhat less secure than ordinary curves, due to the existence of an automorphism of large order. Two types of attack have been suggested 52], 13]. The rst one can be seen as an additive rho method, the second one as a multiplicative method.

The purpose of this article is to point out that these attacks can be generalized to the case where there exists an automorphim on the curve (resp. on the Jacobian of an hyperelliptic curve). In particular, we show how to obtain a speedup of p m if there is an automorphism of order m.

The organization of the article is as follows. First of all, we recall Pollard's algorithm and its additive and multiplicative variants. Then, we describe the use of equivalence classes as originated in [START_REF] Wiener | Faster attacks on elliptic curve cryptosystems[END_REF][START_REF] Gallant | Improving the parallelized Pollard lambda search on binary anomalous curves[END_REF]. In particular, we show how to tackle the problem of useless cycles in the Wiener-Zuccherato approach, by analyzing the number of useless cycles and being able to throw them out. We then show how to use automorphisms of large order on (hyper)elliptic curves, including generalized ABC curves [START_REF] Uller | Fast multiplication on elliptic curves over small elds of characteristic two[END_REF][START_REF] Smart | Elliptic curve cryptosystems over small elds of odd characteristic[END_REF] and curves with CM by Z p 1] or Z (1 + p 3)=2], for which this appears to be the rst published attack. This method applies also to hyperelliptic curves that were presented by Koblitz and others. We support our approach by numerical simulations.

Parallel collision search

Let G be a nite abelian group with law written additively (and multiplication by k denoted by k]P) and P an element of order n of G (w.l.o.g. we will assume that n is prime using the Pohlig-Hellman approach 33]). Let Q be an element of < P >, the cyclic group generated by P. The discrete log problem refers to the search for s.t. Q = ]P . For instance, G can be the group of points of an elliptic curve over a nite eld, or the Jacobian of a hyperelliptic curve.

Generically, there exist three methods for computing discrete logs in time O( p n): Shanks's method 41], Pollard's rho and lambda methods 34], the last one being better when one has to nd the discrete logarithm in a reduced range (that is not over 0; n ). The rst method also uses O( p n) space, which is gen- erally a problem. After recalling Pollard's rho, we show how a parallel collision search method can be described in the same spirit.

Pollard's rho method

It is well known that if we collect approximately k random values from a set of cardinality n, then we will nd two equal values if k = p n=2 on average. To solve the memory problem, Pollard 34] suggested to iterate a random function f on the group < P >. Starting from a point R 0 2< P >, for instance R 0 = u 0 ]P v 0 ]Q with u 0 and v 0 random integers (modulo n), one computes

R i+1 = f(R i )
thereby obtaining two sequences (u i ) and (v i ) modulo n such that:

R i = u i ]P v i ]Q: &% '$ R0 R1 R2 R 1 R R +1 R + 1
Fig. 1. The rho shape of (Ri).

In order to understand the properties of this random sequence, one is led to study the functional graph of f, that is the graph built using all starting points R 2< P >, as shown in Figure 1.

Such a sequence consists in a tail of length and a cycle of length , thus forming a rho of size = + . Asymptotic values for the critical parameters of this graph are given in 10]. For instance, a graph with n vertices should have 0:5 log n (connected) components, the average tail (resp. cycle) length should be p n=8, thus giving a rho length of about p n=2.

These results imply that after about p n=2 iterations, we will nd a collision, that is two integers i and j for which R i = R j . This will give an identity u i u j ]P v i v j ]Q = 0 from which we can deduce if v i 6 v j mod n, which happens with probability 1 1=n: Indeed, each element R of < P > has n di erent representations as u]P v]Q and the values v i and v j are supposed to be random integers in 0; n 1].

Using distinguished points

An e cient implementation of parallel collision search requires storing a limited number of points that have a distinguished property (this idea was used for the rst time in 35]). If is the proportion of distinguished points, then we should nd a collision after computing about p n=2 points, or p n=2 distinguished points. Now, parallelization is straightforward: have each processor contribute to the same list of distinguished points 50]. Each processor would have to nd p n=2=M points, thus yielding a speedup of M to the total running time.

To understand how a parallelized search works, consider gure 2, on which we have drawn two paths, the one corresponding to processor i and the second to processor j. Their paths collide at point C, which lies between the distinguished points D 1 and D 3 (resp. D 2 and D 3 ). The collision will be discovered as soon as we nd that R = D 3 .

Such a random walk has a very important feature: it is deterministic, which An additive random walk. One way of choosing a good random function consists in precomputing r random points (T (j) ) 0 j<r in < P >, with T (j) = u (j) ]P v (j) ]Q and to de ne the random walk as f(R) = R T (j) where j = H(R) with H a hash function sending < P > to f0; 1; : : :; r 1g. This creates an additive random walk in Z=nZ since each point R i can be written as R i = u i ]P v i ]Q for which u i+1 u i + u (j) mod n; v i+1 v i + v (j) mod n:

means that if f(R) = C, then f(f(R)) = f(C),
Satler and Schnorr 39] have shown that the above approach is su ciently random if r 8. Teske has found experimentally 49] that a value of r 20 is more convenient.

A multiplicative random walk. One can also use a function f built with xed multipliers ( j ) 0 j<r , j de ned modulo n. We de ne: f(R) = j ]R where j = H(R) as above. In this version, we would in fact compute:

f(R) = 2 4 r 1 Y j=0 fj j 3 5 R 0 :
A collision with a single sequence would not be interesting since this would lead to ( Q j fj j ) 1 mod n. A collision is interesting if it comes from two distinct sequences: two initial values R 0 = u 0 ]P v 0 ]Q and R 0 0 = u 0 0 ]P v 0 0 ]Q would lead to a more useful Q j fj j ]( u 0 ]P v 0 ]Q) = u 0 0 ]P v 0 0 ]Q. For this to be random enough, we must have r large as above. To be e cient, the method requires that the multiples be e ciently computed.

Mixed walks. In practice, it would be fruitful to mix both strategies. This would lead to a walk that is di cult to analyze in theory but which is likely to be \more random".

Let be an equivalence relation on < P > for which there are n=m equivalence classes. We note R for the equivalence class of R. If we can iterate Pollard's rho on the set of equivalence classes < P > = , then we should nd a collision in time p n=(2m) instead of p n=2.

The easiest way of building an equivalence class is by using automorphisms of the group G. Wiener and Zuccherato 52] considered the case where G is the set of points of an elliptic curve E de ned over a nite eld K . In that case, the equivalence relation would be S T if and only if T = S. The rst known nontrivial example of such a phenomenon came from ABC curves 52, 13] (see section 3.3 below).

More generally, if we know an automorphism of order m operating on G, we can use the equivalence relation:

S T () 9i; S = i ]T and hope to get a speedup of p m. We will give new examples in the following section.

From now on, we suppose our equivalence class is built on an automorphism of order m. For the method to work e ciently, the equivalence class of a point should be easy to compute, that is much faster than an addition in G.

Well de ned mappings

The rst thing we can think of is to iterate f as usual, but perform the matches on the equivalence classes only. Starting from a random point R in < P >, we iterate R = f(R); if R = R j for some j, try to nd a match and stop, otherwise, store R. This looks ne, as long as we do not want to parallelize the algorithm. In that case, we can come across the diagram of gure 3 which shows that the random walk would no longer be deterministic. For instance, imagine that we are again in the case of elliptic curves with an additive walk and that: R i+1 = R i + T (k) = (x; y); S j+1 = S j + T (`) = (x; y):

H H H H H H H H H H H

In that case S j+1 = R i+1 , but in general f(S j+1 ) 6 = f(R i+1 ). Therefore, we must nd a function f de ned over < P > and that is well de ned over the equivalence classes. More precisely, we want that if R 0 2 R, then f(R 0 ) = f(R). The most obvious approach is to use R i+1 = f(R i ) and we iterate R = f(R) until a collision is found.

Useless cycles for additive walks

Let us explain why useless cycles appear. Suppose that G is the set E(K) of points on an elliptic curve E over the nite eld K = F p n . Suppose we use a function f as in section 2.3. Assume that the representative of a class is the point (x; y) with least y. Then we could encounter a situation where starting from R i ,

we nd R i+1 = R i T (j) = R i T (j) : It could happen that R i+2 = R i+1 T (j) (the same j), thus yielding R i+2 = R i T (j) T (j) = R i :
This proves the existence of useless 2-cycles.

We x some notations for studying these cycles. We consider a (primitive)

t-cycle consisting of points R 1 ; R 2 ; : : : ; R t ; R t+1 = R 1 . We denote by j k the value H(R k ) of the hash function and we denote by " k = e k the automorphism which gives the representative of the equivalence class of R k T (j k ) . Thus we have R k+1 = " k ](R k T (j k ) ). See gure 4 for a description of the cycle.

R2

R1 Rt 1 Rt ? 6

j1 "1 jt 1 "t 1 jt "t Fig. 4. A typical useless t-cycle.

We can now derive an expression of R t+1 in terms of R 1 and our parameters j k and " k :

1=" t ]R t+1 = " t 1 " 1 ]R 1 with = " t 1 " 1 ]T (j1) " t 1 " 2 ]T (j2) " t 1 ]T (jt 1) T (jt) . We have a useless t-cycle if = 0. Indeed, when " 1 ; : : : ; " t 1 and j 1 ; : : : ; j t are chosen such that = 0, then R t+1 is in the class of R 1 , which does not impose any restriction on " t . The fact that the T (j) are randomly chosen implies that (very likely) there is no simple relation between them 2 . In that case, a necessary condition for having = 0 is that for all k 2 f1; 2; : : :; tg there exists a l 6 = k such that j k = j l . Now, we can summarize the following results on the expected number of useless t-cycles.

Proposition 31 Suppose there is an automorphism of order m acting on a group G with n elements and that the T (j) are not related by relations involving powers of . We can estimate the probability P(t) of useless t-cycles for small t when iterating an additive function with r branches (the expected number of t-cycles being P(t)(n=m=t)).

We have P(t) min(r;t=2) X k=1 1 m k min 1; r!k t (r k)!r t : Moreover, for small values of t we have the following bounds:

t pattern P(t) 2 j 1 = j 2 1=(mr) 3 2=(mr) 2 3 j m 0 3 -m 4 j 1 = j 2 = j 3 = j 4 (1 1=m) 2 =(mr 3 ) j 1 = j 3 ; j 2 = j 4 (1 1=r)=(mr) 2
The proof of this proposition is given as an appendix. This proposition shows that when t and r are large enough, the probability to nd a t-cycle is very small, and we likely do not encounter one.

Taking care of useless cycles. Using Proposition 31, it is clear that an easy way of solving the problem is to force a large value of r, which is not really a problem in practice. In the rare cases where a cycle appears, we can get out of it by collapsing it as suggested in 13]. If the cycle is R 1 7 ! R 2 7 ! 7 ! R t , we want to get out of it in a symmetric way, that is reach the same point, whichever R i was the point at which we entered the cycle. Our version is to sort the points R i to obtain S 1 , S 2 , : : :, S t and start again, say, from R = L t i=1 i i +1]S i . Anything that breaks linearity would be convenient. From a practical point of view, we count the number of distinguished points we obtain along the path. If this number does not evolve as prescribed by the theory, that is 1 among 1= points, then we decide to inspect the cycle and check out if it comes from a useless one or not. The more frequent case of 2-cycles can be handled with a look-ahead technique (see 52]) that is somewhat simpler.

A multiplicative random walk

Let us explain the situation for ABC curves 22]. In this case, K = F 2 `and E is de ned over F 2 . Then : (x; y) 7 ! (x 2 ; y 2 ) is an automorphism of order `. If `is odd 3 , the equivalence relation is: S T () 9i; S = i ]T with m = 2c lasses. This relation has been exploited in 13] and 52] as well as in real life computations by R. Harley (see http://www.certicom.com/chal/).

Gallant et al. have suggested to use a multiplicative random walk with a function f de ned by f(R) = R ]R, where R is a multiplier depending on the class of R. This walk is well de ned, since f commutes with :

f(R 0 ) = R 0 ]R 0 = R ]R 0 = R ]( i ]R) = i ]( R ]R) 2 f(R):
In order to make the method e cient, the multiples must be computed very quickly. In that case, R is taken to be 1 + H(R) where H is a hash-function sending the equivalence classes to f0; 1; : : :; m 1g. As noted in section 2.3, the number of such multipliers should be large. For the CM examples given below this will prove not to be the case.

Finding new examples

Our idea is to nd new examples of curves with non-trivial automorphisms. We will concentrate on algebraic curves de ned over nite elds of characteristic p.

We will rst summarize the results concerning the number of automorphisms of (the Jacobian of) a curve.

Theoretical results

For g = 1, we know that we can obtain automorphisms of order 4 or 6 for some CM curves (details for both cases follow in Section 4.2) and powers of the Frobenius for ABC curves 22].

We obtain examples for g > 1 by considering CM hyperelliptic curves and curves de ned over nite elds xed by powers of the Frobenius, as well as curves de ned over Q having non-trivial automorphisms.

For genus g > 1, we need a priori distinguish between automorphisms of a curve and automorphisms of its Jacobian. Automorphisms of a curve naturally de ne automorphisms on its Jacobian. By Torelli's theorem 29], all automorphisms of the Jacobian (for a xed projective embedding and a chosen zero element) arise in this way (except for multiplication by minus one on the Jacobian of non-hyperelliptic curves). And we may identify the automorphisms of a curve and those of its Jacobian.

If g > 1, the number of geometric automorphisms (not considering powers of the Frobenius) does not exceed 84(g 1) provided that p > g + 1, with the exception of the curve y 2 = x p x (see 36]). Without the restriction p > g+1, the upper bound becomes 16g 4 , with again a single explicit exception: y q y = x q+1 or a quotient thereof, for q a power of p (see 48]). Under the assumption that the Jacobian has maximal p-rank g, the upper bound 84g(g 1) holds 32].

The exceptions are of no interest to us as the Jacobians of these curves contain no large cyclic components. To some extent this occurs more generally for curves with many automorphisms. Automorphisms induce invariant subgroups in the Jacobian. When these subgroups are non-trivial for many di erent automorphisms, the Jacobian does not admit cyclic components of large prime order. For such a large component would itself have invariant subgroups. It follows that the selection of curves with automorphisms suitable for cryptosystems requires some care. For the decomposition of a Jacobian with given automorphism group, see [START_REF] Accola | Two theorems on Riemann surfaces with noncyclic automorphism groups[END_REF][START_REF] Kani | Idempotent relations and factors of Jacobians[END_REF].

Examples of curves with automorphisms that have large cyclic components in their Jacobian are the curves y 2 = x p x + 1 in odd characteristic p 9].

The automorphism x 7 ! x + 1 of prime order p induces as invariant subgroup the trivial group and the Jacobian itself is often of prime order. Other examples are described in Section 4.3. In this paper we will always consider that the automorphism on the Jacobian can be restricted to an automorphism of the cyclic subgroup we are working in. This will be the case for all practical examples where the group is almost prime. Indeed, assume that we are dealing with a cyclic subgroup of prime cardinality n generated by P. Then n 2 does not divide the cardinality of the whole group, and the only elements of order n in the group are precisely those which constitute the subgroup < P >. Then the image of P by the automorphism is a of order n, and is in < P >, and the subgroup is stable under the action of the automorphism.

New examples with elliptic curves

We can nd the proofs for what follows in 42, Chapter 2]. It is well known that the only elliptic curves having non-trivial automorphisms (over Q ) have CM by

Z i] (resp. Z ]) where i 2 = 1 (resp. 3 = 1). They are: E a;0 : Y 2 = X 3 + aX for a 6 = 0 and E 0;b : Y 2 = X 3 + b with b 6 = 0. On E a;0 , multiplication by i is an automorphism sending a point (x; y) to ( x; iy); on E 0;b , sends (x; y) to ( x; y).

Over Q , this is all the story, an elliptic curve having in general automorphism group f 1g. Over nite elds, Frobenius automorphisms enter the game as seen with ABC curves. It is easy to see how to generalize the automorphism attack to curves suggested by M uller 30] and Smart 45].

The reductions of the curves E a;0 and E 0;b are supersingular for p = 2; 3, so that we will consider them interesting only in the case p > 3. For the sake of simplicity, we suppose that K = F p , p odd prime > 3.

The case E a;0 . We suppose that a 6 0 mod p and p 1 mod 4 (if p 3 mod 4, then E a;0 is supersingular and the MOV reduction applies 26]). Again, we suppose that we are looking for a discrete log on the group < P > with prime order n. Let I 2 p 1 mod p and I 2 n = 1 mod n such that I n ](x; y) = ( x; I p y) (this is possible since p and n are 1 mod 4 by the theory of reduction of CM curves). Then the automorphism is (x; y) = I n ](x; y) and the class of R = (x; y) consists of f(x; y); ( x; I p y); (x; y); ( x; I p y)g. We decide that R is the point with minimal ordinate in absolute value.

The \obvious" choice would be to use a generalization of the ABC approach and use R = 1 + H(R) where H sends the classes to f0; 1; 2; 3g. However, this does not work, due to the fact that 2 = 1 and (1 + )(1 ) = 2. A random walk would compute multiples of the form (1 + ) u (1 ) v which is not random enough (compare with 39]). Using other multiples would be too costly. So, we must use the additive random walk, with the modi cations described in the preceding section. This gives us a speed up of p 4 = 2. In the case of F p (`odd), we can use the Frobenius (x; y) 7 ! (x p ; y p ) to obtain a speedup of p 4`.

The case E 0;b . We suppose b 6 0 mod p and p 1 mod 3 (the case p 2 mod 3 yields a supersingular curve). We let p (resp. n ) denote a primitive third root of unity modulo p (resp. modulo n) such that n ](x; y) = ( p x; y). The automorphism is (x; y) = n ](x; y) and the class of R = (x; y) consists of f(x; y); ( p x; y); ( 2 p x; y)g. We take the representative with smallest x and smallest y.

Here again, the multiplicative choice using multipliers of the form (1 + i ) is disastrous due to the fact that 1 + 2 = and 1 + = 2 and we come back to the additive version, thus yielding a speedup of p 6 and more generally p 6ò ver F p `, `odd.

Examples of hyperelliptic curves

We will consider curves of equation Y 2 = F(X) = X 2g+1 + when p > 2 (resp. Y 2 + H(X)Y = F(X) = X 2g+1 + for p = 2) where g > 1 is the genus of the curve. There is no group law on the curve, but there is one on its Jacobian, noted Jac(C). The only result we need says that every element of Jac(C) can be uniquely represented by a so-called reduced divisor with at most g points. For more precise statements about those things, one can refer to Mumford 31]. [START_REF] Cantor | Computing in the Jacobian of an hyperelliptic curve[END_REF] (see also 20]), Cantor gives an algorithm for computing with the reduced divisors: we can add them in polynomial time. We do not recall his method here, but we give the representation of a reduced divisor: it is a pair of polynomials u(z); v(z)], where u is monic of degree at most g and greater than the degree of v. The opposite of such a reduced divisor (for the Jacobian group law) is just the divisor represented by u(z

); v(z)]. The hyperelliptic involution is u(z); v(z)] 7 ! u(z); v(z)].
From a practical point of view, it is not as easy to compute the cardinality of a Jacobian over nite elds as it is for elliptic curves using the so-called SEA algorithm [START_REF] Lercier | Counting the number of points on elliptic curves over nite elds: strategies and performances[END_REF][START_REF] Lercier | Finding good random elliptic curves for cryptosystems de ned over F2n[END_REF]. So various researchers have suggested some special form of curves for which this computation is easy 21], 9], 5], 46], 37], 3].

Automorphisms. We suppose is an automorphism on the curve of the form : (x; y) 7 ! ( 1 (x); 2 (y)). We restrict ourself to the study of two classes of automorphisms: in case 1, the coordinate-functions 1 and 2 are identical and are also automorphisms (a typical example is the Frobenius action), and in case 2, 1 and 2 are multiplication maps in the nite eld (this occurs for CM curves).

In both cases the automorphism can be extended to the Jacobian of the curve, and we still denote the extended automorphism. With the polynomial representation of reduced divisors, we can derive simple expressions for the action of : for h g, we have

:

z h + u h 1 z h 1 + + u 0 ; v h 1 z h 1 + + v 0 ] 7 ! z h + 1 (u h 1 )z h 1 + + 1 (u 0 ); 1 (v h 1 )z h 1 + + 1 (v 0 )]
for case 1, and

: z h + u h 1 z h 1 + + u 0 ; v h 1 z h 1 + + v 0 ] 7 ! z h + 1 u h 1 z h 1 + + h 1 u 0 ; 2 (h 1) 1 v h 1 z h 1 + + 2 v 0 ]
for case 2. Thus, provided that the computation of the action of 1 and 2 is easy we can obtain the image of a divisor quite quickly.

Examples. In the literature we nd many examples of hyperelliptic curves which come with an automorphism. Some of them are obvious (such as Frobenius endomorphism), but some others were probably not known to the authors (see the curve of Sakai and Sakurai 37]). We summarize in table 1 some examples for which we give the non-trivial automorphisms, and the order m that we obtain when combining them together with the hyperelliptic involution.

Author

Equation of curve Field Automorphisms Frobenius & 4 29 X 9 + X 5 + 1 (y) 8 < :

m Koblitz 20], 21] Y 2 + Y = X 5 + X 3 ( ) F 2 n Frob + X 7 ! X + 1 Y 7 ! Y + X 2 4n Y 2 + Y = X 5 + X 3 + X ( ) F 2 n Frobenius 2n Y 2 + Y = X 2g+1 + X F 2 n Frobenius 2n Y 2 + Y = X 2g+1
X 7 ! X + 1 Y 7 ! Y + X 6 + X 5 + X 4 + X 3 + X 2 Duursma & Y 2 = X p X + 1 (y) F p n Frobenius & 2np Sakurai 9] (X; Y ) 7 ! (X + 1; Y ) Table 1. Examples of curves
The curves marked by ( ) can be broken by the reduction method of 11] which is much faster than the method, even with the use of automorphisms.

For high genus curves in the examples marked by (y), a faster attack is given by the index-calculus method of 2].

For each curve in the table, we can improve the parallel collision search by a factor p m. For example, if one wants to break the cryptosystem proposed by Sakai and Sakurai, which uses a divisor of prime order around 2 171 , we have to perform about 2 86 operations on the Jacobian, and using the Frobenius, the involution and the new automorphism, we have only to perform about 2 82 operations. Note that the authors took into account the use of Frobenius in their evaluation of the security, but not the other automorphism (however it still does not break the system).

The curve Y 2 = X 5 1 and generalizations. The Jacobian of the curve Y 2 = X 5 1 admits complex multiplication by the eld Q ( 5 ) where 5 is a 5-th root of unity. Combining it with the hyperelliptic involution, we obtain an automorphism of order 10. The formulae for the action on reduced divisors are:

: z 2 + u 1 z + u 0 ; v 1 z + v 0 ] 7 ! z 2 + 5 u 1 z + 2 5 u 0 ; 1 5 v 1 z v 0 ] z + u 0 ; v 0 ] 7 ! z + 5 u 0 ; v 0 ] 0 7 ! 0:
This case may be generalized to the curves of equations Y 2 = X 2g+1 1 (or Y 2 + Y = X 2g+1 as suggested in 3]), which admit complex multiplication by the ring of integers of Q ( 2g+1 ), providing an automorphism of order 2g +1 (and even 4g + 2 combined with the trivial involution).

In this case, we could also dream of using a multiplicative random walk with multipliers 1 + i . However, we have to be careful, due to the many algebraic relations between 5-th roots of unity. Apart from 1 + 2 3 + 4 = 0, we have among others 1 + 5 = 0, (1 + 2 )(1 + 4 ) = 3 , (1 + 4 )(1 + 8 ) = , (1+ 6 )(1+ 8 ) = 2 , (1+ 3 )(1+ 8 ) = 1+ , etc. If during the random walk we do a couple of consecutive steps corresponding to one of these relations, then we obtain a cycle of length 2 which is useless. So, we come back to the additive one to get our speedup of p 10.

Numerical experimentations

In order to validate our ndings, we made several experiments on random graphs of reasonable size as well as some real discrete log computations on small examples. The hash function used was H((x; y)) = y mod r in each case. All examples were done using the computer algebra system MAGMA.

Elliptic examples

We built functional graphs for the case of E : Y 2 = X 3 + 2X over K = F 1000037 . We chose P = (301864; 331917) of prime order n = 500153. We made two series of experiments on 50 random mappings with r branches. The following table contains the number of useless t-cycles found: r #2 cycles #4 cycles 20 772(781) 5(5) 1000 16( 15) 0(0) These values are close to those prescribed by Proposition 31 that are given in parentheses.

We did the same for the curve E : Y 2 = X 3 + 2 over K = F 1000381 on which P = (1; 696906) is a point of prime order n = 998839. Again we tried 50 random walks. r #2 cycles #4 cycles #3 cycles 20 694(693) 7( 7) 2(3) 1000 13( 14) 0(0) 0(0) We also did 100 real discrete log computations for the curves given below. We give the average gain obtained, that is the ratio p n=2 divided by the number of distinguished points computed. For E : Y 2 = X 3 + 2X over F 10000003021 with P = (9166669436; 170163551) of prime order n = 5000068261, Q = (1314815213; 7654067643) (with = 2153613198), we got a speed up of 1:88 for r = 20 (resp. 1:82 for r = 1000) and for E : Y 2 = X 3 + 2 over F 10000000963 , P = (2; 5825971627), n = 9999804109, Q = (4; 6715313768) (thus = 8959085671), we got 2:23 for r = 1000.

Hyperelliptic examples

We built the functional graphs of 50 random mappings for the Jacobian of the curve Y 2 = X 5 1 over K = F 31 3, which has a divisor of prime order n = 778201.

We found 201 components on average, with 196 2-cycles and 0.8 4-cycles, which is closed to the expected theoretical values (194 and 0.7). We did the same for the rst example given by Koblitz in 20]: the curve is Y 2 + Y = X 5 + X 3 + X over K = F 2 11 , with a divisor of order n = 599479. We tried 50 di erent pseudo-random walks obtaining on average 31:5 2-cycles (the theory predicts 30:9), and almost no 4-cycles (0:07 expected). With the modi ed walk, we have 5:6 components on average (5:1 for pure random walk). We also did some experiments of discrete log computations. For each of the curves, we did 1000 tests, the r parameter was xed to 50. The rst curve was Y 2 = X 5 1 over F 31 7 , with a divisor of order n = 1440181261. We got an average gain of 3:13 for the number of iterations (to be compared with p 10 3:16). The second test was done for the curve Y 2 + Y = X 5 + X 3 + X over F 2 37 , with a divisor of order n = 319020217. The average gain obtained was 8:83 (theory says p 74 8:60).

Conclusions

We have described a general framework speeding up discrete logarithm computations on curves with large automorphism groups, including in particular some elliptic and hyperelliptic curves with complex multiplication. One could raise the question to nd curves having automorphisms which are not of Frobenius or CM type. Note that for high genus hyperelliptic curves, we can speed up the Adleman{ DeMarrais{Huang discrete log algorithm 2] using all these automorphisms (see 14]). This suggests that the use of such curves in cryptosystems requires great care.

For the genus > 2, most of the curves in the literature for which the cardinality of the Jacobian can be computed have a non-trivial automorphism. It would be interesting to build new curves having no automorphisms. For genus 2, examples are given by the CM construction of Spallek 46], see also 51]. See also [START_REF] Stein | Catching kangaroos in function elds[END_REF] for some examples of high genus random curves and 12] for superelliptic curves.

A. [START_REF] Cantor | Computing in the Jacobian of an hyperelliptic curve[END_REF] The case of t-cycles For a t-cycle, we rewrite the cancellation of as a system of k equations, one for each j i which actually occurs. We evaluate the probability of ( = 0) for every value of k, and then collect the results. Note that k has to be at most t=2, because there has to be at least two terms in each equation, and of course k is at most r. Now let S be the set of the j i which actually occur in . Then Pr( = 0) = min(r;t=2) X k=1 Pr( = 0 j #S = k):Pr(#S = k):

First step: Pr(#S = k) min( r!k t (r k)!r t ; 1). This problem can be expressed as follows: what is the probability to get exactly k distinct elements, when one takes randomly t elements in a set of r elements (we put the element back in the set after each step). This probability is classically (see 8]) r k S 2 (t; k)=r t , where S 2 (t; k) is the Stirling number of the second kind. Then we bound S 2 (t; k) by k!k t , and obtain the formula.

Second step: Pr( = 0 j #S = k).

Let us make the change of variables 8 > > > < > > > : " 1 = " t 1 " 1 " 2 = " t 1 " 2 . . . This transformation is invertible since the " i are invertible. The expression for becomes = " t 1 " 1 ]T (j1) T (jt) = " 1 ]T (j1) " t 1 ]T (jt 1) T (jt) = L k l=1 E l ]T (ji l ) , where the E l are linear expressions in the " i . When the " i are randomly chosen among m values, for each l the probability that E l is veri ed is bounded by 1=m. Thus the probability to have a good (t 1)-uple of " i is bounded by 1=m k , and the result follows.

Note that we used the fact that we have a true t-cycle, because we supposed that the " i were randomly chosen, which is not the case if for example we have a 2-cycle (" 2 has an imposed value in that case).

Fig. 3 .

 3 Fig. 3. Paths that cross each other.

" t 1 = " t 1

 11

If there is one, then we have found the discrete log!

If `is even, we obtain a relation with `classes only.

This is always the case for an automorphism of a cyclic group.

Acknowledgments. We are grateful to Projet CODES at INRIA, and particularly Daniel Augot, for having given the authors the opportunity to meet and work together. We also to thank E. Thom e for helpful discussions concerning this work, as well as R. Harley for his careful reading of an intermediate version of the article. Also, we are very happy to receive constructive reports from the referees, a phenomemon which is so rare that we want to emphasize it.

? On leave from the French Department of Defense, D el egation G en erale pour l'Armement. ?? This work was supported by Action COURBES of INRIA (action coop erative de la direction scienti que de l'INRIA). 1 See http://www.certicom.com/chal/.

A Proof of Proposition 31

Remember that is an automorphism of order m and that we use an additive function with r branches.

A.1 2-cycles

How many useless 2-cycles do we expect? We rst evaluate the probability for a random point R 1 to be in a useless 2-cycle. Let R 2 be the point computed by the pseudo-random walk, and j 1 = H(R 1 ). We have R 2 = R 1 T (j1) . The useless cycle can be produced when the class of R 1 T (j1) is R 1 T (j1) , which occurs with probability 1=m. If this rst condition is satis ed, the cycle is produced when H(R 2 ) equals j 1 , which occurs with probability 1=r. Finally, the probability for a point to be in a useless 2-cycle is 1=(rm).

A.2 3-cycles

For 3-cycles, the expression of is = " 1 " 2 R 1 + " 1 " 2 ]T (j1) " 2 ]T (j2) T (j3) : The condition on the j k 's implies that j 1 = j 2 = j 3 . Then = 0 = " 1 " 2 + " 2 + 1]T (j1) , and we have " 2 (1 + " 1 ) = 1. We study "true" 3-cycles, so we do not want R 3 = R 1 , so we can suppose " 1 6 = 1. Then " 2 = 1=(1 + " 1 ).

If we suppose that the automorphism is a root of unity 4 , the last equation gives j1 + " 1 j = j" 1 j = 1, and then " 1 is a third root of unity. Thus, if the order m of is not a multiple of 3, we cannot have a useless 3-cycle; otherwise we can give an upper bound for the probability for a point to be in a useless 3-cycle by 2=(mr) 2 (" 1 can take 2 values, and then " 2 is unique).

A.3 4-cycles

We have three di erent patterns for the j k 's.

First case: j 1 = j 2 = j 3 = j 4 . Then we have = " 1 " 2 " 3 + " 2 " 3 + " 3 + 1]T (j1) , and we have a cycle if

The properties " 1 6 = 1 and " 2 6 = 1=(1 + " 1 ) are necessary to have a true 4cycle, and guarantee that the expression makes sense. However, for some values of " 1 and " 2 , there is no " 3 satisfying this equation. For example, if 4 = 1, then the only triples of solutions are (" 1 ; " 2 ; " 3 ) = ( ; ; ) or ( ; ; ).

We can bound the probability of a 4-cycle with this pattern. The probability that the j k 's are equal is 1=r 3 ; the probability that " 1 6 = 1 is 1 1=m, the probability that " 2 6 = 1 and " 2 6 = 1=(1 + " 1 ) is bounded by (1 1=m), and nally we have at most one choice for " 3 , i.e. probability 1=m. Finally, the probability for a point to belong to such a 4-cycle is less than (1 1=m) 2 =mr 3 .

Second case: j 1 = j 2 and j 3 = j 4 . We want to have a true 4-cycle, so R 1 6 = R 3 , which implies that " 1 6 = 1. In that case, the equation = 0 becomes " 2 " 3 (1 + " 1 )]T (j1) 1 + " 3 ]T (j3) = 0; with T (j1) 6 = T (j3) , so this equation has no solution with " 1 6 = 1 if the points T (j) are su ciently randomly chosen. Hence such a pattern cannot occur with signi cant probability.

The same result holds for the case: j 1 = j 4 and j 2 = j 3 . Third case: j 1 = j 3 and j 2 = j 4 . In that case, the equation = 0 becomes " 3 (" 1 " 2 + 1)]T (j1) " 2 " 3 + 1]T (j2) = 0; which reduces to the system " 1 " 2 = 1; " 2 " 3 = 1; or " 3 = " 1 = 1=" 2 . If we assume that the automorphism is a root of unity, then for any given " 1 , there is a unique solution of the system for " 2 and " 3 .

The probability that j 1 = j 3 is 1=r, idem for j 2 = j 3 , and moreover we impose j 1 6 = j 2 , which occurs with probability (1 1=r); the probability of nding the good values for " 2 and " 3 is 1=m 2 . Finally the probability for a point to belong in a 4-cycle with such a pattern is (1 1=r)=(rm) 2 ; Putting together these results, we can bound the probability for a point to be in a useless 4-cycle by (1 1=r)=(rm) 2 + (1 1=m) 2 =mr 3 .