Jean-Pierre Clayer
email: jean-pierre.clayer@lium.univ-lemans.fr

Claudine Toffolon
email: claudine.piau-toffolon@lium.univ-lemans.fr

Christophe Choquet
email: christophe.choquet@lium.univ-lemans.fr

A PATTERN-BASED AND TEACHER-CENTERED APPROACH FOR LEARNING DESIGN

Keywords: Educational scenario, model-driven engineering, domainspecific modeling, User Modelling, Adaptation 1

Teaching is changing in deep, due to, on one hand, the evolutions of the society expectations and, on another hand, the widely spreading of new technologies. By the way, teachers and trainers need now to structure and formalize their internal designs and should become designers but do not have the competence. We aim to help them during the instructional design process. In that way we propose some methods and tools to support the scenario design activity and the implementation of the resulting models. We present an adaptive user-centered pattern-based learning design approach and the editor tool to support it. A case study is proposed to illustrate the design process.

INTRODUCTION

Teaching is changing in deep, due to, on one hand, the evolutions of the society expectations and, on another hand, the widely spreading of new technologies. By the way, teachers and trainers, who are used to design their learning scenario with internal -non expressed practices, need now to structure and formalize their internal designs as models able to be implemented. They should become designers but do not have the competence and most of the time need specialists (e.g. pedagogical engineers) to help them during this scenario design activity and to implement resulting models.

This paper presents an adaptive user-centered pattern-based learning design approach. A pattern-based approach facilitates the design and the reuse of implementable scenario by a learning community of practice [START_REF] El Kechaï | Reusing Pedagogical Scenarios at a Knowledge Level: a Model Driven Approach[END_REF][6]. The approach is user-centered and adaptive as teacher is the principal actor involved in the design process but helped/guided during the elaboration of learning scenario according to his/her design practices. We aim to propose methods and tools to support teachers during the scenario design activity.

The main research question of this paper is about the feasibility of an adaptive pattern-based design approach to deal with the design and the reuse of learning scenario by teachers. The originality of our approach comes from (1) the use of different types of Patterns for specific design tasks and (2) the contextual guidance of the design.

The first section presents the scientific groundings of this work. We propose then a design process based on the use of patterns and on adaptive techniques. This process is illustrated in the third section by a case study. The conclusion synthesizes our results and discusses on future works.

THE RESEARCH CONTEXT

The literature has proposed different approaches which deal the instrumentation of instructional design, and specifically learning scenarios centered.

The well-known modeling approach by the help of Educational Modeling Languages (EML), as the IMS Learning Design specification [START_REF] Koper | Representing the Learning Design of Units of Learning[END_REF] leads to enable the design of computational models (in the meaning of understandable by a computer) which could be enacted by compliant systems. However these specifications are not really usable by teachers and do not enforce design processes that support the creation of pedagogically sound designs [START_REF] Hernandez-Leo | A multicase study for the evaluation of a pattern-based visual design process for collaborative learning[END_REF]. Another approach is to allow designers (may be assisted by modeling specialists) to define their own EML by specifying a domain-specific language and to use it for building their scenarios [3] [4]. Our research work is based on this second approach and states that teachers are able to build their learning scenarios by the uses of patterns.

A design pattern is focused on a well-known problem and should provide its most common solution related to a given context, which is illustrated with diagrams or figures. A design pattern"s approach is well-suited in design based research in education as it is sensitive to complexity and context-dependence [START_REF] Mor | Embedding Design Patterns in a Methodology for a Design Science of e-Learning[END_REF].

Our engineering approach aims to support practitioners (classroom teachers) in their day to day pedagogical design tasks. The learning design patterns are a way of collecting "best practices" in learning, providing assistance to novice practitioners by communicating a learning expertise. In that way, an authoring tool could help the design of pedagogical situations, by the use of design patterns gathered into a library [START_REF] Hernandez-Leo | A multicase study for the evaluation of a pattern-based visual design process for collaborative learning[END_REF]. Existing relationships between patterns should be described to facilitate their use/reuse. These design patterns should allow further the definition of learning scenario in different learning situations in terms of objectives, competencies, domain, learning method, activities, resources, observation needs ... Some examples of learning patterns are proposed in the E-LEN projects [6] or the pedagogical patterns project [START_REF]Pedagogical Patterns Project[END_REF]. COLLAGE [START_REF] Hernández-Leo | COLLAGE: A collaborative Learning Design editor based on patterns[END_REF] proposes a pattern-based visual design approach implemented in RELOAD [START_REF] Bolton | Reload Project[END_REF], an authoring tool based on IMS-LD.

The research contribution we present in this paper is based on another pattern based approach that leads to devote specific patterns to specific design tasks (see infra.). Morever, patterns may be expressed in the teachers" business language [START_REF] El Kechaï | Reusing Pedagogical Scenarios at a Knowledge Level: a Model Driven Approach[END_REF] [4] (e.g. within their own business concepts and representation model).

Even if we do not yet aiming at creating productive models (e.g. operationalisable scenarios), this feature underpins our work. Thus, we have chosen to base the approach we propose in a Domain Specific Modeling (DSM) [START_REF] Kelly | Domain-Specific Modeling: Enabling full code generation[END_REF] framework which is a robust software engineering approach to deal with this Technology Enhanced Learning (TEL) context [START_REF] Kelly | Domain Specific Languages vs. Generic Modelling Languages[END_REF].More specifically, we have chosen to develop with EMF (Eclipse Modeling Framework) and GMF (Graphical Modeling Framework) to implement the DSM approach [START_REF] Eclipse | Eclipse Modeling Projects[END_REF].

Another part of the research question is about adaptation of the pattern-based design. Teachers, as they should become designers, could be guided in their design activity. The pattern approach we propose is user-centered. User models and user modeling are key elements for personalizing interaction. User modeling is motivated by differences in individual user"s needs and characteristics and heterogeneity between different groups of people [START_REF] Razmerita | On the Role of User Models and User Modeling in Knowledge Management Systems[END_REF]. We address an automatic user modeling approach where the user"s model is defined during a tool design activity session from user"s characteristics (user profile, user"s preference, competency, level of activity, level of competence …). Those user"s characteristics are relevant tracks to collect and will be used to help teachers to manage their learning design activity. An analysis solution of these tracks is needed to adapt the system to the user"s design needs. For structuring tracks from row data, acquired and provided by the system during a design session, to indicators (something significant for its user), we have used the Usage Tracking Language (UTL) [START_REF] Choquet | Modeling Tracks for the Model Driven Reengineering of a TEL System -Journal of Interactive Learning Research (JILR)[END_REF] which allows to model indicators as patterns and to calculate them at real time.

PATTERN-BASED AND TEACHER-CENTERED APPROACH

Meta-model of Patterns

According to the DSM approach, a meta-model (figure 1) has to be defined to describe the language allowing to compose or merge patterns with different formalisms. The purpose of this meta-model MOF compliant (Meta-Object Facilities) is to be used to generate an editor tool.

The Design Context

To facilitate and guide the designer"s task, an edition tool has to collect information on the design context and to adapt patterns to the purpose of the design session. This information relies to a set of indicators (UTL meaning: a significant datum which qualifies the activity, here the

The Learning Scenario Editor

The editor we have developed is generated into the EMF-GMF framework, from the meta-model of Patterns (see figures 1 and4). This editor allows the teacher to design a learning scenario by using a domain-specific visual language and by organizing and instantiating patterns. Upon this editing tool is added the adapting system able to capitalize the design contexts, and to adapt the domainspecific models and the editing interface, according to the DSM features of EMF/GMF. This interface allows the designer to visualize the patterns he instantiates as frames divided in three boxes: one for the pattern name, one for the statement of the problem and one for the graphical representation of the solution (Figure 4-A). A toolbox (Figure 4-B) provides the design primitives. Finally, information concerning the pattern is also accessible through the tab property (Figure 4-C) by which GMF characterizes each object.

The Design Process

When designing a learning scenario, a teacher can elaborate a solution by combining the four types of patterns allowed by the meta-model (see Figure 1).

The design process is iterative and consists of the following steps (Figure 2):

1 -Instantiate the specifying requirements pattern: the teacher has to define the requirements of the pedagogical situation (objectives, resources, tools, learning strategy, actors, roles, etc.); 2 -Select a pattern: the teacher can choose an existing pattern or create a new one. According to the pedagogical context, the teacher defines parameters to select the most relevant pattern. He can choose one pattern among the four types of patterns proposed by the editor: a design pattern for specifying learning situations, an analysis pattern for human or material resources, a process pattern for tasks or activities or a pedagogical one for objectives.

3 -Merge the patterns: The teacher has to associate the selected pattern to the ones he has already selected during previous iterations. The scenario is updated with the selected pattern and both user's actions and pattern properties are analyzed in order to infer indicators.

-Collect context information:

Once the data analysis achieved, the indicators feed the design context and the adaptation rules could be fired.

-Adapt the solution:

The system proposes possible adaptations to the designer, according to the fired rules set. Adaptations could lead to provide some recommendations on the design method, or to propose patterns related to the user's action, or to suggest an evolution of the editor configuration, better suited for the design context. The user has always the adaptation under control with the possibility given to modify himself his profile. The pattern representing situations of learning are not directly operational on platforms. To implement the pattern, as it is illustrated by Figure 3, one needs to bind the information of patterns with the concept used in platforms. This binding can be realized with one or some model-tomodel transformation if a meta-model of the target platform exists, as our team has proposed [START_REF] Abedmouleh | Operationalization of Learning Scenarios on Open and Distance Learning platforms: the case of the Moodle Platform[END_REF]. 2 -The implementation activities in continuity of our approach.

The cycle continues with the realization (using) of the scenario. Data are collected from this realization and are transformed into tracks. Tracks are then analyzed and the information of this analysis is capitalized to be used in one future design.

CASE OF STUDY

TPWorks is a learning platform for lab session in automation training introduced in French technological engineering cursus. TPWorks facilitates the sharing of documents and digital resources.

Every lab session has to be well defined and planned in terms of chapters, sub-chapters ordered according to the teacher"s intention and motivation. Activities and resources associated have to be defined too (texts, media, and so on).

Observation requirements are also defined in this preliminary step in order to model indicators in relation with each facet of the design context. These indicators are to existing indicators and implemented with UTL (with the assistance of a computer specialist).

