Paper 2011/483

Adaption of Pollard's kangaroo algorithm to the FACTOR problem

Mario Romsy

Abstract

In \cite{BKT11} Baba, Kotyada and Teja introduced the FACTOR problem over non-abelian groups as base of an ElGamal-like cryptosystem. They conjectured that there is no better method than the naive one to solve the FACTOR problem in a general group. Shortly afterwards Stanek published an extension of the baby-step giant-step algorithm disproving this conjecture \cite{Sta11}. Since baby-step giant-step methods are limited in practice because of memory requirements we present a modification of Pollard's kangaroo algorithm that solves the FACTOR problem requiring only negligible memory.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
mario romsy @ unibw de
History
2011-11-10: last of 2 revisions
2011-09-08: received
See all versions
Short URL
https://ia.cr/2011/483
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/483,
      author = {Mario Romsy},
      title = {Adaption of Pollard's kangaroo algorithm to the FACTOR problem},
      howpublished = {Cryptology ePrint Archive, Paper 2011/483},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/483}},
      url = {https://eprint.iacr.org/2011/483}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.