nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

A Deterministic Algorithm for Computing Divisors in an Interval

verfasst von : Liqiang Peng, Yao Lu, Noboru Kunihiro, Rui Zhang, Lei Hu

Erschienen in: Information Security and Privacy

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We revisit the problem of finding a nontrivial divisor of a composite integer when it has a divisor in an interval \([\alpha , \beta ]\). We use Strassen’s algorithm to solve this problem. Compared with Kim-Cheon’s algorithms (Math Comp 84(291): 339–354, 2015), our method is a deterministic algorithm but with the same complexity as Kim-Cheon’s probabilistic algorithm, and our algorithm does not need to impose that the divisor is prime. In addition, we can further speed up the theoretical complexity of Kim-Cheon’s algorithms and our algorithm by a logarithmic term \(\log (\beta -\alpha )\) based on the peculiar property of polynomial arithmetic we consider.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Correction to: Fast Lottery-Based Micropayments for Decentralized Currencies

Nächstes Kapitel Reusable Fuzzy Extractor from LWE

Bluestein, L.I.: A linear filtering approach to the computation of the discrete fourier transform. IEEE Trans. Electroacoust. 18, 451–466 (1970)CrossRef

Bostan, A.: Algorithmique efficace pour des opérations de base en calcul formel. Ph.D. thesis (2003). École polytechnique (in English)

Bostan, A., Gaudry, P., Schost, E.: Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM J. Comput. 36(6), 1777–1806 (2007)MathSciNetCrossRefMATH

Chen, Y., Nguyen, P.Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 502–519. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_30CrossRef

Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH

Coron, J.-S., Joux, A., Mandal, A., Naccache, D., Tibouchi, M.: Cryptanalysis of the RSA subgroup assumption from TCC 2005. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 147–155. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_9CrossRef

Costa, E., Harvey, D.: Faster deterministic integer factorization. Math. Comput. 83(285), 339–345 (2014)MathSciNetCrossRefMATH

Fouque, P.-A., Tibouchi, M., Zapalowicz, J.-C.: Recovering private keys generated with weak PRNGs. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 158–172. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45239-0_10CrossRef

Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 51–66. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44670-2_6CrossRef

10.

Kim, M., Cheon, J.H.: Computing prime divisors in an interval. Math. Comp. 84(291), 339–354 (2015)MathSciNetCrossRefMATH

11.

Konyagin, S., Pomerance, C.: On primes recognizable in deterministic polynomial time. In: Graham, R.L., Nešetřil, J. (eds.) The mathematics of Paul Erdős I. Springer, Heidelberg (1997)

12.

Pollard, J.M.: Monte Carlo methods for index computation (mod \(p\)). Math. Comp. 32(143), 918–928 (1978)MathSciNetMATH

13.

Pollard, J.M.: Theorems on factorization and primality testing. In: Proceedings of the Cambridge Philosophical Society, vol. 76, pp. 521–528 (1974)MathSciNetCrossRefMATH

14.

Strassen, V.: Einige Resultate \(\ddot{u}\)ber Berechnungskomplexit\(\ddot{a}\)t. Jber. Deutsh. Math. -Verein. 78(1), 1–8 (1976/1977)

Titel: A Deterministic Algorithm for Computing Divisors in an Interval
verfasst von: Liqiang Peng
Yao Lu
Noboru Kunihiro
Rui Zhang
Lei Hu
Verlag: Springer International Publishing
Buch: Information Security and Privacy
Print ISBN: 978-3-319-93637-6

Electronic ISBN: 978-3-319-93638-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93638-3_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner