2
2.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Erich Kaltofen

texts

#
eye 2

#
favorite 0

#
comment 0

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size $N$, meaning $N$ times a factor $N^{o(1)}$, i.e., a factor $N^{\eta(N)}$ with $\lim_{N\to \infty} \eta(N)$ $=$ $0$. We give algorithms that compute essentially...

Topics: Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1401.4567

2
2.0

Jun 29, 2018
06/18

by
Jean-Guillaume Dumas; Erich Kaltofen; Emmanuel Thomé; Gilles Villard

texts

#
eye 2

#
favorite 0

#
comment 0

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that compute a certificate for the minimal polynomial of sparse or structured n x n matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear...

Topics: Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1602.00810

45
45

Sep 22, 2013
09/13

by
Jean-Guillaume Dumas; Clément Pernet; B. David Saunders

texts

#
eye 45

#
favorite 0

#
comment 0

We present algorithms and heuristics to compute the characteristic polynomial of a matrix given its minimal polynomial. The matrix is represented as a black-box, i.e., by a function to compute its matrix-vector product. The methods apply to matrices either over the integers or over a large enough finite field. Experiments show that these methods perform efficiently in practice. Combined in an adaptive strategy, these algorithms reach significant speedups in practice for some integer matrices...

Source: http://arxiv.org/abs/0901.4747v2

0
0.0

Jan 4, 2021
01/21

by
Guillaume Dumas (guitoud)

data

#
eye 0

#
favorite 0

#
comment 0

## hand writen "stop la pub" in inkscape, extruded with openscad.

Topics: stop_advertising, stl, Signs & Logos, thingiverse, postal

3
3.0

Jun 30, 2018
06/18

by
Brice Boyer; Jean-Guillaume Dumas; Pascal Giorgi; Clément Pernet; B. David Saunders

texts

#
eye 3

#
favorite 0

#
comment 0

We describe in this paper new design techniques used in the \cpp exact linear algebra library \linbox, intended to make the library safer and easier to use, while keeping it generic and efficient. First, we review the new simplified structure for containers, based on our \emph{founding scope allocation} model. We explain design choices and their impact on coding: unification of our matrix classes, clearer model for matrices and submatrices, \etc Then we present a variation of the...

Topics: Mathematical Software, Symbolic Computation, Computing Research Repository, Software Engineering

Source: http://arxiv.org/abs/1407.3262

47
47

Sep 22, 2013
09/13

by
Jannik Dreier; Jean-Guillaume Dumas; Pascal Lafourcade

texts

#
eye 47

#
favorite 1

#
comment 0

Auctions have a long history, having been recorded as early as 500 B.C. Nowadays, electronic auctions have been a great success and are increasingly used. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the...

Source: http://arxiv.org/abs/1210.6780v3

35
35

Sep 22, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Laurent Fousse; Jean-Claude Reynaud

texts

#
eye 35

#
favorite 0

#
comment 0

In this paper we consider the two major computational effects of states and exceptions, from the point of view of diagrammatic logics. We get a surprising result: there exists a symmetry between these two effects, based on the well-known categorical duality between products and coproducts. More precisely, the lookup and update operations for states are respectively dual to the throw and catch operations for exceptions. This symmetry is deeply hidden in the programming languages; in order to...

Source: http://arxiv.org/abs/1001.1662v4

41
41

Sep 21, 2013
09/13

by
Jean-Guillaume Dumas; Clément Pernet; Ziad Sultan

texts

#
eye 41

#
favorite 0

#
comment 0

Gaussian elimination with full pivoting generates a PLUQ matrix decomposition. Depending on the strategy used in the search for pivots, the permutation matrices can reveal some information about the row or the column rank profiles of the matrix. We propose a new pivoting strategy that makes it possible to recover at the same time both row and column rank profiles of the input matrix and of any of its leading sub-matrices. We propose a rank-sensitive and quad-recursive algorithm that computes...

Source: http://arxiv.org/abs/1301.4438v1

2
2.0

Jun 29, 2018
06/18

by
Jean-Guillaume Dumas; Pascal Lafourcade; Jean-Baptiste Orfila; Maxime Puys

texts

#
eye 2

#
favorite 0

#
comment 0

This paper deals with distributed matrix multiplication. Each player owns only one row of both matrices and wishes to learn about one distinct row of the product matrix, without revealing its input to the other players. We first improve on a weighted average protocol, in order to securely compute a dot-product with a quadratic volume of communications and linear number of rounds. We also propose a protocol with five communication rounds, using a Paillier-like underlying homomorphic public key...

Topics: Symbolic Computation, Cryptography and Security, Computing Research Repository

Source: http://arxiv.org/abs/1607.03629

41
41

Jul 20, 2013
07/13

by
Jean-Guillaume Dumas; Dominique Duval; Laurent Fousse; Jean-Claude Reynaud

texts

#
eye 41

#
favorite 0

#
comment 0

We define a proof system for exceptions which is close to the syntax for exceptions, in the sense that the exceptions do not appear explicitly in the type of any expression. This proof system is sound with respect to the intended denotational semantics of exceptions. With this inference system we prove several properties of exceptions.

Source: http://arxiv.org/abs/1203.2900v1

3
3.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Vincent Zucca

texts

#
eye 3

#
favorite 0

#
comment 0

With the emergence of cloud computing services, computationally weak devices (Clients) can delegate expensive tasks to more powerful entities (Servers). This raises the question of verifying a result at a lower cost than that of recomputing it. This verification can be private, between the Client and the Server, or public, when the result can be verified by any third party. We here present protocols for the verification of matrix-vector multiplications, that are secure against malicious...

Topics: Cryptography and Security, Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1704.02768

6
6.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Dominique Duval; Jean-Claude Reynaud

texts

#
eye 6

#
favorite 0

#
comment 0

Computational effects may often be interpreted in the Kleisli category of a monad or in the coKleisli category of a comonad. The duality between monads and comonads corresponds, in general, to a symmetry between construction and observation, for instance between raising an exception and looking up a state. Thanks to the properties of adjunction one may go one step further: the coKleisli-on-Kleisli category of a monad provides a kind of observation with respect to a given construction, while...

Topics: Mathematics, Category Theory, Logic in Computer Science, Computing Research Repository

Source: http://arxiv.org/abs/1402.1051

3
3.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Dominique Duval; Burak Ekici; Damien Pous

texts

#
eye 3

#
favorite 0

#
comment 0

Dynamic evaluation is a paradigm in computer algebra which was introduced for computing with algebraic numbers. In linear algebra, for instance, dynamic evaluation can be used to apply programs which have been written for matrices with coefficients modulo some prime number to matrices with coefficients modulo some composite number. A way to implement dynamic evaluation in modern computing languages is to use the exceptions mechanism provided by the language. In this paper, we pesent a proof...

Topics: Logic in Computer Science, Computing Research Repository

Source: http://arxiv.org/abs/1411.7140

35
35

Sep 18, 2013
09/13

by
Jean-Guillaume Dumas

texts

#
eye 35

#
favorite 0

#
comment 0

We study algorithms for the fast computation of modular inverses. Newton-Raphson iteration over $p$-adic numbers gives a recurrence relation computing modular inverse modulo $p^m$, that is logarithmic in $m$. We solve the recurrence to obtain an explicit formula for the inverse. Then we study different implementation variants of this iteration and show that our explicit formula is interesting for small exponent values but slower or large exponent, say of more than 700 bits. Overall we thus...

Source: http://arxiv.org/abs/1209.6626v3

2
2.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; David Lucas; Clement Pernet

texts

#
eye 2

#
favorite 0

#
comment 0

In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead. We first provide quadratic time and space non-interactive certificates saving the logarithmic factors of previously known ones. Then we propose interactive certificates for the same problems whose Monte Carlo verification complexity requires a...

Topics: Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1702.03755

3
3.0

Jun 29, 2018
06/18

by
Jean-Guillaume Dumas; Clement Pernet; Ziad Sultan

texts

#
eye 3

#
favorite 0

#
comment 0

The row (resp. column) rank profile of a matrix describes the stair-case shape of its row (resp. column) echelon form.We here propose a new matrix invariant, the rank profile matrix, summarizing all information on the row andcolumn rank profiles of all the leading sub-matrices.We show that this normal form exists and is unique over any ring, provided that the notion of McCoy's rank is used, in the presence of zero divisors.We then explore the conditions for a Gaussian elimination algorithm to...

Topics: Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1601.01798

5
5.0

Jun 29, 2018
06/18

by
Xavier Bultel; Jannik Dreier; Jean-Guillaume Dumas; Pascal Lafourcade

texts

#
eye 5

#
favorite 0

#
comment 0

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given...

Topics: Cryptography and Security, Computing Research Repository

Source: http://arxiv.org/abs/1606.01045

65
65

Sep 22, 2013
09/13

by
Jacques Dubrois; Jean-Guillaume Dumas

texts

#
eye 65

#
favorite 0

#
comment 0

E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of $\pF{p}$\cite{Bach:1997:sppr,Itoh:2001:PPR}. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. We thus derive several algorithms computing primitive roots correct with very high...

Source: http://arxiv.org/abs/cs/0409029v2

303
303

Feb 19, 2008
02/08

by
Françoise Guillaume Dumas

texts

#
eye 303

#
favorite 0

#
comment 0

Book digitized by Google and uploaded to the Internet Archive by user tpb.

Source: http://books.google.com/books?id=LyQKAAAAIAAJ&oe=UTF-8

0
0.0

Aug 9, 2021
08/21

by
Guillaume Dumas (Guigui86)

data

#
eye 0

#
favorite 0

#
comment 0

Leapmotion stand for htc vive pro2.

Topics: htc vive pro 2, LEAPMOTION, vr_headset, Electronics, thingiverse, stl, stand

21
21

Jun 27, 2018
06/18

by
Jean-Guillaume Dumas; Dominique Duval; Burak Ekici; Damien Pous; Jean-Claude Reynaud

texts

#
eye 21

#
favorite 0

#
comment 0

In this paper, we present a novel framework for studying the syntactic completeness of computational effects and we apply it to the exception effect. When applied to the states effect, our framework can be seen as a generalization of Pretnar's work on this subject. We first introduce a relative notion of Hilbert-Post completeness, well-suited to the composition of effects. Then we prove that the exception effect is relatively Hilbert-Post complete, as well as the "core" language which...

Topics: Computing Research Repository, Logic in Computer Science

Source: http://arxiv.org/abs/1503.00948

52
52

Sep 18, 2013
09/13

by
Jean-Guillaume Dumas; Laurent Fousse; Bruno Salvy

texts

#
eye 52

#
favorite 0

#
comment 0

We present algorithms to perform modular polynomial multiplication or modular dot product efficiently in a single machine word. We pack polynomials into integers and perform several modular operations with machine integer or floating point arithmetic. The modular polynomials are converted into integers using Kronecker substitution (evaluation at a sufficiently large integer). With some control on the sizes and degrees, arithmetic operations on the polynomials can be performed directly with...

Source: http://arxiv.org/abs/0809.0063v1

79
79

Sep 18, 2013
09/13

by
Brice Boyer; Jean-Guillaume Dumas; Clément Pernet; Wei Zhou

texts

#
eye 79

#
favorite 0

#
comment 0