Once logged, the tool editor adapts the set of patterns to the user"s design context and configures parameters of the tool according to its profile.

Rooted in this context, we relate here the instantiation of some iterations of the teachers"s design process.

First iteration of the design process

Step 1

The teacher defines the name of the session as "Dynamic behavior of a mechanical charge". Lab session content is composed of the following sections:

 A short presentation of the system the students will use.

 An explanation of the technical problems they may deal with.  A list of the different tasks to be realized.  Additional activities to extent the learning.  Digital resources for the lab work.

The teacher has to book the classroom, the electronical equipment, prepare the classroom, check equipment and define the lab session scenario.

Step 2

The teacher defines his intentionthat means the way he wants to create his scenarios. He may build the scenario by defining first the learning objectives, then resources needed, and so on. But here, the teacher has preferred describing first the learning situation. So he selects the design primitive associated to the "learning situation" concept.

The editor proposes a list of design patterns related to all types of existing learning situations. The teacher may filter the pattern list with the terms "lab work" and "implement". The resulting list is ordered and highlights, at the top, the proposals related to one of the terms or both. Among these choices, the teacher selects the pattern "Implementation for a lab work".

Step 3

The editor adds the selected pattern to the graphical representation of the solution part (Figure 4-A). The scenario is updated with the selected pattern.

Step 4

Indicators associated to the filters are updated. The concepts used to filter patterns list are added to the domain facet if they were not already among the domain concepts. The facet "Context of use" is updated too.

Step 5

The tool adapts the list of concepts to retrieve patterns lists. The pattern "Implementation for a lab work" is composed of a problem and activities. The teacher only needs to modify the solution to apply it to its learning situation.

Second iteration of the design process

Step 1

Issue of the first iteration is compliant with the teacher requirements and he does not specify new ones.

Step 2

When he selects the primitive "activity" in the graphical part, the editor proposes a list of all existing activities. The activities related to the selected learning situation are in the top of the list. The teacher creates a new activity rather than to select an activity in the set of existing activities.

Step 3

The scenario is updated and this activity is added to the solution.

Step 4

The indicators related to this design activity (add an activity) are updated. The method of the indicator "Concept in the Domain Vocabulary" checks if the concept "TPWorks" is part of the current domain facet and if not the domain facet the concept is updated.

Step 5

The tool proposes to adapt the solution by adding the resource material "Computer with TPWorks ".

Third iteration of the design process

Step 1

The teacher analyzes the solution and refines the list of activities and resources needs.

Step The teacher needs to define human resources. He 2 adds an analysis pattern to the solution and selects or defines the resources he needs in the resources list. He selects the resource "IT technician".

Step 3

The scenario is updated with this human resource.

Step 4

The method of the associated indicator identifies this analysis pattern as a new one and adds the resource "IT Technician" in the "Institutional Context" facet.

Step 5

The tool adapts the set of proposed patterns (add ""IT Technician" resource) in the list of analysis patterns.

Fourth iteration of the design process

Step 1

The teacher analyzes the solution and refines the list of activities and resources needs.

Step 2 He chooses to create an association between the activities "Implemention of a lab work with TPWorks" and "Define a scenario for a lab work session".

Step 3

The solution is updated with the new association.

Step 4

The method of indicators associated to the observation needs "Associations between activities" for two patterns checks if this association has been already defined and add it to "Context of use" facet.

Step 5

The tool proposes to the user to define an association between existing patterns in the design context to complete the solution.

Finally, the teacher adds the learning objectives selected in a list to complete the solution. He changes the property field "Participant" in order to add the number of expected students (cf Figure 5). For deploying on TPWorks the resulting design, the teacher has finally to detail the activity "Define a scenario for a lab work session" with some sub-activities (as "short presentation", "technical problems", and so on). These activities will be implemented as Web pages in TPWorks. The link between the activities and the web pages can be seen as a transformation rule with a transformation Modelto-Model, even if we have not yet implemented this feature.

CONCLUSION AND FUTURE WORKS

The evolution of the educational context and technologies requires the teachers to be able to adapt their practices. They have to explicit and to formalize their practices as well as to acquire designer"s competencies. We propose in this paper an adaptive user-centered patternbased learning design approach to help teachers in their learning design activity. An editing tool is proposed to support this approach. This tool is generated into the EMF-GMF framework from a given meta-model of patterns. The tool could be adapted to the user"s characteristics (user"s profile, user"s activities…) and allows the teacher to design a learning scenario by using a domain-specific visual language (expressing patterns in the teacher"s business language). This approach is part of an engineering process which includes in particular an implementation process based, for example, on a binding with the meta-model of the targeted LMS. We do not have yet tested our research proposition with teachers but, by developing the tool presented here, we have made the demonstration of its technical feasibility. Further works will be focused on the refinement of the adaptation process.

  A study of the TEL domain combined to a review of the type of patterns available in software engineering, leaded us to select the following four types of patterns, thus the four concepts of a meta-model of patterns: -Pedagogical Patterns are well-suited for describing learning objective or strategy. They are structured around Forces (how forces or constraints interact on pattern), Resulting Context (the result after the pattern has been applied) and Rationale (why one has selected this pattern).[16] -We have chosen Analysis Patterns for describing material or human resources because of their structure which allows to define the use of a material or a role. [17] -Process Patterns could describe the activities and the tasks realized as a workflow of the actions or subtasks.[18] -Design Patterns are used to characterize the learning situation. Design Patterns are usually composed of several sections: motivation (description of the problem stated and the context where the pattern can be used), participant (list of classes and objects used in the pattern and their design role) and/or collaboration (description of the way classes and objects used in the pattern interact with each other).[19]

Figure 1 :

 1 Figure 1: Meta-model of Patterns

  instructional design task) which falls into five facets characterizing the design context. : -The User Profile is made of information on user and editing tool configuration. As an example, a registered information of this profile is for instance the level of adaptation proposed by the tool and/or fixed by the designer (automatically, with user's confirmation, minimum adaptation ...) -The Learning context qualifies the learning strategies defined by the designer. -The Institutional context is a set of information on the constraints and the limits stated by the institution (classroom, materials ...). -The Domain facet gathers the information concerning the concepts of the learning domain. An example of domain indicator is the "Concept in the Domain Vocabulary". This indicator checks if a concept used as a property for qualifying a given pattern is part of the current domain facet. This is operationalized by a simple toggle rule as "if the current concept is in the vocabulary, then search a pattern containing this term". -The Context of use gathers information during the designing session in order to qualify the nature of the task. Indicators of the design context cannot be strictly related to one of these facets which are interrelated and some indicators can feed several facets.

Figure 2 :

 2 Figure 2: The design process

Figure 3 :

 3 Figure 3: Cycle of a pedagogical scenario 1 -The part of the cycle concerned by our pattern based approach.2 -The implementation activities in continuity of our approach.The cycle continues with the realization (using) of the scenario. Data are collected from this realization and are transformed into tracks. Tracks are then analyzed and the information of this analysis is capitalized to be used in one future design.

Figure 4 :

 4 Figure 4: The design tool editor of learning scenario

Figure 5 :

 5 Figure 5: Design Pattern "Implementation of a lab work session with TPWorks"


Firas Abdallah
email: firas.abdallah@lium.univ-lemans.fr

Claudine Toffolon
email: claudine.piau-toffolon@lium.univ-lemans.fr

Bruno Warin
email: warin@iutcalais.univ-littoral.fr

Models transformation to implement a Project-Based Collaborative Learning (PBCL) scenario: Moodle case study

In this paper, a Project-Based Collaborative Learning (PBCL) meta-model is proposed. It allows a teacher to build up a PBCL scenario and to implement it in a learning system which is not designed to this learning method. A MDA (Model Driven Architecture) approach is described to elaborate transformation rules between the PBCL metamodel and that of the learning system. Moodle platform, used in the UIT of Laval, is the chosen case study.

Introduction

The work described in this paper focuses on the definition, specification, design, and implementation of learning situation supported by ICT (Information and Communication Technologies), especially, Project-Based Collaborative Learning (PBCL). PBCL is often recommended in the academic world. It has been a part of the instructional culture since Dewey, Decroly, Freinet, etc. and it is opposed to the behaviorist pedagogy which is based on a unilateral and passive transmission of the knowledge from the teacher to the student.

The specification of PBCL situation is described by learning scenario. The traditional approach is mainly focused on mechanisms that facilitate the (re)engineering, repurposing and the effective use of existing digital resources to support learning and teaching (depending on the platform selected). A new approach recommends starting from a learning scenario to lead to a learning system such as a web site for example. According to this approach, the learning scenario is the central part of a learning environment [START_REF] Pernin | Dispositifs d'apprentissage instrumentés par les technologies : vers une ingénierie centrée sur les scénarios[END_REF].

To allow teacher to elaborate a PBCL scenario, a meta-model dedicated to the PBCL is proposed. This meta-model is briefly described in section 2. It is explained in details in [START_REF] Abdallah | Assistance to projectbased learning support: from learning models to platforms[END_REF]. The PBCL meta-model is a challenging proposal to the limits of existing approach to express PBCL scenario. In particular, the major proposal made by the IMS Global Learning Consortium, the Instructional Management Systems-Learning Design (IMS-LD) [START_REF] Norm | IMS Learning Design (Best Practice Guide, Information Binding, Information Model)[END_REF][START_REF] Koper | Current Research in Learning Design[END_REF], is not satisfying to express a PBCL scenario by teachers. Many experiments have been carried out that shown the limits of this approach [START_REF] Burgos | IMS Learning Design: la flexibilité pédagogique au service des besoins de l'e-formation[END_REF][START_REF] Martel | Modelling the case study with LDL and implementing it with LDI[END_REF]. A meta-model is a domain specific modeling language which is used to express the common concepts for models in the same area. It is build from informal models, recommendations in a natural language and semiformal models usually written in the Unified Modeling Language (UML).

Most of commercial or open sources learning systems are available [7], but none of these systems seems to be adapted to PBCL context. In the present study, the strategy is to assist the teacher to implement his PBCL scenario in the chosen target platform, rather than developing a new one. A models transformation approach is proposed allowing the integration of the PBCL scenarios in a platform. The Model Driven Architecture (MDA) oriented approach in the software engineering domain [START_REF]Technical Guide to Model Driven Architecture[END_REF] can be recommended in the instructional engineering field as well. Indeed we support a design approach based on models, so-called Model-Driven Engineering (MDE). In the MDE software process methodology, refining models develops a system. The model transformation technique is a principle key within this approach. It allows traceability between the different models produced at the different abstraction levels. Within this approach, teachers can design a learning scenario based on the PBCL meta-model. Then, this scenario is adapted to a chosen platform. To illustrate this proposal, Moodle platform is taken as a case study being used in the University Institute of Technology (UIT) of Laval.

Project-Based Collaborative Learning (PBCL) meta-model

The PBCL meta-model is built according PBCL concepts, theories (theoretical study), and practices (empirical study). From the existing literature on this topic, George PBCL characteristics were selected [START_REF] George | SPLACH: a Computer Environment Supporting Distance Project-Based Learning[END_REF] to describe the Project-Based Collaborative Learning. This meta-model is presented as a diagram class in UML language (Figure 1). The construction manner of this PBCL meta-model is explained in details in [START_REF] Abdallah | Assistance to projectbased learning support: from learning models to platforms[END_REF]. An example of a PBCL scenario is developed that conforms to PBCL meta-model. This scenario was elaborated for the first year INFO at the UIT of Laval starting from PBCL meta-model. To elaborate this scenario, ModX tool is used [START_REF]ModX[END_REF]. This is a graphic tool allowing creating both model (PBCL scenario) and MOF-based meta-model (PBCL meta-model). It supports XMI format in order to be compatible with other MDA tools (The XMI file of PBCL scenario generated will be used in ATL transformation tool). To elaborate the PBCL scenario model, a PBCL metamodel has to be created (Figure 1). The PBCL scenario (model level) is created in a graphical way. It consists of proposing to students a computer development project. This project is made of steps (from the "project definition" step to the "validation" one). These steps are divided into tasks. For all these steps and tasks, prerequisites, objectives, learning objectives, tools, productions, and evaluation factors have been defined. To be completed, the scenario is accomplished by a clear definition of all actors (Student, designer, expert, and tutor) and their roles (Facilitator, writer, technical, etc. role).

Introduce MDA approach in learning instructional design

To reconcile the two approaches: learning and technology, a MDA approach is adopted. This development approach proposed by OMG (Object Management Group) divides the vision of a system in three focal points of view [START_REF]Technical Guide to Model Driven Architecture[END_REF]: The Computation Independent Model (CIM) corresponding to a domain model is independent of any computer implementation. The Platform Independent Model (PIM) is a view of a system from the platform independent viewpoint. The Platform Specific Model (PSM) is a view of a system from the platform specific viewpoint.

Through the three MDA models CIM / PIM / PSM, MDA seems appropriate for learning scenarios. The viewpoint of Laforcade et al. [START_REF] Laforcade | Scénarisation Pédagogique et Ingénierie Dirigé par les Modèles. Cadre d'étude pour la définition de langages et environnements-outils de scénarisation pédagogique spécifiques à des domaines[END_REF] is adopted. It proposes a new framework inspired by that of MDA. This new framework is represented by the proposal for different types of possible learning scenarios. These learning scenarios are categorized into three types and inspired by three MDA viewpoints: 1) Scenario at Knowledge level (SK): captures the teacher's common vocabulary associated with specific learning approaches, known platforms. The purpose of this scenarios type is to guide and facilitate (to the teacher of a community) design activity used in defining the learning scenario. 2) Abstract Scenario (AS): its vocabulary is independent from that of the e-learning platform (IMS-LD). 3) Specific Scenario to an e-learning platform (SS): its vocabulary is consistent with that of a specific platform.

The software engineering process requires consideration of the three MDA approach viewpoints. However, the learning scenario process does not necessarily take into account these three aspects [START_REF] Laforcade | Scénarisation Pédagogique et Ingénierie Dirigé par les Modèles. Cadre d'étude pour la définition de langages et environnements-outils de scénarisation pédagogique spécifiques à des domaines[END_REF]. That means it is entirely appropriate to make the transformation of SK to SS. Since the PBCL metamodel captures the common vocabulary related to the Project Based Collaborative Learning, the PBCL scenario proposed above is situated at SK level. On the other hand, the PBCL scenario able to be implemented in Moodle is situated at the SS one, having a vocabulary that corresponds to the Moodle platform.

Transforming PBCL scenario to PBCL scenario able to be implemented in Moodle

Transformation activities are performed as automated processes that take one or more source models as inputs and produce one or more target models as outputs, while following a set of transformation rules. This process is referred as model transformation [START_REF] Sendall | Model Transformation: The Heart and Soul of Model-Driven Software Development[END_REF]. The transformation of MDA model is established by a relation (mapping) between a source model and a target one. Each model is described by a meta-model, which identifies the model characteristics. The mapping is then defined as a translation between the initial meta-model and the target one.

ATL transformation language

To make transformation, it is necessary to have transformation tools. These tools are based on transformation language having to respect the QVT (Query / Views / Transformations) standard [START_REF]OMG/RFP/QVT MOF 2.0 Query/Views/Transformations RFP[END_REF]. In the measurement of our work, the commercial tools (e.g. MIA) are excluded. Among a number of "free" tools such as MTF, MTL, QVTP... ATL (Atlas Transformation Language) is selected because it answers best the problems of models transformation [START_REF] Canals | Une Utilisation opérationnelle d'ATL : l'intégration de la transformation de modèles dans le projet TOPCASED[END_REF].

The ATL abstract syntax is specified as a MOF meta-model and a corresponding textual concrete syntax has been defined [START_REF] Bézivin | First experiments with the ATL model transformation language: Transformation XSLT into XQuery[END_REF]. In the field of Model-Driven Engineering (MDE), ATL provides developers with a mean to specify the way to produce a number of target models from a set of source models [START_REF]Atlas Transformation Language -ATL User Manual[END_REF]. ATL is made available as a part of the ATL Development Tools (ADT). The current ADT distribution runs over the Eclipse platform, and is based on the Eclipse Modeling Framework (EMF) [START_REF] Budinsky | Eclipse Modeling Framework[END_REF].

Transformation rules

In the field of model engineering, models are considered as first class entities. A model has to be defined according to the semantics provided by its meta-model: a model is said to conform to its metamodel. In the same way, a meta-model has to conform to a meta-meta-model. In this three layers architecture (models, meta-models, meta-meta-model), the metameta-model usually self-conforms to its own semantics (e.g. it can be defined using its own concepts). Existing meta-meta-models include, by example, MOF [START_REF]OMG/RFP/QVT MOF 2.0 Query/Views/Transformations RFP[END_REF], defined by the OMG and Ecore [START_REF] Budinsky | Eclipse Modeling Framework[END_REF], introduced with the Eclipse Modelling Framework (EMF) [START_REF] Budinsky | Eclipse Modeling Framework[END_REF].

A major feature in model engineering is to consider, as far as possible, all handled items as models. The model transformation itself has to be defined as a model. This transformation model has to conform to a transformation meta-model that defines the model transformation semantics. As the other meta-models, the transformation meta-model has, in turn, to conform to the considered meta-metamodel. Moodle.ecore) and the ATL transformation (PBCL2Moodle.atl) that will be handled during the design of the PBCL to Moodle ATL transformation. Note that the transformation to be designed (PBCL2Moodle.atl) will have to conform to the ATL transformation meta-model. The ATL syntax is detailed in [START_REF]Atlas Transformation Language -ATL User Manual[END_REF].

A rule defines the "mapping" between the classes of the meta-models as well as the handling rules of the attributes and the classes relations. Performing a model transformation requires a clear understanding of the abstract syntax and semantics of both the source and target. The source PBCL meta-model was presented in Figure 1, and now a vision of the target Moodle platform meta-model is shown (Figure 3).

Figure 3.Moodle meta-model

In general, the transformations between two different domains are difficult to be implemented in practice since the two meta-models specifying the concepts and relations of each domain are able to be close but also very distant in terms of semantic "distance". Moreover, certain meta-model concepts/relations do not have necessarily "neighbour" all corresponding (concepts/relations) in the other one (and vice versa): such transformations can thus produce semantic losses (certain information specified in a scenario disappears) [START_REF] Laforcade | Scénarisation Pédagogique et Ingénierie Dirigé par les Modèles. Cadre d'étude pour la définition de langages et environnements-outils de scénarisation pédagogique spécifiques à des domaines[END_REF]. Twelve transformation rules are elaborated from the PBCL meta-model towards the Moodle one. These transformation rules have two goals: the first one is the PBCL scenario implementation in the Moodle platform techno-centred universe. The second one is the semantic loss qualification, compared to the PBCL, of each rule application. In the table below (Table 1), an example of this transformation rules elaborated since PBCL meta-model towards the Moodle one is shown:

Table 1

. Transformation rules

For example, the Step2Course rule consists of simple and 'complex' codes: A matched rule (Step2Course) is composed of a source pattern and a target pattern. The source pattern of a matched rule is defined after the keyword "from". It enables to specify a variable model element that corresponds to the type of source elements the rule has to match. The target pattern of a matched rule is introduced by the keyword "to". It specifies the elements to be generated when the source pattern of the rule is matched, and how these generated elements are initialized. This rule aims to produce a "Course" model element from a "Step" model element. It initializes the Full_name, Course_ID_number, Start_date, End_date and Summary features of the generated "Course". The bindings also enable to initialize reference features (line 11). The Full_name of the "Course" corresponds to the Project_title of the "Project" concatenated with the Step_title of the "Step". The Course_ID_number, Start_date, and End_date, of the "Course" correspond to the Step_number, Step_start_date, and Step_end_date of the "Step". Moodle does not have an equivalent element of the LearningObjective in PBCL. Then, a helper is used in line 10 (correspond to a function in Java) to regroup all LearningObjective values in the Summary attribute of the "Course", without any duplicate. The written helper is shown below. if acc = '' 7.

then LearObj 8.

else ' and ' + LearObj 9.

endif);

Results

As result, the PBCL scenario elaborated by ModX (represented in ecore format on the left of Figure 4) is successfully converted to a PBCL scenario able to be implemented in Moodle (represented in ecore format on the right of the Figure 4). The instructional engineer, expert in Moodle platform, can now deploy the transformed scenario in the platform.

