京都大学 / 新制・課程博士 / 博士(理学) / 甲第25086号 / 理博第4993号 / 新制||理||1713(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 宍倉 光広, 教授 COLLINSBenoit Vincent Pierre, 教授 塚本 真輝 / 学位規則第4条第1項該当 / Doctor of Agricultural Science / Kyoto University / DFAM

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n}) / Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

While there has been research on development of multiplicative reasoning, and how to teach multiplication facts, there is little research on how children consider they learn these. This study explores the children's learning as they consider how they commit their multiplication facts to memory, discover calculation strategies and develop multiplicative thinking. A group of eleven Year 4 children (8 years old) participated in a series of 13 lessons where they became coresearchers in the exploration of their learning. A contextually based thematic approach was provided through 'Crocodilian Studies'. The mixed-method approach to this study included formal assessment, participant observation, individual interviews, the children's written ideas, and individual case studies. The most significant finding of this study was the powerful influence of peer learning. The children enriched and directed each other's learning as they shared ideas and reflected on their own mathematical learning as they observed and critiqued the thinking of peers. As the children were involved in thinking about how they learn they were able to identify gaps and construct their own learning pathways. A significant finding was that children can develop their multiplicative strategies while they commit their multiplication facts to memory, in a relatively short time provided that the learning process facilitates strategy development and understanding. By exposing the children to multiplication facts in sequenced clusters provided them with a manageable number of facts to be learnt at one time. Another finding related to how children develop calculation strategies through lesson activities rather than being explicitly taught them. The children considered practice important for memorisation. Parental support was significant in enriching the children's learning.

Des nanostructures basées sur des différences de cristallinité ont été insérées dans des cellules test en silicium par des techniques d’amorphisation innovantes. Un nouveau mécanisme de multiplication de porteurs a ainsi été observé. Cet effet peut provenir des niveaux d’énergie électronique introduits par de grandes densités locales de bi-lacunes. Un principe de fonctionnement impliquant des mécanismes à niveaux d’énergie multiples et un transport électronique rapide au sein de la bande d’énergie des atomes de phosphore non-ionisés a également été proposé. Cela conduit à une asymétrie favorable entre la génération et la recombinaison des porteurs libres.L’énergie nécessaire à un photon pour enclencher le procédé s’est révélée plus petite que deux fois celle de la bande interdite. L’amélioration du rendement photovoltaïque devient donc concevable et une nouvelle génération de cellules solaires à haute efficacité pourrait ainsi émerger de cet effet de multiplication à faible-énergie. / Nanostructures based on differences of crystallinity have been embedded into all-silicon test devices by innovative amorphization techniques and a new carrier multiplication mechanism was observed. This effect can indeed originate from the electron energy levels resulting from the high densities of divacancies localized at the crystalline/amorphous interfaces.An operating principle involving multiple energy level mechanisms and fast electronic transport within the unionized phosphorus energy band was also advanced. It led to a favourable asymmetry between generation and recombination of free carriers.Besides, contrary to other carrier multiplication effects, photon energy lower than twice the band gap was found sufficient to initiate the process. The enhancement of photovoltaic yields becomes therefore conceivable and propositions of prototypes are made. A new generation of high efficiency solar cells may then emerge from this Low-Energy Electron Multiplication effect.

On s'intéresse dans cette thèse à la complexité bilinéaire de la multiplication dans toute extension de degré $n$ d'un corps $F_{q}$ à $q$ éléments, qui est étroitement liée au rang de tenseur de la multiplication dans $F_{q^n}$. L'algorithme de type évaluation-interpolation, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes uniformes et asymptotiques de la complexité bilinéaire. Pour obtenir ces meilleures bornes, la stratégie adoptée jusqu'à présent consistait à fixer le degré des places en augmentant le genre du corps de fonctions algébriques.Néanmoins, l'étude de la construction effective associée à ce type de stratégie fut jusqu'à présent négligée en raison d'un obstacle, lié à la construction du point de degré $n$, relevé par Shparlinski, Tsfasman et Vladut en 1992.On présente dans cette thèse une nouvelle stratégie qui consiste à fixer le genre du corps de fonctions algébriques tout en augmentant le degré des places.En appliquant cette stratégie aux corps de fonctions elliptiques, on montre d'une part que le rang de tenseur de la multiplication dans $F_{q^n}$ est quasi-linéaire en $n$, et d'autre part que la construction des algorithmes de multiplications bilinéaires issus de cette stratégie est réalisable en temps polynomial. On montre également comment construire explicitement ces algorithmes sur $F_{q^n}$, en les illustrant par un exemple. Enfin, on établit la première construction asymétrique de l'algorithme de type Chudnovsky. / In this thesis, we focus on the bilinear complexity of multiplication in any degree $n$ extension of the finite field $ F_{q}$, which is closely related to the tensor rank of multiplication in $ F_{q^n} $. The evaluation-interpolation type algorithm introduced by D.V and G.V Chudnovsky in 1987, is the basis of all algorithmic technique providing for now, the lower asymptotic and uniform bounds for the bilinear complexity.So far, the strategy to obtain these lower bounds was to fix the degree of places while increasing the genus of algebraic function fields. However, the study of the effective construction associated with this kind of strategy was until now neglected because of an obstacle related to the construction of a degree $n$ point, identified par Shparlinski, Tsfasman and Vladut in 1992. We present a new strategy which consists in fixing the genus of algebraic function fields while increasing the degree of places. Applying this strategy to the elliptic function fields, we show on the one hand that the tensor rank of multiplication in $ F_{q^n} $ is quasi-linear in $ n $, and on the other hand we prove that the construction of bilinear multiplication algorithms with this strategy is feasible in polynomial time. We also show how to construct explicitly these algorithms over $ F_{q^n} $ for large $n$ by illustrating the construction with an example. Finally, we establish the first asymmetric construction of the Chudnovsky type algorithm.

The focus of this study is to explore three key aspects of learners’ multiplicative proficiency: the nature of learners’ conceptual understanding of multiplication, the nature of learners’ numeracy dispositions (in the context of learning multiplication), and the relationship between conceptual understanding and productive dispositions in the context of multiplication. The study used a qualitative case study approach to gather rich data in relation to these. In the study a purposively selected sample of six Grade 4 learners was used from the same school: two high, two average, and two low performers. Kilpatrick, Swafford, and Findell (2001) define conceptual understanding as a functional grasp of mathematical ideas and its significant indicator is being able to represent mathematical situations in different ways and knowing how different representations can be useful for different purposes. They then refer to productive disposition as the ‘tendency to see sense in mathematics, to perceive it as both useful and worthwhile, to believe that steady effort in learning mathematics pays off, and to see oneself as an effective learner and doer of mathematics’ (p.131). Individual interviews were conducted using Wright, et al.’s (2006) instrument for exploring the nature of students’ conceptual understanding of multiplication. Wright, et al. (2006) argue that the topics of multiplication and division build on the students’ knowledge of addition and subtraction, and also multiplication and division provide foundational knowledge for topics such as fractions, ratios, proportion and percentage, all of which are core and essential areas of mathematical learning typically addressed in the primary or elementary grades. Researchers agree that learners have to be exposed to various strategies so that they are able to see that there is a difference between additive reasoning and multiplicative reasoning. In order to classify learners’ conceptual understanding of multiplication an analysis of the data was done and learners were allocated levels according to the Wright, et al. (2006) levels of achievement. For the classification of learner dispositions, the data was analysed in terms of the elements of productive disposition as defined by Kilpatrick, et al. (2001) and Carr and Claxton (2002). The key findings of the study indicate that for conceptual understanding most of the learners depended on using concrete materials in solving multiplication and they also used basic strategies and methods. The findings for productive dispositions were that most of the learners saw themselves as competent in doing multiplication but the aspect of sense making and steady effort was less developed. The findings for the relationship between conceptual understanding and productive disposition were that both strands have a mutual relationship in which one helped the other to develop.

De nombreuses études ont montré qu’une activation d'indices moteurs (mouvement d’approche ou de retrait ; Cretenet et Dru 2004) ou spatiaux (verticale ou horizontale ; Casasanto, 2009) était de nature à influencer un jugement ou des réponses finales. Dans le cadre des théories de la cognition incarnée, ce travail examine l’effet de l’activation synchrone ou asynchrone de ces indices comme étant révélatrice de processus cognitifs. Dans cette perspective, nos travaux, présentés sous la forme de deux articles, ont pour objectif d’analyser l’effet de ces activations, impliquant la théorie de la correspondance de polarité (Proctor et Cho, 2006), sur la résolution d’opérations arithmétiques, comme l’expression d’une combinatoire cognitive particulière. De plus, cette thèse supporte l’idée qu’une analogie entre la PCE et ces résultats peut être faite. En effet, le cœur de notre travail consiste défendre l’idée que quelque soit les indices conceptuels (motivationnel ou émotionnel) activés, de mêmes effets sont observés, traduisant la mise en jeu d’un même système de codage de polarités. Lors de l’activation d’indices de polarité (motivationnelle ou émotionnelle), un phénomène de compatibilité s’opère influençant le raisonnement mathématique.Nous proposons d'étudier l'effet d’un mouvement moteur (effectué) ou spatial (perçu) combinant deux dimensions spatiales (latérale et verticale) simultanément ou non sur la performance numérique. L’objectif est d’analyser l’influence de conditions de congruence ou de non congruence sur la résolution d’opérations arithmétiques. L’idée est de montrer qu’une activation synchrone d’indices moteurs ou spatiaux influencerait une combinatoire cognitive telle que la multiplication (Article 1) ; tandis qu’une activation asynchrone d’indices spatiaux influencerait une combinatoire cognitive telle que l’addition (Article 2).Ces travaux démontrent pour la première fois comment des combinatoires perceptives ou motrices déterminent des combinatoires cognitives. / Several studies have shown that an activation of motors (approach-avoidance behaviors, Cretenet & Dru 2004) or spatial cues (vertical or horizontal, Casasanto, 2009) is likely to influence the affective judgment or the final responses. In regards of the theories of embodiment, this studies examine the effect of combined (synchronous or asynchronous) motor and spatial cues on mathematical reasoning as revealing cognitive processes. In this perspective, our work, presented in two articles, with the aim to analyze the effect of these activations, involving the theory of polarity correspondence (Proctor & Cho, 2006), on the resolution of arithmetic operations, as the expression of a particular cognitive functioning. Furthermore, this thesis supports the idea that this operation has some analogy with the polarity correspondence effect (PCE). Indeed, our work supports the idea that whatever the activated conceptual cues are (motivational or emotional), the same effects are observed - a similar system is activated, coded as polarities which might be indicative of the PCE. When the activation of polarity indices (motivational or emotional), a phenomenon of compatibility occurs that also influences mathematical reasoning.We investigate the effect of a motor (performed) or spatial (perceived) movement combining two spatial dimensions (laterality and verticality) simultaneously or not on numerical performance. The objective is to investigate the influence of congruence or noncongruence conditions on the resolution of arithmetic operations. When a synchronous activation of peripheral cues (motor or spatial) is activated, we would observed an effect on mathematical reasoning, such as multiplication (Article 1); while when an asynchronous activation, deferred in time and space, of spatial cues would influence a mathematical reasonning, such as addition (Article 2). For the first time, studies demonstrate how a particular combination of perceptual or motor activations reveals some correspondent cognitive mechanism.

Modern public-key cryptography relies extensively on modular multiplication with long operands. We investigate the opportunities to optimize this operation in a heterogeneous multiprocessing platform such as TI OMAP3530. By migrating the long operand modular multiplication from a general-purpose ARM Cortex A8 to a specialized C64x+ VLIW DSP, we are able to exploit the XOR-Multiply instruction and the inherent parallelism of the DSP. The proposed multiplication utilizes Multi-Precision Binary Polynomial Multiplication with Unbalanced Exponent Modular Reduction. The resulting DSP implementation performs a GF(2^233) multiplication in less than 1.31us, which is over a seven times speed up when compared with the ARM implementation on the same chip. We present several strategies for different field sizes and field polynomials, and show that a 360MHz DSP easily outperforms the 500MHz ARM. / Master of Science

