Adela Barbulescu

Rémi Ronfard

Gérard Bailly

Georges Gagneré

Hüseyin Cakmak

Beyond Basic Emotions: Expressive Virtual Actors with Social Attitudes

Keywords: audio-visual prosody, head motion, social attitudes

The purpose of this work is to evaluate the contribution of audiovisual prosody to the perception of complex mental states of virtual actors. We propose that global audio-visual prosodic contours -i.e. melody, rhythm and head movements over the utterance -constitute discriminant features for both the generation and recognition of social attitudes. The hypothesis is tested on an acted corpus of social attitudes in virtual actors and evaluation is done using objective measures and perceptual tests.

Introduction

This study represents preliminary work towards expressive audiovisual speaker conversion. Given a context in which speaker A creates a performance in an affective state X, we want to develop approaches to convert it to an expressive performance of speaker B, realised in affective state Y. While in previous work [START_REF] Barbulescu | Audio-visual speaker conversion using prosody features[END_REF] we have studied the conversion between speakers A and B, this paper approaches the problem of expressivity conversion and investigates the contribution of different prosodic parameters in expressive generation and recognition.

The term of prosody was initially introduced to denominate a general set of functions that convey the style in which speech is presented, such as intonation, rhythm or stress. As the combination between acoustic and visual cues has been shown to improve the perception of speech [START_REF] Summerfield | Lipreading and audio-visual speech perception[END_REF]], the term was generalized to include visual information. Therefore the concept of audio-visual prosody [START_REF] Krahmer | Audiovisual prosodyintroduction to the special issue[END_REF] refers to the use of multimodal cues for signaling and perceiving linguistic, paralinguistic and non linguistic functions in social communication.

The proper generation of expressive audio-visual prosody is an important factor in the perception of expressive speech animations. This topic is situated at the crossroads between computer graphics, vision and speech research areas, and it has received a considerable amount of interest as animated characters are now indispensable components of computer games, movies as well as smart humancomputer interfaces.

In a majority of research papers [START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions. Pattern Analysis and Machine Intelligence[END_REF], expressivity is defined in terms of limited sets of categorical emotional states or using multi-dimensional emotional models such as the well-known Pleasure-Arousal-Dominance model (PAD). However, an expressive speech is expected to encode complex mental states, which usually go beyond the basic set of emotional states [START_REF] Ekman | An argument for basic emotions[END_REF]]. Scherer proposes that affective expression in speech communications happens either involuntarily (expression of emotion) or voluntarily (expression of attitude) [START_REF] Scherer | Multimodal expression of emotion: Affect programs or componential appraisal patterns?[END_REF]. Similar proposals have been done in the domain of intonation; Bolinger notably states: "Intonation [is] a nonarbitrary, sound-symbolic system with intimate ties to facial expression and bodily gesture, and conveying, underneath it all, emotions and attitudes... [it is] primarily a symptom of how we feel about what we say, or how we feel when we say" [START_REF] Bolinger | Intonation and its uses: Melody in grammar and discourse[END_REF]]. Social attitudes (example: comforting, doubtful, ironic etc) directly concern carrier speech acts. These attitudes are highly conventionalized -entirely part of the language and the speech communication system -and socio-culturally built. If the production and evaluation of emotional content is highly dynamical, we will also show that social attitudes are also encoded into signals via complex dynamical multimodal patterns.

For this study, we choose a discrete set of social attitudes to high-light interactive dimensions of face-to-face communication in realistic social contexts. Related work on perception and production of audio-visual prosody [START_REF] De Moraes | Multimodal perception and production of attitudinal meaning in brazilian portuguese[END_REF][START_REF] Rilliard | Perception of french audio-visual prosodic attitudes[END_REF]] has been carried with the goal of explaining the contribution of each modality for attitude recognition. Besides analyzing the influence of each modality, we study the contribution of specific prosodic parameters by objective measurements and analyze the correlation between these objective metrics and perceptual tests.

Most of the existing approaches to acoustic affect recognition and generation use spectral (MFCC, cepstral features) and prosodic features (related to pitch, energy, speech rate). Among these, pitch and energy are most used in affect recognition systems [START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions. Pattern Analysis and Machine Intelligence[END_REF]. Statistical models based on durations and F0 contours are used in neutral to expressive speech conversion [Tao et al. 2006] [Inanoglu and[START_REF] Inanoglu | A system for transforming the emotion in speech: combining data-driven conversion techniques for prosody and voice quality[END_REF]. The global statistical patterns of pitch are studied in [START_REF] Vroomen | Duration and intonation in emotional speech[END_REF] proving that affective states can be expressed accurately by manipulating pitch and duration in a rule-based way. Rule-based generation of animated dialog is also studied in [START_REF] Cassell | Animated conversation: Rule-based generation of facial expression, gesture & spoken intonation for multiple conversational agents[END_REF]]. Recent studies have shown that specific visual cues such as head and eyebrow movements are correlated with pitch contours [START_REF] Yehia | Facial animation and head motion driven by speech acoustics[END_REF]]. This correlation is exploited in [START_REF] Busso | Rigid head motion in expressive speech animation: Analysis and synthesis. Audio, Speech, and Language Processing[END_REF]], [START_REF] Chuang | Mood swings: expressive speech animation[END_REF] and [START_REF] Ben Youssef | Articulatory features for speech-driven head motion synthesis[END_REF] to synthesize head motion for expressive speech animation.

Our work is preliminary to prosody generation as we first want to quantify the importance of the proposed prosodic parameters: melody, rhythm and head movement. We focus on a theoretical framework which proposes the size of the utterance as a dependent factor.

The paper is structured as follows. Section 2 describes our experimental setup, based on the paradigm of "exercises in style" [Queneau 2013] [ [START_REF] Madden | 99 ways to tell a story: exercises in style[END_REF]]. Section 3 summarizes the methods we used to add expressive contents to neutral audio-visual performances. Subjective evaluations of the performances are presented in Section 4. Section 5 presents experimental results with subjective and objective evaluations of synthetic audio-visual performances obtained with our methods. Section 6 discusses those results and proposes directions for future work.

Theoretical framework and experimental data

Our study is based on the theoretical approach described in [START_REF] Morlec | Generating prosodic attitudes in french: data, model and evaluation[END_REF], which proposes that prosodic information is encoded via global multiparametric contours that are organized as prototypical shapes depending on the length of the carrier part of speech (i.e. number of syllables). This model of intonation builds on the seminal work of Fónagy who first put forward the existence of protopypical melodic patterns in French for expressing attitudes, the socalled "melodic clichés" [Fónagy et al. 1983]. Aubergé and Bailly [Aubergé and [START_REF] Auberg É | Generation of intonation: a global approach[END_REF] proposed a more general framework that supposes that metalinguistic functions associated with various linguistic units are encoded via elementary global multiparametric contours that are coextensive to these units. The multiparametric prosodic contour of an utterance is then built by superposing and adding these elementary contours by parameter-specific operators.

The SFC model [START_REF] Bailly | Sfc: a trainable prosodic model[END_REF] proposes a method for extracting these elementary multiparametric contours from arbitrary utterances given the set of attitudes and their scopes. This model supposes that the set of training utterances randomly samples the possible functions and the positions, lengths and numbers of their overlapping contributions. As we focus on analyzing audio-visual prosody, this theoretical model is extended for the joint modelling of melody, the pattern of syllabic lengthening and head motion trajectories.

As emphasized above, the extraction of prosodic shapes requires sufficient statistical coverage of the metalinguistic functions at varied positions and scope sizes. We have therefore designed and recorded an acted corpus of "pure" social attitudes, i.e. isolated sentences carrying only one attitude over the entire utterance.

Selected attitudes

A starting point for the possible attitudes considered was the Baron-Cohen's Mind Reading project [START_REF] Baron-Cohen | Mind reading: the interactive guide to emotions[END_REF]. The taxonomy proposed in this work gathers a total of 412 emotions grouped under 24 main categories, each comprizing several layers of subexpressions. Due to the complexity of the taxonomy, we choose a limited number of attitudes which are possibly expressed in one selected act from the play "Reigen" by Arthur Schnitzler [START_REF] Schnitzler | Invito alla lettura[END_REF]], translated in French by Maurice Rémon et Wilhelm Bauer. This play nicely consists in a series of seduction pitches during dyadic face-to-face conversation. The set of short turns exhibit a large variety of emotions and attitudes, intimately associated with the verbal content.

Table 1 contains the list of attitudes we decided to study, to which the three basic modalities have been added: assertion (DC), exclamation (EX) and full question (QS)(see table 2). The correspondance to the Mind Reading emotional set is indicated and instructions given to actors to perform the attitudes are also included. Video snaphots of chosen social attitudes are illustrated in figure 2.

Corpus

Two semi-professional actors recorded two corpora under the active supervision of one director:

• dialogs: The two actors played the selected scene in a neutral and an expressive way.

• monologs: The director and each actor recorded 35 sentences uttered with each of the selected 16 attitudes. These sentences were selected from the target scene so that to span the distribution of lengths of sentences in the final text (from one syl-

Recordings

The synchronized recording of voice signals and motion are performed by the commercial system Faceshift 1 with a short-range Kinect camera and a Lavalier microphone. Faceshift enables the creation of a customized user profile consisting of a 3D face mesh and an expression model characterised by a set of predefined blendshapes that correspond to facial expressions (smile, eye blink, brows up, jaw open etc). The sampling rate for audio is 44.1 kHz. Recordings are done in front of the camera, while seated, without additional markers such that the acting is not constrained. The use of Faceshift requires soft, non-saturated light conditions. Therefore, the recordings are done in a sound-proof, uniformly illuminated studio.

For the monologs, the actors were asked to utter the set of 35 sentences for each attitude in raw. Due to the nature of the desired social attitudes and to the eye gaze tracker, the actors perform as if they are addressing to a person standing in front of them, at the same height. For the dialogs, the actors sat in front of each other across a table, where two kinect cameras were laying.

1 http://www.faceshift.com/

Annotation and characterization

All utterances were automatically aligned with their phonetic transcription obtained by an automatic text-to-speech phonetizer [START_REF] Bailly | Automatic labeling of large prosodic databases: Tools, methodology and links with a text-to-speech system[END_REF]]. The linguistic analysis (part-of-speech tagging, syllabation), the phonetic annotation and the automatic estimation of melody were further checked and corrected by hand using a speech analysis software [START_REF] Boersma | Praat, a system for doing phonetics by computer[END_REF]]. Figure 3 presents a snapshot of Praat and the video frames associated to the annotated utterance. The subjects' performances are then caracterized by the following parameters associated with each syllable:

• Melody: When the vocalic nucleus of the syllable is voiced, we sample the F0 contour of this vowel at three timestamps: 20%, 50% and 80% of its duration. The three values are left unspecified otherwise.

• Rhythm: A lengthening/shortening factor is computed by considering an elastic model of the syllable. This model that the syllable compress/expand according to the elasticity of its segmental constituents. Contingent pauses are included in the model by saturating the elastic lengthening [START_REF] Barbosa | Characterisation of rhythmic patterns for text-to-speech synthesis[END_REF]].

• Head movements: We sample the head movements of the vocalic nucleus of the syllable at three timestamps: 20%, 50% and 80% of its duration. Principal component analysis is applied to rotation and translation and only the first three composants are kept for further analysis (explaining up to 80% of the information contained). Note that we considered one silent syllable (250 ms) before each utterance to gather preparatory head movements of prior to speech production.

Animation

As explained in the previous section, performances are recorded using a microphone and a Kinect camera. We synchronously collected audio, 2D (RGB images) and 3D data. Along with information regarding blendshapes, eye gaze and head movements, Faceshift can also generate RGB textures for each expression scanned during the training phrase.

We rendered the 3D performances of the actors using Blender2 . This rendering consisted in morphing static face textures on the facial mesh animated by the blendshapes estimated by Faceshift. A simple mode of the neck deformation with fixed torso is applied (video sample of an expressive animated dialog between the two actors3 ). Figure 4 presents examples of rendered frames for different attitudes.

Expressive Synthesis

One approach to evaluate the proposed prosodic features is by copying the time structure, pitch contours and head movements from the emotional performance samples onto declarative performances.

We synthesize expressive versions of performances by simply substituting prosodic parameters of the DC version with prosodic parameters of the target expressive version. Blendshapes trajectories

Acoustic synthesis

Prosodic manipulation of the DC stimuli is performed by Time-Domain Pitch-Synchronous Overlap-and-Add (TD-PSOLA) technique that consists in controlling pitch and duration of sounds by moving, deleting or duplicating short-time signals [START_REF] Moulines | Pitch-synchronous waveform processing techniques for text-to-speech synthesis using diphones[END_REF]].

Visual synthesis

Synthesized blendshapes and eye gaze are obtained by computing a Dynamic Time Warping path [START_REF] Berndt | Using dynamic time warping to find patterns in time series[END_REF] as we know the phoneme durations of DC and the analyzed attitude, and applying it to the movements of DC. The head movements are generated by interpolating between the movements at syllable landmarks of the analyzed attitude. In the interpolation step, movements are computed for 30 points per second to match the visual framerate. Rotations are used in quaternion representation so we use cubic interpolation (SQUAD) [START_REF] Eberly | 3D game engine design[END_REF]] to smoothly interpolate over a path of quaternions. This method is build upon the spherical linear interpolation (slerp) [START_REF] Shoemake | Animating rotation with quaternion curves[END_REF]]:

slerp(q1, q2, t) = sin(1 -t)θ sin θ q1 + sin tθ sin t q2 (1)
SQU AD(q1, q2, q3, q4, t) = = slerp(slerp(q1, q4, t), slerp(q2, q3, t), 2t(1 -t))

(2)

where qi represent quaternions, θ is obtained by computing the dot product between quaternions and t is the desired interpolation position.

Translations are obtained using cubic spline interpolation. Examples of synthesized trajectories are given in Figure 5 (video sample of animations obtained from original and synthesized from neutral performances4 ).

Subjective evaluation

For evaluation purposes, a series of subjective and objective tests are conducted on for three separate modalities: audio, visual and audio-visual. All subjective evaluations consist in forced-choice identification tests. Subjects are asked to label heard and/or viewed performances with one of the 16 attitudes.

Auto-evaluation

The persons who participated in the recording of our corpus (the two actors and director) are asked to perform an auto-evaluation test in which they were asked to label samples from their own performances, a few days after having been recorded. They are presented with random sets of 32 performances for each modality, which they can play several times. No explanation is given for the labels. Table 3 shows the accuracy rates for all performers on all modalities used:

The audio channel seems to encode slightly less discriminant information than the video channel. Note however that the audio/video hierarchy is strongly attitude-dependent. Overall, the recognition rate is high above the chance level (6.25%) and in the case of the Note that for some syllables, only two landmarks appear. This happens when the vocalic duration is very short and at the conversion to the visual framerate, some landmarks are attributed to the same frame.

actors, is generally higher than 60%. Actor 2 has the highest consistency. We thus choose performances made by this female speaker for a crowdsourcing subjective test.

Evaluation of original material

Eighty anonymous participants accessed the evaluation test which was carried using a normal web browser. Before starting the test, user information is collected, of which the most important is whether french is the mother tongue. Participants were given the definitions of all the attitudes and asked to identify the attitudes performed by the chosen actor (Actor 2) using audio files, video-only files and audio-video files. For each modality, the participants have to label 32 random performances. Each set is obtained by a random function which picks 2 performances from each attitude with the condition of not retrieving identical adjacent phrases. Performances last up to 5 seconds and can be played several times until they are labeled. Only the answers provided by native speakers are taken into account. After test completion, users have the option of The test containing original material consists in original audio files and video files obtained from sequences of 2D images which are synchronized with sound. Confusion matrices are built based on the choices made in the subjective tests for each modality. For representation of attitudes, we use the abbreviations indicated in Tables 1 and2. The recognition rates for all modalities are presented in Table 4. The best recognized attitudes are: Interrogative(QS), Seductive(SE), Thinking(TH) and Unfriendly-Sarcastic(US), while the lowest result values are obtained for: Exclamative(EX), Jealous(JE), Doubt-Incredulity(DI) and Hurt-Confrunted(HC). Except for EX, most attitudes have a recognition score high above chance level (0.0625%). Declarative (DC) also presents low scores as it was confused with EX and RE in all modalities. According to the comments left by users, the meaning of the HC attitude was not well understood, thus explaining the low score obtained. For this reason and for the fact that many users considered the test was too long, HC is removed from the set of attitudes in the following tests. A factor which may explain why for some attitudes (DC, JE, RE, HC) the scores obtained for video-only were higher than the ones including audio cues is the difficulty of dissociating the attitude from the semantic content of the carrier sentence.

Evaluation of animation

As the main focus of our work involves animated performances, a necessary step is the evaluation of animations obtained using data from original performances. Our expectation is that the level of recognition will be lower than in the case of the original video sources. This loss of expressivity has been studied in works as [START_REF] Afzal | Perception of emotional expressions in different representations using facial feature points[END_REF]] and in our case may be due to several causes: systematical errors of the data capture system, inability of capturing very fine facial expressions, audio-visual data synchronisation, unrealistic effects of the face texture, complex nature of the attitudes studied etc. The audio data is original as in the previous section.

Forty two anonymous participants were recruited to label performances via an online test. The performances are obtained using the original audio files and animations obtained from the original blendshape, eye gaze and head movement values. The total number of attitudes is 15 and each participant has to label 30 performances per modality. Tables 5, 6 and7 show the confusion matrices obtained.

Table 5: Confusion matrix obtained for audio-only.

DC EX QS CF FL SE FA JE TH DI SH SS SD RE EM DC 42 13 1 3 1 0 1 4 7 0 0 1 3 5 3 EX 43 11 0 8 0 0 3 3 2 1 1 6 1 4 1 QS 5 12 51 1 0 0 0 0 0 5 1 2 1 1 4 CF 22 5 0 16 9 5 7 1 5 1 2 0 2 4 4 FL 6 21 0 8 17 3 15 0 1 2 5 0 4 1 1 SE 5 0 3 2 1 35 6 1 9 4 10 2 1 3 2 FA 7 3 0 4 1 14 20 1 5 5 3 2 6 7 6 JE 34 4 3 5 3 1 0 2 2 8 7 2 1 7 5 TH 14 5 3 3 2 0 5 1 22 12 2 0 2 3 9 DI 7 18 4 12 3 2 5 0 3 10 1 3 6 5 5 SH 12 8 4 5 2 0 4 2 3 6 15 2 3 8 9 SS 1 23 5 0 0 0 0 1 0 2 1 34 16 1 0 SD 7 9 20 0 1 2 4 2 2 11 2 1 13 4 6 RE 35 17 0 8 0 0 2 3 5 1 3 5 1 3 1 EM 7 1 1 2 3 9 6 0 1 6 3 0 0 8 37 Table 6: Confusion matrix obtained for video-only.

DC EX QS CF FL SE FA JE TH DI SH SS SD RE EM

DC 29 1 3 1 0 0 6 1 7 8 0 0 6 5 4 EX 40 8 3 1 2 2 1 2 3 4 2 1 0 2 0 QS 16 3 19 1 1 1 1 0 4 7 0 3 8 2 6 CF 8 16 3 12 8 3 6 0 4 1 5 1 3 1 0 FL 5 19 0 6 24 0 10 2 0 0 4 0 1 0 1 SE 3 12 2 7 11 6 10 1 2 1 10 2 2 1 2 FA 14 1 2 0 0 1 13 1 2 12 3 1 13 5 4 JE 11 7 9 2 1 2 0 2 11 4 11 3 3 4 2 TH 4 8 7 3 1 0 0 0 29 9 7 1 1 0 2 DI 5 15 3 0 0 0 1 6 0 3 5 27 6 0 0 SH 10 10 6 5 1 3 1 0 3 4 5 10 7 2 5 SS 3 12 4 2 0 0 1 8 1 5 3 17 13 3 0 SD 5 8 14 0 2 1 1 1 4 15 2 9 7 2 1 RE 4 1 13 0 0 0 3 2 9 16 3 2 12 4 2 EM 7 1 3 7 3 11 2 3 5 3 7 2 0 5 13

