Geodesic
Using a deterministic partitioning function for Pollard’s rho method paralellization
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 2 (2013) no. 3, pp. 73-80 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An improved method for parallelization of Pollard’s algorithm for solving the discrete logarithm problem in a group of elliptic curve points and in a multiplicative group of a Galois field for shared memory systems is suggested in the paper. Improvement of the method is achieved by constructing a deterministic partitioning function. Such a function allows to organize two independent load balancing computational threads for building a block of group elements of fixed length. Also we analyze advanced iteration functions for Pollard’s algorithm and build generic deterministic partitioning function.
Keywords: discrete logarithm, Pollard’s rho method, elliptic curve. 
@article{VYURV_2013_2_3_a4,
     author = {E. G. Kachko and K. A. Pogrebnyak},
     title = {Using a deterministic partitioning function for {Pollard{\textquoteright}s} rho method paralellization},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {73--80},
     year = {2013},
     volume = {2},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2013_2_3_a4/}
}
TY  - JOUR
AU  - E. G. Kachko
AU  - K. A. Pogrebnyak
TI  - Using a deterministic partitioning function for Pollard’s rho method paralellization
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2013
SP  - 73
EP  - 80
VL  - 2
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2013_2_3_a4/
LA  - ru
ID  - VYURV_2013_2_3_a4
ER  - 
%0 Journal Article
%A E. G. Kachko
%A K. A. Pogrebnyak
%T Using a deterministic partitioning function for Pollard’s rho method paralellization
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2013
%P 73-80
%V 2
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2013_2_3_a4/
%G ru
%F VYURV_2013_2_3_a4
E. G. Kachko; K. A. Pogrebnyak. Using a deterministic partitioning function for Pollard’s rho method paralellization. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 2 (2013) no. 3, pp. 73-80. http://geodesic.mathdoc.fr/item/VYURV_2013_2_3_a4/

[1] S. Bai, R. P. Brent, “On the efficiency of Pollard’s rho method for discrete logarithms”, Fourteenth Computing: The Australasian Theory Symposium (January 22–25, 2008, Wollongong, NSW, Australia), v. 77, ed. J. Harland J., P. Manyem, ACS, 125–131

[2] E. G. Kachko, K. A. Pogrebnyak, “Parallelized Pollard’s Method for Solving the Elliptic Curve Discrete Logatrithm Problem”, Proceedings of the International Scientific Conference Parallel Computational Technologies (PCT–2012) (March 26–30, 2012, Novosibirsk), YUrGU Publ., Chelyabinsk, 2012, 723

[3] I. D. Gorbenko, E. G. Kachko, K. A. Pogrebnyak, “Methods of Parallelization of Pollard’s Algorithm for Solving the Discrete Logarithm Problem for Shared Memory Systems”, Proceedings of the International Scientific Conference High performance computing (HPC–UA’2012) (October 8–10, 2012, Kiev), NANU, Kiev, 2012, 152–157

[4] I. D. Gorbenko, E. G. Kachko, K. A. Pogrebnyak, “Parallelized Pollard’s Method for Solving the Discrete Logatrithm Problem in the Multiplicative Group of a Galois Field”, Proceedings of the Scientific Conference Modern problems of information security on transport (November 29–30, 2012, Nikolaev), NUK, Nikolaev, 2012, 9–11