Top

Published in:

2021 | OriginalPaper | Chapter

ECM Factorization with QRT Maps

Author : Andrew N. W. Hone

Published in: Advances in Software Engineering, Education, and e-Learning

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Quispel–Roberts–Thompson (QRT) maps are a family of birational maps of the plane which provide the simplest discrete analogue of an integrable Hamiltonian system and are associated with elliptic fibrations in terms of biquadratic curves. Each generic orbit of a QRT map corresponds to a sequence of points on an elliptic curve. In this preliminary study, we explore versions of the elliptic curve method (ECM) for integer factorization based on performing scalar multiplication of a point on an elliptic curve by iterating three different QRT maps with particular initial data. Pseudorandom number generation and other possible applications are briefly discussed.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Random Self-modifiable Computation

next chapter What Have Google’s Random Quantum Circuit Simulation Experiments Demonstrated About Quantum Supremacy?

D.J. Bernstein, T. Lange, Faster addition and doubling on elliptic curves, in ed. by K. Kurosawa, Advances in Cryptology – ASIACRYPT 2007 (Springer, Berlin, 2007), pp. 29–50. https://doi.org/10.1007/978-3-540-76900-2_3

D.J. Bernstein, P. Birkner, T. Lange, C. Peters, ECM using Edwards curves. Math. Comput. 82, 1139–1179 (2013). https://doi.org/10.1090/S0025-5718-2012-02633-0 MathSciNetCrossRef

A. Cima, A. Gasull, V. Mañosa, Integrability and non-integrability of periodic non-autonomous Lyness recurrences. Dyn. Syst. 28, 518–538 (2013). https://doi.org/10.1080/14689367.2013.821103 MathSciNetCrossRef

R. Crandall, C. Pomerance, Prime Numbers - A Computational Perspective, 2nd edn (Springer, New York, 2005)MATH

J.J. Duistermaat, Discrete Integrable Systems: QRT Maps and Elliptic Surfaces (Springer, New York, 2010)CrossRef

H.M. Edwards, A normal form for elliptic curves. Bull. Amer. Math. Soc. 44, 393–422 (2007). https://doi.org/10.1090/S0273-0979-07-01153-6 MathSciNetCrossRef

Y.N. Fedorov, A.N.W. Hone, Sigma-function solution to the general Somos-6 recurrence via hyperelliptic Prym varieties. J. Integrable Syst. 1, xyw012 (2016). https://doi.org/10.1093/integr/xyw012

A.P. Fordy, A.N.W. Hone, Discrete integrable systems and Poisson algebras from cluster maps. Commun. Math. Phys. 325, 527–584 (2014). https://doi.org/10.1007/s00220-013-1867-y MathSciNetCrossRef

A.P. Fordy, R.J. Marsh, Cluster mutation-periodic quivers and associated Laurent sequences. J. Algebraic Combin. 34, 19–66 (2011). https://doi.org/10.1007/s10801-010-0262-4 MathSciNetCrossRef

10.

D. Gale, The strange and surprising saga of the Somos sequences. Math. Intell. 13(1), 40–42 (1991); Somos sequence update, Math. Intell. 13(4), 49–50 (1991). Reprinted in D. Gale, Tracking the Automatic Ant (Springer, New York, 1998)

11.

R.R. Goundar, M. Joye, A. Miyaji, Co-Z addition formulae and binary ladders on elliptic curves, in ed. by S. Mangard, F.-X. Standaert, Cryptographic Hardware and Embedded Systems, CHES 2010. Lecture Notes in Computer Science, vol. 6225. (Springer, Berlin, 2010), pp. 65–79. https://doi.org/10.1007/978-3-642-15031-9_5

12.

R.G. Halburd, Diophantine integrability. J. Phys. A Math. Gen. 38, L1–L7 (2005). https://doi.org/10.1088/0305-4470/38/16/L01 MathSciNetCrossRef

13.

H. Huseyin, K.K.-H. Wong, G. Carter, E. Dawson, Twisted Edwards curves revisited, in ed. by J. Pieprzyk, Advances in Cryptology - ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350 (2008), pp. 326–343. https://doi.org/10.1007/978-3-540-89255-7_20

14.

A.N.W. Hone, Elliptic curves and quadratic recurrence sequences. Bull. Lond. Math. Soc. 37, 161–171 (2005). https://doi.org/10.1112/S0024609304004163. Corrigendum. Bull. Lond. Math. Soc. 38, 741–742 (2006). https://doi.org/10.1112/S0024609306018844

15.

A.N.W. Hone, Sigma function solution of the initial value problem for Somos 5 sequences. Trans. Amer. Math. Soc. 359, 5019–5034 (2007). https://doi.org/10.1090/S0002-9947-07-04215-8 MathSciNetCrossRef

16.

A.N.W. Hone, R. Inoue, Discrete Painlevé equations from Y-systems. J. Phys. A: Math. Theor. 47, 474007 (2014). https://doi.org/10.1088/1751-8113/47/47/474007 CrossRef

17.

A.N.W. Hone, T.E. Kouloukas, C. Ward, On reductions of the Hirota-Miwa equation. SIGMA 13, 057 (2017). https://doi.org/10.3842/SIGMA.2017.057 MathSciNetMATH

18.

A.N.W. Hone, C.S. Swart, Integrality and the Laurent phenomenon for Somos 4 and Somos 5 sequences. Math. Proc. Camb. Phil. Soc. 145, 65–85 (2008). https://doi.org/10.1017/S030500410800114X MathSciNetCrossRef

19.

A.N.W. Hone, Efficient ECM factorization in parallel with the Lyness map (2020). arXiv:2002:03811

20.

A. Iatrou, J.A.G. Roberts, Integrable mappings of the plane preserving biquadratic invariant curves. J. Phys. A: Math. Gen. 34, 6617–6636 (2001). https://doi.org/10.1088/0305-4470/34/34/308 MathSciNetCrossRef

21.

A. Iatrou, J.A.G. Roberts, Integrable mappings of the plane preserving biquadratic invariant curves II. Nonlinearity 15, 459–489 (2002). https://doi.org/10.1088/0951-7715/15/2/313 MathSciNetCrossRef

22.

N. Koblitz, Algebraic Aspects of Cryptography (Springer, Berlin, 1998)CrossRef

23.

T. Lam, P. Pylyavskyy, Laurent phenomenon algebras. Cam. J. Math. 4, 121–162 (2012). https://doi.org/10.4310/CJM.2016.v4.n1.a2 MathSciNetCrossRef

24.

H.W. Lenstra, Jr., Factoring integers with elliptic curves. Ann. Math. 126, 649–673 (1987). https://doi.org/10.2307/1971363 MathSciNetCrossRef

25.

R.C. Lyness, Cycles. Math. Gaz. 26, 62 (1942)CrossRef

26.

J.L. Malouf, An integer sequence from a rational recursion. Discrete Math. 110, 257–261 (1992). https://doi.org/10.1016/0012-365X(92)90714-Q MathSciNetCrossRef

27.

T. Nakanishi, Periodicities in cluster algebras and dilogarithm identities, in ed. by A. Skowronski, K. Yamagata, Representations of Algebras and Related Topics, EMS Series of Congress Reports (European Mathematical Society, Zurich, 2011), pp. 407–444

28.

F.W.J. Olver, A.B. Olde Daalhuis, D.W. Lozier, B.I. Schneider, R.F. Boisvert, C.W. Clark, B.R. Miller, B.V. Saunders, H.S. Cohl, M.A. McClain, (Eds.), NIST Digital Library of Mathematical Functions. http://dlmf.nist.gov/. Release 1.0.25 of 2019-12-15

29.

A.J. van der Poorten, C.S. Swart, Recurrence relations for elliptic sequences: every Somos 4 is a Somos k. Bull. London Math. Soc. 38, 546–554 (2006). https://doi.org/10.1112/S0024609306018534

30.

G.R.W. Quispel, J.A.G. Roberts, C.J. Thompson, Integrable mappings and soliton equations. Phys. Lett. A 126, 419–421 (1988)MathSciNetCrossRef

31.

M. Somos, Problem 1470. Crux Math. 15, 208 (1989)

32.

D.R. Stinson, Cryptography Theory and Practice, 3rd edn (Chapman & Hall/CRC, Boca Raton, 2006)

33.

T. Tsuda, Integrable mappings via rational elliptic surfaces. J. Phys. A: Math. Gen. 37, 2721–2730 (2004). https://doi.org/10.1088/0305-4470/37/7/014 MathSciNetCrossRef

34.

M. Ward, Memoir on elliptic divisibility sequences. Amer. J. Math. 70, 31–74 (1948). https://doi.org/10.2307/2371930 MathSciNetCrossRef

35.

E.T. Whittaker, G.N. Watson, A Course of Modern Analysis, 4th edn. (Cambridge University Press, Cambridge, 1927)MATH

36.

S.Y. Yan, Primality Testing and Integer Factorization in Public-Key Cryptography (Kluwer Academic Publishers, Boston, 2004)CrossRef

Title: ECM Factorization with QRT Maps
Author: Andrew N. W. Hone
Publisher: Springer International Publishing
Book: Advances in Software Engineering, Education, and e-Learning
Print ISBN: 978-3-030-70872-6

Electronic ISBN: 978-3-030-70873-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-70873-3_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"