Search

Showing total 2 results
Start Over Topic factorization
2 results

1. Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment

Author

Pierrick Gaudry, Emmanuel Thomé, Fabrice Boudot, Aurore Guillevic, Nadia Heninger, Paul Zimmermann, XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of California [San Diego] (UC San Diego), University of California (UC), This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French 'Ministère de l'Enseignement Supérieur et de la Recherche', by the 'Conseil Régional de Lorraine', by theEuropean Union, through the 'Cyber-Entreprises' project, and by the US National Science Foundation under grant no. 1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco., Daniele Micciancio, Thomas Ristenpart, Grid5000, University of California, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French ``Ministère de l'Enseignement Supérieur et de la Recherche', by the ``Conseil Régional de Lorraine', by theEuropean Union, through the ``Cyber-Entreprises' project, and by the US National Science Foundation under grant no.~1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco., and Daniele Micciancio, Thomas Ristenpart

Subjects
FOS: Computer and information sciences, Computer Science - Cryptography and Security, Computer science, discrete logarithm, Computation, number field sieve, 02 engineering and technology, law.invention, General number field sieve, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Software, cryptanalysis, Factorization, law, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Hardware_ARITHMETICANDLOGICSTRUCTURES, Arithmetic, factoring, business.industry, Numerical digit, Factoring, Discrete logarithm, 020201 artificial intelligence & image processing, Cryptanalysis, business, Cryptography and Security (cs.CR)
Abstract

International audience; We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.The last page of this paper also reports on the factorization of RSA-250.

Published
2020

2. Enclosings of decompositions of complete multigraphs in 2-edge-connected r -factorizations

Author

John Asplund, Pierre Charbit, Carl Feghali, Dalton State College, University System of Georgia (USG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Bergen (UIB), This paper received partial support his paper received partial support by Fondation Sciences Mathématiques de Paris and the Research Council of Norway via the project CLASSIS, Grant Number 249994., and University of Bergen (UiB)

Subjects
Discrete mathematics, 010102 general mathematics, Multigraph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, Factorization, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, 05B99
Abstract

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

Published
2019