Conclusion

Transforming a PBCL scenario into a PBCL scenario able to be implemented in Moodle renders possible to draw up a communication bond between the teacher and the instructional engineer. The teacher, expert in the PBCL domain, can now elaborate his scenario by using the proposed PBCL meta-model. Then, he can transform it into a PBCL scenario which can be implemented in Moodle, using the developed transformation rules. The transformed PBCL scenario is given to the instructional engineer who is charged to deploy it in Moodle.

The current state of transformation rules requires installation of the Eclipse platform and some plug-ins, plus the loading of the PBCL scenario to be transformed from ModX. This process is not obvious to the teacher. Thus, a graphical interface tool will be developed. It will help the teacher uploading his PBCL scenario generated by ModX and using the developed transformation rules. As future work, the process of automation will be continued to enable the teacher deploying its PBCL scenario into the target platform with less instructional engineer support.

Figure 1 .

 1 Figure 1. PBCL meta-model

Figure 2 .

 2 Figure 2. PBCL to Moodle ATL transformation Figure 2 provides an overview of the PBCL to Moodle ATL transformation process. This figure introduces the name of the files (in italics) that are going to encode the models (PBCLscenario.ecore generated by ModX in a XMI file, PBCL_Moodle_Scenario.ecore), the meta-models (PBCL.ecore,Moodle.ecore) and the ATL transformation (PBCL2Moodle.atl) that will be handled during the design of the PBCL to Moodle ATL transformation. Note that the transformation to be designed (PBCL2Moodle.atl) will have to conform to the ATL transformation meta-model. The ATL syntax is detailed in[START_REF]Atlas Transformation Language -ATL User Manual[END_REF].A rule defines the "mapping" between the classes of the meta-models as well as the handling rules of the attributes and the classes relations. Performing a model transformation requires a clear understanding of the abstract syntax and semantics of both the source and target. The source PBCL meta-model was presented in

1 .

 1 helper context PBCL!Step def: getStepLearningObjective(): String = 2. self.StepHasLO->collect(e | e.Description)

Figure 4 .

 4 Figure 4. PBCL scenario and transformed PBCL scenario


Antoine Joux
email: antoine.joux@m4x.org

Cécile Pierrot
email: cecile.pierrot@lip6.fr

Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations

Keywords: Sparse Linear Algebra, Block Wiedemann, Discrete Log, Finite Fields

In this article 1 , we propose a method to perform linear algebra on a matrix with nearly sparse properties. More precisely, although we require the main part of the matrix to be sparse, we allow some dense columns with possibly large coe cients. This is achieved by modifying the Block Wiedemann algorithm. Under some precisely stated conditions on the choices of initial vectors in the algorithm, we show that our variation not only produces a random solution of a linear system but gives a full basis of the set of solutions. Moreover, when the number of heavy columns is small, the cost of dealing with them becomes negligible. In particular, this eases the computation of discrete logarithms in medium and high characteristic finite fields, where nearly sparse matrices naturally occur.

Introduction

Linear algebra is a widely used tool in both mathematics and computer science. At the boundary of these two disciplines, cryptography is no exception to this rule. Yet, one notable di↵erence is that cryptographers mostly consider linear algebra over finite fields, bringing both drawbacks -the notion of convergence is no longer available -and advantages -no stability problems can occur. As in combinatory analysis or in the course of solving partial di↵erential equations, cryptography also presents the specificity of frequently dealing with sparse matrices. For instance, sparse linear systems over finite fields appeared in cryptography in the late 70s when the first sub-exponential algorithm to solve the discrete logarithm problem in finite fields with prime order was designed [START_REF] Adleman | A subexponential algorithm for the discrete logarithm problem with applications to cryptography[END_REF]. Nowadays, every algorithm belonging to the Index Calculus family deals with a sparse matrix [START_REF] Joux | The past, evolving present and future of discrete logarithm[END_REF]Section 3.4]. Hence, since both Frobenius Representation Algorithms (for small characteristic finite fields) and discrete logarithm variants of the Number Field Sieve (for medium and high characteristics) belong to this Index Calculus family, all recent discrete logarithm records on finite fields need to find a solution of a sparse system of linear equations modulo a large integer. Similarly, all recent record-breaking factorizations of composite numbers, which are based on the Number Field Sieve, need to perform a sparse linear algebra step modulo 2.

A sparse matrix is a matrix containing a relatively small number of coe cients that are not equal to zero. It often takes the form of a matrix in which each row (or column) only has a small number of non-zero entries, compared to the dimension of the matrix. With sparse matrices, it is possible to represent in computer memory much larger matrices, by giving for each row (or column) the list of positions containing a non-zero coefficient, together with its value. When dealing with a sparse linear system of equations, using plain Gaussian Elimination is often a bad idea, since it does not consider nor preserve the sparsity of the input matrix. Indeed, each pivoting step during Gaussian Elimination may increase the number of entries in the matrix and, after a relatively small number of steps, it overflows the available memory.

Thus, in order to deal with sparse systems, a di↵erent approach is required. Three main families of algorithms have been devised: the first one adapts the ordinary Gaussian Elimination in order to choose pivots that minimize the loss of sparsity and is generally used to reduce the initial problem to a smaller and slightly less sparse problem. The two other al-gorithm families work in a totally di↵erent way. Namely, they do not try to modify the input matrix but directly aim at finding a solution of the sparse linear system by computing only matrix-by-vector multiplications. One of these families consists of Krylov Subspace methods, adapted from numerical analysis, and constructs sequences of mutually orthogonal vectors. For instance, this family contains the Lanczos and Conjugate Gradient algorithms, adapted for the first time to finite fields in 1986 [START_REF] Coppersmith | Discrete Logarithms in GF[END_REF].

Throughout this article, we focus on the second family that contains Wiedemann algorithm and its generalizations. Instead of computing an orthogonal family of vectors, D. Wiedemann proposed in 1986 [START_REF] Douglas | Solving sparse linear equations over finite fields[END_REF] to reconstruct the minimal polynomial of the considered matrix. This algorithm computes a sequence of scalars of the form t wA i v where v and w are two vectors and A is the sparse matrix of the linear algebra problem. It then tries to extract a linear recurrence relationship that holds for this sequence. In 1994, to achieve computations in realistic time, D. Coppersmith [START_REF] Coppersmith | Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm[END_REF] adapted the Wiedemann algorithm over the finite field F 2 for parallel and even distributed computations. One year later E. Kaltofen [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF] not only generalized this algorithm to arbitrary finite fields but also gave a provable variant of Coppersmith's heuristic method. The main idea of Coppersmith's Block Wiedemann algorithm is to compute a sequence of matrices of the form

t W A i
V where V and W are not vectors as previously but blocks of vectors. This step is parallelized by distributing the vectors of the block V to several processors or CPUs -let us say c of them. The asymptotic complexity of extracting the recursive relationships within the sequence of small matrices is in Õ(cN2 ) where N is the largest dimension of the input matrix. Another algorithm was presented by B. Beckerman and G. Labahn in 1994 [START_REF] Beckermann | Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants[END_REF] for performing the same task in subquadratic time and a further improvement was proposed by E. Thomé [START_REF] Thomé | Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann Algorithm[END_REF] in 2002: he reduced the complexity of finding the recursive relationships to Õ(c 2 N ). The current fastest method is an application of the algorithm proposed by P. Giorgi, C-P. Jeannerod and G. Villard in 2003 [START_REF] Giorgi | On the complexity of polynomial matrix computations[END_REF] which runs in time Õ(c ! 1 N ), where ! is the exponent of matrix multiplication. At the time of writing the best known 2 asymptotic value of this exponent is ! ⇡ 2.37286. It comes from a slight improvement of Coppersmith-Winograd algorithm [START_REF] Coppersmith | Matrix Multiplication via Arithmetic Progressions[END_REF] due to F. Le Gall [START_REF] François | Powers of tensors and fast matrix multiplication[END_REF] and published in 2014.

Note that both Krylov Subspace methods and Wiedemann algorithms Sparse part d Dense columns cost a number of matrix-by-vector multiplications equal to a small multiple of the matrix dimension: for a matrix containing entries per row in average, the cost of these matrix-by-vector multiplications is O( N 2 ). With Block Wiedemann, it is possible to distribute the cost of these products up to c machines. In this case, the search for recursive relationships adds an extra cost of the form Õ(c ! 1 N ). For a nearly sparse matrix, which includes d dense columns in addition to its sparse part, the cost of matrixby-vector multiplications increases. As a consequence, the total complexity becomes O(( + d)N 2 ) with an extra cost of Õ(c ! 1 N ) for Block Wiedemann. Figure 1.1 provides a quick overview of the structure of such nearly sparse matrices.

In this article, we aim at adapting the Coppersmith's Block Wiedemann algorithm to improve the cost of linear algebra on matrices that have nearly sparse properties and reduce it to O( N 2 ) + Õ(max(c, d) ! 1 N ). In particular, when the number of dense columns is lower than the number of processors used for the matrix-by-vector steps, we show that the presence of these unwelcome columns does not a↵ect the complexity of solving linear systems associated to these matrices. In practice, this result precisely applies to the discrete logarithm problem. Indeed, nearly sparse matrices appear in both medium and high characteristic finite fields discrete logarithm computations. To illustrate this claim, we recall the latest record [START_REF] Bouvier | Discrete logarithms in GF(p) -180 digits[END_REF] announced in June 2014 for the computation of discrete logarithms in a prime field F p , where p is a 180 digit prime number. It uses a matrix containing 7.28M rows and columns with an average weight of 150 non-zero coe cients per row and also presents 4 dense Schirokauer maps columns. These columns precisely give to the matrix the nearly sparse structure we study in the sequel.

Outline. Section 1.2 makes a short recap on Coppersmith's Block Wiedemann algorithm, which is the currently best known algorithm to perform algebra on sparse linear systems while tolerating some amount of distributed computation. We propose in Section 1.4 the definition of a nearly sparse matrix and present then a rigorous algorithm to solve linear algebra problems associated to these matrices. In Section 1.4.7 we give a comparison of our method with preexisting linear algebra techniques and show that it is potentially competitive even with a tremendous number of dense columns. Section 1.5 ends by a practical application of this result: it explains how nearly sparse linear algebra eases discrete logarithm computations in medium and high characteristic finite fields.

A Reminder of Block Wiedemann Algorithm

This section first presents the classical problems of linear algebra that are encountered when dealing with sparse matrices. We then explain how the considered matrix is preconditioned into a square matrix. Section 1.2.2 draws the outline of the algorithm proposed by Wiedemann to solve linear systems given by a square matrix whereas Section 1.2.3 presents the parallelized variant due to Coppersmith. More precisely, the goal is to solve: Problem 1.1. Let K = Z/pZ be a prime finite field and S 2 M n⇥N (K) be a (non necessarily square) sparse matrix with at most non-zero coe cients per row. Let ṽ be a vector with n coe cients. The problem is to find a vector x with N coe cients such that S • x = ṽ or, alternatively, a non-zero vector x such that S • x = 0.

In practice, this problem is often generalized to rings Z/N Z for a modulus N of unknown factorization. However, for simplicity of exposition, and due to the fact that the algorithm of [START_REF] Giorgi | On the complexity of polynomial matrix computations[END_REF] is only proved over fields, we prefer to restrict ourselves to the prime field case.

Preconditioning: making a sparse matrix square

In order to be able to compute sequences of matrix-by-vector products of the form (A i ỹ) i>0 , both Wiedemann and Block Wiedemann algorithms need to work with a square matrix. Indeed, powers are only defined for square matrices. Consequently, if N 6 = n, there is a necessary preliminary step to transform the given matrix into a square one. For example, it is possible to pad the matrix with zeroes and then apply the analysis of [START_REF] Kaltofen | On Wiedemann's Method of Solving Sparse Linear Systems[END_REF] for solving linear systems which do not have full rank using Wiedemann's method. This is done by multiplying on the left and right by random matrices and then by truncating the matrix to a smaller invertible square matrix with the same rank as the original one.

In practice, heuristic methods are used instead. Typically, one creates a random sparse matrix R 2 M N ⇥n (K) with at most non-zero coe cients per row, and transform afterwards the two problems into finding a vector x such that (RS)x = Rṽ or, alternatively, such that (RS)x = 0. Setting A = RS and ỹ = Rṽ, we can rewrite Problem 1.1 as finding a vector x such that:

A • x = ỹ
or such that:

A • x = 0
depending on the initial problem. In addition, in order to avoid the trivial solution when solving Ax = 0, one frequently computes ỹ = Ar for a random vector r, solves Ax = ỹ and outputs x r as a kernel element.

We do not go further into the details of how preconditioning is usually performed. Indeed, we propose in Section 1.4.2 a simple alternative technique, that provably works with our algorithm for nearly sparse matrices, under some explicit technical conditions. Since sparse matrices are a special case of nearly sparse matrices, this alternative would also work for usual sparse matrices.

Wiedemann algorithm

Let us now consider a square matrix A of size N ⇥ N and denote m A the number of operations required to compute the product of a vector of K N by A. Wiedemann algorithm works by finding a non-trivial sequence of coe cients (a i ) 0iN such that:

N X i=0 a i A i = 0.
(1.1)

Solving Ax = ỹ. If A is invertible, then we can assume a 0 6 = 0. Indeed, if a 0 = 0 we can rewrite 0 = P N i=1 a i A i = A (

P N i=1 a i A i )
where a is the first non zero coe cient. Multiplying by (A 1 ) it yields the equality Algorithm 1.1 Wiedemann algorithm for Ax = ỹ

Input: A matrix A of size N ⇥ N , ỹ 6 = 0 a vector with N coe cients Output: x such that A • x = ỹ.
Computing a sequence of scalars

1: ṽ0 2 K N , w 2 K N two random vectors 2: for i = 0, • • • , 2N do 3: i w • ṽi 4: ṽi+1 Aṽ i 5: end for Berlekamp-Massey algorithm 6: From 0 , • • • , 2N recover coe cients (a i ) 0iN s.t. P N i=0 a i A i = 0 and a 0 6 = 0. Resolution 7: return (1/a 0 ) P N 1 i=1 a i+1 A i ỹ.
P N i=0 a i+ A i = 0. So, shifting the coe cients until we find the first nonzero one allows to write a 0 6 = 0. Let us apply Equation (1.1) to the vector x we are seeking. It yields

a 0 x = P N i=1 a i A i x = P N i=1 a i A i 1 (Ax). Finally we recover x = (1/a 0 ) P N i=1 a i A i 1 ỹ.
This last sum can be computed using N sequential multiplications of the initial vector ỹ by the matrix A. The total cost to compute x as this sum is O(N • m A ) operations.

Solving Ax = 0. Assuming that there exists a non-trivial element of the kernel of A, we deduce that a 0 = 0. Let again be the first index such that a 6 = 0. Thus, for any vector r we have 0 =

P N i= a i A i r = A ( P N i= a i A i r). We know that P N i= a i A i 6 = 0. Indeed, otherwise, a Id + P N i= +1 a i A i = a Id + A( P N i= +1 a i A i 1 ) = 0 would lead to A( (1/a ) P N i= +1 a i A i 1 ) =
Id, yet A is assumed non invertible. Thus, for a random vector r, the sum P N i= a i A i r is non zero with high probability: this vector is the zero vector if and only if r belongs to the kernel of the non null matrix P N i= a i A i . Since the kernel of a non null matrix has at most dimension N 1, the probability for a random vector to be in its kernel is upper bounded by

|K| N 1 /|K| N = 1/|K|. Now, computing iteratively A( P N i= a i A i r), A 2 ( P N i= a i A i r), • • • , A ( P N i= a i A i r) yields an element of the kernel of A in O(N • m A ) operations as well. Indeed, the first index j in [[1, ]] such that A j ( P N i= a i A i r) = 0 shows that A j 1 ( P N i= a i A i r) 6
= 0 belongs to the kernel of A. Thus, this method finds a non trivial element of Ker(A) with probability higher than (|K| 1)/|K|, which quickly tends to 1 as the cardinality of the field grows.

How to find coe cients a i verifying Equation (1.1). Cayley-Hamilton theorem testifies that the polynomial defined as P = det(A X • Id) annihilates the matrix A, i.e. P (A) = 0. So we know that there exists a polynomial of degree at most N whose coe cients satisfy Equation (1.1). Yet, directly computing such a polynomial would be too costly. The idea of Wiedemann algorithm is, in fact, to process by necessary conditions.

Let (a i ) i2[[0,N ]] be such that P N i=0 a i A i = 0. Then, for any arbitrary vector ṽ we obtain P N i=0 a i A i ṽ = 0. Again, for any arbitrary vector w and for any integer j we can write

P N i=0 a i t wA i+j ṽ = 0. Conversely, if P N i=0 a i t
wA i+j ṽ = 0 for any random vectors ṽ and w and for any j in [[0, N]] then the probability to obtain coe cients verifying Equation (1.1) is high, assuming the cardinality of the field is su ciently large [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF]. Thus, Wiedemann algorithm seeks coe cients a i that annihilate the sequence of scalars t wA i ṽ.

To do so, it can use the classical Berlekamp-Massey algorithm [START_REF] Berlekamp | Nonbinary BCH decoding[END_REF][START_REF] James | Shift-register synthesis and BCH decoding[END_REF] that finds the minimal polynomial of a recursive linear sequence in an arbitrary field. In a nutshell, the idea is to consider the generating function f of the sequence t wṽ, t wAṽ, t wA 2 ṽ, • • • , t wA 2N ṽ and to find afterwards two polynomials g and h such that f = g/h mod X 2N . Alternatively, the Berlekamp-Massey algorithm can be replaced by a half extended Euclidean algorithm, yielding a quasi-linear algorithm in the size of the matrix A.

Coppersmith's Block Wiedemann algorithm

The Block Wiedemann algorithm is a parallelization of the previous Wiedemann algorithm introduced by Don Coppersmith. It targets the context where sequences of matrix-vector products are computed on `processors, instead of one. In this case, rather than solving Equation (1.1), it searches, given `vectors ṽ1 , • • • , ṽ`, for coe cients a ij such that:

X j=1 dN/`e X i=0 a ij A i ṽj = 0 (1.2)
Note that the number of coe cients remains approximately the same as in the previous algorithm.

Solving Ax = 0. There, we choose `random vectors r1

Input: A matrix A of size N ⇥ N Output: x such that A • x = 0.
Computing a sequence of matrices

1: r1 2 K N , • • • , r` 2 K N and w1 2 K N , • • • , w` 2 K N 2: ṽ1
Ar 1 , • • • , ṽ` Ar 3: for any of the `processors indexed by j do 4:

u 0 v j 5:
for i = 0, • • • , 2dN/`e do 6:

for k = 1, • • • , `do 7: i,j,k wk • ũi 8: ũ i+1 A ũi 9:
end for

P j=1 P dN/`e i= a ij A i rj .
According to [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF], b is non zero with high probability. Hence, computing iteratively A b,

A 2 b, • • • , A b yields an element of the kernel of A in O(N • m A ) operations again. Indeed, the first index k in [[1, ]] such that A k b = 0 shows that A k 1 b is a non trivial element of the kernel of A.
Solving Ax = ỹ. In order to solve Ax = ỹ, several di↵erent approaches are possible. For example, in [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF] the size of A is increased by 1, adding ỹ as an new column and adding a new zero row. It is then explained that a random kernel element, as produced by the above method, involves ỹ and thus produces a solution of Ax = ỹ.

Another option is to set ṽ1 = ỹ and choose for i 2 [[2, `]] the vectors ṽi = Ar i , where each ri is a random vector of the right size and to assume that a 01 6 = 0. From Equation (1.2) we derive:

dN/`e X i=0 a i1 A i ỹ + X j=2 dN/`e X i=0 a ij A i+1 rj = 0.
Multiplying by the inverse of A, we obtain:

a 01 x + dN/`e X i=1 a i1 A i ỹ + X j=2 dN/`e X i=0 a ij A i rj = 0.
Thus, we can recover x by computing:

( 1/a 01 ) • 0 @ dN/`e X i=1 a i1 A i 1 ỹ + X j=2 dN/`e X i=0 a ij A i rj 1 A .
This can be done with a total cost of O(N • m A ) operations parallelized over the `processors: each one is given one starting vector ṽ and computes a sequence of matrix-by-vector products of the form A i ṽ. The cost for each sequence is O(N • m A /`) arithmetic operations. We do not deal here with the case where a 01 = 0 since Section 1.4 covers all cases for nearly sparse matrices, thus for sparse matrices.

How to find coe cients a i verifying Equation (1.2).

Let ṽ1 , • • • , ṽ`b e `vectors and let consider the `(dN/`e) elements obtained by the matrix-by-vector products of the form A i ṽj that appear in the sum of Equation (1.2). Since `(dN/`e) > N, all these vectors cannot be independent, so there exist coe cients satisfying (1.2). As for Wiedemann algorithm, we process by necessary conditions. More precisely, let w1 , . . . , w`b e `vectors. Assume that for any  in [[0, dN/`e]] and k in [[1, `]] we have P j=1 P dN/`e i=0 a ij t wk A i+ ṽj = 0, then the probability that the coecients a ij verify Equation (1.2) is close to 1 when K is large3 (again see [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF]). So Block Wiedemann algorithm looks for coe cients that annihilate the sequence of 2dN/`e small matrices of dimension `⇥`computed as ( t wk A ⌫ ṽj ). Here, ⌫ 2 [[0, 2dN/`e]] numbers the matrices, while k and j respectively denote the column and row numbers within each matrix. It is possible to compute the coe cients a ij in subquadratic time (see Section 1.3 for details). For instance, Giorgi, Jeannerod, Villard give an e cient method with complexity Õ(`! 1 N ). This is the final component needed to write Block Wiedemann as Algorithm 1.2.

Moreover, putting together the matrix-by-vector products and the search for coe cients, the overall complexity can be expressed as

O(N • m A ) + Õ(`! 1 N ).
Where the O(N • m A ) part can be distributed on up to `processors and the Õ(`! 1 N ) part is computed sequentially.

Remark 1.1. In this section, we assumed that the number of sequences ìs equal to the number of processors c. This is the most natural choice in the classical application of Block Wiedemann, since increasing `beyond the number of processors can only degrades the overall performance. More precisely, the change leaves the O(N • m A ) contribution una↵ected but increases Õ(`! 1 N ). However, since values of `larger than c are considered in Section 1.4, it is useful to know that this can be achieved by sequentially computing several independent sequences on each processor. In this case, it is a good idea in practice to make the number of sequences a multiple of the number of processors, in order to minimize the wall clock running time of the matrix-by-vector multiplications.

Minimal basis computations

In this section, we recall an important result of Giorgi, Jeannerod and Villard [START_REF] Giorgi | On the complexity of polynomial matrix computations[END_REF], used in Section 1.2 for presenting Block Wiedemann. This result is a key ingredient for the algorithm we describe in Section 1.4. Let K be a finite field and G a matrix of power series over K of dimension m ⇥ n with n < m, i.e. an element of K[[X]] m⇥n . For an approximation order b, we consider m-dimensional row vectors ũ(X) of polynomials that satisfy the equation:

ũ • G ⌘ 0 mod X b . (1.
3) For a vector of polynomial, we define its degree deg(ũ) as the maximum of the degree of the coordinates of ũ.

ũ = m X i=1 c i Mi .
Giorgi, Jeannerod and Villard give an algorithm that computes a -basis for Equation (1.3) using Õ(m ! b) algebraic operations in K. Note that for practical implementations, especially with small values of m, ! should be replaced by 3, thus matching the complexity of the related algorithm given by Thomé [START_REF] Thomé | Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann Algorithm[END_REF].

Nearly Sparse Linear Algebra

In this section, our aim is twofold. We first aim at adapting the Block Wiedemann algorithm to improve the resolution of some linear algebra problems that are not exactly sparse but close enough to be treated similarly. We also give more precise conditions on the choices of the vectors ṽi and wi that are made in Block Wiedemann algorithm. Rather than insisting on random choices as in [START_REF] Kaltofen | Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems[END_REF] we give explicit conditions on these choices. When the conditions are satisfied, we show that our algorithm not only recovers a random solution of the linear system of equations given as input but, in fact, gives an explicit description of the full set of solutions.

The cornerstone of our method consists in working with the sparse part of the matrix while forcing part of the initial vectors of the sequences computed by Block Wiedemann algorithm to be derived from the dense columns of the matrix in addition to random initial vectors. In the rest of this section, we describe this idea in details.

Nearly sparse matrices

In the sequel we focus on linear algebra problems of the following form: Problem 1.2. Let M be a matrix of size N ⇥ (s + d) with coe cients in a field K. We assume that there exist two smaller matrices M s 2 M N ⇥s (K) and M d 2 M N ⇥d (K) such that :

(1) M = M s |M d , where | is the concatenation of matrices. 4 (2) M d is arbitrary.

(3) M s is sparse. Let us assume it has at most non-zero coe cients per row.

If ỹ is a given vector with N coe cients, the problem is to find all vectors x 4 Our method would also work for matrices with d dense columns located at any position. It would su ce to reorder the columns of the linear algebra problem. However, for simplicity of exposition, we assume the dense columns are the d final columns of M .

with s + d coe cients such that:

M • x = ỹ
or, alternatively, such that:

M • x = 0.
Such a matrix M is said to be d-nearly sparse, or as a shortcut, simply nearly sparse when d is implied by context. Note that, in our definition, there is no a priori restriction on the number of dense columns that appear in the matrix. An interesting consequence of the fact that we want to construct all the solutions of these linear algebra problems is that we only need to deal with the second (homogeneous) sub-problem of Problem 1.2. Indeed, it is easy to transform the resolution of M •x = ỹ into the resolution of M 0 • x0 = 0 for a nearly sparse matrix M 0 closely related to M . It su ces to set M 0 = M |ỹ the matrix obtained by concatenating one additional dense column equal to ỹ to the right of M . Now we see that x is a solution of M

• x = ỹ if and only if x0 = t ( t x| 1) is a solution of M 0 • x0 = 0.
Keeping this transformation in mind, in the sequel we only explain how to compute a basis of the kernel of a nearly sparse matrix. When solving the first (a ne) sub-problem, we just need at the end to select in the kernel of M 0 the vectors with a 1 in the last position.

Thus, the two variants that appear in Problem 1.2 are more directly related in our context than their counterparts in Problem 1.1 are in the context of the traditional (Block) Wiedemann algorithm.

With such a nearly sparse matrix M , it would of course be possible to directly apply the usual Block Wiedemann algorithm and find a random element of its kernel. However, in this case, the cost of multiplying a vector by the matrix M becomes larger, of the order of ( + d)N operations. As a consequence, the complete cost of the usual Block Wiedemann algorithm becomes O(( + d) • N 2 ) + Õ(`! 1 N ) when using `processors.

Figure 1.3 gives a roadmap of the various steps we go through in order to obtain an e cient bijection between the kernel of M and a subset of the solutions resulting from a minimal basis computation using the algorithm of Giorgi, Jeannerod and Villard.

Preconditioning for a nearly sparse matrix

If N = s, the matrix is already square and nothing needs to be done. Note the case N < s does not usually appear in applications such as discrete logarithm computations where extra equations can easily be added. In the rare event where this case would appear, the simplest approach to deal with it is probably to artificially move s N columns from the sparse part to the dense part of the matrix. After this, the dense part becomes square (N ⇥ N ) while the number of columns in M d increases to

d 0 = d + s N .
So in the sequel we focus on the case where the sparse part of M has more rows than columns, namely N > s. To turn the sparse part of M into a square matrix, a simple method consists in embedding the rectangular matrix M s into a square one A by adding N s zero columns5 at the right side of M s .

Finding an element t (x s , x d ) in the kernel of M is equivalent to finding a longer vector t (x s , x tra , x d ) in the kernel of (A|M d ), where x s , x tra and x d are respectively row vectors of K s , K N s and K d (x tra denotes the extraneous coordinates).

In the sequel, we focus on the matrix A regardless of how it has been constructed.

Preliminary transformations with conditions

We set B an integer to be determined later (see Section 1. where the coe cients a 0j are zeroes for j > d. Conversely (whether or not condition (1.4) is satisfied) any solution of Equation (1.5) with zeroes on these positions yields an element of the kernel of (A|M d ). Thus, under condition (1.4), determining the kernel of (A|M d ) is equivalent to finding a basis of the solutions of Equation (1.5) with the ` d aforementioned zeroes.

Condition on W .

Of course, Equation (1.5) can be seen as a system of N linear equations over K. However, solving it directly would not be more e cient than directly computing the kernel of M . Instead, we remark that for any matrix

W = ( w1 | • • • | w`) consisting in `columns of vectors in K N , a solution (a ij ) of Equation (1.5) leads to a solution of: X j=1 B X i=0 a ij t wk A i+ ṽj = 0 (1.6)
for any k 2 [[1, `]] and any  2 N.

In the reverse direction, assume that we are given a solution (a ij )

j2[[0,B]] i2[[1,`]]
that satisfies Equation (1.6) for all k 2 [[1, `]] and for all  2 [[0, B 1]]. Now assume that:

Vect { t wj A i | i = 0, • • • , B 1 j = 1, • • • , `} = K N . (1.7)
Under this condition, a ij is also a solution of Equation (1.5). Indeed, by assumption, the vector P j=1 P B i=0 a ij A i ṽj is orthogonal to every vector in the basis of K N listed in condition (1.7). Thus, it must be the zero vector.

Rewriting Equation (1.6) with matrix power series.

For a fixed value of , we can paste together the `copies of Equation (1.6) for k 2 [ [1, `]]. In order to do this, let ãi denote the vector t (a i1 , a i2 , • • • , a il ). With this notation, the `equations can be grouped as:

B X i=0 ( t W A i+ V ) • ãi = 0. (1.8)
Let us now define the matrix power series S(X) and the vector polynomial P (X) as follows:

S(X) = X i2N ( t W A i V )X i and P (X) = B X i=0 ãi X B i .
Consider the product of S(X) by P (X). By definition of the multiplication for power series, we see that the coe cient corresponding to the monomial X B+ in the product S(X)P (X) is

P B i=0 ( t W A i+ V ) • ãi . According to Equation (1.8), this is 0 for all  2 N.
As a consequence, the vector power series S(X)P (X) is in fact a vector polynomial Q(X) of degree at most B 1. Thus, given S(X) we search for vector polynomials P (X) and Q(X) of respective degrees at most B and at most B 1 such that S(X)P (X) Q(X) = 0. To fit into the notations of Section 1.3, define G(X) = (S(X)| Id(X)) to be the `⇥ 2`matrix power series formed by concatenating the opposite of the `⇥ `identity matrix to S(X). Denote ũ(X) the dimension 2`row vector obtained by concatenating t P (X) and t Q(X). We now have G(X) t ũ = 0, transpose and obtain:

ũ(X) • t G(X) = 0.
(1.9)

Note that ũ(X) has degree at most B on its first `coordinates and degree at most B 1 on the other coordinates. Furthermore, knowing that the coe cients a 0j are zeroes for j > d leads to a zero constant coe cient for all polynomial coordinates from d + 1 to `.

In order to use the algorithm of Giorgi, Jeannerod and Villard, we prefer to work modulo a large monomial instead of dealing with power series. Indeed, we clearly have ũ(X) • t G(X) = 0 modulo X b for any integer b, with the same three constraints on ũ(X). We analyze the value of b permitting to claim that a solution of Equation (1.9) modulo X b , and with the same constraints on the vector ũ, can be transformed back into a solution of Equation (1.6) for any integer  in [[0, B 1]].

Let us assume we have a vector ũ = t (u (1) , • • • , u (2`) ) solution of Equation (1.9) modulo X b with:

• 8i 2 [[1, `]], deg u (i) (X)  B, • 8i 2 [[`+ 1, 2`]], deg u (i) (X)  B 1, • 8i 2 [[d + 1, `]], u (i) (0) = 0.
Since ũ consists of 2`polynomials we can cut it into two separate parts and consider only its first `polynomial terms, that are of degree at most B. There exists a canonical correspondence between this vector of polynomials and a polynomial P (X) of degree at most B where the coe cients are vectors in K `. Writing P (X) = P B i=0 zi X i with zi 2 K `we can define for all i in [[0, B]] and all j in [[1, `]]:

a ij = the j-th coordinate of the vector zB i . M • x = 0 (A|M d ) • x = 0 Equation (1.5) X j=1 B X i=0 a ij A i ṽj = 0 with a 0j =0 for j>d Equation (1.6) 8 2 N, 8k 2 [[1, `]] X j=1 B X i=0 a ij t wk A i+ ṽj = 0 with a 0j =0 for j>d Equation (1.6) 8  B 1, 8k 2 [[1, `]] X j=1 B X i=0 a ij t wk A i+ ṽj = 0 with a 0j =0 for j>d Equation (1.9) ũ(X) • t G(X) = 0 with ũ(X)=(u (1) (X),••• ,u (2`) (X)) s.t.: 8i2[[1,`]], deg u (i) (X)B, 8i2[[`+1,2`]], deg u (i) (X)B 1, 8i2[[d+1,`]], X|u (i) (X). Equation (1.9) mod X 2B ũ(X) • t G(X) = 0 mod X 2B with ũ(X)=(u (1) (X),••• ,u (2`) (X)) s.t.: 8i2[[1,`]], deg u (i) (X)B, 8i2[[`+1,2`]], deg u (i) (X)B 1, 8i2[[d+1,`]], X|u (i) (X). Assuming Condition (1.4) on V Assuming Condition (1.7) on W
M, d, M d , A, `, B, V = {ṽ 1 , • • • , ṽ`} , W = { w1 , • • • , w`}
and G are assumed to be known. Note that, even if it is true, we don't prove Equation (1.9) ) Equation (1.6) here since the others implications are already su cient to conclude. Same remark for Equation (1.6) with all   B 1 ) Equation (1.9) mod X 2B . of all solution vectors of Equation (1.9) with degree at most B is generated by the family:

E := t [ i=1 { bi , X bi , X 2 bi , • • • , X B deg bib i }.
Note that this family is free and thus a basis of the subspace of solutions of Equation (1.9). Indeed, the t vectors bi belong to a -basis and, thus, are linearly independent. Moreover, multiplication by X induces a block diagonal structure on the matrix representing E. Due to this structure, all vectors in E are also linearly independent.

To obtain a basis of the kernel of M , we now need a filtering step to ensure that we only keep the vectors of E with degree at most B 1 on the last `coordinates and constant coe cients that are zeroes in positions d + 1 to `. Interestingly, the first property already holds for all vectors of E but the final multiple of each bi , i.e. X B deg bi bi . Similarly, the second property already holds for all multiples of X j bi with j 6 = 0. Thus, for each vector bi all multiples except (possibly) the first and last already satisfy all extra condition. In addition, some linear combinations of these first and last multiples may satisfy the extra conditions and some may not. However, it is easy to construct the combinations that work. Indeed, the extra conditions are linear and only involve coe cients in 2` d positions. Thus, to find these combinations, it su ces to extract the relevant coe cients from the polynomial multiples that do not already satisfy the condition and assemble them in a matrix of dimension 2` d by at most7 2t. The kernel of this matrix describes the desired combinations and it can be computed it in O(`!) operations asymptotically; in O(`3) operations in practice, especially for small values of `. We let b0 i denote the t 0 combinations which are thus obtained.

We conclude that the basis of all solutions of Equation (1.9) that satisfy the three conditions is given by:

U := { b0 1 , • • • , b0 t 0 } [ t [ i=1 {X bi , X 2 bi , • • • , X B 1 deg bib i }.
Note that this can be represented in a compact form, just by giving t + t 0 vectors, with t 0  2t. This precisely gives a basis of the solutions of the equation highlighted by a frame in Figure 1. Compute a sequence of matrices

1: rd+1 2 K N , • • • , r` 2 K N and w1 2 K N , • • • , w` 2 K N 2: ṽ1 ~ 1 , • • • , ṽd ~ d 3: ṽd+1 rd+1 , • • • , ṽ` r4 : B dN/`e 5:
for any of the `processors indexed by j do 6:

u 0 v j 7:
for i = 0,

21: U [ b0 1 , • • • , b0 t 0 , X b1 , • • • , X B 1 deg b 1 b1 , • • • , X bt , • • • , X B
for i = 0, • • • , B do 25: for j = 1, • • • , `do 26:
a ij the coe cient associated to the monomial X B i in the polynomial that is the j-th coe cient of ũ. x t ( t (

P j=1 P B 1 i=0 a (i+1)j A i ṽj )|a 01 | • • • |a 0d ) 30:
Add x to Sol 31: end for 32: return Sol Algorithm 1.3 sums up in pseudo-code the main steps that occur to compute the kernel of a nearly sparse matrix M that has been preconditioned into a matrix composed of a square matrix A concatenated with the dense part M d of M . A benefit of this process is that it also checks the validity of (1.4). Indeed, looking back at the family F we see that is consists of `B vectors in K N . The matrix corresponding to F has full rank if and only if the dimension of its kernel is `B N . Yet, an element of this kernel is exactly a family of coe cients (a ij ) such that P j=1 P B 1 i=0 a ij A i v j = 0. Note that it di↵ers from Equation (1.5) from the fact that the sum ends at B 1 and not B and nothing it said about the coe cients a 0j . Following the paths given in Figure 1.3 we can derive a bijection between the kernel of this matrix and the set of solutions of Equation (1.9) with degree B 1 on the first `coordinates and B 2 on the last `coordinates. Since we already have computed a larger set of solutions of Equation (1.9), we can check if the dimension of the restricted set is `B N . If not, the elements of the kernel of M that are obtained are still valid, but the basis of the kernel may be incomplete.

Requirements on the parameters

At this point, we need to choose the values of the parameters B and depending on the input parameters N , s and d. By construction, we already know that ` d. However, for conditions (1.4) and (1.7) to be satisfiable, there are additional restrictions. In particular, condition (1.7) requires a family of `B vectors to have rank N , thus we need:

B ⇠ N `⇡ .
There are other hidden implied requirements. Indeed, looking again at condition (1.7), we see that all vectors of t wj A

i | i = 1, • • • , B 1 j = 1, • • • , `
belong to the image of A. Thus, the dimension of the vector space in condition (1.7) is upper bounded by Rank(A) + `. Moreover, due to the preconditioning of Section 1.4.2, we know that the rank of A is at most s. This implies that the algorithm requires:

` max(N s, d). Note that, over a large field K, the dimension of the vector space in condition (1.7) for randomly chosen vectors wi is Rank(A) + `with probability close to one.

The requirements associated to condition (1.4) do not give stronger arithmetic conditions on `and B. However, the family of vectors in condition (1.4) also contains fixed vectors (derived from the dense columns of M ), thus we cannot claim that the condition hold for random choices of V . However, since our algorithm also checks the validity of Condition (1.4), this is a minor drawback.

Complexity analysis

The total cost of our method contains two parts. One part is the complexity of the matrix-by-vector products whose sequential cost is O( N 2 ) including the preparation of the sequence of `⇥`matrices and the final computation of the kernel basis. It can easily be distributed on several processors, especially when the number of sequences `is equal to the number of processors c or a multiple of it. This minimizes the wall clock time of the matrix-by-vector phases at O( N 2 /c). Moreover, since B ⇡ N/`, the phase that recovers the coe cients a ij has complexity Õ(`! 1 N ) using Giorgi, Jeannerod and Villard algorithm. The filtering step after this algorithm costs O(`w) and can thus be neglected (since obviously ` N ).

To minimize the cost of Giorgi, Jeannerod and Villard algorithm, we let `be the smallest multiple of c larger than d. In that case, the total sequencial cost of the algorithm becomes:

O( N 2 ) + Õ(max(c, d) ! 1 N ).
This has to be compared with the previous O(( + d)N 2 ) + Õ(c ! 1 N ) obtained when combining Block Wiedemann algorithm with Giorgi, Jeannerod and Villard variant to solve the same problem. Note that the wall clock time also decreases from O((

+ d)N 2 /c) + Õ(c ! 1 N ) to O( N 2 /c) + Õ(max(c, d) ! 1 N ). If d  c then the complexity of the variant we propose is clearly in O( N 2 ) + Õ(c ! 1
N ), which is exactly the complexity obtained when combining Block Wiedeman algorithm with Giorgi, Jeannerod and Villard variant to solve a linear algebra problem on a (truly) sparse matrix of the same size. In a nutshell, when parallelizing on c processors, it is possible to tackle up to c dense columns for free.

How dense can nearly sparse matrices be ?

We already know that our nearly sparse algorithm behaves better than the direct adaptation of sparse methods. However, when the number d of dense columns becomes much larger, it makes more sense to compare to the complexity of dense methods, i.e. to compare our complexity with O(N ! ). In this case, we expect the number of processors to be smaller that the number of dense columns and thus replace max(c, d) by d in the complexity formulas.

Assume that d  N 1 ✏ with ✏ > 0 then our complexity becomes Õ(d ! 1 N ) = O(N ! ✏(! 1) (log N ) ↵ ) for some ↵ > 0, which is asymptotically lower than O(N ! ). However, when the matrix is almost fully dense, i.e. for d = ⌦(N ), our technique becomes slower, by a logarithm factor, than the dense linear algebra methods.

Application to Discrete Logarithm Computations

In this section, we discuss the application of our adaptation of Block Wiedemann to discrete logarithm computations using the Number Field Sieve (NFS) algorithm [START_REF] Joux | The number field sieve in the medium prime case[END_REF][START_REF] Arjen | The development of the number field sieve[END_REF][START_REF] Pierrot | The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods[END_REF], which applies to medium and high characteristic finite fields F q .

NFS contains several phases. First, a preparation phase constructs a commutative diagram of the form:

Z[X] Q[X]/(f (X)) Z F q
when using a rational side. Even if there also exists a generalization with a number field on each side of the diagram, for the sake of simplicity, we only sketch the description of the rational-side case.

The second phase builds multiplicative relations between the images in Fq of products of ideals of small prime norms in the number field Q[X]/(f (X)) and products of small primes. These relations are then transformed into linear relations between virtual logarithms of ideals and logarithms of primes modulo the multiplicative order of F ⇤ q . Writing down these linear relations requires to get rid of a number of technical obstructions. In practice, this means that each relation is completed using a few extra unknowns in the linear system whose coe cients are computed from the so-called Schirokauer's maps [START_REF] Schirokauer | Discrete logarithm and local units[END_REF]. Essentially, these maps represent the contribution of units from the number field in the equations. Due to the way they are computed, each of these maps introduces a dense column in the linear system of equations. The total number of such columns is upperbounded by the degree of f (or the sum of the degrees when there are two number fields in the diagram).

The third phase is simply the resolution of the above linear system. In a final phase which we do not describe, NFS computes individual logarithms of field elements. An optimal candidate to apply our adaptation of Coppersmith's Block Wiedemann algorithm precisely lies in this third sparse linear algebra phase. Indeed, the number of dense columns is small enough to be smaller than the number of processors that one would expect to use in such a computation. Typically, in [START_REF] Bouvier | Discrete logarithms in GF(p) -180 digits[END_REF], the degree of the number field was 5, whereas the number of maps (so the number of dense columns) was 4, and the number of processors 12. Asymptotically, we know that in the range of application of NFS, the degree of the polynomials defining the number fields are at most O((log q/ log log q) 2/3 ). This is negligible compared to the size of the linear system, which is about L q (1/3) = exp(O((log q) 1/3 (log log q) 2/3 )).

Thus, our new adaptation of Coppersmith's Block Wiedemann algorithm completely removes the di culty of taking care of the dense columns that appear in this context. It is worth noting that these dense columns were a real practical worry and that other, less e cient, approaches have been tried to lighten the associated cost. For instance, in [START_REF] Barbulescu | Improvements to the number field sieve for non-prime finite fields[END_REF], the construction of the commutative diagram was replaced by a sophisticated method based on automorphisms to reduce the number of maps required in the computation. In this extend, this approach is no longer useful.

Moreover, since we generally have some extra processors in practice, it is even possible to consider the columns corresponding to very small primes or to ideals of very small norms as part of the dense part of the matrix and further reduce the cost of the linear algebra.

Fig. 1 . 1 A

 11 Fig. 1.1 A nearly sparse matrix

Definition 1 . 1 .

 11 A -basis of the set of solutions of Equation (1.3) is a square m ⇥ m matrix M of polynomials of K[X] such that:• Every row vector Mi of M satisfies (1.3).• For every solution ũ of (1.3), there exists a unique family of m polynomials c 1 , . . . , c m such that for each i: deg(c i Mi )  deg(ũ), that, in addition, satisfies the relation:

Fig. 1 . 2

 12 Fig. 1.2 Parameters of the nearly spare linear algebra problem

  4.5), let ~ 1 , . . . , ~ d denote the column vectors of M d and choose ` d random vectors

Fig. 1 . 3

 13 Fig. 1.3 How the computation of the kernel of a nearly sparse matrix M reduces to the computation of the kernel of a power series matrix G. Equivalences and implications between various problems have to be read as follows: A ) B means that a solution of Equation A can be transformed into a solution of Equation B. The unknowns are denoted by x, a ij or ũ whereas all the other variablesM, d, M d , A, `, B, V = {ṽ 1 , • • • , ṽ`} , W = { w1 , • • • , w`}and G are assumed to be known. Note that, even if it is true, we don't prove Equation (1.9) ) Equation (1.6) here since the others implications are already su cient to conclude. Same remark for Equation (1.6) with all   B 1 ) Equation (1.9) mod X 2B .

3 . 1 . 3

 313 Algorithm Nearly sparse algorithm for (A|M d )x = 0 Input: A matrix A of size N ⇥ N and a matrix M d = ( ~ 1 | • • • | ~ d ) of size N ⇥ d Output: A basis of Ker(A|M d ).

20 : b0 1 ,

 201 • • • , b0 t 0 a basis of the linear combinations of b1 , • • • , bt , X B deg b 1 b1 , • • • , X B deg b 1 bt s.t.the `last coordinates have degree lower than B 1 and coordinates between d + 1 and `are divisible by X.

1. 4 . 4 . 1

 441 Checking condition (1.4).

  • • • , 2B do Recover a basis of the matrix t (S| Id) modulo X 2B .

	8: 9: 10:	for k = 1, • • • , `do i,j,k wk • ũi ũi+1 Aũ i
	11:	end for
	12:	end for
	13: end for
	14: for i = 0, • • • , 2B do 15: M i ( i,j,k ) the `⇥ `matrix containing all the products of the form t	wA i	ṽ
	16: end for
	Apply Giorgi, Jeannerod, Villard's algorithm 17: S P 2B 1 i=0 M i X i .
	18: 19: b1 , • • • , bt	the vectors in this	basis of degree lower than B.

  1 deg b t bt ]

	Resolution
	22: Sol	[ ]
	23: for ũ 2 U do 24:

Yet, for practical purposes, asymptotically fast matrix multiplication is unusable and working implementations of the algorithm of Giorgi, Jeannerod and Villard have complexity Õ(c 2 N ).

When K is small, it is easy to make the probability close to 1 by increasing the number of vectors w beyond `in the analysis as done in[START_REF] Coppersmith | Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm[END_REF].

Although this zero-padding method fits the theoretical analysis well, other randomized preconditionning methods are also used in practice.

At most, there are 2`such vectors. Note in practice, it is convenient to run the -basis algorithm on power series with precision slightly higher than 2B in order to have fewer vectors at this point (usually `).

Indeed, vectors bi with exact degree B appear once in the matrix while others appear twice.

 [START_REF] Adleman | A subexponential algorithm for the discrete logarithm problem with applications to cryptography[END_REF]This work has been supported in part by the European Union's H2020 Programme under grant agreement number ERC-669891. Cécile Pierrot has been funded by Direction Générale de l'Armement and CNRS. 1

rd+1 , • • • , r`i n K N . From these vectors, we construct the family:

.

Our first condition is the assumption that F generates the full vector space K N . We discuss the validity of this assumption in Section 1.4.4.1.

Condition on V .

To initialize the `sequences the main idea is to force the first d ones to start from the d dense columns of M . In other words, by setting ṽi = ~ i for i in [ [1, d]] and ṽi = ri for in [[d + 1, `]]. Then, we see that the assumption on F can be rewritten as:

) be a vector in the kernel of (A|M d ). If Equation (1.4) is satisfied, there exist, in particular, coe cients ij 2 K such that:

Thus we obtain:

where the coe cients a ij are defined through:

x 0

To put it in a nutshell, as soon as the condition given by Equation (1.4) on the matrix V = (ṽ 1 | • • • |ṽ `) is verified, every element of the kernel of (A|M d ) gives a solution of:

Book Title

Since modulo X b the product P (X)S(X) is a vector polynomial of degree at most B 1 we deduce that for any integer  such that 0    b B 1 the coe cient in P (X)S(X) related to the monomial X B+ is the zero vector.

Combining with P (X) = P B i=0 ãi X B i and S(X) =

Hence multiplying V by the vectors ãi we get

Summary of the transformations.

To sum it up, we have transformed the problem of finding the kernel of M into the problem of finding all solutions of Equation (1.9) modulo X 2B , with degree at most B on the first `coordinates, degree at most B 1 on the other coordinates and a zero constant coe cient for coordinates d + 1 to `. Under the two conditions (1.4) and (1.7), the above analysis directly gives a bijection between the set of solutions of the two problems, as illustrated in Figure 1.3.

Applying Giorgi, Jeannerod and Villard algorithm.

Thanks to Giorgi, Jeannerod and Villard [START_REF] Giorgi | On the complexity of polynomial matrix computations[END_REF] we can compute a minimalbasis of the solution vectors of Equation (1.9) modulo X 2B in time Õ(`!B). However, we need to post-process this -basis to recover a basis of the kernel of M . More precisely, we need to derive an explicit description of all solution vectors of Equation (1.9) that have degree at most B on the first `coordinates, degree at most B 1 on the last `coordinates and a zero constant coe cient for coordinates d + 1 to `. We first show how to obtain all solution vectors that have degree at most B on the 2`coordinates. A final filtering is then used to ensure that the stronger degree bound on the last `coordinates holds and the ` d constant coe cients are zeroes.

We first let b1 , • • • , bt denote the t vectors 6 in the -base with degree at most B. Let ũ denote any solution vector of Equation (1.9) with degree at most B. From the minimality of the -base, we know that ũ can be written as linear combinations P t i=1 c i bi where the c i are polynomials in K[X] such that deg c i + deg b i  deg ũ for any i = 1, • • • , t. Thus, the set