Plusieurs tourbières ombrotrophes des régions tempérées sont présentement caractérisées par un processus de densification rapide de leur couverture forestière. Au Québec, ce phénomène implique diverses espèces, autant conifériennes qu'à feuillage décidu. La présente étude visait à documenter le boisement de la tourbière de la base de plein air de Sainte-Foy, située au sein d'un paysage semi-urbain de la ville de Québec, qui montre un important déploiement du mélèze laricin et de l'érable rouge. Les principaux objectifs étaient de caractériser la dynamique contemporaine du couvert forestier à l'aide d'analyses dendrométriques, dendrochronologiques et de photographies aériennes, et de reconstituer l'évolution à long terme (plusieurs millénaires) des espèces arborescentes via la conjugaison de l'identification botanique de pièces de bois préservées dans la tourbe et de l'analyse macrofossile. L'hypothèse qui a été testée est que la flore de la tourbière a toujours comporté des espèces arborescentes conifériennes mais de façon éparse. La constitution d'une couvert forestier dense et mixte serait un phénomène récent, associé à des perturbations anthropiques. Le couvert végétal s'est modifié rapidement depuis 1970, d'abord par la formation d'un mélèzin. Le mélèze étant présentement incapable de se régénérer, il est progressivement supplanté par l'érable rouge. Cette dynamique récente fait suite à plusieurs millénaires durant lesquels la tourbière a toujours présenté une physionomie arbustive et où les arbres étaient présents de façon éparse. La densification du couvert forestier fut causée par les activités humaines en périphérie de la tourbière (agriculture, construction d'une gare de triage) qui ont eu pour effet de réduire sa superficie et de l'assécher. L'érable rouge domine maintenant la régénération au sol et devrait, à plus ou moins long terme, devenir l'espèce dominante pour former une érablière rouge sur tourbe.

Les changements climatiques et la surexploitation des ressources naturelles dans les zones arides ont conduit à la dégradation et au déclin de la couverture végétale. Pour restaurer ces écosystèmes, les plantations d'espèces agroforestières à usages multiples sont recommandées. Cependant, la production en pépinière de ces types d'arbres à l'aide de semences ou de techniques de multiplication végétative est confrontée à plusieurs problèmes, tels que l'utilisation de substrats avec des propriétés physico-chimiques défavorables et souvent contaminés avec des pathogènes. Pour cette thèse, deux espèces agroforestières à haute valeur socioéconomique ajoutée, Ceratonia siliqua et Argania spinosa, ont été produites respectivement par graines et par boutures. Une approche novatrice et simple a été développée pour produire des substrats de croissance par compostage de branches broyées d'Acacia cyanophylla, Acacia cyclops et Eucalyptus gomphocephala. Les propriétés physico-chimiques (pH, conductivité électrique, capacité d’échange cationique, masse volumique, porosités, conductivité hydraulique et diffusion des gaz) de ces trois composts et du substrat standard tourbe-vermiculite ont été évaluées et leurs effets sur la croissance des semis de Ceratonia ont été étudiés. Les analyses en composantes principales ont montré que la composition chimique des substrats est reproductible et prédictible à partir de leurs matières organiques premières. Les composts d’Acacia ont permis aux semis de produire des systèmes racinaires bien développés. L’excès du drainage était négativement corrélé avec les variables de croissance, tandis que la disponibilité en eau et la porosité d'air étaient positivement corrélées. Le champignon endophyte Pestalotiopsis clavispora, responsable de la mortalité des boutures d’Argania, a été identifié et des mesures de prévention et de lutte ont été évaluées. Ces résultats permettraient d'améliorer la qualité des plants et leur protection contre les agents pathogènes en pépinière. La généralisation de l'approche de compostage décrite ici pour les pays disposant de ressources limitées dans les régions arides est prometteuse. / Climate change and the overexploitation of natural resources in arid zones have led to the degradation and decline of vegetative cover. To restore the ecological functions and services provided by these ecosystems, planting multipurpose agro-forestry species that are adapted to arid climates is increasingly recommended. However, nursery production of these types of tree species using seeds or vegetative propagation techniques faces several problems, such as the widespread use of substrates with inadequate physicochemical properties that are unfavorable to growth and that can lead to high rates of infection by pathogens. For this thesis, two high-value agroforestry species, Ceratonia siliqua and Argania spinosa, were produced from seeds and cuttings, respectively. A simple, innovative approach was developed for producing growing media in arid regions from ground branches of Acacia cyanophylla, Acacia cyclops, and Eucalyptus gomphocephala. The physico-chemical properties (pH, electrical conductivity, cation exchange capacity, density, air and water porosity, hydraulic conductivity, gas diffusion) of these three substrates as well as of a standard peat-vermiculite substrate were evaluated and their influence on the growth of Ceratonia seedlings was assessed. Principal components analyses showed that the chemical composition of the substrates is reproducible and can be predicted from its raw organic materials. Acacia composts produced seedlings with well-developed root systems. Excessive drainage was negatively correlated with growth variables, while water availability and air porosity were positively correlated. As well, the endophytic fungus Pestalotiopsis clavispora (Atkinson) Steyaert, responsible for the mortality of Argania cuttings before rooting, was identified and different preventive and control measures were evaluated. These results should be useful for improving nursery substrates, seedling quality, and protection against pathogens during the nursery production of trees in arid regions. The generalisation of the composting approach described here to countries with limited resources in arid regions is promising.