New modular multiplication and division algorithms based on continued fraction expansion

In this paper, we apply results on number systems based on continued fraction expansions to modular arithmetic. We provide two new algorithms in order to compute modular multiplication and modular division. The presented algorithms are based on the Euclidean algorithm and are of quadratic complexity.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00800497
Author Gouicem, Mourad
Maintainer CCSD
Last Updated May 12, 2026, 19:06 (UTC)
Created May 12, 2026, 19:06 (UTC)
Identifier hal-00800497
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Performance et Qualité des Algorithmes Numériques (PEQUAN) ; Laboratoire d'Informatique de Paris 6 (LIP6) ; Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
creator Gouicem, Mourad
date 2013-03-13T00:00:00
harvest_object_id 7f310ca3-d8b5-41fb-ac11-4429c0ed92f5
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2023-04-11T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1303.3445
set_spec type:UNDEFINED