Similarly to the previous test, DC is confused with EX and RE in all modalities, leading to small recognition rate for DC. The best recognition scores are obtained by QS, SE, SS and EM, especially for the modalities which include audio cues. As expected, the biggest difference between the scores obtained in this test and the ones from the previous test are caused by a general lower recognition rate for the video-only modality.

Evaluation of expressive synthesis

The last subjective experiment evaluates the relevance of the characteristics of the audio-visual prosody we chose to extract and control. We used the approaches presented in Section 3 to synthesize expressive performances for all modalities. Two modal attitudes are DC 43 4 0 0 1 0 7 1 5 3 1 1 4 2 0 EX 41 14 0 5 0 0 2 3 2 0 1 1 1 1 1 QS 2 5 48 2 0 0 0 1 0 7 0 2 3 1 1 CF 12 6 0 21 8 6 5 0 3 2 1 1 2 2 3 FL 3 20 0 13 16 2 12 1 1 0 1 0 3 0 0 SE 6 3 2 4 4 27 14 0 3 0 3 0 1 4 1 FA 4 3 1 5 3 2 24 0 5 2 2 0 13 4 4 JE 27 0 1 1 0 0 1 6 5 7 13 1 0 6 4 TH 11 4 4 2 0 2 0 1 35 11 0 0 0 1 1 DI 3 21 3 4 1 0 3 2 2 12 2 7 5 4 3 SH 10 5 1 4 2 1 5 0 4 7 16 0 4 9 4 SS 0 20 2 1 0 0 0 0 0 1 0 32 15 1 0 SD 2 7 12 1 1 1 3 1 2 10 9 4 16 2 1 RE 27 8 0 3 0 0 0 3 9 8 1 2 4 2 3 EM 3 0 1 0 3 10 6 0 4 3 2 0 1 8 31 removed in order to shorten the test duration: EX and QS. Up to the time of this submission, thirteen native speakers participated in the online evaluation test and were presented a total of 26 performances per modality. Table 8 shows the recognition scores obtained for all attitudes: The best recognition rates are obtained by FA, TH, SS and EM, showing results higher than chance level (7.69%). As expected, DC has a low recognition rate as it was confused with all other attitudes for all modalities. Attitudes such as SE and RE were not recognized at all for the video-only modality. This proves that the chosen prosodic parameters are more discriminant for certain attitudes; for example, there are distinguishable head movement patterns (for FA and TH, there is a tendency in rising the head) or speech patterns (for SS the rythm is much faster than in EM, and the pitch is higher). However, for more subtle attitudes such as SE, JE and RE, the visual cues rely more on eye gaze and eyebrow movements. As commented by a few participants in the study, confusion is induced by the neutral appearance of the eye gaze and expressions generated in the upper part of the face.

Objective evaluation

The objective evaluation refers to inter-class distances between all attitudes. These are computed for all modalities considering as metric the euclidian distance between the prosodic parameters for equal-sized utterances:

d(atti, attj) = 35 k=1 n l=1 3 m=1 (P iklm -P jklm ) 2 (3)
where n is the number of syllables of the phrase k and P represents the value of the prosodic element.

Depending on the modality chosen, the distance is computed at syllable level between the respective three values of prosodic parameters: F0 for audio-only, the first 3 PCA components over rotation and translation for video-only or all of them for audio-video. A confusion matrix is obtained for each modality using a K-nearest framework which enables the formation of attitudinal clusters. The accuracy rates obtained from the confusion matrix for all performers and modalities are presented in Table 9. The results show that Actor 1 presents overall more discriminant prosodic features for each modality. Next we will focus on the results obtained by Actor 2 in order to study the correlation between the objective measures and perceptual tests.

Discussion

The accuracy rates for all modalities and tests performed are presented in Table 11. The recognition rates for the three crowdsourced tests for the Audio-Video modality are presented in figure 6. Depending on the material used for each crowdsourced test we will consider the following notations: Material 1 for original video performances (Section 4.2), Material 2 for original animated performances (Section 4.3) and Material 3 for synthesized animated performances (Section 4.4). We notice that the accuracy rates for objective test and the subjective where the original audio and video were used are comparable only for the audio channel. The subjective tests reveal general higher recognition rates for original video and lower rates for synthesized from neutral performances. A higher recognition in the test using original video means that we need to include other visual parameters. Considering only head movements is not sufficient to obtain an objective signature of our set of social attitudes. F0 and rhythm are sufficient for obtaining discriminating audio contours.

The correlation between the objective and perceptual confusions on different modalities may help determining if the chosen audiovisual characteristics can explain the perceptual judgements and how much of the variance of the perceptual results they capture.

The correlations between the objective and subjective confusion matrices are computed using the Pearson coefficients:

Ri,j = Ci,j Ci,iCj,j (4)
where C is the covariance matrix of [CM online CM objective ] and CM are the two confusion matrices.

Figure 7 presents the coefficient values obtained between each of the online perceptual tests and the objective test for all attitudes:

The first caption suggests correlations for all modalities between the results of the objective test and the recognition scores given by the first online test. Attitudes that are well correlated are: DC, QS, FL, SE, US. Video-only presents a general correlation higher than 0.5, except for EX, JE, DI, EM which have low correlations for all modalities. Audio-only has very strong correlations with DC and QS (higher than 0.9), proving that the F0 shapes have a high influence on the auditive perception of attitude.

The second caption presents correlations between the objective test and the second online test. The correlations obtained in the audioonly modality are very similar to the ones obtained in the previous test, which is expected, as both experiments use random samples of original audio-data. The video-only correlations are generally lower for this test, showing that perceptual recognition scores are degraded overall. Audio-visual correlations are also similar to the ones obtained in the previous test.

The third online test presents much lower correlations with the objective test; strong correlations exist only for DC for all modalities, then for CF and US for audio-only and TH, DI and US for audiovisual. The low scores obtained on the third experiment (see Table 11) show that modifying the proposed parameters is not sufficient for obtaining an acceptable perceptive score for all attitudes. Therefore it is necessary to include more prosodic features -more subtle and surely more segment-dependent -in our analysis.

Conclusion

We have examined the contribution of audio-visual prosodic parameters to the evaluation of expressive performances. The prosodic features studied are voice pitch, audio-visual rhythm and head motion. Our dataset of social attitudes is validated through autoevaluation and crowdsourcing evaluation tests. Using objective measures and perceptual tests, we have proved that the parameters reveal distinguishable attitude characteristics. Comparable recognition scores for perceptive tests and objective measures show that F0 and rhythm are sufficient for obtaining attitude signatures, especially for Question, Fond-Liking, Disbelieving-Incredulous and Surprised-Scandalized. However, considering only head motion as video cues is not sufficient for attitude recognition.

The lower scores obtained when using animations show that they can be improved (texture, eye and lips movements). Another reason for obtaining lower scores in the perceptual tests may be the amount and nature of the attitudes studied, which require a good understanding of their definitions. When evaluating audio data, participants dissociate from the meaning of the sentence with difficulty.

The test using synthesized data shows that there are more parameters needed to better exploit the signatures of the recorded attitudes.

At the acoustic level such parameters are intensity and timbre. For visual cues the first parameters we will look into eye gaze and eyebrow movements.

Future work will include further analysis of the new prosodic features, improvement of the animation platform and the development of the prosodic model sustained by the theoretical framework described in Section 2. The visual prosody model will be extended to other parameters including eye movements, eye blinks, eyebrow movements and related FACS parameters. Idiosincracies will also be studied with the goal of building person-specific models of prosodic contours to enable the expression transfer across speakers and utterances. This study represents an initial step towards audiovideo expressive speaker conversion, ultimately targeting numerous applications within the domains of video games, intelligent user interfaces and expressive speech animations.

Figure 2 :

 2 Figure 2: Examples of attitudes interpreted by Actor 2.

  lable up to 21-syllable sentences) and have a large variability of positions and lengths of constitutive grammar groups.The recording session began with an intensive training of the actors, who received scenic indications from the theater director. The training consisted in fully understanding the interpreted attitudes and developing the ability to dissociate the affective state imposed by each attitude and the meanings of the phrases and to maintain a constant voice modulation, specific for each attitude, throughout uttering the 35 phrases. The actors did not receive any instruction related to head movements. The same set of sentences are then recorded by the director himself.

Figure 3 :

 3 Figure 3: Illustration of Praat usage for phonetic annotation of a the phrase: "Toute la salle était emballée." uttered by Actor 1 with the attitude Question. The contour highlighted over the spectrogram represents the F0 trajectory. The rising of the contour towards the end of phrase is characteristic for interogative phrases. Every eight video frames are selected from the performance and they illustrate the production of sounds: /t/, /a/, /e/, /a∼/ and /e/ respectively.

Figure 4 :

 4 Figure 4: Top: video images, bottom: rendered frames for animated performances for the respective attitudes: Seductive, Jealous, Scandalized, Thinking and Question.

Figure 5 :

 5 Figure5: Interpolated trajectories of prosodic parameters for phrase 30, attitude Question. Top: Interpolated and original trajectories of first dimension of the rotation quaternion, bottom: interpolated and original trajectories of translation along axis X of the coordinate system used. Prosodic landmarks are marked as circles and syllables are delimited by green lines. Note that for some syllables, only two landmarks appear. This happens when the vocalic duration is very short and at the conversion to the visual framerate, some landmarks are attributed to the same frame.

Figure 6 :

 6 Figure 6: For each attitude, the bars represent recognition rates for the audio-video modality.

Figure 7 :

 7 Figure 7: For each attitude, the bars represent the correlation coefficients obtained for audio, video and audio-video.

Table 1 :

 1 Description of chosen social attitudes.

	Category	Subgroup	Abbr. Definition
	Kind	Comforting	CF	Making people feel less worried, unhappy or insecure
	Fond	Liking	FL	Finding something or someone appealing and pleasant; being fond of something or someone
	Romantic	Seductive	SE	Physically attractive
	Interested	Fascinated	FA	Very curious about and interested in something that you find attractive or impressive
	Wanting	Jealous	JE	Feeling resentment against someone because of that person's rivalry, success, or advantages
	Thinking	Thoughtful	TH	Thinking deeply or seriously about something
	Disbelieving Incredulous	DI	Unwilling or unable to believe something
	Unfriendly	Sarcastic	US	Using words to convey a meaning that is the opposite of its literal meaning
	Surprised	Scandalized	SS	Shocked or offended by someone else's improper behavior
	Surprised	Dazed	SD	So shocked and stunned that you can't think clearly
	Sorry	Responsible	RE	Feeling that you are the cause of something that has happened and must therefore take the blame for its affects
	Hurt	Confronted	HC	Approached in a critical or threatening way
	Sorry	Embarrassed	EM	Worried about what other people will think of you

Table 2 :

 2 Attitudes added.

	Name	Abbr. Definition
	Declarative	DC	Making a declaration; neutral
	Exclamative	EX	Making an exclamation
	Interrogative	QS	Making an interrogation; question

Table 3 :

 3 Accuracy rates obtained for all modalities and performers for the auto-evaluation test.

	Performer Gender	Audio	Video	Audio-Video
	Director	male	43.75% 68.75%	68.75%
	Actor 1	male	65.62% 71.87%	75.00%
	Actor 2	female	78.12% 81.25%	78.12%
	leaving comments. Evaluation tests took on average 20 minutes to
	be completed.

Table 4 :

 4 Recognition rates for the online test containing original audio and video performances.

		Audio Video Audio-Video
	DC	0.148	0.251	0.170
	EX	0.048	0.014	0.066
	QS	0.725	0.412	0.788
	CF	0.130	0.563	0.290
	FL	0.481	0.340	0.368
	SE	0.506	0.731	0.761
	FA	0.192	0.289	0.391
	JE	0.000	0.250	0.167
	TH	0.597	0.722	0.814
	DI	0.180	0.083	0.214
	US	0.672	0.383	0.640
	SS	0.435	0.250	0.264
	SD	0.325	0.294	0.357
	RE	0.314	0.462	0.273
	HC	0.216	0.361	0.150
	EM	0.263	0.464	0.617

Table 7 :

 7 Confusion matrix obtained for audio-video. DC EX QS CF FL SE FA JE TH DI SH SS SD RE EM

Table 8 :

 8 Recognition rates obtained for the online test on synthesized performances.

		Audio Video Audio-Video
	DC	0.120	0.101	0.124
	CF	0.140	0.162	0.105
	FL	0.130	0.125	0.143
	SE	0.000	0.000	0.091
	FA	0.133	0.158	0.231
	JE	0.000	0.136	0.067
	TH	0.194	0.257	0.379
	DI	0.036	0.149	0.135
	US	0.120	0.045	0.222
	SS	0.350	0.033	0.333
	SD	0.130	0.071	0.200
	RE	0.059	0.000	0.000
	EM	0.313	0.182	0.192

Table 9 :

 9 Accuracy rates obtained for all modalities and actors for the objective test.

	Performer	Audio	Video	Audio-Video
	Director	13.02% 26.35%	33.48%
	Actor 1	32.53% 31.47%	46.98%
	Actor 2	30.60% 24.14%	40.95%

  Table 10 presents the recognition rates for each attitude:

Table 10 :

 10 Recognition rate for the objective measure.

		Audio Video Audio-Video
	DC	0.514	0.294	0.442
	EX	0.125	0.471	0.625
	QS	0.714	0.250	0.455
	CF	0.100	0.143	0.458
	FL	0.773	0.182	0.783
	SE	0.290	0.200	0.244
	FA	0.154	0.241	0.304
	JE	0.154	0.438	0.714
	TH	0.250	0.120	0.292
	DI	0.440	0.250	0.556
	US	0.235	0.310	0.476
	SS	0.333	0.182	0.238
	SD	0.333	0.073	0.344
	RE	0.184	0.321	0.304
	HC	0.385	0.333	0.389
	EM	0.150	0.158	0.167
	For the audio-only modality the most distinguishable attitudes are
	DC, QS, FL and DI. For video-only these are DC, EX, JE, US,
	RE and HC. Audio-video modality generally receives the highest
	scores and especially for EX, FL, JE and DI. The video-only modal-
	ity receives the lowest scores among modalities reinforcing the re-
	sults obtained from the perceptive tests. Overall, the recognition
	rates are higher than the chance level (6.25%) proving that there
	are distinguishable attitude characteristics in the analyzed prosodic
	features.

Table 11 :

 11 Accuracy rates obtained for all modalities and tests for Actor 2.

	Test type	Audio	Video	Audio-Video
	Auto-evaluation 78.12% 81.25%	78.12%
	Material 1	30.98% 35.47%	36.90%
	Material 2	26.00% 17.73%	31.72%
	Material 3	15.58% 11.65%	16.96%
	Objective	30.60% 24.14%	40.95%

http://www.blender.org/

http://youtu.be/Se P26Tg6-s/ -notably facial displays such as eyebrows, eye and lip movementsare kept from the DC version and only time-warped to comply with the target rhythm and syllabic durations.

http://youtu.be/B BjeBnaC7I/

Acknowledgements

This work is supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025). H. Cakmak receives a PhD grant from the Fonds de la Recherche pour l'Industrie et l'Agriculture (FRIA), Belgium. We strongly thank Georges Gagneré, Lucie Carta et Grégoire Gouby for providing us with these invaluable experimental resources. This research will not be possible without the numerous anonymous contributions of crowdsourced participants.


domain: math info

text:
Maike Massierer
email: maike.massierer@inria.fr

Some experiments investigating a possible L(1/4) algorithm for the discrete logarithm problem in algebraic curves

The function field sieve, a subexponential algorithm of complexity L(1/3) that computes discrete logarithms in finite fields, has recently been improved to an algorithm of complexity L(1/4) and subsequently to a quasi-polynomial time algorithm. We investigate whether the new ideas also apply to index calculus algorithms for computing discrete logarithms in Jacobians of algebraic curves. While we do not give a final answer to the question, we discuss a number of ideas, experiments, and possible conclusions.

Introduction

The computation of discrete logarithms in certain classes of finite fields has recently been revolutionized by a number of developments building on the well-known function field sieve algorithm. As a result, pairing-based cryptosystems in small characteristic are no longer considered secure (see e.g. [START_REF] Granger | Breaking '128-bit secure' supersingular binary curves[END_REF]), to name just one implication of these spectacular results.

The L(1/3) subexponential complexity of the function field sieve was first improved by Joux [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF] to L(1/4 + o(1)), and then by Göloglu, Granger, McGuire, and Zumbrägel [START_REF] Göloglu | Solving a 6120-bit DLP on a desktop computer[END_REF] to L(1/4). Shortly thereafter, Bȃrbulescu, Gaudry, Joux, and Thomé [START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] presented the first quasipolynomial algorithm for computing discrete logarithms in finite fields. Granger, Kleinjung, and Zumbrägel [START_REF] Granger | On the powers of 2[END_REF] took some important steps towards provability of the heuristic complexity results by presenting an alternative descent method.

The computation of discrete logarithms in Jacobians of algebraic curves has developed essentially in parallel to finite fields. The L(1/3) index calculus algorithm due to Enge, Gaudry, and Thomé [START_REF] Enge | An L(1/3) discrete logarithm algorithm for low degree curves[END_REF] for computing discrete logarithms in Jacobians of low degree curves has very much in common with the function field sieve. In particular, many of the results that the function field sieve is based on hold analogously for algebraic curves, such as the splitting probability of polynomials and divisors, respectively.

The recent developments therefore raise the question of whether analogous improvements can be made to the index calculus algorithm for curves, thus producing an L(1/4) or even quasi-polynomial algorithm. In this article, we report some thoughts on this questions, focusing particularly on the relation generation phase of the algorithm. While at this point, we are not able to answer the question completely, we discuss some possible approaches, the primary goal being to provide a basis for further discussion of this question in the scientific community.

We start by reviewing the concept of index calculus in general in Section 2, followed by a more detailed discussion of the function field sieve and its successors in Section 3 and index calculus in algebraic curves in Section 4. We then present some ideas for adaptation to curves For simplicity, it is often assumed that G = g , i.e. that G is a cyclic group. In this paper, G is either a subgroup of the multiplicative group of a finite field of small characteristic or the Jacobian of an algebraic curve of large genus defined over a finite field. In both cases, the most efficient known attacks on the DLP are variants and further developments of a basic index calculus algorithm, which we describe below.

Suppose we want to compute a discrete logarithm log g h. The main phase of index calculus computes the discrete logarithms of all small primes of G. These are all primes of size below a certain bound, the smoothness bound B, and the set of such small primes is called the factor base F B . This phase can again be divided into two parts: First, one collects a sufficient number (more precisely, |F B |) of relations between the factor base elements, then one solves a sparse linear system in order to obtain the discrete logarithms of the factor base elements. Finally, the individual logarithm phase of the algorithm computes log g h by rewriting this value as a sum of discrete logarithms of the factor base elements, which were computed earlier. For a detailed description of this index calculus method, see Algorithm 1.

Notice that both types of groups we are interested in are quotient groups. Therefore we write G = G 1 /G 2 , and for ĝ ∈ G 1 , we denote by g = ĝ • G 2 the class of ĝ in G.

Algorithm 1 General outline of an index calculus algorithm

Input: h ∈ G = G 1 /G 2 = g , smoothness bound B Output: d = log g h 1:
Factor base: Construct factor base F B = {ĝ 1 , . . . , ĝr } ⊆ G 1 .