We propose several new schedules for Strassen-Winograd's matrix multiplication algorithm, they reduce the extra memory allocation requirements by three different means: by introducing a few pre-additions, by overwriting the input matrices, or by using a first recursive level of classical multiplication. In particular, we show two fully in-place schedules: one having the same number of operations, if the input matrices can be overwritten; the other one, slightly increasing the constant of the...

Source: http://arxiv.org/abs/0707.2347v5

41
41

Sep 23, 2013
09/13

by
Grégory Nuel; Jean-Guillaume Dumas

texts

#
eye 41

#
favorite 0

#
comment 0

We present two novel approaches for the computation of the exact distribution of a pattern in a long sequence. Both approaches take into account the sparse structure of the problem and are two-part algorithms. The first approach relies on a partial recursion after a fast computation of the second largest eigenvalue of the transition matrix of a Markov chain embedding. The second approach uses fast Taylor expansions of an exact bivariate rational reconstruction of the distribution. We illustrate...

Source: http://arxiv.org/abs/1006.3246v4

57
57

Sep 24, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Laurent Fousse; Jean-Claude Reynaud

texts

#
eye 57

#
favorite 0

#
comment 0

In this short note we study the semantics of two basic computational effects, exceptions and states, from a new point of view. In the handling of exceptions we dissociate the control from the elementary operation which recovers from the exception. In this way it becomes apparent that there is a duality, in the categorical sense, between exceptions and states.

Source: http://arxiv.org/abs/1112.2394v1

65
65

Sep 20, 2013
09/13

by
Jean-Guillaume Dumas; Pascal Giorgi; Clément Pernet

texts

#
eye 65

#
favorite 0

#
comment 0

In the past two decades, some major efforts have been made to reduce exact (e.g. integer, rational, polynomial) linear algebra problems to matrix multiplication in order to provide algorithms with optimal asymptotic complexity. To provide efficient implementations of such algorithms one need to be careful with the underlying arithmetic. It is well known that modular techniques such as the Chinese remainder algorithm or the p-adic lifting allow very good practical performance, especially when...

Source: http://arxiv.org/abs/cs/0601133v3

49
49

Sep 21, 2013
09/13

by
Christophe Chabot; Jean-Guillaume Dumas; Laurent Fousse; Pascal Giorgi

texts

#
eye 49

#
favorite 0

#
comment 0

This work is a part of the SHIVA (Secured Hardware Immune Versatile Architecture) project whose purpose is to provide a programmable and reconfigurable hardware module with high level of security. We propose a recursive double-size fixed precision arithmetic called RecInt. Our work can be split in two parts. First we developped a C++ software library with performances comparable to GMP ones. Secondly our simple representation of the integers allows an implementation on FPGA. Our idea is to...

Source: http://arxiv.org/abs/1104.0478v1

0
0.0

Sep 11, 2021
09/21

by
Julia Ayache; Darren Rhodes; Guillaume Dumas; Nadja Heym; Daria Kuss; Alexander Sumich

data

#
eye 0

#
favorite 0

#
comment 0

This project aims to investigate the role played by inter-individual differences in emotional awareness and emotional regulation on the pro-social consequences (e.g., trust, altruism) usually associated with interpersonal coordination (e.g., in-phase synchronization).

Source: https://osf.io/apxch/

44
44

Sep 19, 2013
09/13

by
Jean-Guillaume Dumas

texts

#
eye 44

#
favorite 0

#
comment 0

This note presents absolute bounds on the size of the coefficients of the characteristic and minimal polynomials depending on the size of the coefficients of the associated matrix. Moreover, we present algorithms to compute more precise input-dependant bounds on these coefficients. Such bounds are e.g. useful to perform deterministic chinese remaindering of the characteristic or minimal polynomial of an integer matrix.

Source: http://arxiv.org/abs/cs/0610136v4

12
12

Jun 26, 2018
06/18

by
Jean-Guillaume Dumas; Clément Pernet; Ziad Sultan

texts

#
eye 12

#
favorite 0

#
comment 0

The row (resp. column) rank profile of a matrix describes the staircase shape of its row (resp. column) echelon form. In an ISSAC'13 paper, we proposed a recursive Gaussian elimination that can compute simultaneously the row and column rank profiles of a matrix as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. Here we first study the conditions making a Gaus-sian elimination algorithm reveal this information. Therefore, we...

Topics: Computing Research Repository, Symbolic Computation

Source: http://arxiv.org/abs/1501.05239

36
36

Sep 22, 2013
09/13

by
Jean-Guillaume Dumas; Clément Pernet; Zhendong Wan

texts

#
eye 36

#
favorite 0

#
comment 0

This article deals with the computation of the characteristic polynomial of dense matrices over small finite fields and over the integers. We first present two algorithms for the finite fields: one is based on Krylov iterates and Gaussian elimination. We compare it to an improvement of the second algorithm of Keller-Gehrig. Then we show that a generalization of Keller-Gehrig's third algorithm could improve both complexity and computational time. We use these results as a basis for the...

Source: http://arxiv.org/abs/cs/0501074v2

43
43

Sep 23, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval

texts

#
eye 43

#
favorite 0

#
comment 0

We propose a new diagrammatic modeling language, DML. The paradigm used is that of the category theory and in particular of the pushout tool. We show that most of the object-oriented structures can be described with this tool and have many examples in C++, ranging from virtual inheritance and polymorphism to template genericity. With this powerful tool, we propose a quite simple description of the C++ LinBox library. This library has been designed for efficiency and genericity and therefore...

Source: http://arxiv.org/abs/cs/0510057v1

37
37

Sep 23, 2013
09/13

by
Jean-Guillaume Dumas

texts

#
eye 37

#
favorite 0

#
comment 0

We present an algorithm to perform a simultaneous modular reduction of several residues. This algorithm is applied fast modular polynomial multiplication. The idea is to convert the $X$-adic representation of modular polynomials, with $X$ an indeterminate, to a $q$-adic representation where $q$ is an integer larger than the field characteristic. With some control on the different involved sizes it is then possible to perform some of the $q$-adic arithmetic directly with machine integers or...

Source: http://arxiv.org/abs/0710.0510v5

2
2.0

Jan 4, 2021
01/21

by
Guillaume Dumas (guitoud)

data

#
eye 2

#
favorite 0

#
comment 0

## French public postal service banner.

Topics: stl, Signs & Logos, logo, postal_service, thingiverse, french

363
363

Feb 19, 2008
02/08

by
Françoise Guillaume Dumas

texts

#
eye 363

#
favorite 0

#
comment 0

Book digitized by Google from the library of Harvard University and uploaded to the Internet Archive by user tpb.

Source: http://books.google.com/books?id=80QAAAAAYAAJ&oe=UTF-8

95
95

Jul 20, 2013
07/13

by
Jean-Guillaume Dumas; Hicham Hossayni

texts

#
eye 95

#
favorite 0

#
comment 0

This paper deals with the evaluation of trust in public-key infrastructures. Different trust models have been proposed to interconnect the various PKI components in order to propagate the trust between them. In this paper we provide a new polynomial algorithm using linear algebra to assess trust relationships in a network using different trust evaluation schemes. The advantages are twofold: first the use of matrix computations instead of graph algorithms provides an optimized computational...

Source: http://arxiv.org/abs/1107.1880v3

5
5.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Thierry Gautier; Clément Pernet; Ziad Sultan

texts

#
eye 5

#
favorite 0

#
comment 0

We propose efficient parallel algorithms and implementations on shared memory architectures of LU factorization over a finite field. Compared to the corresponding numerical routines, we have identified three main difficulties specific to linear algebra over finite fields. First, the arithmetic complexity could be dominated by modular reductions. Therefore, it is mandatory to delay as much as possible these reductions while mixing fine-grain parallelizations of tiled iterative and recursive...

Topics: Distributed, Parallel, and Cluster Computing, Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1402.3501

121
121

Jul 19, 2013
07/13

by
Jean-Guillaume Dumas; Thierry Gautier; Jean-Louis Roch

texts

#
eye 121

#
favorite 0

#
comment 0

We propose a generic design for Chinese remainder algorithms. A Chinese remainder computation consists in reconstructing an integer value from its residues modulo non coprime integers. We also propose an efficient linear data structure, a radix ladder, for the intermediate storage and computations. Our design is structured into three main modules: a black box residue computation in charge of computing each residue; a Chinese remaindering controller in charge of launching the computation and of...

Source: http://arxiv.org/abs/1005.0830v1

60
60

Sep 22, 2013
09/13

by
Brice Boyer; Jean-Guillaume Dumas; Pascal Giorgi

texts

#
eye 60

#
favorite 0

#
comment 0

We propose different implementations of the sparse matrix--dense vector multiplication (\spmv{}) for finite fields and rings $\Zb/m\Zb$. We take advantage of graphic card processors (GPU) and multi-core architectures. Our aim is to improve the speed of \spmv{} in the \linbox library, and henceforth the speed of its black box algorithms. Besides, we use this and a new parallelization of the sigma-basis algorithm in a parallel block Wiedemann rank implementation over finite fields.

Source: http://arxiv.org/abs/1004.3719v1

42
42

Sep 19, 2013
09/13

by
Jean-Guillaume Dumas; Thierry Gautier; Clément Pernet; B. David Saunders

texts

#
eye 42

#
favorite 0

#
comment 0

To maximize efficiency in time and space, allocations and deallocations, in the exact linear algebra library \linbox, must always occur in the founding scope. This provides a simple lightweight allocation model. We present this model and its usage for the rebinding of matrices between different coefficient domains. We also present automatic tools to speed-up the compilation of template libraries and a software abstraction layer for the introduction of transparent parallelism at the algorithmic...

Source: http://arxiv.org/abs/1009.1317v1

43
43

Sep 18, 2013
09/13

by
Jean-Guillaume Dumas; Philippe Elbaz-Vincent; Pascal Giorgi; Anna Urbanska

texts

#
eye 43

#
favorite 0

#
comment 0

This paper deals with the computation of the rank and of some integer Smith forms of a series of sparse matrices arising in algebraic K-theory. The number of non zero entries in the considered matrices ranges from 8 to 37 millions. The largest rank computation took more than 35 days on 50 processors. We report on the actual algorithms we used to build the matrices, their link to the motivic cohomology and the linear algebra and parallelizations required to perform such huge computations. In...

Source: http://arxiv.org/abs/0704.2351v2

49
49

Sep 18, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Jean-Claude Reynaud

texts

#
eye 49

#
favorite 0

#
comment 0

A new categorical framework is provided for dealing with multiple arguments in a programming language with effects, for example in a language with imperative features. Like related frameworks (Monads, Arrows, Freyd categories), we distinguish two kinds of functions. In addition, we also distinguish two kinds of equations. Then, we are able to define a kind of product, that generalizes the usual categorical product. This yields a powerful tool for deriving many results about languages with...

Source: http://arxiv.org/abs/0707.1432v1

60
60

Sep 21, 2013
09/13

by
Alexandre Berzati; Cécile Canovas; Jean-Guillaume Dumas; Louis Goubin

texts

#
eye 60

#
favorite 0

#
comment 0

After attacking the RSA by injecting fault and corresponding countermeasures, works appear now about the need for protecting RSA public elements against fault attacks. We provide here an extension of a recent attack based on the public modulus corruption. The difficulty to decompose the "Left-To-Right" exponentiation into partial multiplications is overcome by modifying the public modulus to a number with known factorization. This fault model is justified here by a complete study of...

Source: http://arxiv.org/abs/0901.0911v3

48
48

Sep 22, 2013
09/13

by
Jean-Guillaume Dumas; Thierry Gautier; Jean-Louis Roch

texts

#
eye 48

#
favorite 0

#
comment 0

We propose a generic design for Chinese remainder algorithms. A Chinese remainder computation consists in reconstructing an integer value from its residues modulo non coprime integers. We also propose an efficient linear data structure, a radix ladder, for the intermediate storage and computations. Our design is structured into three main modules: a black box residue computation in charge of computing each residue; a Chinese remaindering controller in charge of launching the computation and of...

Source: http://arxiv.org/abs/1001.4150v1

65
65

Sep 24, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Laurent Fousse; Jean-Claude Reynaud

texts

#
eye 65

#
favorite 0

#
comment 0

The syntax of an imperative language does not mention explicitly the state, while its denotational semantics has to mention it. In this paper we show that the equational proofs about an imperative language may hide the state, in the same way as the syntax does.

Source: http://arxiv.org/abs/1112.2396v3

3
3.0

Jun 30, 2018
06/18

by
Jean-Guillaume Dumas; Jean-Baptiste Orfila

texts

#
eye 3

#
favorite 0

#
comment 0

Specific vectorial boolean functions, such as S-Boxes or APN functions have many applications, for instance in symmetric ciphers. In cryptography they must satisfy some criteria (balancedness, high nonlinearity, high algebraic degree, avalanche, or transparency) to provide best possible resistance against attacks. Functions satisfying most criteria are however difficult to find. Indeed, random generation does not work and the S-Boxes used in the AES or Camellia ciphers are actually variations...

Topics: Cryptography and Security, Computing Research Repository

Source: http://arxiv.org/abs/1411.2503

437
437

Feb 12, 2009
02/09

by
François Guillaume Dumas

texts

#
eye 437

#
favorite 0

#
comment 0

Book digitized by Google from the library of Oxford University and uploaded to the Internet Archive by user tpb.

Source: http://books.google.com/books?id=iT8GAAAAQAAJ&oe=UTF-8

59
59

Sep 23, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Jean-Claude Reynaud

texts

#
eye 59

#
favorite 0

#
comment 0

Most often, in a categorical semantics for a programming language, the substitution of terms is expressed by composition and finite products. However this does not deal with the order of evaluation of arguments, which may have major consequences when there are side-effects. In this paper Cartesian effect categories are introduced for solving this issue, and they are compared with strong monads, Freyd-categories and Haskell's Arrows. It is proved that a Cartesian effect category is a...

Source: http://arxiv.org/abs/0903.3311v3

11
11

Jun 29, 2018
06/18

by
Jean-Guillaume Dumas; Victor Pan

texts

#
eye 11

#
favorite 0

#
comment 0

The complexity of matrix multiplication (hereafter MM) has been intensively studied since 1969, when Strassen surprisingly decreased the exponent 3 in the cubic cost of the straightforward classical MM to log 2 (7) $\approx$ 2.8074. Applications to some fundamental problems of Linear Algebra and Computer Science have been immediately recognized, but the researchers in Computer Algebra keep discovering more and more applications even today, with no sign of slowdown. We survey the unfinished...

Topics: Symbolic Computation, Computing Research Repository

Source: http://arxiv.org/abs/1612.05766

42
42

Sep 20, 2013
09/13

by
Jean-Guillaume Dumas; Dominique Duval; Laurent Fousse; Jean-Claude Reynaud

texts

#
eye 42

#
favorite 0

#
comment 0

An algebraic method is used to study the semantics of exceptions in computer languages. The exceptions form a computational effect, in the sense that there is an apparent mismatch between the syntax of exceptions and their intended semantics. We solve this apparent contradiction by efining a logic for exceptions with a proof system which is close to their syntax and where their intended semantics can be seen as a model. This requires a robust framework for logics and their morphisms, which is...

Source: http://arxiv.org/abs/1207.1255v2