2: Relation collection: Construct relations of the form r+1) , where m i1 = -α i for all i = 1, . . . , k, compute a non-zero column vector γ = (γ 1 , . . . , γ r+1 ) ⊤ such that M γ = 0 and γ 1 = 1. Then we have γ j+1 = log g g j for all j = 1, . . . , r. In order to discuss the complexity of this algorithm, let us denote by 1-α the subexponential complexity in x, where x is usually the input size |G|, for 0 < α < 1 and a constant c > 0. When we do not want to specify the constant, we often write only L x (α), or L(α) when the context is clear.

g αi = r j=1 g m i(j+1) j for i = 1, . . . , k > r. 3: Linear algebra: Given the matrix M = (m ij ) ∈ (Z/|G|Z) k×(
L x (α, c) = exp c(1 + o(1))(log x) α (log log x)
In both the case where G is a subgroup of the multiplicative group of a finite field and where G is the subgroup of the Jacobian of an algebraic curve of large genus, Algorithm 1 has heuristic complexity L(1/2) when steps 2 and 4 are implemented in a simple way: In step 2, we pick random α i ∈ Z/|G|Z and check whether g αi splits over the factor base. In step 4, we pick random β ∈ Z/|G|Z until we find one such that g β h splits over the factor base.

The crucial question in the complexity analysis of the above algorithm is with which probability an element of G splits over the factor base. If the factor base is defined in terms of the smoothness bound B, we call such elements B-smooth.

For the sake of concreteness, let us first assume that G ⊆ F × q n , where F q n is a finite field of small characteristic, meaning that q < L q n (1/2, 1/ √ 2). Hence all elements of F q n can be represented uniquely by polynomials of degree at most n in F q [x]. In this case, the small primes are defined to be the monic irreducible polynomials of small degree, i.e. for a given smoothness bound B we have the factor base

F B = {f ∈ F q [x] | f monic, irreducible, deg f ≤ B}.
Hence an element of F q [x] is B-smooth if all its irreducible factors have degree at most B. The probability of this happening is given by the following result.

Theorem 1 ([20]

). A polynomial over a finite field F q of degree n is B-smooth with probability u -u(1+o(1)) , where u = n/B.

Using this result, a rough analysis of the index calculus algorithm in G ⊆ F × p n is as follows. We choose B = log q L q n (1/2, 1/ √ 2), so that

|F B | = L q n (1/2, 1/ √ 2)
. Then the probability that a given element of F q n , represented by a polynomial over F q of degree less than n, is B-smooth,

is u -u(1+o(1)) = exp(-u(1 + o(1)) log u) = L q n (1/2, 1/ √ 2) -1 for u = n B = √ 2 log q n log log q n 1/2
, according to Theorem 1. Since we need to collect about

L q n (1/2, 1/ √ 2) relations, step 2 takes time L q n (1/2, 1/ √ 2) 2 = L q n (1/2, √ 2
) (notice that smoothness tests and polynomial factorization over F q [x] can be done in time polynomial in q). The linear system to be solved in step 3 is of size

L q n (1/2, 1/ √ 2) × L q n (1/2, 1/ √ 2)
and sparse, since there are at most n entries per row. Hence it can be solved with Wiedemann's or Lanczos' algorithm in time

L q n (1/2, 1/ √ 2) 2 = L q n (1/2, √ 2
). In step 4, the expected number of tries until we find a value for β such that

g β h is smooth is u u(1+o(1)) = L q n (1/2, 1/ √ 2)
, which is the time needed for the individual logarithm phase. Finally, since the factor base can clearly be enumerated (step 1) in time L q n (1/2, 1/ √ 2), the total time of Algorithm 1 in the case of finite fields is

L q n (1/2, √ 2
).

An analogous result can be proven for Jacobians of algebraic curves, since there is a smoothness result for divisors similar to Theorem 1. Let C be a projective algebraic curve of genus g given by an absolutely irreducible plane affine model C : C(x, y), where C ∈ F q [x, y] and F q is the exact constant field of the function field of C. The arithmetic in the Jacobian of such curves is detailed in [START_REF] Heß | Computing Riemann-Roch spaces in algebraic function fields and related topics[END_REF], and in particular, splitting a divisor into a sum of places can be performed in polynomial time. The factor base consists of divisor classes represented by prime divisors of degree bounded by B, therefore a divisor is B-smooth if it has only places of degree at most B in its support. The smoothness probability of divisors is analogous to that of polynomials (and, in fact, also that of integers or, more generally, elements of arithmetic semigroups):

Theorem 2 ([16, Theorem 13]). Let 0 < ε < 1, γ = 3 1-ε , and n, B with u = n B be given such that 3 log q (14g + 4) ≤ B ≤ n ε and u ≥ 2 log(g + 1). Then for n and B sufficiently large (with an explicit bound depending only on ε but not on q or g), the probability that a given effective divisor on C of degree n is B-smooth is at least u -u(1+o(1)) .

Using this theorem, we can show as above that index calculus in Jac C (F q ), which is a group of size approximately q g , has heuristic complexity L q g (1/2, √ 2) for q, g → ∞. The complexity results discussed in this section as well as the following section are always of heuristic nature, since the complexity analysis relies on heuristic assumptions, for example that the polynomials (respectively divisors) that are constructed in the computation have the same smoothness probability as random polynomials (respectively, divisors) of the same degree and that the linear system to be solved has full rank.

In the following we discuss the variants of Algorithm 1 that lead to first an L(1/3) and then even L(1/4) and quasi-polynomial algorithms for finite fields of small characteristic, and an L(1/3) algorithm for a certain type of algebraic curves. In our exposition, we concentrate mainly on the relation collection phase of the algorithm, since it is the focus of this work.

Finite fields of small characteristic

The function field sieve, due to Adleman [START_REF] Adleman | The function field sieve[END_REF], and its successors are the best algorithms for computing discrete logarithms in finite fields of small characteristic. The function field sieve gets its name from the fact that relations are produced with the help of two different function fields, a strategy originally developed in the number field sieve (which is good for factoring integers and computing discrete logarithms in finite fields of large characteristic) and subsequently adapted to finite fields of small characteristic. By searching for half-relations in each of the function fields and then combining them into full relations afterwards, one is able to reduce the degree of the polynomials that are required to be smooth, thus increasing the smoothness probability. This leads to a relation collection phase of complexity L(1/3), as opposed to L(1/2) above. The individual logarithm phase is also modified so that it has complexity L(1/3). The individual logarithm is computed with a so-called descent strategy, where log g h is first written as a sum of logarithms of elements of moderate degree, and then one proceeds recursively, writing each summand as a sum of logarithms of elements of smaller degree, until one finally arrives at a sum of logarithms of elements of small enough degree (i.e. all lying in the factor base). Combining these two speed-ups, one gets an algorithm of overall complexity L(1/3). We now give some more details of the relation collection phase, which can best be explained with the help of the commutative diagram given in Figure 1, where K = F q and the field L = F q n on the bottom is the field where the discrete logarithm is to be computed.

In order to produce relations, one starts with a polynomial φ ∈ F q [x, y], typically of shape φ(x, y) = a(x)y + b(x), and maps it via ψ 1 and ψ 2 into O 1 and O 2 , respectively. If ψ 1 (φ) ∈ O 1 and ψ 2 (φ) ∈ O 2 are both B-smooth, then one maps both of these elements into F q n via η 1 and η 2 , where they produce a relation of the form

η 1 (ψ 1 (φ)) = η 2 (ψ 2 (φ)),
O 1 = K[x, y]/f 1 (x, y) O 2 = K[x, y]/f 2 (x, y) L = K[x]/k(x) ψ 1 ψ 2 η 2 η 1
due to the commutativity of the diagram. The function fields involved are

F i = Quot(O i ) ⊇ O i , i = 1, 2.

The original function field sieve

Applicability. The function field sieve computes discrete logarithms in a field F q n = F q [x]/k(x) (with k monic and irreducible of degree n) of small characteristic, meaning that q ≤ L q n (1/3). Write K = F q and L = F q n . Function fields. The function field sieve usually chooses f 1 monic in y of degree d (a parameter to be optimized in the complexity analysis) and of degree O(1) in x, and f 2 (x, y) = y -h(x) where h has degree n/d. It is further required that f 1 (x, h(x)) ≡ 0 mod k, since this allows to define the maps in the way specified below.

Thus the function fields involved are F 1 = Quot(O 1 ) = F q (x)[y]/f 1 (x, y), an extension of F q (x) of degree d, and F 2 = Quot(O 2 ) = F q (x)[y]/f 2 (x, y), which is in fact the rational function field F q (x), since it is a degree 1 extension of F q (x). Let us write O i = F q [x, α i (x)] with f i (x, α i (x)) = 0 for i = 1, 2, and notice that α 2 = h.

Maps. We have ψ 1 : y → α 1 (x), ψ 2 : y → h(x) and η i : P (x, α i (x)) → P (x, h(x)). Notice that the η i are well-defined since we have f i (x, h(x)) ≡ 0 mod k.

Factor base. Since the O i are in general not unique factorization domains, one considers ideals, which factor uniquely. Hence one defines the factor base in terms of ideals in O i :

F (i) B = { ℓ(x), α i (x) -r(x) | ℓ irreducible, deg ℓ ≤ B, f i (x, r(x)) ≡ 0 mod ℓ(x)} and F B = F (1) B ∪ F (2) B .
Relations. In order to produce relations, one picks φ = a(x)y-b(x) ∈ F q [x, y] with deg a, deg b ≤ e for some sieving parameter e (to be optimized in the complexity analysis). One imposes further that a and b are coprime in order to avoid pairs (a, b) which are multiples of each other. We have ψ i (φ) = a(x)α i (x) -b(x), and it is easy to see that the ideal (a(x)α i (x) -b(x))O i is smooth with respect to the factor base

F (i) B if and only if the norm N Fi|Fq(x) (a(x)α i (x) -b(x)) is B-smooth as a polynomial (note that this is a polynomial, since aα i -b is a polynomial). Furthermore, we have N Fi|Fq(x) (a(x)α i (x) -b(x)) = Res y (a(x)y -b(x), f i ) = f (h) i (a, b) where f (h) i (a, b) = f i (a/b)b deg fi is the homogenization of f i ,
regarded as a polynomial in y. By sieving, we find enough pairs (a, b) ∈ F q [x] 2 such that f (h) i (a, b) are B-smooth for both i = 1, 2; such pairs are called doubly B-smooth. By raising the decompositions to the respective class numbers, we obtain factorizations into principal ideals, or equivalently by looking at the generators of the ideals, half-relations in O i , which can then be mapped via η i into F q n , thus producing full relations there. For the many technical details we are skipping here, see e.g. [START_REF] Bȃrbulescu | Algorithmes de logarithmes discrets dans les corps finis[END_REF].

Descent. In a first step, the descent rewrites the sought after logarithm as a sum of logarithms of L(2/3)-smooth elements. Then it recursively descends the elements in the sum to elements of F B by sieving elements of a lattice.

Complexity. Choose e = B = log q L q n (1/3) such that |F B | = L q n (1/3), and choose d = n log q log n 1/3
. Working out the constants as shown e.g. in [3, Chapter 7.5], the function field sieve has a total complexity of L q n (1/3, (32/9) 1/3 ).

The Joux-Lercier variant of the function field sieve

Joux and Lercier [START_REF] Joux | The function field sieve in the medium prime case[END_REF] give a simplified version of FFS, where the function fields are no longer visible as such, though they are still present "in the background" as described above, and one no longer has to deal with ideals.

Applicability. As before, this variant of the function field sieve applies to fields F q n = F q [x]/k(x), and we write

K = F q , L = F q n . Function fields. Let f 1 (x, y) = γ 1 (y) -x and f 2 (x, y) = y -γ 2 (x) for γ i of degree d i with d 1 d 2 ≥ n, and assume that k | γ 1 (γ 2 (x)) -x.
The function fields involved are

F 1 = F q (x)[y]/(γ 1 (y) -x), an extension of F q (x) of degree d 1 , and F 2 = F q (x)[y]/(y -γ 2 (x))
, which is in fact the rational function field (since it is a degree 1 extension of F q (x)). Hence as above, there is one rational side.

Interpreting F 1 as F q (y)[x]/(γ 1 (y) -x), which is the rational function field in y, one might even say that this algorithm has two rational sides.

Maps. We have ψ 1 : y → γ 2 (x), ψ 2 : x → γ 1 (y) and η 1 :

x → γ 1 (γ 2 (x)) = γ 1 (η 2 (y)), η 2 : y → γ 2 (x).
Factor base. Define

F B = {ℓ(x), ℓ(y) | ℓ ∈ F q [x] monic, irreducible, deg ℓ ≤ B}.
Relations. By sieving (as above), find φ(x, y) = a(x)y-b(x) ∈ F q [x, y] such that φ(x, γ 2 (x)) and φ(γ 1 (y), y) are both B-smooth. Such φ give relations since φ(x, γ 2 (x)) = φ(x, y) = φ(γ 1 (y), y).

Descent. This is the same as for the function field sieve.

Complexity. This is also the same as for the function field sieve.

The L(1/4) algorithm

A series of papers [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities[END_REF][START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF][START_REF] Göloglu | Solving a 6120-bit DLP on a desktop computer[END_REF][START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF][START_REF] Granger | Breaking '128-bit secure' supersingular binary curves[END_REF][START_REF] Granger | On the powers of 2[END_REF] with very similar ideas, often building on each other, drastically improved the efficiency of discrete logarithm computations in certain classes of finite fields. While Göloglu, Granger, McGuire, and Zumbrägel [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities[END_REF] were the first to point out that relation collection can be achieved in polynomial time, Joux [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF] gave the first algorithm of complexity L(1/4 + o(1)), which was subsequently improved to L(1/4) in [START_REF] Göloglu | Solving a 6120-bit DLP on a desktop computer[END_REF]. Finally, Granger, Kleinjung, and Zumbrägel took some steps in the direction of a provable complexity result by suggesting an alternative descent method in [START_REF] Granger | On the powers of 2[END_REF]. Most of these papers also present record breaking computations. The differences between these algorithms lie mostly in the individual logarithm (descent) phase, while they share very similar strategies for relation collection. Therefore, we present the basic ideas of all of them together in this section. We point out though that [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities[END_REF][START_REF] Göloglu | Solving a 6120-bit DLP on a desktop computer[END_REF][START_REF] Granger | Breaking '128-bit secure' supersingular binary curves[END_REF][START_REF] Granger | On the powers of 2[END_REF] limit themselves to fields of characteristic two.

Applicability. The algorithms apply to fields F q mn , where q ≈ n and m is small and fixed ( [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF][START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] consider only m = 2). Hence a given field must be embedded into a finite field of this shape as a first step. Writing K = F q m and L = F q mn , the relation collection phase can also be described via the diagram in Figure 1.

Function fields. Let f 1 (x, y) = y -x q and f 2 (x, y) = h 1 (x)y -h 0 (x) (respectively f 2 (x, y) = h 1 (y)x -h 0 (y)) for polynomials h 0 , h 1 ∈ F q [x
] of small, constant degree. Experiments suggest that suitable h 0 , h 1 of degree at most 2 always exist, see [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF].

Writing F q mn = F q m [x]/k(x), [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF][START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] require that k | h 1 (x)x q -h 0 (x), while [START_REF] Granger | Breaking '128-bit secure' supersingular binary curves[END_REF][START_REF] Granger | On the powers of 2[END_REF] require that k | h 1 (x q )x -h 0 (x q ), where the latter allows a slightly larger class of fields to be embedded into F q mn than the former.

We have

O 1 ∼ = F q m [x] and O 2 ∼ = F q m [x, 1/h 1 (x)] (respectively O 2 ∼ = F q m [y, 1/h 1 (y)]
), and the function fields are F i = Quot(O i ), which are both degree one extensions of F q m (x) (respectively F 2 is a degree one extension of F q m (y)), i.e. they are the rational function field themselves.

Maps. Let ψ 1 : y → x q and ψ 2 : y → h 0 (x)/h 1 (x) (respectively x → h 0 (y)/h 1 (y)), and let η 1 and η 2 be reduction modulo k.

Factor base. Set B = 1, the factor base consists of all monic linear polynomials over F q m . Notice that [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF] includes also quadratic polynomials for technical reasons concerning the descent, we disregard this here.

Relations. The approach of [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF][START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] can be interpreted as follows. Start with a polynomial of the shape φ = (a q y + b q )(cx + d) -(ax + b)(c q y + d q ) for (a, b, c, d) ∈ F 4 q m \ F q 4 . Then on the left (meaning ψ 1 (φ) ∈ O 1 ), this splits completely: set y → x q and use the identity

F (x) q G(x) -F (x)G(x) q = G(x) α∈Fq (F (x) -αG(x)) for F, G ∈ F q m [x]
. On the right (meaning ψ 2 (φ) ∈ O 2 ), this becomes a polynomial of small, constant degree and therefore has high splitting probability (for this purpose, h 1 is included in F B by definition). We get a relation as soon as the right-hand-side is smooth.

The other papers start with a polynomial φ = xy + ay + bx + c ∈ F q m [x, y] and map it to both sides. On the left, the resulting polynomial is of the form ψ 1 (φ) = x q+1 + ax q + bx + c, and it can be shown (using a transformation resulting in a polynomial of shape x q+1 + Dx + D and results of Bluher [START_REF] Bluher | On x q+1 + ax + b[END_REF] and Helleseth-Kholosha [START_REF] Helleseth | x 2 l + x + a and related affine polynomials over GF(2 k )[END_REF] on the splitting probability of polynomials of this shape, see [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities[END_REF]) that such polynomials split with probability q -3 , which is much higher than the splitting probability given by Theorem 1 for random polynomials of the same degree. A parametrization of such polynomials which split completely is also given. On the right, again, the polynomial ψ 2 (φ) splits with large constant probability.

Descent. We skip this, since it is different in all the papers mentioned above.

Complexity. Since n ≈ q and m is small and fixed, we have that q m is polynomial in the input size q mn . Then the relation generation takes only polynomial time, since the splitting probability is constant. The linear algebra is of size q m × q m .

Comparison

A schematic comparison of the relation collection phase for all algorithms discussed in this section is given in Figure 2.

Algebraic curves

The algorithm of Enge, Gaudry, and Thomé [START_REF] Enge | An L(1/3 + ε) algorithm for the discrete logarithm problem for low degree curves[END_REF][START_REF] Enge | An L(1/3) discrete logarithm algorithm for low degree curves[END_REF] is the most efficient currently known algorithm to compute discrete logarithms in Jacobians of algebraic curves. It has complexity L(1/3), but it is important that this improvement over the L(1/2) algorithm presented in Section 2 is not due to the search of relations in two different function fields, but rather to the bounds on the degrees of the curve equation, which are due to the fact that the algorithm applies only to C ab -curves.

Applicability. The algorithm applies to so-called C ab -curves defined over F q by an equation

C ab : y a + x b + f (x, y) = 0,
such that the affine part of the curve is smooth, and where gcd(a, b) = 1 and ai + bj ≤ ab for all monomials x i y j of f . Such curves have genus g = (a -1)(b -1)/2. The DLP is defined in its Jacobian Jac C ab (F q ), which has size about q g . The elements of the Jacobian are degree zero divisor classes, which we denote by [D] for a divisor D.

Function field. There is only one function field involved in the relation search, namely the function field F q (C ab ) = F q (x)[y]/(y a + x b + f (x, y)) of the curve. It is a degree a extension of F q (x).

Factor base. The factor base consists of all prime divisors on the curve of degree at most B, where B = log q L q g (1/3) is chosen such that the factor base has size L q g (1/3).

Relations. One searches for polynomial functions φ ∈ F q (C ab ) such that div(φ) is B-smooth. If div(φ) = ν i P i with P i ∈ F B , then ν i [P i ] = 0 gives a relation in Jac C ab . Smoothness of a divisor can be tested by checking if N Fq(C ab )|Fq(x) (φ) ∈ F q (x), and actually ∈ F q [x] since φ is a polynomial function, is B-smooth. Notice that N Fq(C ab )|Fq(x) (φ) = Res y (φ(x, y), y a + x b + f (x, y)) and can therefore easily be computed as a resultant.

Descent. The algorithm recursively descends a place of degree g 1/3+τ , τ ∈ [0, 2/3], to a sum of places of degree g 1/3+τ /2 by sieving elements of a lattice. Notice that there is no initial smoothing.

Complexity. Choosing a ≈ g α , b ≈ g 1-α for α ∈ [1/3, 2/3], and deg y φ ≈ g α-1/3 , deg x φ ≈ g 2/3-α , one can estimate deg x N Fq(C ab )|Fq(x) (φ) ≤ g 2/3
, hence the norm (and therefore div(φ)) is B-smooth with probability L q g (1/3) -1 . Hence one can collect |F B | = L q g (1/3) relations in time L q g (1/3), and the linear system can be solved in the same time. The descent phase has the same complexity, and therefore we get an overall complexity of L q g (1/3), where q and g grow to infinity.

Ideas for a faster relation generation phase for curves

The first goal in an attempt to transport the ideas of the L(1/4) algorithm to algebraic curves may be to devise a strategy to produce relations in a more efficient way. One may take Joux's

F q [x, y] F q [x, y]/f 1 (x, y) F q [x, y]/(y -h(x)) F q n = F q [x]/k(x) y → α 1 (x) y → h(x) modk(x) modk(x)
where k(x) | f 1 (x, h(x))

F B = { ℓ(x), α i (x) -r(x) | ℓ irreducible, deg ℓ ≤ B, f i (x, r(x)) ≡ 0 mod ℓ(x)} with B = log q L q n (1/3) φ = a(x)y -b(x) ∈ F q [x, y]
Criterion for relation:

f 1 (x, a(x)/b(x))b(x) d , a(x) -b(x)h(x) are B-smooth
Joux-Lercier variant of FFS [START_REF] Joux | The function field sieve in the medium prime case[END_REF], Section 3.2

F q [x, y] F q [x, y]/(γ 1 (y) -x) F q [x, y]/(y -γ 2 (x)) F q n = F q [x]/k(x) y → γ 2 (x) x → γ 1 (y) y → γ 2 (x) x → γ 1 (γ 2 (x))
where

k(x) | γ 1 (γ 2 (x)) -x F B = {ℓ(x), ℓ(y) | ℓ ∈ F q [x] monic, irreducible, deg ℓ ≤ B} with B = log q L q n (1/3) φ = a(x)y -b(x) ∈ F q [x, y] Criterion for relation: φ(x, γ 2 (x)), φ(γ 1 (y), y) are B-smooth
French relation search [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic[END_REF][START_REF] Bȃrbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF], Section 3.3

F q 2 [x, y] F q 2 [x, y]/(y -x q ) F q 2 [x, y]/(h 1 (x)y -h 0 (x)) F q 2n = F q 2 [x]/k(x) y → x q y → h 0 (x)/h 1 (x) modk(x) modk(x)
where k(x) | h 1 (x)x q -h 0 (x)

F B = {ℓ(x) | ℓ ∈ F q 2 [x] monic, linear} i.e. B = 1 φ = (a q y + b q )(cx + d) -(ax + b)(c q y + d q ) ∈ F q 2 [x, y]
Criterion for relation: (a q c -ac q )xh 0 (x) + (a q d -bc q )h 0 (x)+ +(b q c -ad q )xh 1 (x) + (b q d -bd q )h 1 (x) splits into linear factors Irish-Swiss relation search [START_REF] Granger | Breaking '128-bit secure' supersingular binary curves[END_REF][START_REF] Granger | On the powers of 2[END_REF], Section 3.3

F q m [x, y] F q m [x, y]/(y -x q ) F q m [x, y]/(h 1 (y)x -h 0 (y)) F q mn = F q m [x]/k(x) y → x q x → h 0 (y)/h 1 (y) modk(x) modk(x) where k(x) | h 1 (x q )x -h 0 (x q ) F B = {ℓ(x), ℓ(y) | ℓ ∈ F q m [x] monic, linear} i.e. B = 1 φ = xy + ay + bx + c ∈ F q m [x, y]
Criterion for relation: x q+1 + ax q + bx + c and yh 0 (y) + ayh 1 (y) + bh 0 (y) + ch 1 (y) split into linear factors point of view and try to amplify relations (e.g. via homographies), or that of the Irish-Swiss team of finding families of functions that have higher-than-usual splitting probability. In both cases, the shape of the function field plays a crucial role, and the new algorithms profit precisely from this freedom to choose convenient function fields.

In the case of algebraic curves, the function field is given by the curve in question, and there is unfortunately no freedom to choose it. Therefore, we ask ourselves instead whether there exist curves (with corresponding function fields) for which we are easily able to produce relations. The curves should, of course, have no known weaknesses with respect to the DLP. In particular, they should not be supersingular, or more generally, not have a Jacobian of smooth order, they should not have small embedding degree, and they should obviously not have genus 0. In fact, in order to mimic the finite field algorithms, we would need a curve defined over F q of genus about q, so that the Jacobian has order about q q . A more precise formulation of the question we wish to answer is the following. We write poly(q) = q Θ(1) . Question 1. Let C be a projective curve defined over F q of degree poly(q). Under which conditions is the number of polynomial functions of degree O(1) defining divisors which split into factors of degree O(1) unexpectedly large, say of the form poly(q)? Unfortunately our impression is that there may not exist curves which satisfy all of these criteria. A precise formulation of this impression is given in Section 7, but before we get to it, we explain the reasoning and experiments that led to this conclusion.

A first observation is that the function fields chosen in the L(1/4) algorithms for finite fields are not interesting in our context, since the corresponding curves y -x q and h 1 (x)y + h 0 (x) both have genus zero.

We tried two approaches, corresponding to the point of view of Joux (and the "French team") and that of the "Irish-Swiss team", respectively.

The first approach would be to find a curve, together with one smooth function, which gives a relation, and to then amplify this into many relations using homographies. This works well for the specific curve y -x q , since it is of particularly simple shape, as shown in Example 1. For curves with more complicated equations, this becomes more difficult, as the application of the homography is no longer compatible with taking the resultant. Example 2 shows a curve where this approach does not work, i.e. where we find exactly two polynomial functions that have smooth principal divisors but no more.

The second approach would be to find a curve, together with a (parametrized) family of smooth functions, such that the (parametrized) resultant has high splitting probability. Again, this works well for the curve y -x q , since we have Res y (φ(x, y), y -x q ) = νφ(x, x q ) for some constant ν, and therefore the norm of φ depends on φ in a very simple way. For this reason, simple φ's produce simple N(φ)'s, and it is easy to produce polynomials for which results on higher splitting probability are known, see Example 1. The difficulty about generalizing this approach is that there exist few known families of polynomials with high splitting probability, and it is difficult to produce these few very simple polynomials with more interesting curves.

Example 1. Let C : y -x q = 0 and φ(x, y) = y -x ∈ F q (C). Then N Fq(C)|Fq(x) (φ) = Res y (y -x, y -x q ) = ν(x q -x) = ν α∈Fq (x -α)
for some constant ν. Since N(φ) splits completely into linear factors, div(φ) is smooth and therefore gives a relation.

In order to amplify this one relation into many, Joux proposes to apply a homography x → ax+b cx+d , where a, b, c, d ∈ F q 2 . After multiplication by (cx + d) q+1 , this gives

(ax + b) q (cx + d) -(ax + b)(cx + d) q = (cx + d) α∈Fq ((a -αc)x + (b -αd)),
and one has found many polynomials that split into linear factors. How many? As many as there are matrices a b c d ∈ PGL 2 (F q 2 )/ PGL 2 (F q ), which has cardinality q 3 + q.

Interpreting this in terms of relations on the curve C, we "apply" the homography to φ(x, y) = y -x as follows. Setting

φ hom (x, y) = (a q y + b q )(cx + d) -(ax + b)(c q y + d q ), we get Res y (φ hom (x, y), y -x q ) = ν(cx + d) α∈Fq ((a -αc)x + (b -αd))
for a constant ν, which gives about q 3 different relations in Jac C . Alternatively, we may define φ(x, y) = xy + ay + bx + c for a, b, c, d ∈ F q m , which gives Res y (φ(x, y), y -x q ) = x q+1 + ax q + bx + c.

If c = ab and b = a q , then the transformation x → ab+c b+a q x + a maps the result to x q+1 -Dx + D which, for D ∈ F q m , splits into linear factors for about q m-3 values of D according to [2, Lemma 4.4]. In other words, φ has splitting probability q -3 , which is much higher than that of a random polynomial of degree q + 1, which is on the order of q -q according to Theorem 1.

The connection between the two approaches, and an interesting observation, is that polynomials (ax + b) q (cx + d) -(ax + b)(cx + d) q are of the form Ax q+1 + Bx q + Cx + D, and such polynomials have splitting probability q -3 according to [START_REF] Bluher | On x q+1 + ax + b[END_REF], which is higher than expected. It is possible that this phenomenon holds more generally. For example, (ax 2 + bx + c) q (dx 2 + ex + f ) -(ax 2 + bx + c)(dx 2 + ex + f ) q splits completely into factors of degree 2 and has terms x 2q+2 , x 2q+1 , x 2q , x q+2 , x q+1 , x q , x 2 , x, 1, so one might expect that polynomials Ax 2q+2 +Bx 2q+1 + Cx 2q + Dx q+2 + Ex q+1 + F x q + Gx 2 + Hx + I split into quadratic factors with higher probability than expected. Counting arguments as well as experiments for m = 2 and small fields suggest that this may be the case with probability q -7 , but such counting experiments are only possible for very small fields and therefore only give a vague idea, and we are not aware of any results similar to those of [START_REF] Bluher | On x q+1 + ax + b[END_REF][START_REF] Helleseth | x 2 l + x + a and related affine polynomials over GF(2 k )[END_REF] for such polynomials. If such a thing were true, we could search for pairs of C, φ such that the resultant has such a shape. Notice that it is obviously possible to extend this idea, using e.g. polynomials of larger degrees and possibly products of polynomials of different degrees.

Example 2. Consider C : y 2 -x q+1 + 2x -1 = 0, which is a hyperelliptic, non-supersingular curve of genus g = (q -1)/2, and φ(x, y) = y -x + 1. Then Res y (φ, y 2 -x q+1 + 2x -1) = x(x q -x) and therefore splits into linear factors. However, exhaustive search shows that the only functions of the form ψ = axy + by + cx + d with a, b, c, d ∈ F q 2 such that Res y (ψ, y 2 -x q+1 + 2x -1) splits into linear factors and produces a non-trivial relation are ψ = y + x -1, y -x + 1, for q = 7, 11, 19, 23 (notice that these are all primes ≡ 3 mod 4). For these values of ψ, we have Res y (ψ, y 2 -x q+1 + 2x -1) = x(x q -x).

Therefore, for this curve and the values of q mentioned above, there is no way of applying a homography appropriately to φ or of finding ψ with higher splitting probability.

Example 3. Let C : y 2 -x q-1 + 1 = 0, which is a hyperelliptic, non-supersingular curve of genus g = (q -3)/2. In fact, it is a CM-curve and has 2q -2 automorphisms. We look for a polynomial function φ ∈ F q (C) such that Res y (φ, y 2 -x q-1 + 1) = x q -x or a small multiple thereof. Since the curve equation is quadratic in y, the function must be of shape φ(x, y) = φ 1 (x)y + φ 0 (x). Furthermore, the degrees of φ 0 and φ 1 should be very small. If we allow degree at most one, then by solving Res y (φ 1 (x)y + φ 0 (x), y 2 -x q-1 + 1) = (x q -x)(x + a)

for some a, we get a = 0, φ 0 = x, φ 1 = 0 and therefore φ(x, y) = xy. This is not interesting, as φ is not irreducible.

If we allow φ 0 , φ 1 of degree up to two, then with the same reasoning, we get φ(x, y) = (x 2 + ax)y for any choice of a. Again, this is not interesting as it is not irreducible.

Example 4. Let C : y 2 -x q-2 + x + 1 = 0, which is a hyperelliptic, non-supersingular curve of genus g = (q -3)/2. As in Example 3, we try to find a function φ = φ 1 (x)y + φ 0 (x) such that Res(φ, y 2 -x q-2 + x + 1) is a multiple of x q -x by some linear factors. Trying to solve the equation, we find that neither linear nor quadratic φ 0 , φ 1 produce a resultant which is divisible by x q -x. The same is true for C : y 2 -x q-1 -1 and many other curves.

Example 5. Let C : y 2 + y = x n be a Koblitz-Buhler curve (see [START_REF] Buhler | Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems[END_REF]), which is a hyperelliptic curve. Its equation can be transformed into y 2 = x n + 3/4 via the transformation y → y -1/2 in odd characteristic. For this curve, which functions split over F q [x] depends on q. For some values of q (e.g. q = 7), we can show that there are no φ 0 , φ 1 of degree 2 such that Res y (φ 1 (x)y + φ 0 (x), y 2 + y = x n ) = x q -x by solving the corresponding polynomial system with coefficients of the φ i as indeterminates.

Example 6. Consider the Hermitian curve C : x q+1 + y q+1 -1 = 0. These curves have genus g = q(q-1)/2 and are known for the fact that they have many F q 2 -rational points, more precisely, exactly q 3 + 1. In other words, the function field F q 2 (C) is maximal (in the sense that the upper Hasse-Weil bound on the number of places of degree one is attained). For this reason, such curves are of interest e.g. in coding theory. It is also known that Hermitian curves are supersingular, and therefore not interesting in the context of cryptography. For more on Hermitian curves, see e.g. [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF]Chapter VI,VII]. Now let φ = xy + ay + bx 2 + cx + d with a, b, c, d ∈ F q 2 . Experiments suggest that this function has higher-than-expected splitting probability. More precisely, for fields small enough so that we can enumerate all functions of this shape over F q 2 , more than q 6 out of q 8 possible such functions φ split into factors of degree at most two. This is much more than expected for a random function of the same degree (here, the splitting probability behaves like q -q for q → ∞). However, experiments also show that special things are happening here: If the resultant is 2-smooth, then it is always automatically already 1-smooth (i.e. we did not find functions that produced a resultant which was 2-smooth but not 1-smooth).

Example 7. Let C : y q+1 + x q+1 y -1 = 0, which is a non-hyperelliptic, non-supersingular curve of genus g = q(q + 1)/2. Experiments for q = 5, 7, 11, 13, 17, 19, 23 show that there is no irreducible function φ = xy + ay + bx + c ∈ F q 2 [x, y] such that Res y (φ, y q+1 + x q+1 y -1) splits completely into linear factors.

A possible obstruction

A possible conclusion from the experiments described in Section 6 is that curves for which principal divisors with higher-than-expected splitting probability exist are very special, and in fact, so special that the DLP is already known to be easy for these curves. A more precise formulation and possible answer to Question 1 is the following. Conjecture 1. Let (C q ) q be a family of projective curves defined over F q of genus poly(q), given by an equation of degree poly(q). Assume that there exist poly(q) monic, irreducible polynomial functions φ ∈ F q 2 (C q ) of degree O(1) such that div(φ) is O(1)-smooth. Then Jac Cq is isogenous to a product of elliptic curves, for large enough q.

The main example supporting this conjecture are Hermitian curves, which are supersingular and therefore, in particular, have a Jacobian isogenous to a product of supersingular elliptic curves.

It is a priori not clear how to prove such a statement, since one would have to relate splitting probabilities of rational functions to the structure of the Jacobian of a curve. However, there are some results related to the special case of Question 1 where we set both constants equal to one: Question 2. Let C be a projective curve defined over F q of degree poly(q). Under which conditions is the number of lines defining divisors which split completely unexpectedly large, say of the form poly(q)? Heuristically, for a curve of degree d, we expect about q 2 /d! such divisors to split completely. Moreover, for reflexive curves of fixed degree d ≥ 3, it has been proven by Diem that this count holds asymptotically: Theorem 3 ([6, Theorem 3]). Let d ≥ 3 be fixed, and let C be a projective curve of genus at least one given by a plane model of degree d. If d > 4, then assume that the plane model is reflexive. Then the number of divisors on C that are given by lines in P 2 and split completely into distinct points is in 1 d! q 2 + O(q 3/2 ). For example, Hermitian curves are non-reflexive, and as explained in Example 6, they have many points. This corresponds to the fact that there are many divisors given by lines, and therefore also many that split.

Since we are interested in curves where there are rational functions with higher-than-expected splitting probability, this rules out reflexive curves as possible candidates. This leaves nonreflexive curves, which are relatively well-studied in the literature, see e.g. [START_REF] Hefez | Non-reflexive curves[END_REF][START_REF] Hefez | Non-reflexive projective curves of low degree[END_REF].

A projective variety V is called reflexive if the conormal variety of V and its dual variety V ′ are equal up to the canonical identification of projective space with its double dual. Varieties defined over characteristic zero base fields are always reflexive, and even over positive characteristic fields, most varieties are reflexive. The main examples for non-reflexive varieties are strange curves, which have the property that all tangents pass through a common point.

In fact, non-reflexive curves are so special that they have been classified according to their degree by Ballico and Hefez [START_REF] Hefez | Non-reflexive projective curves of low degree[END_REF]. Among other things, they show that for non-reflexive plane curves C of degree d with "moderate singularities" defined over fields of characteristic p > 2, we always have p | d -1. Moreover, for such curves, they give the following result.

Theorem 4 ([14, Proposition 1]). Any non-reflexive plane curve of degree d = q + 1 ≥ 4, for q a power of the characteristic of the field of definition, and of genus greater than zero is projectively equivalent to the curve x q+1 + y q+1 + z q+1 = 0.

(1)

These are the Hermitian curves, which are known to be supersingular. As discussed earlier, such curves are not interesting in our context. Summarizing, because of Diem's theorem, the only curves which are candidates in response to Question 2 are non-reflexive curves, but such curves are not interesting in our context. This is in accordance with our experiments, in which we found only curves of shape [START_REF] Adleman | The function field sieve[END_REF].

The question that remains is whether a more general statement, perhaps along the lines of our conjecture, can be proven in response to the more general Question 1. One possible approach to this would be to use Cebotarev's density theorem, which is the main argument in the proof of Diem's theorem.

Conclusion

Our investigation of possible ways of adapting the relation collection phase of the new L(1/4) and quasi-polynomial algorithms to algebraic curves suggests that this is a difficult problem. In particular, our experiments indicate that curves which permit rational functions whose principal divisors have higher-than-expected splitting probability are very special and therefore not interesting in our context, since the DLP in these curves is already known to be weak. We conjecture that this is always true and show that a special case of this conjecture can be proven using known results of Diem and Ballico-Hefez. If the more general statement could be proven, this would rule out a more general approach that allows polynomial functions of constant degree and the corresponding divisors to split into factors of constant degree. Clearly, this would still not mean that there is no L(1/4) DLP algorithm for Jacobians of curves, it would mean simply that one needs to investigate more sophisticated ideas than the rather obvious analogy we have considered here.

4 :Remark 1 .= 1 .

 411 Individual logarithm: Search for β such that g β h = r j=1 g βj j for some β j , output d = -β + r j=1 β j γ j+1 . Notice that the following slightly modified version of Algorithm 1 is equivalent. It will be useful later on. In step 2, we collect relations of the form In step 3, the matrix M consists simply of the m ij .

Figure 1 :

 1 Figure 1: Commutative diagram illustrating relation collection phase of FFS and its successors K[x, y]

Figure 2 :

 2 Figure 2: Comparison relation search of FFS and its successors

ExperimentsWe discuss the approaches that we tried using some exemplary curves. In this entire section, we give resultants only up to multiplication by a constant, since this simplifies notation and is sufficient for determining the splitting properties.

The author was supported by the Swiss National Science Foundation under grant no. 151884.